Interaktive Computersimulationen sind ein wichtiges Werkzeug vieler Industriezweige wie z. B. der Film-, Textil- und Computerspielebranche. Sie ermöglichen bzw. vereinfachen Arbeitsschritte und -abläufe, ohne die eine große Fülle von Produkten nicht realisiert werden könnte.

Damit diese Simulationen ein so hohes Maß an Realität bieten können, müssen darin verwendete Verfahren unter anderem den Anspruch der Echtzeitfähigkeit erfüllen. Um die Realitätsnähe noch weiter zu erhöhen, wird in heutzutage die Möglichkeit eingebaut, deformierbare Flächen (z. B. Kleidung) zu simulieren. Um dies zu ermöglichen, werden spezielle Algorithmen, unter anderem bei der Kollisionserkennung, benötigt.

Diese Arbeit beschreibt den Entwurf, die Implementierung und die anschließende Leistungsmessung eines Algorithmus zur Kollisionserkennung zwischen deformierbaren Flächen (in Form von Dreiecksnetzen) und ihrer Umwelt. Selbstkollisionen werden vom Algorithmus ebenfalls erkannt. Das grundlegende Konzept des Algorithmus besteht darin, die deformierbare Fläche durch eine Menge von sehr kleinen Kugeln zu repräsentieren, die die Fläche möglichst vollständig einschließen und das Volumen und somit den Kollisionskörper der Fläche bilden. Um bei einer Kollisionsanfrage nicht alle Kugeln der Fläche auf Kollision mit dem anfragenden Objekt prüfen zu müssen, wird das räumliche Hashing von Matthias Teschner leicht modifiziert implementiert. Dabei wird der Raum in Zellen eingeteilt, die mit Hilfe einer Hash-Funktion auf Zeilen einer Hash-Tabelle abgebildet werden. Zu Beginn eines Zeitschritts werden Verweise auf alle Kugeln einer deformierbaren Fläche entsprechend in die Tabelle eingefügt. Bei einer Kollisionsanfrage wird mit Hilfe der Hash-Tabelle überprüft, welche Kugeln das anfragende Objekt potentiell schneiden. Wahlweise ist es auch möglich, alle Dreiecke, die in kollidierenden Kugeln eingeschlossen sind, auf Kollision mit dem Objekt zu überprüfen. Jede deformierbare Fläche besitzt ihre eigene Hash-Tabelle. Als Simulation wurde die impulsbasierte Dynamiksimulation von Jan Bender gewählt, welche für die Kollisionserkennung teilweise auf die freie Physikbibliothek Bullet Physics Simulation zurückgreift. Das Laufzeitverhalten wird schießlich mit dem eines Brute-Force-Algorithmus verglichen. Dabei zeigt sich, dass der Algorithmus im Normalfall um ein Vielfaches schneller arbeitet. Das entwickelte Verfahren ist auch in sehr komplexen Szenarien schnell genug, um als echtzeitfähig angesehen zu werden.