Advanced Games Physics
Inhaltsverzeichnis zum
Inhalt

Verfahren zur Erkennung von Kollisionen

Bitte einen Augenblick Geduld
während das Programm geladen wird!
Alle Themen in diesem Kapitel:

Das Standardverfahren für einfach geformte Körper

Kaum ein Spiel, dass ohne zusammenprallende Objekte auskommt! Zur Behandlung von Stößen gehört, dass die Kollision als örtliches und zeitliches Ereignis erkannt wird. Das leistet die Kollisionserkennung.

Für die Besprechung der Kollisionserkennung benutzen wir zweckmäßiger Weise die Vektordarstellung. Schauen wir uns zunächst den einfachsten Fall einer Kollision an, nämlich den Zusammenstoß von zwei Kugeln. Kugeln sind in diesem Sinne ideale Objekte, ist doch jeder Punkt ihrer Oberfläche gleich weit vom Zentrum entfernt.

In vektorieller Schreibweise ergibt sich der Abstand distance zwischen den beiden Kugeln entsprechend zu:

()
Formel
Dabei ist klar, dass der Abstand der Mittelpunkte beider Kugeln nicht kleiner als die Summe beider Radien r1 + r2 werden kann. So lautet die Kollisionsbedingung also:

()
Formel
kollidierende Kugeln

Abb. kollidierende Kugeln


Nach dem Satz des PYTHAGORAS lautet die geometrische Interpretation von
()
Formel

Eines der bekanntesten Verfahren, mit unregelmäßig geformten Objekten umzugehen, ist das bounding volume-Verfahren. Hier wird eine kompliziertere geometrische Struktur eines Objektes von einem einfach zu behandelnden Körper, z.B. eine Kugel oder ein Würfel, umhüllt. Für dieses Verfahren gibt es Algorithmen, die die optimalen Abmessungen des ersetzenden Objektes berechnen.
Nun erfolgt die Kollisionserkennung an Stelle des komplizierten Körpers an dem einfachen Hüllkörper. Dieses Verfahren ist einfach in der Behandlung, liefert aber wenig befriedigende Ergebnisse.
Die Welt ist aber nicht so einfach gestrickt, dass wir mit dem Modell der kollidierenden Kugeln alle vorkommenden Situationen, d.h. indem alle beliebig geformten Objekte einfach durch Kugeln ersetzt werden, meistern könnten. Insbesondere der Dezentrale Stoß und die Problematik Stoß und Drehimpuls können mit diesem einfachen Modell nicht behandelt werden!
Wie könnten denn alternative Methoden aussehen?

Sehen wir uns ein kosmisches Objekt wie den Kometen 67P/Tschurjumow-Gerassimenko an. Der Höhepunkt der Rosetta-Mission war die Landung der Sonde Philae auf dem Kometen Tschuri. Welchen Einfluss mag wohl diese Landung auf die weitere Bewegung des Kometen haben? Diese Frage zu beantworten, heißt das Stoßgeschehen in der Simulation zu berechnen.
Diese Aufgabenstellung wird uns über mehrere Kapitel hinweg beschäftigen. Zuvor müssen aber die Parameter des Zusammenstoßes ermittelt werden. Dazu werden wir in den folgenden Abschnitten verschiedene Verfahren erproben.
Der Komet Tschuri und die Sonde Philae

Abb. Der Komet Tschuri und die Sonde Philae
Quelle: ESA/Rosetta/MPS for OSIRIS Team MPS/UPD/LAM/IAA/SSO/INTA/UPM/DASP/IDA License: CC-BY-SA

Extended bounding-volume Verfahren

Im Grunde entspricht dieses Verfahren dem oben beschriebenen Standardverfahren. Der Unterschied besteht darin, dass statt einer Kugel mehrere Kugeln zur Approximation der Hülle verwendet werden.

