6. Kapitel

Vektorbasierte Kollisionserkennung

Vektorbasierte Verfahren für Polygone

Kreis trifft auf Polygon

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. Voraussetzung für die Anwendung dieses Verfahrens ist, dass die Objekte - ob photorealsistisch oder nicht - als Polygon vorliegen müssen. Um zu einem solchen Polygon zu kommen, schau Dir das Kapitel Photorealistische Objekte an. Dort wird ein Programm zur Digitalisierung - besser Konturerfassung - von Images vorgestellt und zur Anwendung bereit gestellt.

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 P_i, die durch Geradenstücke miteinander verbunden werden. Benachbarte Punkte, z.B. P_i bzw. P_i+1 grenzen die durch beide Punkte verlaufende Gerade zu einem Segment ein. Beide Punkte werden geometrisch durch ihre Ortsvektoren

{\vec{x}}_{i}

und

{\vec{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

{\vec{x}}_{Obj}

beschrieben wird. Philae als Kreis (bzw. Kugel in 3D) zu betrachten, ist bei den gegebenen Größenverhältnissen zu rechtfertigen.

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 I₁·I₂ Berechnungen erforderlich!
Nun zur Berechnung der Distanzen. Siehe hierzu und .

Abb. Betrachtung eines Polygonsegmentes

Abb. Benennung der Vektoren

Zur Berechnung der Distanzen sind für jedes Segment i im einzelnen die folgenden Schritte notwendig:

Berechnung der einzelnen Vektoren:

()

${\vec{O}}_{i} = {\vec{P}}_{O b j} - {\vec{P}}_{i}$

und

()

${\vec{S}}_{i} = {\vec{P}}_{i + 1} - {\vec{P}}_{i}$
Berechnung der Distanz:
Da die Distanzvektoren $\vec{D}$ stets senkrecht auf den Segmentvektoren $\vec{S}$ stehen, handelt es sich hier um rechtwinklige Dreiecke. Die Beträge der Distanzvektoren $| {\vec{D}}_{i} |$ stellen die Gegenkatheten zum Betrag des jeweiligen Objektvektors $| {\vec{O}}_{i} |$ dar. So kann der Betrag des Distanzvektors $| {\vec{D}}_{i} |$ wie folgt errechnet werden:

()

$| {\vec{D}}_{i} | = | {\vec{O}}_{i} | \cdot \sin (α_{i})$

Erweitern wir nun mit dem Betrag des Segmentvektors $| {\vec{S}}_{i} |$ so erhalten wir

()

$| {\vec{D}}_{i} | = \frac{| {\vec{O}}_{i} | \cdot | {\vec{S}}_{i} | \cdot \sin (α_{i})}{| {\vec{S}}_{i} |}$

Der eingeschlossen Winkel α_i 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:

()

$| {\vec{D}}_{i} | = \frac{| {\vec{O}}_{i} \times {\vec{S}}_{i} |}{| {\vec{S}}_{i} |} = d_{i}$

Somit können jetzt alle Abstände d_i - die ja den Beträgen der Distanzvektoren $| {\vec{D}}_{i} |$ entsprechen - zwischen dem Objekt Kreis und den einzelnen Segmenten des Objektes Tschuri berechnet und miteinander verglichen werden. Der kleinste Distanzwert macht das Rennen und kann mit dem Kreisradius verglichen werden.

Wenn die kleinste Distanz

()

$d_{i} \leq r_{O b j}$

dann liegt möglicher Weise eine Kollision vor!
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 Part → i geben. Das ist der Vektor, der den Abstand des Distanzvektors D → i auf den Segmentvektor S → i vom Ausgangspunkt P_i 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}} \geq l_{p a r t_{i}} \geq 0$
Abb. Auswahl des Segmentes mit der kürzesten Distanz
Berechnen wir die Länge des Part-Vektors Part → i . Die Länge (nicht der Betrag, die Länge kann ja auch negativ werden!) des Partvektors l_part stellt die Ankathete zum Betrag des Objektvektors | O → i | 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} = \frac{| {\vec{S}}_{i} | \cdot | {\vec{O}}_{i} | \cdot \cos (α)}{| {\vec{S}}_{i} |}$

also

()

