Advanced Games Physics
Inhaltsverzeichnis zum
Inhalt

Kollisionserkennung

Vektorbasierte Kollisionserkennung

Vektorbasierte Verfahren für Polygone

Eingedenk der Tatsache, dass die Leistungsfähigkeit künftiger Prozessoren immer weiter getrieben wird, soll hier ein Verfahren vorgestellt werden, dessen Präzission beliebig gesteigert werden kann.

Während die einfachen Verfahren meist die Abstände zwischen den Mittelpunkten der kollidierenden Objekte messen, liegen die Dinge in der Regel nicht so einfach: Von gleichen Abständen zum Mittelpunkt (was ist hier eigentlich der Mittelpunkt?) kann ja nicht mehr die Rede sein! So behelfen wir uns mit einer stückweise linearen Approximation der Kontur des Objektes. D.h. wir verteilen auf der Kontur charakteristische Punkte Pi, die durch Geradenstücke miteinander verbunden werden. Benachbarte Punkte, z.B. Pi bzw. Pi+1 grenzen die durch beide Punkte verlaufende Gerade zu einem Segment ein. Beide Punkte werden geometrisch durch ihre Ortsvektoren x i und x i+1 beschrieben.
Wir bleiben bei dem oben beschriebenen Szenarium: der Komet Tschuri wird von dem Lander Philae besucht. Der Einfachheit halber betrachten wir das kollidierende Objekt, also Philae, als Kreis (bzw. Kugel in 3D), deren Lage durch den Ortsvektor x Obj beschrieben wird. Philae als Kreis (bzw. Kugel in 3D) zu betrachten, ist bei den gegebenen Größen­verhältnissen zu rechtfertigen.
2D-Approximation des Kometen Tschuri durch ein Polygon

Abb. 2D-Approximation des Kometen Tschuri durch ein Polygon
Quelle: ESA/Rosetta/MPS for OSIRIS Team MPS/UPD/LAM/IAA/SSO/INTA/UPM/DASP/IDA License: CC-BY-SA

Die Aufgabe besteht jetzt darin, die kürzeste Entfernung zwischen dem Objekt Kreis und dem Objekt Tschuri zu finden. Zu diesem Zweck sind zunächst einmal alle Entfernungen zwischen dem Kreis (Philae) und den einzelnen Segmenten des Polygons, das die Kontur von Tschuri beschreibt, zu berechnen. Dazu sind I Berechnungen erforderlich, wenn das Polygon aus I Punkten bzw. Segmenten besteht. Sind aber beide Objekte als Polygone umschrieben, dann sind I1·I2 Berechnungen erforderlich!
Nun zur Berechnung der Distanzen. Siehe hierzu und .

Betrachtung eines Polygonsegmentes

Abb. Betrachtung eines Polygon­segmentes

Benennung der Vektoren

Abb. Benennung der Vek­toren


Zur Berechnung der Distanzen sind im einzelnen die folgenden Schritte notwendig.
  1. Berechnung der einzelnen Vektoren:
    ()
    Formel 1
    und
    ()
    Formel 1

  2. Berechnung der Distanz:
    Da der Distanzvektor D senkrecht auf dem Segmentvektor S steht, handelt es sich hier um ein rechtwinkliges Dreieck. Der Betrag des Distanzvektors | D | stellt die Gegenkathete zum Betrag des Objektvektors | O | dar. So kann der Betrag des Distanzvektors | D | wie folgt errechnet werden:
    ()
    Formel 1

    Erweitern wir nun mit dem Betrag des Distanzvektors | D | so erhalten wir
    ()
    Formel 1

    Der eingeschlossen Winkel α kann aus den gegebenen Größen berechnet werden, aber das ist gar nicht erforderlich, denn wir sehen, dass der Zähler von genau der Definition des vektoriellen Kreuzproduktes entspricht. Deshalb kann unter Verwendung des Kreuzproduktes auch geschrieben werden:
    ()
    Formel 1

    Somit können jetzt alle Abstände zwischen dem Objekt Kreis und den einzelnen Segmenten des Objektes Tschuri berechnet und miteinander verglichen werden. Die kleinste Distanz macht das Rennen und kann mit dem Kreisradius verglichen werden.

    Wenn die kleinste Distanz
    ()
    Formel 1
    dann liegt eine Kollision vor!

  3. Berechnung des Stoßortes:
    Nun dürfte noch von Interesse sein, wo auf dem Segment die Kollision stattfindet. Dazu berechnen wir den Partvektor P . Der Betrag des Partvektors | P | stellt die Ankathete zum Betrag des Objektvektors | O | dar. Somit kann dem obigen Schema folgend, der Betrag des Partvektors | P | als das vektorielle Punktprodukt (auch Skalarprodukt genannt) geschrieben werden:
    ()
    Formel 1
    also
    ()
    Formel 1

    Für die Ortsbestimmung reicht der Betrag aber nicht aus, hierfür ist ein Vektor erforderlich. Da das Skalarprodukt im Ergebnis einen Skalar liefert, muss die Umwandlung in einen Vektor in einem weiteren Schritt erfolgen. Da der Partvektor P parallel zu Segmentvektor S verläuft, können wir von diesem die Richtung übernehmen, d.h. wir bilden den Einheitsvektor des Segmentvektors und multiplizieren diesen mit dem Betrag des Partvektors:
    ()
    Formel 1

