Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Parallelisierung der Kollisionserkennung bei Bekleidungssimulationen

 
: Morch, H.
: Fuhrmann, A.

Bingen, 2006, 72 S.
Bingen, FH, Dipl.-Arb., 2006
Deutsch
Diplomarbeit
Fraunhofer IGD ()
Collision Detection; Parallel; hierarchical bounding volumes; cloth simulation; multi-thread handling

Abstract
Mehrkern Prozessoren, eine Untergruppe von SMP-Systemen, werden im Bereich von Desktop PC System immer häufiger. Um die daraus resultierenden Vorteile nutzbar zu machen, müssen Programme für diese Umgebung angepasst werden. Eine entsprechende Anpassung und Optimierung für die Kollisionserkennung bei Bekleidungssimulationen ist das Ziel dieser Diplomarbeit.
Es wird untersucht, wie diese modernen Technologien im Bereich der CPU und Rechnerarchitektur verwendet werden können, um die Bearbeitung der Kollisionserkennung bei Bekleidungssimulationen zu beschleunigen. Hierfür wird sowohl auf die SIMD-Möglichkeiten der IA32 Architektur in Form der SSE-Befehlssätze, als auch auf die Möglichkeiten von SMP-Systeme zurückgegriffen. Bei der Umsetzung der Ansätze konnte auf eine vorhandene sequenzielle Implementierung der Kollisionserkennung aufgesetzt werden. Diese Implementierung ist ein Bestandteil einer in Java realisierten Bekleidungssimulation.
Im ersten Teil dieser Arbeit wird der Einsatz von SSE in zwei unterschiedlichen Ansätzen untersucht. Der erste Ansatz behandelt die Umsetzung von einzelnen Operationen aus dem Bereich der linearen Algebra mit SSE. Diese werden dann mit den entsprechenden Operationen aus der Programmbibliothek VecMath verglichen. Im zweiten Ansatz wird ein längerer Algorithmus mit SSE gegen dessen Version auf Basis der VecMath-Bibliothek getestet. Hierfür wird ein Verfahren zur kontinuierlichen Kollisionserkennung zwischen zwei Dreiecken teilweise mit SSE implementiert.
Im zweiten Teil wird die Kollisionserkennung auf Basis einer Hüllkörperhierarchie mit k-DOPs verwendet, um zu beschreiben, wie die Traversierung eines Baums parallelisiert werden kann. Hierbei wird nicht nur auf das Auffinden der Kollisionen eingegangen, sondern auch auf das Aktualisieren der Hüllkörperhierarchie. Dies stellt eine besondere Hausforderung dar, falls nicht die gesamte Hierarchie aktualisiert werden muss.
Es hat sich gezeigt, dass SSE keine Vorteile gegenüber einem in Java implementierten Algorithmus erzielen kann. Der Einsatz von mehreren Prozessoren hat sich hingegen als effektiv erwiesen.

 

Multi core processors, a subgroup of SMP systems, have an increasing distribution rate among desktop pc systems. To make there advantages usable programmes have to be adapted to this new environment. The purpose of this degree dissertation is an adaptation of the collision detection within cloth simulations.
It is researched how modern technologies in the area of CPUs and computer architecture and can be used to increase the speed of the collision detection within cloth simulations. SIMD technologies in terms of the SSE instruction set are investigated as well as the capabilities of SMP systems. The realisation of the two approaches was based on an existing sequential algorithm of the collision detection. This algorithm is part of a cloth simulation realised with Java.
The first part of this thesis analyses two different approaches how SSE can be used. At first SSE is used to calculate operations in the area of linear algebra. This solution is then compared to operations of the VecMath library. The second approach analyses a longer algorithm implemented with SSE. Afterwards the SSE algorithm is compared to its VecMath pendant. As an example of this complex algorithm a method of continuous collision detection between two triangles is used.
The traversation of a bounding volume hierarchy and its parallelization is described in the second part of the thesis. The parallelization can be accomplished with multiple Java threads. This part not only mentions traversation as a way of finding collisions but also the parallel update of a bounding volume hierarchy. This is a special challenge if not all nodes of the hierarchy have to be updated.
The comparison of the two different approaches showed that SSE has no advantages over the existing Java algorithm. Nevertheless, the use of multi core processors has proven effective.

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