$l_{p a r t} = \frac{{\vec{S}}_{i} \cdot {\vec{O}}_{i}}{| {\vec{S}}_{i} |}$
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 die Partvektoren ${\vec{P a r t}}_{i}$ parallel zu den Segmentvektoren ${\vec{S}}_{i}$ verlaufen, können wir von diesen die Richtung übernehmen, d.h. wir bilden den Einheitsvektor der Segmentvektoren und multiplizieren diese mit dem jeweiligen Betrag des Partvektors:

()

${\vec{P a r t}}_{i} = l_{p a r t} \cdot \frac{{\vec{S}}_{i}}{| {\vec{S}}_{i} |}$
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:

()

$β_{i} = \arctan (\frac{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 Segmentvektor. Beide Situationen sind programmtechnisch leicht abzutesten. Hier gilt als Distanz die einfache Entfernung zwischen Objektmittelpunkt und dem jeweiligen Eckpunkt gegeben durch den Objektvektor ${\vec{O}}_{i}$ . Es gilt .
Und der Normalenwinkel entspricht dem Winkel der Verbindungsline Objekt - Eckpunkt_i:

()

$β_{i} = \arctan (\frac{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!

Abb. Sonderfall Ecke

demonstriert die Funktion der Vektor basierten Kollisionserkennung. 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 Kollisionserkennung 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.

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.

Polygon trifft auf Polygon

Vom geometrischen Ansatz her ist die Lösung für die Kollisionserkennung von zwei oder mehreren Polygonen nicht schwerer als die vorangehend beschriebene Aufgabe. Die Herausforderung besteht hier darin, den Rechenauswand so klein wie möglich zu halten. Weil hier nicht nur ein Punkt (Kreismittelpunkt) mit den I Punkten des Polygons interagiert, sondern die I Punkte des einen mit den J Punkten des anderen Polygons in Abhängigkeit zu bringen sind. Damit müssten theoretisch I·J Berechnungen ausgeführt werden.
Deshalb werden, bevor die eigentliche Ermittlung der Kollisionen beginnt, alle Maßnahmen ergriffen, um die Zahl der Berechnungen zu minimieren.

Zunächst werden die Polygone (2D) wie Kreise, deren Radius R_ext dem Abstand des am weitesten vom Mittelpunkt entfernten Konturpunktes entspricht, behandelt. So kann vorab geprüft werden, ob eine Kollision zwischen zwei oder mehreren Polygonen überhaupt auftreten kann. Diese Aufgabe entspricht dem Standardverfahren und bedarf nur eines geringen Rechenaufwandes. Dieser geringe Zusatzaufwand lohnt sich insbesondere dann, wenn mehrere Objekte kollidieren können.
Im nächsten Schritt wird geprüft, welche Konturpunkte überhaupt kollidieren können. Es ist einsichtig, dass die vom Kollisionsgegner abgewendeten Punkte nie in eine Kollision verwickelt werden können. Wenn zwei Objekte aufeinander treffen und kollidieren, ist die Frage "wer trifft auf wen". Bei Polygonen ist klar, dass immer nur Konturpunkte des einen Objektes auf die Verbindungslinien (Segmente) oder ebenfalls Konturpunkte des anderen Objektes treffen. Das eine Objekt benenne ich in Bezug auf die Kollisionserkennung als Initiator und das andere als Opponent. Dabei spielt es keine Rolle, wer sich auf wen zubewegt.
zeigt diese Situation für zwei Objekte (alle Objekte werden mit dem Index k numeriert, hier also mit 0 und 1). Das betrifft alle Konturpunkte, die aus Sicht des Initiator-Objektes (k = 1) hinter einer gedachten Linie, die einerseits durch den Mittelpunkt (oder besser Schwerpunkt) des Opponent-Objektes (k= 0) und andererseits rechtwinklig zur Verbindungslinie zwischen den Mittelpunkten beider Objekte verläuft, liegen.
Im folgenden wird nur eine Kollisionssituation, nämlich die nach , betrachtet.

Um zu prüfen, ob eine beliebiger Konturpunkt P_k,i vor oder hinter der gedachten Linie liegt, genügt es, die Länge d_k,i ins Verhältnis zum Mittelpunktsabstand D_k zu setzen. Die Länge d_k,i wiederum ist dem vektoriellen Skalarprodukt aus Quasi-Ortsvektor ${\vec{Q}}_{k,i}$ und dem Distanzvektor ${\vec{D}}_{k}$ proportional:

()

$| {\vec{d}}_{k, i} | = \frac{{\vec{D}}_{k} \cdot {\vec{Q}}_{k, i}}{| {\vec{D}}_{k} |}$

Quasi-Ortsvektor, weil dieser Vektor vom Schwerpunkt des Initiator-Objektes ausgeht und nicht wie üblich vom Ursprung des Koordinatensystems!

Im folgenden werde ich mich nur auf die in gezeigten Objekte und Wirkrichtung beschränken. Das heißt, es wird geprüft, ob der i-te Punkt des 0-ten Objektes (Opponent) im Kollisionsbereich des 1-ten Objektes (Initiator) liegt.

Mit den Vektoren:

(a)

$\vec{D} = {\vec{X}}_{0} - {\vec{X}}_{1}$

und

(b)

$\vec{Q} = \vec{P} - {\vec{X}}_{1}$

den Abkürzungen:

(a)

$D_{y} = X_{0} . y - X_{1} . y$

und

(b)

$D_{x} = X_{0} . x - X_{1} . x$

sowie

(c)

$Q_{y} = P . y - X_{1} . y$

und

(d)

$Q_{x} = P . x - X_{1} . x$

ergeben sich die Vektoren zu

(a)

$\vec{D} = (\begin{matrix} D_{x} \\ D_{y} \end{matrix})$

und

(b)

$\vec{Q} = (\begin{matrix} Q_{x} \\ Q_{y} \end{matrix})$

Abb. Auswahl der nächstliegenden Konturpunkte

Jetzt können wir das Skalarprodukt - ohne die p5.Vector()-Funktion zu verwenden - berechnen

()

$| \vec{d} | = \frac{1}{| \vec{D} |} \cdot {(\begin{matrix} D_{x} \\ D_{y} \end{matrix})}^{T} \cdot (\begin{matrix} Q_{x} \\ Q_{y} \end{matrix})$

denn so erhalten wir ein Ergebnis, das mit einer sehr viel geringeren Anzahl von Rechenoperationen auskommt!
Mit dem Betrag

()

$| \vec{D} | = \sqrt{{D_{x}}^{2} + {D_{y}}^{2}}$

ergibt sich der auf den Teststrahl projezierte Abstand zu:

()

$d = \frac{D_{x} \cdot Q_{x} + D_{y} \cdot Q_{y}}{\sqrt{({D_{x}}^{2} + {D_{y}}^{2})}}$

Also, alle Konturpunkte i, die die Bedingung d > D erfüllen, liegen außerhalb des Kollisionbereiches (grauer Bereich in ). Ausgedrückt durch unsere Hilfsgrößen Dx und Dy bedeutet das

()

$d_{i} > \sqrt{{D_{x}}^{2} + {D_{y}}^{2}}$

Mit dem Ergebnis von lautet die Bedingung für den Ausschluß aus der Kollisionsermittlung:

()

$D_{x} \cdot Q_{x} + D_{y} \cdot Q_{y} > {D_{x}}^{2} + {D_{y}}^{2}$

Nun zur Kollisionserkennung. Die Kollisionserkennung zwischen Polygonen hat mehrere Anforderungen zu erfüllen:

Im Gegensatz zur Kollision zwischen Polygon und Kreis (bzw. Kugel), wie sie im Abschnitt Kreis trifft auf Polygon beschrieben wird, gibt es beim Aufeinandertreffen von Polygonen ein Problem. Während im ersten Fall eine Prüfung, ob der Betrag des Distanzvektors im i-ten Segment $| {\vec{D}}_{i} |$ kleiner als der Kreisradius ist, genügt, funktioniert dies hier nicht. Warum? Weil die Konturelemente, die kollidieren können, Punkte sind. Deren Radius ist aber gleich 0! Das führt in Hinblick auf die Unschärfen, bedingt durch die zeitliche Quantisierung, dazu, dass kaum ein Treffer registriert werden wird. Wir suchen also nach einem Verfahren, dass auch für Punkte, die Linien treffen oder diese unterschreiten, geeignet ist.
Der Regelfall wird sein, dass die Ecke des einen Polygons auf eine Verbindungslinie des anderen Polynoms trifft. Was aber, wenn die kollidierenden Linien auf beiden Seiten parallel verlaufen? Dann treffen zwei Konturpunkte auf eine Linie!

zeigt eine Situation, in der ein Konturpunkt (blau) des einen Objekts (Initiator: k = 1) auf ein Segment (rot) eines anderen Objektes (Opponent: k = 0) zu treffen scheint. Es soll nun geprüft werden, ob der blaue Konturpunkt das rote Segment berührt oder ggf. darüber hinaus geht.

Eine wichtige Rolle bei der Ermittlung des Kollisionsortes spielen die Schwerpunkte X₀ (Opponent) und X₁ (Initiator). Da Schwerpunkte als invariant gegenüber rotatorischen Bewegungen sind, kann jedes beliebig geformte Objekt durch eine Punktmasse genau im Schwerpunkt repräsentiert werden. Das bedeutet für translatorische Bewegungen, dass möglich Kollisionen längs eines Teststrahls, der vom Schwerpunkt X₁ des Initiators ausgeht und durch den betreffenden Konturpunkt (P_1,j) verläuft, auftreten können.
Auf Seiten des Opponenten schneidet der Teststrahl ein Kontursegment, begrenzt durch die Konturpunkte P_0,i und P_0,i+1. Herauszufinden, wo sich diese beiden Geraden schneiden, ist eine Standardaufgabe der Geometrie.

Zunächst werden beide Geraden als Vektoren behandelt. Zunächst die Gerade g₀, die parallel zum Segmentvektor S_0,i verläuft:

(a)

{\vec{g}}_{0} = {\vec{P}}_{0, i} + λ \cdot \vec{S}

worin

(b)

\vec{S} = {\vec{P}}_{0, i + 1} - {\vec{P}}_{0, i} = (\begin{matrix} S_{x} \\ S_{y} \end{matrix})

den Segmentvektor darstellt.

Und eine weitere Gerade g₁ repräsentiert den Teststrahl, der parallel zum Radialvektor R_1,j verläuft:

(a)

{\vec{g}}_{1} = {\vec{X}}_{1} + μ \cdot \vec{R}

worin

(b)

\vec{R} = {\vec{P}}_{1, j} - {\vec{X}}_{1} = (\begin{matrix} R_{x} \\ R_{y} \end{matrix})

den Radialvektor darstellt.
Die Parameter der Geradengleichungen λ und μ erlauben, jeden beliebigen Punkt auf diesen Geraden zu erreichen.

Abb. Bestimmung des Kollisionsortes

Um den Schnittpunkt beider Geraden zu bestimmen, werden die und einander gleich gesetzt. Die Gleichheit muss sowohl für die x- als auch für die y-Komponenten gelten. So erhalten wir nach Umsortieren ein Gleichungssystem bestehend aus zwei Gleichungen (2D!) für die Unbekannten λ und μ:

(a)

({\vec{P}}_{0, i} - {\vec{X}}_{1}) . x = μ \cdot \vec{R} . x - λ \cdot \vec{S} . x

und

(b)

({\vec{P}}_{0, i} - {\vec{X}}_{1}) . y = μ \cdot \vec{R} . y - λ \cdot \vec{S} . y

Noch eine weitere Abkürzung für die Differenz des Vektors auf der linken Seite der a) bzw. b) ist sinnvoll:

()

\vec{Q} = {\vec{P}}_{0, i} - {\vec{X}}_{1} = (\begin{matrix} Q_{x} \\ Q_{y} \end{matrix})

Dieser Vektor stellt im Prinzip den Quasi-Ortsvektor dar (wie schon erwähnt liegt dessen Ursprung im Schwerpunkt des Initiator-Objektes und nicht wie gewöhlich im Koordinatenursprung!)

Jetzt können wir das Gleichungssystem lösen. Das liefert für

(a)

μ = \frac{S_{x} \cdot Q_{y} - Q_{x} \cdot S_{y}}{S_{x} \cdot R_{y} - R_{x} \cdot S_{y}}

und für

(b)

λ = \frac{R_{x} \cdot Q_{y} - Q_{x} \cdot R_{y}}{S_{x} \cdot R_{y} - R_{x} \cdot S_{y}}

Mit den so bestimmten Werten für λ und μ kann nun der Schnittpunkt der beiden Geraden durch Einsetzen in eine der beiden a) oder a) ermittelt werden. Liegt dieser Schnittpunkt aber wirklich auf dem ausgewählten Segment des Opponent-Objekts? Darüber gibt der Wert von λ Auskunft. λ muss die Bedingung