Nun gibt es noch eine Kleinigkeit zu beachten. Dort wo benachbarte Segmente aneinander stoßen, entsteht eine Ecke ().

  • Konvexe Ecken
    Eine konvexe Ecke liegt dann vor, wenn das Objekt links außerhalb des aktuellen Segmentes liegt. Dann wird der Partvektor negativ. Oder das Objekt liegt rechts außerhalb des aktuellen Segmentes, dann ist der Partvektor größer als der Segment­vektor. Beide Situationen sind programm­technisch leicht abzutesten. Hier gilt als Distanz die einfache Entfernung zwischen Objekt­mittel­punkt und dem jeweiligen Eckpunkt gegeben durch den Objektvektor O . Es gilt .

  • Konkave Ecken
    Konkave Ecken bedürfen keiner besonderen Behandlung bei den Berechnung. Allerdings kann der Fall eintreten, dass der Kreis genau beide benachbarten Segmente berührt. Da alle Segmente aufeinander folgend abgetestet werden, wird in einem solchen Fall erst das Segment mit dem kleineren Index und anschließend das Segment mit höherem Index abgeprüft. Es gibt also zwei kürzeste Entfernungen und es werden zwei Kontaktorte ermittelt!
Sonderfall Ecke

Abb. Sonderfall Ecke


demonstriert die Funktion der Vektor basierten Kollisions­erkennung. Du kannst den grünen Ball mit der Maus über das gesamte Feld bewegen. Sobald Du damit aber ein Kontursegment berührst wird eine Kollision signalisiert (roter Punkt). Gleichzeitig werden auch die entsprechenden Vektoren angezeigt (diese sind farblich gekennzeichnet, ihre Bedeutung wird rechts in der Agenda benannt). Besondere Beachtung verdienen die Ecken und die Anfangs- und Endpunkte der Kontur. Bei konkaven Ecken treten mehrfache Kontakte (touch)s auf. Zusätzlich erfolgt eine Information darüber, welcher Typ Ecke vorliegt. Das Sympol < steht für eine konvexe Ecke, das Symbol > steht für keine oder eine konkave Ecke.
Die Kollisions­erkennung ist unabhängig von der Seite, von der Du Dich der Kontur näherst.
Neben dem Kontaktort P(x, y) werden der Normalenwinkel β und die Eindringtiefe dErr numerisch angegeben.

Bitte einen Augenblick Geduld
während das Programm geladen wird!
Abb. Vektor basierte Kollisionserkennung


Das nebenstehende Beispielprogramm wird so wie das in gezeigte Programm bedient. Hinzu kommt eine Auswahl unterschiedlicher Konturen, die mit dem Button Profil ausgewählt werden können.
download processing
download p5.js
run program


Zusammenfassung Die ausschließlich Distanz besierte Kollisionserkennung erfordert einen relativ geringen Rechenaufwand, der sich auf das Quadrieren von Abstandsdifferenzen der Ortskomponenten beschränkt. Allerdings erkennt er eine Kollision immer erst nachdem die Kollision statt gefunden hat. Das kann in dynamischen Anwendungen zu Problemen führen. Darüber werden wir in den folgenden Abschnitten sprechen.