Massiv parallele Algorithmen und Architekturen zur hardware-beschleunigten Kollisionserkennung in der Echtzeit Computergraphik
Zusammenfassung der Projektergebnisse
Die Ansprüche an die virtuelle Realität sind im Laufe der Zeit stetig gestiegen. Interaktionen mit virtuellen Objekten verbreiten sich in immer mehr Fachbereichen und sind längst nicht mehr nur aus Computerspielen bekannt. So wird bei der Entwicklung und dem Designen neuer Fahrzeuge oder anderer Produkte immer häufiger zum virtuellen Prototyping gegriffen, um kostengünstigeres und flexibleres arbeiten zu ermöglichen. Auch in der Produktion von Industrierobotern (KUKA) wird verstärkt auf eine Validierung der Bewegungsfreiheit und Erreichbarkeit der Roboterarme durch virtuelle Modelle und Simulationen gesetzt. Der Einsatz von virtuell simulierten Umgebungen findet auch in Ausbildungen und Schulungen, wie zum Beispiel der Flugsimulation oder Operationssimulation, vermehrt Einzug und Anwendung. Die Technik der Kollisionserkennung nimmt in virtuellen Anwendungen und Simulationen, mit dem Fokus auf der Interaktion innerhalb einer virtuellen Umgebung, einen sehr hohen Stellenwert ein. Die Kollisionserkennung und -behandlung ist eine der Techniken, welche einer virtuellen Umgebung Realismus verleiht. Die Vermeidung der Durchdringung von zwei oder mehreren Objekten, wie dies in einer realen Umgebung bei Festkörpern der Fall ist, stellt eine der grundlegenden Bestandteile bei der Interaktion von Objekten untereinander, aber auch bei der Interaktion des Benutzers mit der Umgebung, dar, und dient der Aufrechterhaltung der Immersion in der virtuellen Welt. Somit kann die Technik der Kollisionserkennung und -behandlung als eine der wichtigsten Techniken in der Interaktion mit virtuellen Objekten angesehen werden. Auf Grund dieser Tatsache, dass das Erkennen von Kollisionen eine der Grundfunktionen in virtuellen Umgebungen ist, lag das Hauptaugenmerk in dem Forschungsprojekt auf der Erkennung von Kollisionen zwischen rigiden und flexiblen virtuellen Objekten, welche durch eine physikalisch basierte Simulation oder ein ähnliches Systeme bewegt und verformt beziehungsweise deformiert werden. Hierbei ist ein hierarchisch basierter Ansatz nicht optimal, da dieser zu jedem Schritt der Simulation, auf Grund einer möglichen Verformung des Objektes, die aufgebaute Hierarchie aktualisieren muss. Weiterhin sollte keine Approximationsdatenstruktur verwendet werden, welche das Objekt vereinfacht darstellt (zum Beispiel das Annähern der Form der Objekte durch Voxel oder das Füllen der Objekte mit Tetraedern oder Kugeln), da in diesem Zusammenhang Ungenauigkeiten auftreten können, was in kritischen Anwendungen, wie zum Beispiel medizinischen Anwendungen, ausgeschlossen werden muss. Wir haben im Rahmen dieses Projektes einen Benchmark entwickelt, mit dessen Hilfe man erstmalig Kollisionsalgorithmen bezüglich ihrer Geschwindigkeit im Fall von Kollisionen bestimmen und vergleichen kann. Dieser Benchmark stellt erstmals die Möglichkeit die Genauigkeit der bestimmten Kräfte und Drehmomente auf ihre Qualität hin zu vergleichen. Wir haben außerdem eine einfache Clustering-Methode für Triangel-Soups entwickelt, welche auf einem Machine- Learning-Verfahren beruht. Der Vorteil dieses Verfahrens ist die Zerlegung der Szene in einzelne Komponenten. Diese Komponenten können im Anschluss unabhängig voneinander bearbeitet werden, was die Möglichkeit der Verteilung auf mehrere Graphikkarten bietet. Weiterhin wird durch dieses Verfahren eine Vielzahl von False- Positive-Fälle eliminiert, was in einer Performancesteigerung resultiert. Darüber hinaus haben wir im Rahmen dieses Projektes eine Methode zur Schnittberechnung von beliebigen Mengen von Dreiecken entwickelt, die vollständig auf der Graphikkarte läuft und ohne eine Beschleunigungsdatenstruktur auskommt. Hierdurch ist eine einfachere Implementierung möglich und es ist keine Unterteilung in Broad und Narrow Phase notwendig. Ein Verfahren zur Erstellung von dichten Kugelpackung, welches auf der Graphikkarte läuft, wurde ebenfalls im Rahmen dieses Projektes entwickelt. Das Füllen von Objekten mit Kugeln findet in vielen Bereichen Anwendung, z.B. stellte Weller und Zachmann eine Datenstruktur, Inner Sphere Tree, vor, welche auf Kugelpackungen beruht und hierdurch Kollisionserkennungen zwischen komplexen Objekten mit einer Geschwindigkeit von 1000Hz ermöglicht. Weiterhin ermöglicht die Kugelpackung dem Autor die effektive Berechnung des Eindringvolumens zwischen zwei Körpern. Im Rahmen des Projektes wurde der Protosphere Algorithmus (welcher zum Erstellen von Kugelpackungen verwendet wird) deutlich verbessert und beschleunigt, was in naher Zukunft die Ladezeit für das Füllen der Objekte mit Kugeln drastisch reduzieren soll und somit diesen Vorverarbeitungsschritt zur Startzeit des Programmes ermöglicht.
Projektbezogene Publikationen (Auswahl)
- “A benchmarking suite for 6-DOF real time collision response algorithms”. In: Proceedings of the 17th ACM Symposium on Virtual Reality Software and Technology (VRST). Hong Kong: ACM, Nov. 2010, S. 63–70. isbn: 978-1-4503-0441-2
René Weller, David Mainzer, Mikel Sagardia, Thomas Hulin, Gabriel Zachmann und Carsten Preusche
(Siehe online unter https://doi.org/10.1145/1889863.1889874) - “ProtoSphere: A GPU-Assisted Prototype-Guided Sphere Packing Algorithm for Arbitrary Objects”. In: ACM SIGGRAPH ASIA 2010 Sketches. Seoul, Republic of Korea: ACM, Dez. 2010, 8:1–8:2. isbn: 978-1-4503-0523-5
René Weller und Gabriel Zachmann
(Siehe online unter https://doi.org/10.1145/1899950.1899958) - “Inner Sphere Trees and Their Application to Collision Detection”. In: Virtual Realities. Hrsg. von Sabine Coquillart, Guido Brunnett und Greg Welch. Springer (Dagstuhl), 2011. Kap. 10, S. 181–202. isbn: 978-3-211-99177-0
René Weller und Gabriel Zachmann
(Siehe online unter https://doi.org/10.1007/978-3-211-99178-7_10) - “Kollisionserkennung und natürliche Interaktion in virtuellen Umgebungen”. In: Virtuelle Techniken im industriellen Umfeld. Hrsg. von Werner Schreiber und Peter Zimmermann. Springer, 2011. Kap. 3.2, 3.4, S. 33–38, 114–116. isbn: 978-3-642-20635-1
David Mainzer, René Weller und Gabriel Zachmann
- “CDFC: Collision Detection Based on Fuzzy Clustering for Deformable Objects on GPU’s”. In: WSCG 2013 Proceedings. Bd. 21. 3. Plzeň, Czech Republic, Juli 2013, S. 5–8. isbn: 978-80-86943-76-3
David Mainzer und Gabriel Zachmann
- “Fast Sphere Packings with Adaptive Grids on the GPU”. In: In GI AR/VRWorkshop. Würzburg, Germany, Sep. 2013
Jörn Teuber, René Weller, Gabriel Zachmann und Stefan Guthe
