TUD Logo

TUD Startseite » ... » Ergebnisse studentischer Arbeiten » Große Belege » S. König

Computergraphik

Großer Beleg von Sören König

Echtzeitberechnung und Visualisierung der Dynamik von Gesteinsbrocken
in einer sich verändernden Landschaft

Studiengang Medieninformatik, Wintersemester 2003/2004
Institut für Software- und Multimediatechnik
Lehrstuhl für Computergraphik und Visualisierung

Betreuer: Dipl.-Inf. (FH) Benjamin Neidhold
Hochschullehrer: Prof. Dr. Siegfried Fuchs (Institut für Erkennende Systeme)

Inhalt

  • Aufgabenstellung
  • Einleitung
  • Starrkörperdynamik
  • Kollisionserkennung
  • Kollisionsbehandlung
  • Umsetzung
  • Download

Aufgabenstellung

Zur Simulation und Visualisierung von Erosionsprozessen in einem gegebenen Gelände ist es notwendig, neben der Höhenkarte auch darauf befindliche Objekte (z.B. Gesteinsbrocken) in die Simulation einzubeziehen. Für diese Anwendung soll im Rahmen eines Großen Beleges das physikalisch korrekte (bzw. angenäherte) Verhalten von Steinen in einer sich verändernden Landschaft implementiert werden (Wirkung der Schwerkraft; Berücksichtigung von Wechselwirkungen zwischen einzelnen Gesteinsbrocken). Für die Simulation können die Steine z.B. durch Kugeln approximiert werden. Ein mit OpenGL implementiertes Beispiel soll eine grafische Darstellung der Simulation in bestimmten Intervallen ermöglichen.

Einleitung

In diesem Beleg wurde die Umsetzung einer Dynamiksimulation von Steinen in einer sich verändernden Landschaft und die dafür notwendigen physikalischen, mathematischen und algorithmischen Grundlagen und Ideen beschrieben. Nach einer ausführlichen Erläuterung, wie sich die Bewegung von Steinen durch das allgemeine Modell des Starrkörpers aufgrund verschiedener Einflüsse (z.B. anwirkende Kräfte) berechnen lässt, folgen Details zur Herleitung und Lösung einer für die Simulation besser geeigneten Form der Dynamikgleichung.

Da diese Gleichung zunächst nur eine freie Starrkörperbewegung darstellt, wurde im weiteren Verlauf die Problematik der Erkennung und Behandlung von Kollisionen untersucht. Dabei lag das Hauptaugenmerk auf effizienten Methoden der Kollisionserkennung zwischen beliebigen Dreiecksnetzen, um eine schrittweise Darstellung der Simulation in Echtzeit zu realisieren, denn dies stellt das Hauptperformanceproblem für die Berechnung dar. Mit den Ergebnissen ist es möglich, neben den über Kräfte realisierbaren Einflüssen (z.B. Schwerkraft) auch nichtkontinuierliche Bewegungsänderungen, wie sie durch Stöße hervorgerufen werden, zu behandeln.

Für die Bereitstellung der Oberflächengeometrien wurde ein Exporter für Maya implementiert.

Starrkörperdynamik

Das physikalische Modell des Starrkörpers fasst ein Objekt als eine Menge von Massepunkten auf, dessen Abstand zueinander fixiert ist. Damit lässt sich die Lage eines Objektes durch 6 Freiheitsgrade im dreidimensionalen Raum beschreiben, drei für die Position des Schwerpunktes und drei für die Orientierung.

Kollisionsbaum

Ziel ist es nun, die Änderung dieser 6 Werte über die Zeit zu simulieren. Dabei spielen sowohl Materialeigenschaften wie die Masse oder das Trägheitsverhalten des jeweiligen Objektes als auch die am Objekt anwirkenden Kräfte (und die daraus ableitbaren Drehmomente) ein Rolle. Mithilfe von Gesetzmäßigkeiten aus der klassischen Mechanik lassen sich diese Änderungen durch gewöhnliche Differentialgleichungen beschreiben.

Zur Lösung der aufgestellten Gleichungen kommen numerische Verfahren, wie das explizite Euler-, Midpoint-, oder das Runge-Kutta-Verfahren 4. Ordnung zum Einsatz.

Kollisionserkennung

Die Problematik der Kollisionserkennung gliedert sich im wesentlichen in zwei Fragestellungen:

  1. Wann tritt Kollision auf?
  2. Wo tritt Kollision auf?

Da die Simulation zeitlich diskret abläuft, kann es passieren, dass sich ein Objekt zunächst in einer gültigen und im nächsten Zeitschritt bereits in einer ungültigen Konfiguration befindet (Objekte tauchen räumlich ineinander ein). Grund für diese Situation ist die fehlende Behandlung des Kontaktes. Diese Behandlung muss möglichst genau dann stattfinden, wenn eine Berührung vorliegt.

