Sprachen

D-Collide - SS 2007, WS 2007/08

Thema: 
Entwicklung einer echtzeitfähigen Kollisionsbehandlung für die physikalische Simulation in virtuellen Umgebungen
Zeitraum: 
SS 2007, WS 2007/08
Umfang: 
8 SWS pro Semester
Veranstalter: 

Martin Wawro, Informatik VII (Graphische Systeme),
OH16, R.120, Tel.: 6344, E-Mail: wawro@ls7.cs.uni-dortmund.de
Claus-Peter Alberts, Informatik VII (Graphische Systeme),
OH16, R.102, Tel.: 6134, E-Mail: alberts@ls7.cs.uni-dortmund.de

Teilnehmer: 
1. Beckermann Andreas
2. Bode Christian
3. Ens Marcel
4. Ens Sebastian
5. Fassbach Martin
6. Haus Daniel
7. Hegele Maximilian
8. Horst Oliver
9. Jochmann Gregor
10. Loist Timo
11. Nienhaus Marcel
12. Schulz Marc
Thematik: 

Die Computerspieleindustrie stellt heutzutage einen der größten Zweige der Unterhaltungsindustrie dar. Bereits 2004 übertrafen die Umsatzzahlen dieser Branche die Einnahmen der Ticketverkäufe der Filmindustrie um ein Mehrfaches. Die Wichtigkeit dieser Industrie schlägt sich auch in aktueller Forschung nieder. So tauchen z.B. auf den weltweit wichtigsten Konferenzen im Bereich Computergrafik viele Beiträge auf, die im Zusammenhang mit der Spieleindustrie stehen.

Das zur Zeit am häufigsten diskutierte Thema dürfte dabei die physikalische Simulation in Computerspielen sein (sog. Physics Engines). Zur Zeit erstrecken sich die Ansätze in diesem Bereich von CPU-basierten Systemen, über Systemen die auf GPUs (Grafikkarten) laufen, bis hin zu eigens dafür entwickelter Spezialhardware (PhysX). Gerade im Hinblick auf die Verbreitung von Multicore Architekturen (z.B. Cell Broadband Engine, Intel/AMD Quadcore) wird es in diesem Bereich viele Verbesserungen und Neuerungen geben, welche die hinzugewonnene Rechenzeit f&uum;r noch realistischeren Effekten ausnutzen.

Abbildung 1: SimulationsszenarienAbbildung 1: Simulationsszenarien

Die Hauptaufgabe der Projektgruppe besteht darin, Kollisionsdetektionsverfahren zu entwickeln, welche in der Lage sind, Kollisionen von Starrkörpern, derformierbaren Objekten und auch Textilien (siehe Abb. 1) in komplexen Umgebungen in Echtzeit behandeln. Die Kollisionsdetektion stellt in der physikalischen Simulation eines der herausforderndsten Probleme dar. In derzeit eingesetzten virtuellen Umgebungen sind Kollisionen zwischen hunderten bis tausenden Objekten möglich und müssen in Echtzeit abgearbeitet werden können (Zielrechenzeit liegt hier bei < 20ms). Ansätze reichen hier von der Nutzung hierarchischer Bounding-Boxes [Gotts96] oder anderer Bounding Volumes [Klos98] (siehe z.B. Abb. 2) bis hin zum Erstellen von Distanzfeldern [Fuhr03]. Mit der verbesserten Programmierbarkeit moderner GPUs wurden auch Kollisionsdetektionsans ätze auf Grafikkartenbasis untersucht [Knott03,Heid04]. Eine besondere Schwierigkeit besteht hier im Bereich der Simulation von Textilien, welche z.B. auch mit sich selbst kollidieren können und nicht unerheblich viele Kontaktpunkte besitzen [Brid02] (siehe Abb. 3).

Abbildung 2:  	k-DOP Bounding Volume HierarchieAbbildung 2: k-DOP Bounding Volume Hierarchie

Ausgangsbasis für das von der PG zu entwickelnde Verfahren wird eine hierarchische Bounding- Volume Struktur sein, für die, aufgrund von möglichen Deformationen, effiziente Updates berechnet werden müssen. Insbesondere für Kleidungssimulation wird ein anderer Ansatz gewählt werden müssen als für Starrkörper oder deformierbare Volumenmodelle. Hier könnte sich ein Ansatz auf GPU Basis als vorteilhaft erweisen.

Abbildung 3: Selbstkollision bei TextilienAbbildung 3: Selbstkollision bei Textilien