0 \leq λ \leq 1

erfüllen. Und wenn μ noch diese Bedingung

0 \leq μ \leq 1

erfüllt, dann berühren oder überdecken sich Initiator- und Opponenten-Objekt, d.h. eine Kollision liegt vor!

Zusammenfassung
Nach dem Einlesen und Entpacken der Konturdaten werden die oben aufgeführten Schritte, die der Aufwandsminimierung dienen, der Reihe nach ausgeführt.

Schon in der setup()-Funktion werden die maximalen Abmessungen R_ext der einzelnen Objekte bestimmt. Damit und mit dem Abstand von Schwerpunkt zu Schwerpunkt wird in der draw()-Funktion geprüft, ob eine Kollision überhaupt möglich ist.
Im nächsten Schritt werden die Konturpunkte bestimmt, die dem gegenüber liegenden Objekt zugewandt sind. Dies geschieht wechselseitig und das Resultat wird im Array closestPoints für jedes Objekt gespeichert.
Erst im letzten Schritt erfolgt die Prüfung auf Kollisionen. Mit den beiden vorgeschalteten Schritten wurde die Anzahl der Prüfungen auf Kollision auf das notwendige Maß reduziert.

Da jeder Konturpunkt jedes Objektes die Rolle des Initiators, sowie auch die des Opponenten, einnehmen kann, müssen die Kollisionserkennungen mit allen vorgeschalteten Schritten wechselseitig für jedes Objekt ausgeführt werden! Also, jedes Objekt ist gleichzeitig sowohl Initiator als auch Opponent! Weil nun jedes Objekt durch mehrere Konturpunkte charakterisiert ist, müssen wechselseitig alle infrage kommenden Konturpunkte des einen Objektes auf Kollisionen mit dem (oder den) anderen Objekt(en) geprüft werden.

