Advanced Games Physics

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­seg­men­tes

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 Segmentvektors | S | 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 möglicher Weise eine Kollision vor!

  3. Auswahl des Segmentes mit der kürzesten Distanz:

    Wie zeigt, gibt es in einem Polygon nicht nur eine "kürzeste" Distanz, die nach der Rechenvorschrift ermittelt wird. Wir dürfen nicht vergessen, dass zu jedem Segment ein - verschieblicher - Segmentvektor gehört, zu dem stets auch eine kürzeste Distanz zum Objekt existiert!
    Auskunft kann der part-Vektor P geben. Das ist der Vektor, der den Abstand des Distanzvektors D auf den Segmentvektor S vom Ausgangspunkt Pi angibt. Es ist die Länge des Partvektors, die wir als Kriterium für die wirklich kürzeste Distanz aus allen Segmenten heranziehen können: Es gilt

    • ist der Partvektor länger als die Länge des jeweiligen Segmentes, liegt der Distanzvektor außerhalb des aktuellen Segmentes (in im Segment i-1). Diese Distanz ist zu verwerfen!

    • ist die Länge des Partvektors negativ (in im Segment i+1), ist die gefundene Distanz ebenfalls zu verwerfen.

    • nur im Segment i findet keine Verletzung der Auswahlkriterien statt! Die Bedingung für das zutreffende Segment und damit die wirklich kürzeste Distanz lautet:
    ()
    l S e g m e n t i l p a r t i 0
    Auswahl des Segmentes mit der kürzesten Distanz

    Abb. Auswahl des Segmentes mit der kürzesten Distanz

    Berechnen wir die Länge des Part-Vektors P . Die Länge (nicht der Betrag, die Länge kann ja auch negativ werden!) des Partvektors lpart stellt die Ankathete zum Betrag des Objektvektors | O | dar. Somit kann dem obigen Schema folgend, die Länge des Partvektors als das vektorielle Punktprodukt (auch Skalarprodukt genannt) geschrieben werden:
    ()
    l p a r t = | S | · | O | · cos α | S |
    also
    ()
    l p a r t = S · O | S |
  4. Berechnung des Stoßortes:

    Nun dürfte noch von Interesse sein, wo auf dem Segment die Kollision stattfindet. Auch hier hilft uns wieder der Part-Vektor. Für die Ortsbestimmung reicht die Länge des Part-Vektors 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:
    ()
    P = l p a r t · S | S |

  5. Berechnung des Normalenwinkels:

    Die Kenntnis des Normalenwinkels β () ist für die Berechnung des Ausfallswinkels nach einem Stoß wichtig. Er berechnet sich, sofern der Stoßort auf einem Segment liegt, aus den Koordinaten des Partvektors und des Objektvektors:
    ()
    β = arctan y O b j y P a r t x O b j x P a r t

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 .
    Und der Normalenwinkel entspricht dem Winkel der Verbindungsline Objekt - Eckpunkti:
    ()
    β = arctan y O b j y i x O b j x i

  • 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 bzw. es werden zwei Kontaktorte und zwei Normalenwinkel 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.