Sarrazin, Roland (2002)
Kollisionserkennung und -behandlung zwischen stark deformierbaren und starren Körpern.
Technische Universität Darmstadt
Diplom- oder Magisterarbeit, Bibliographie

Kurzbeschreibung (Abstract)

Die heutige Rechner- und Grafikhardware ermöglicht es, sich immer realitätsnähere Anwendungen vorzustellen. Dabei spielt die physikalisch basierte Simulation, die die simulierte virtuelle Welt anhand echter physikalischer Gesetze zu modellieren versucht, eine wichtige Rolle. In einer simulierten virtuellen Welt wird oft der Unterschied zwischen dem eigentlich simulierten Objekt und der Umgebung, in der dieses sich bewegt, gemacht. Die physikalisch basierte Simulation wird anhand dieses Unterschieds in zwei Teilprobleme aufgeteilt: zum einen die Bestimmung anhand der physikalischen Gesetze des neuen Wunschzustands des simulierten Objektes, zum anderen die Kollisionsbehandlung, die die Durchdringung des simulierten Objektes in die Umgebung, also die Kollisionsszene, vermeidet bzw. auflöst. Das Laufzeitverhältnis dieser zwei Teilaufgaben zeigt auf, dass die Kollisionsbehandlung oft der Engpass der physikalisch basierten Simulation ist. Diese Tatsache ist in dem Fall eines stark deformierbaren Körpers als simuliertes Objektes noch kritischer, da die meisten Komponenten der virtuellen Welt ständig kollidieren. Ein solcher Anwendungsfall ist z.B. bei der Textilsimulation, bzw. bei dem virtuellen Echtzeit-Bekleiden menschlicher Avatar zu finden. In der vorliegenden Arbeit wurde also ein Verfahren entwickelt, das die Eigenschaft der virtuellen Welt, dass sie einerseits aus einem stark deformierbaren, simulierten Objekt, andererseits aus einer starren Kollisionsszene besteht, ausnutzt. Die bisher eingesetzten Methoden zur Kollisionsbehandlung ziehen oft aus dieser Eigenschaft keinen Vorteil, so dass ihre Laufzeit zum einen hoch ist, zum anderen besonders schwankend ist. Aus diesen Gründen lassen sich diese Methoden schlecht in den vorgesehenen Echtzeit-Anwendungen einsetzen. Die hier entwickelte Methode nutzt im Gegenteil diese Eigenschaft, um die tatsächliche Laufzeit der Kollisionsbehandlung zu verkürzen, indem sie aufwändige Aufgaben in einen Vorberechnungsschritt verlegt. Diese Methode basiert auf dem Konzept des Distanzfeldes. Ein Distanzfeld ist ein reguläres räumliches Gitter, dessen Gittereckpunkte den vorzeichenbehafteten Abstand zur Kollisionsszene enthalten. Pro Kollisionsszene gibt es ein einziges Distanzfeld, so dass es in einem Vorberechnungsschritt bestimmt werden kann. Diese Erzeugung basiert wiederum auf dem kd-Tree, einer räumlichen Datenstruktur, um die Brute-Force-Abstandbestimmung zu vermeiden. Während der eigentlichen Kollisionsbehandlung wird das Distanzfeld so abgefragt, dass die Kollisionen erstens erkannt, zweitens entsprechend aufgelöst werden. Die Kollisionsbehandlung verläuft demzufolge in konstanter Zeit. Ein Prototyp dieser Methode wurde in einer bereits existierenden Java-Simulationsumgebung implementiert, so dass ein unmittelbarer Vergleich der verschiedenen Laufzeiten möglich war. Zum einen bestätigt dieser Vergleich die besondere Eigenschaft der Methode, in konstanter Zeit zu verlaufen, zum anderen weist er auf, dass sie robust und stabil sowie um eine Größenordnung schneller als bisher eingesetzte Methoden ist. Diese Methode eignet sich also gut für kollisionsreiche virtuelle Welten, und viele Einsatzbereiche, wie die Textilsimulation oder allgemeinere partikelsystem-ähnliche Modelle, lassen sich vorstellen. Außerdem ist auch eine Animation der Kollisionsszene möglich, so dass diese Methode ein breites Anwendungsfeld gestattet.

Frage zum Eintrag

Redaktionelle Details anzeigen