Im Beispielprogramm sehen wir die beiden Objekte Tschuri und Philae. Da es in diesem Beispiel nur um die Funktionalität der Kollisionserkennung geht, werden hier Objektbewegungen nur durch Mausinteraktionen simuliert. Wird die Maus auf einen der roten Punkte (Schwerpunkt) gesetzt, werden translatorische Bewegungen per Maus möglich. Fasst die Maus den gelben Punkt, können Drehbewegungen ausgeführt werden.
Betätigung des Buttons Debug zeigt die Konturen und die Aktionsradien der Objekte an. Überdecken sich diese Radien, d.h. Kollisionen sind möglich, werden die aktiven Konturpunkte und die durch sie hindurch laufenden Teststrahlen angezeigt. Der Button Item erlaubt die Auswahl, von welchem Objekt diese Informationen herrühren.

Symbol	Bedeutung
P_i bzw. ${\vec{P}}_{i}$	Punkte bzw. deren Ortsvektoren [m]
dist_i bzw. d_i	Abstandsbeträge zwischen den Punkten [m]
r_Obj	Radius des i-ten approximierenden Kreises [m]
$\vec{O}$	Ortsvektor [m]
$\vec{Q}$	Quasi-Ortsvektor [m]
$\vec{S}$	Segmentvektor
$\vec{R}$	Radialvektor
$\vec{D}$	Distanzvektor [m]
${\vec{P a r t}}_{i}$	Partvektor [m]
l	Längen [m]
β_i	Normalenwinkel auf dem i-ten Segment [°] oder [rad]
${\vec{X}}_{k}$	Schwerpunktvektor des k-ten Objekts
${\vec{X}}_{0}$	Schwerpunktvektor des gegenüber liegenden Objekts (k = 0)
${\vec{X}}_{1}$	Schwerpunktvektor des Kollision auslösenden Objekts (k = 1)
${\vec{g}}_{0,i}$	Gerade vom i-ten Punkt längs des i-ten Segmentvektors des 0-ten Objektes
${\vec{g}}_{1,j}$	Gerade vom Schwerpunkt durch den j-ten Punkt des 1-ten Objektes