Zeitschritt

Weiterhin ist es notwendig die genauen Stellen zu kennen, an denen diese Berührung stattfindet, wie die Oberflächennormale an diesen Stellen aussieht und welche Geschwindigkeiten dort vorliegen, um einen entsprechenden Stoß zwischen den Objekten zu berechnen (eine diskontinuierliche Impulsänderung).

Da die Oberflächen der Kollisionsobjekte durch sehr viele Dreiecke beschrieben sind, ist es in Echtzeit nicht mehr möglich einfach jedes Dreieck des einen Kollisionspartners mit jedem Dreieck des anderen Kollisionspartners auf Schnitt zu überprüfen.

Deshalb wurden für die Umsetzung spezielle räumliche Datenstrukturen (sog. Kollisionsbäume) benutzt, die eine effiziente Überprüfung der Dreiecke ermöglichen. Das Grundprinzip dabei ist die hierarchische Einteilung der Dreiecke in einen Baum aus Hüllvolumen. Der Wurzelknoten stellt zunächst ein Hüllvolumen um das gesamte Objekt (alle Dreiecke) dar. Danach wird die Menge der Dreiecke entlang der Hauptausdehnung des Hüllvolumens in zwei Teilmengen zerlegt, um die dann wiederum ein Hüllvolumen gelegt werden kann. Diese bilden dann die Kindsknoten des vorherigen. Den Abschluss bilden dann die einzelnen Dreiecke als Blätter des Baumes.

Kollisionsbaum
2-dimensionales Beispiel für die Erzeugung eines Kollisionsbaumes mit OBBs als Hüllvolumen. Die Linien sind im 3-dimensionalen dann die Dreiecke.
Kollisionsbaum
Struktur des Kollisionsbaumes

Der Test auf Schnitt bzw. Überlappung kann dann effizient anhand der Bäume durchgeführt werden, indem beim Wurzelknoten begonnen und dann rekursiv durch den Baum traversiert wird. Findet bei einem Knotenpaar keine Überlappung statt, so fallen sofort alle Kindsknoten aus dem Test heraus.

Die Wahl der Hüllvolumen richtet sich danach, wie schnell der Überlappungstest durchführbar ist und ob eine gute Volumenapproximation vorliegt. Für die Implementation wurden OBBs verwendet, die im Durchschnitt die besten Ergebnisse liefern.

Kollisionsbaum
Diverse Hüllvolumina (von links nach rechts) AxisAlignedBoundingBox, BoundingSphere, OrientatedBoundingBox

Kollisionsbehandlung

Durch die Kollisionserkennung wurden nun alle zur Behandlung notwendigen Informationen zusam-mengetragen, so dass nun der Stoß zwischen den beiden Objekten berechnet werden kann. Dieser muss so gewählt werden, dass die negativen Relativgeschwindigkeiten der Objekte an den Kontaktstellen in Normalenrichtung entsprechend dem empirischen Stoßgesetz angepasst werden:

Formel

Das - ist die Stoßzahl. Sie nimmt einen Wert zwischen 0 und 1 an, 0 entspricht einem vollkommen unelastischen und 1 einem vollkommen elastischen Stoß. (+ Größe nach dem Stoß, - Größe vor dem Stoß)

Genauer bedeutet dies eine entsprechende Änderung der Gesamtimpulse und Gesamtdrehimpulse der beteiligten Objekte.

Stoss

Umsetzung

Die Programme wurden in C++ bzw. Managed C++ als .NET-Anwendung unter Microsoft Visual Studio .NET 2003 entwickelt. Die grafische Darstellung und Verarbeitung wird durch OpenGL realisiert. Zur Navigation der Ansicht werden folgende Shortcuts verwendet:

Screenshot
Links: Test mit Reibung rechts: Kollisions mit Höhenkarte
  • ALT + linke Maustaste: Rotate
  • ALT + mittlere Maustaste: Move
  • ALT + rechte Maustaste: Zoom
  • linke Maustaste: Stoß applizieren (nicht in allen Demos)
  • Leertaste: Stein hinzufügen (nicht in allen Demos)
  • Bild auf/ab : Höhenkarte ändern (nicht in allen Demos)
  • Download

    • Ausführbare Demos (.zip): Download (2,73 MB)
    • Belegarbeit (.pdf): Download (1,86 MB)
    • Vortragsfolien (.pdf): Download (3,33 MB)
Stand: 1.2.2010, 14:40 Uhr
Autor: Dipl.-Medieninf. cand. Johannes Richter

Kontakt
Dipl.-Medieninf.
Sören König

Tel.: +49 (0) 351 463-38395
Fax: +49 (0) 351 463-38396
E-Mail-Kontaktformular