Das von der Projektgruppe zu entwickelnde Kollisionsbehandlungsverfahren soll mit einer frei verfügbaren Grafikengine (die Auswahl bleibt der PG überlassen) und einer ebenfalls frei verfügbaren Physikengine (z.B. ODE) integriert werden und in einer Beispielumgebung laufen. Sollten die PG-Teilnehmer daran interessiert sein, die Physikengine selbst zu entwickeln, so ist das auch möglich (genügend Motivation vorausgesetzt). Aufgrund der zeitkritischen Natur von Echtzeitanwendungen sind insbesondere effiziente Algorithmen (selbst O(n2) ist in vielen Fällen nicht mit den Zeitanforderungen vereinbar) und auch eine effiziente Umsetzung in Programmcode sehr wichtig. Da die Kollisionsbehandlung in eine bestehende (freie) Simulationsumgebung integriert werden soll/kann, ist ein softwaretechnisch sauberes Vorgehen unerlässlich, da der Rahmen der Umgebung sehr umfangreich sein kann und saubere Schnittstellen i.d.R. auch eine höhere Effizienz gewährleisten.

Teilnahmevorraussetzungen:

Legende: [V] vorausgesetzt, [W] wünschenswert
  • Eine der Wahlpflichtvorlesungen Mensch-Maschine Interaktion, Rechensysteme, Eingebettete Systeme oder Komplexitätstheorie und Effiziente Algorithmen. [V]
  • Wahlvorlesung Geometrisches Modellieren, Digitale Bilderzeugung oder Verteilte numerische Algorithmen [W]
  • Linux-Kenntnisse [W]
  • C++ Kenntnisse (Assemblerkenntnisse wären von weiterem Vorteil) [W]
  • Kenntnisse im Bereich Shader-Programmierung (GLSL) [W]

Minimalziele:

  • Dokumentierter Systementwurf.
  • Dokumentierte Implementierung eines Prototypen zur Handhabung von Kollisionen.
  • Demonstration der Grundfunktionalität der Kollisionsbehandlung mit Hilfe von bereits vorhandenen Physik- und Grafikengines anhand eines Beispiels mit 100 kollidierenden Starrkörpern in Echtzeit.
  • Demonstration der Kollisionsbehandlung im Bereich Selbstkollision anhand eines fallenden Tuches (in Echtzeit).

Erweiterungsmöglichkeiten:

  • Wie bereits erwähnt kann eine eigene Physik-Engine implementiert werden. Hier wäre insbesondere
  • die Handhabung von deformierbaren Objekten in Echtzeit sehr interessant
  • Zeitkritische Teile der Kollisionsbehandlung können mit SSE/MMX Beschleunigung ausgestattet werden.

Literatur:

[Tesch04] M. Teschner et al., Collision Detection for Deformable Objects, EUROGRAPHICS 2004, State of the Art Report, 2004.
[Heid04] B. Heidelberger et al., Detection of Collisions and Self-Collisions using Image-Space Techniques, Proc. WSCG’04, 2004.
[Lars01] T. Larsson et al., Collision Detection for Continuously Deforming Bodies, EUROGRAPHICS 2001, 325-333, 2001.
[Klos98] J. Klosowski et al., Efficient Collision Detection using Bounding Volume Hierarchies of k-DOPs, IEEE Trans. Vis. Comp. Graph., 4(1), 21-36, 1998.
[Knott03] D. Knott, Cinder: Collision and Interference Detection in Real-Time Using Graphics Hardware, Proc. Graphics Interface, 2003.
[Gotts96] S. Gottschalk et al., A Hierarchical Structure for Rapid Interference Detection, SIGGRAPH 1996, 171-180, 1996.
[Brid02] R. Bridson et al., Robust Treatment of Collisions, Contact and Friction for Cloth Animation, Proc. Intl. Conf. Comp. Graph. Int. Techn., 594-603, 2002.
[Fuhr03] A. Fuhrmann et al., Distance Fields for Rapid Collision Detection in Physically Based Modelling, Proc. of GraphiCon 2003, 58-65, 2003.

Rechtliche Hinweise:

Die Ergebnisse der Projektarbeit inklusive der dabei erstellten Software sollen der Fakultät für Informatik uneingeschränkt zur freien Forschung zur Verfügung stehen. Darüber hinaus sind keine Einschränkungen der Verwertungsrechte an den Ergebnissen der Projektgruppe und keine Vertraulichkeitsvereinbarungen vorgesehen.