Der Übersichtlichkeit halber beschränken wir uns auf die Betrachtung eines 2D-Modells. Statt durch Kugeln unterschiedlicher Radien approximieren wir die Objekte durch Kreise.
Allgemein beinhaltet die Szene K Objekte, von denen jedes durch IK Kreise approximiert wurde. Allerdings wird die Distanz nicht nur einmal zwischen zwei Kreisen bestimmt, sondern sie wird von allen IK Kreisen zu allen anderen Kreisen der anderen Objekte bestimmt. zeigt die Situation für zwei Objekte. Die Distanzen zwischen den i = 0...IK einzelnen Kreisen des Kten Objekts zu den j = 0...JL Kreisen des Lten Objekts berechnen sich dann allgemein zu:

()
Formel

und die Kollisionsbedingung lautet demnach:
()
Formel

Schauen wir uns das Beispiel in an. Setzen wir voraus, dass die Approximation durch Kreise bereits erfolgt ist, dann sind die Orte P1,i und die Radien r1,i aller Kreise des 1. Objektes (hier Philae) und Orte P2,j und die Radien r2,j aller Kreise des 2. Objektes (hier Tschuri) bekannt. So lautet die Berechnung der blau gezeichneten Distanz unseres Beispiels:

2D-Approximation des Kometen Tschuri und der Sonde Philae durch Kreise

Abb. 2D-Approximation des Kometen Tschuri und der Sonde Philae durch Kreise

()
Formel

Insgesamt sind vom 1. Objekt (3 Kreise) zum 2. Objekt (4 Kreise) 3·4 = 12 Distanzen zu berechnen und alle Distanzen, die der Bedingung genügen, zu finden:

()
Formel

Dabei ist nicht auszuschließen, dass es mehrere Kandidaten für die kleinste Distanz geben kann!

Das hier gezeigte Beispielprogramm arbeitet zweistufig:

1. Editiermodus: Es werden drei Objekte dargestellt (der Komet Tschuri, die Raumfähre Rosetta und der Lander Philae). Klicke eines dieser Objekte mit der Maus an, um es zu selektieren. Mit Betätigung des Buttons Circle erzeugst Du einen Kreis, der in der linken oberen Ecke erscheint. Fasst Du diesen Kreis in seinem Inneren an, kannst Du ihn mit der Maus verschieben. Fasst Du hingegen seinen Rand an, veränderst Du mit der Maus den Kreisradius!
download p5.js
run program
Per drag'n drop plazierst bzw. formst Du nun den Kreis optimal zur Form des Objektes passend. Erneutes Betätigen des Buttons Circle erzeugt einen weiteren Kreis, den Du ebenso passend in das aktive Objekt einfügst. Hast Du die Form genügend genau mit solchen Kreisen gefüllt, klickst Du auf das nächste Objekt, um auch diese mit passenden Kreisen zu füllen.
Sind alle Objekte, die an der Kollisionserkennung beteiligt sein sollen, mit Kreisen ausgefüllt. Betätigst Du den Button run und kommst damit in die nächste Stufe.

2. Arbeitsmodus: Hier kannst Du nun die Arbeitsweise des extended bounding-volume Verfahrens studieren. Fasse ein beliebiges Objekt mit der Maus an und bewege es an eines der anderen Objekte heran. Berühren sich die Objekte, wird die Kontaktstelle angezeigt.
Mit dem Button show kannst Du die Hilfskreise und Verbindungslinien anzeigen lassen.

Ergebnisdiskussion: Bei einer hinreichend großen Anzahl approximierender Kreise ist eine gute Modellierung beliebig geformter Objekte möglich. Natürlich steigt mit der Anzahl der Kreise auch der Rechenaufwand der Kollisionserkennung. Vorteilhaft ist, dass mit diesem Verfahren beliebig viele Objekte durch Kreise (Kugeln bei 3D-Anwendungen) nachgebildet werden können, indem im setup() die maximale Anzahl Kmax von Objekten eingegebenwerden kann. Die Anzahl der approximierenden Kreise I(K) je Objekt wird dynamisch bei der Kreation der Kreise ermittelt.
Da das Verfahren auch multiple Kollisionen erkennt, ist es bei der Auswertung der Kollisionsresultate wichtig zu unterscheiden, ob multiple Kontakte wirklich gleichzeitig oder aufeinander folgend auftreten. Davon hängt ab, wie sich Objekte nach einer Kollision weiter bewegen.