Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Konzeption und vergleichende Evaluierung von Algorithmen zur Kollisionserkennung im Kontext von dynamischen, gekoppelten Simulationen

 
: Henzel, Carola
: Linneweber, Bastian

Wiesbaden, 2008, 73 S.
Wiesbaden, FH, Bachelor Thesis, 2008
Deutsch
Bachelor Thesis
Fraunhofer IGD ()
Collision Detection; physically based simulation; coupled simulation

Abstract
In der vorliegenden Bachelorarbeit wurden vorhandene Ansätze zur Kollisionserkennung beschrieben, analysiert und verbessert. Dazu wurde das Vorgehen einer Kollisionserkennung mit Hilfe einer Distance Prism Hierarchy und die Kollisionserkennung durch Spatial Hashing in einer Simulation zur Bekleidung untersucht. Es wurden verschiedene Möglichkeiten der Implementierung dieser Algorithmen getestet. So wurde beim Spatial Hashing die Laufzeit von HashMaps mit Arrays und von HashSets mit Listen verglichen und ein umgekehrtes Spatial Hashing getestet. Außerdem wurden Methoden zur Optimierung des Prozesses zur Kollisionserkennung konzipiert, implementiert und untersucht. Dazu wurden redundante und unnötige Berechnungen eliminiert und die Information über Kollisionen des jeweils vorangegangenen Simulationsschrittes verwendet.
Des Weiteren wurde die Performanz zur Aktualisierung der jeweils zur Kollisionserkennung benötigten Datenstrukturen analysiert und verbessert. Dazu wurde ein Lazy Update Verfahren entwickelt, welches Berechnungen bei der Aktualisierung der Datenstruktur reduziert, indem approximierte Zustände zugelassen werden. Dabei wurde darauf geachtet, dass sich keine negativen visuellen Auswirkungen durch die Verwendung dieses Verfahrens ergeben und keine redundanten Berechnungen erfolgen. Zusätzlich dazu wurde das Required Update Verfahren konzipiert, um Berechnungen in einem Simulationsschritt zu eliminieren, deren Ergebnisse im aktuellen Schritt nicht verwendet werden. Diese erarbeiteten Verfahren und Methoden zeigten in der Analyse und den Testläufen große Beschleunigungen der Algorithmen.

 

In this bachelor thesis existing approaches for collision detection are described, analyzed and improved. For that purpose the procedure of collision detection with a Distance Prism Hierarchy and the procedure of collision detection by Spatial Hashing have been examined in a cloth simulator. Different implementations of these algorithms were tested. Thus for the Spatial Hashing the runtime of an implementation by HashMaps was compared with arrays and an implementation by HashSets was compared with lists. Also a reverse Spatial Hashing was tested. Besides optimization methods for the collision detection process were designed, implemented and investigated. For that purpose redundant and unnecessary calculations were eliminated and the collision information of the preceding simulation step was used.
Furthermore the performance of the actualization of the required data structures was analyzed and improved. To do this, a procedure called Lazy Update has been developed. It reduces calculations in the update process of the data structure, while approximated states are admitted. Special attention was paid to the fact, that no negative visual effects arise by the use of this procedure and no redundant calculations occur. Also a Required Update procedure was conceived to eliminate calculations in a simulation step, whose results are not used in the current step. In the analysis these compiled procedures showed great accelerations of the algorithms.

: http://publica.fraunhofer.de/dokumente/N-84118.html