6. Kapitel

Verfahren zur Erkennung von Kollisionen

Bitte einen Augenblick Geduld
während das Programm geladen wird!

Alle Themen in diesem Kapitel:

Die Kollisionserkennung ist ein Teil, wenn auch ein sehr wesentlicher, einer Reihe von Schritten von einem als Bitmap vorliegenden fotorealistischen Objekt bis hin zu einer digitalen Repräsentation dieses Objektes:

Konturerfassung (2D) bzw. Hüllenerfassung (3D). Dies kann automatisch oder händisch erfolgen.
Aufbereitung der Kontur- oder Hülleninformation für eine Kollisionserkennung. Ergebnis dieses Schrittes ist eine einfachere geometrische Figur, die mathematisch und rechentechnisch optimal für eine Kollisionserkennung verwendet werden kann. Dabei ist es wichtig, dass diese Ersatzfigur unabhängig von Translation oder Rotation des Objektes unveränderlich sein muss. Hier seien die Bounding Volume-Verfahren genannt. Einige Polygon-basierte Verfahren kommen ohne diesen Schritt aus und ermöglichen die Kollisionserkennung direkt an den als Polygon vorliegenden Konturen.
Schließlich werden geeignete Kollisionserkennungsverfahren angewendet, die anhand der vereinfachten Kontur- bzw. Hülleninformationen eine Kollision erkennen können.
Im Ergebnis einer erkannten Kollision müssen die physikalisch begründeten Bewegungsparamter für die kollidierten Objekte nach der Kollision bereit gestellt werden. Dies leistet die Stoßbehandlung.
Generell ist es notwendig, parallel zur mathematischen Kollisionsbehandlung, die auf den digitalisierten Kontur- oder Hülleninformationen beruht, eine fotorealistischen, deckungsgleiche Darstellung (z.B. mittels der Matrix-Operationen) auszuführen.

Alle im folgenden beschriebenen Verfahren oder Schritte zur Kollisionserkennung und -behandlung setzen voraus, dass die kollidierenden Objekte digitalisiert vorliegen. Entweder werden die Objekte durch einfache geometrische Formen wie z.B. Kreise, deren Mittelpunktkoordinaten und Radien bekannt sind, ersetzt oder sie werden durch Punktwolken bzw. Polygone beschrieben und als kollidierende "Ersatz"-Objekte verwendet. Das hindert nicht, diese Ersatzobjekte mit ihren fotorealistischen Vorbildern zu überdecken, so dass im Ergebnis der Eindruck erweckt wird, als fände die Kollision an den fotorealistischen Objekten statt. Um bequem und passend zu den hier gezeigten Anwendungsbeispielen fotorealistisch vorliegende Objekte zu digitalisieren, stelle ich ein Programm zur Digitalisierung solcher Objekte zur Verfügung.
Oft sind die digitalisiert vorliegenden Punktwolken für eine direkte Verwendung zu komplex oder ihre Berechnung erfordert einen zu hohen Rechenaufwand, so dass nach vereinfachten Hüllen für die betreffenden Objekte gesucht wird. Sowohl diese Methoden als auch die direkte Verwendung der als Polygon-Repräsentationen vorliegenden Objekte in Kollisionssituationen wollen wir untersuchen.

Die Kollisionserkennung selbst hat zwei wichtige Aufgaben zu erfüllen:

Feststellen des Ortes und des Zeitpunktes der Kollision. Mit dieser Aufgabe verbunden ist insbesondere die Korrektur der Ortsfehler, die durch die Zeitquantisierung hervorgerufen werden.
Bereitstellung der Bewegungsparameter (Geschwindigkeitskomponenten), die für die Bewegungen nach der Kollision erforderlich sind.

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:

()

Dabei ist klar, dass der Abstand der Mittelpunkte beider Kugeln nicht kleiner als die Summe beider Radien r₁ + r₂ werden kann. So lautet die Kollisionsbedingung also:

()

d i s t \leq r_{1} + r_{2}

Abb. kollidierende Kugeln

Nach dem Satz des PYTHAGORAS lautet die geometrische Interpretation von

()

{(x_{1} - x_{2})}^{2} + {(y_{1} - y_{2})}^{2} \leq {(r_{1} + r_{2})}^{2}

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 einem Quader, umhüllt. Für dieses Verfahren gibt es Algorithmen, die die optimalen Abmessungen des ersetzenden Objektes, und im Falle der Approximation durch einen Quader, auch dessen optimale Orientierung 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.

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

Bounding volume Verfahren

Axis alligned bounding box - AABB

Eine Kollisionserkennung an Kugel förmigen Objekten ist vergleichsweise einfach, wie bzw. zeigen. Aber, die Approximationsqualität ist eingeschränkt, weil längliche Körper nur mit größeren Fehlern behandelt werden können. Deshalb ist eine Approximation durch einen Quader (Box) besser ().

Eine Axis Aligned Bounding Box (AABB) ist ein spezieller Hüllkörper für ein 2D- bzw. 3D-Objekt in der Form eines achsenparallelen Rechtecks (2D) bzw. Quaders (3D). Das Objekt berührt alle 4 bzw. 6 Seiten der AABB. Für jedes kompakte Objekt gibt es jeweils genau eine AABB. Dieses ist das kleinstmögliche Objekt einschließende achsenparallele Rechteck bzw. der kleinstmögliche achsenparallele Quader. Eine Axis Aligned Bounding Box kann per Definition nicht gedreht werden!
Daher können für einfache geometrische Objekte wie Kreise (Kugeln) oder Ellipsen (Ellipsoide) und polygonal approximierte Objekte die Abmessungen der AABB sehr einfach über eine Minimum- und Maximumsuche über die Koordinaten aller Eckpunkte des Objektes ermittelt werden.
Auch die Kollisionserkennung ist recht einfach. Eine Kollision zweier oder mehrerer Objekte liegt vor, wenn es Überlappungen oder Berührungen von linken und rechten bzw. oberen und unteren Rändern verschiedener Objekte gibt. Dies ist sehr einfach zu verifizieren! Allerdings gibt es auch gravierende Nachteile: dieses Verfahren ist nur bedingt auf rotierende Körper anwendbar und die Hülle ist nur eine sehr grobe Approximation des Körpers! Sollten dennoch rotierende Körper behandelt werden, sind zu jedem Frame die Abmaße der AABB neu zu berechnen.

Abb. 2D_Approximation mittels eines Rechtecks

Oriented bounding box - OBB

Eine geeignetere Hülle lässt sich ermitteln, wenn auf die Achsen-Parallelität der Boxen verzichtet wird. Dann würden schräg orientierte Boxen bessere Annäherungen der Hüllen an des Objekt erlauben. Auch rotierende Objekte wären einfacher zu behandeln, da sich die Hülle mit dem Objekt drehen kann und nicht bei jedem Frame neu berechnet werden muss. In der Literatur ist dieses Verfahren unter der Bezeichnung Oriented Bounding Box - OBB bekannt oder detailierter Verwendung von geometrischen Hüllkörpern in einem Präprozessor Framework für numerische Simulationen.

Berechnung der Maße und Orientierung der OBB

Bevor die Hülle eines Objektes bestimmt werden kann, muss die Orientierung der Hülle, also des Quaders oder des Rechtecks bekannt sein. Zur Lösung dieser Aufgabe bedienen wir uns eines Verfahrens aus der Statistik - nämlich der Hauptkompunentenanalyse. Dort soll eine Punktwolke, z.B. von mehrdimensionalen Messwerten, auf eine konzentrierte Darstellung überführt werden. Auf unser Problem angewandt heißt das, die Punktwolke bestehend aus den Polygon-Koordinaten durch zwei (2D) bzw. drei (3D) orthogonale Geraden zu beschreiben. Diese sog. Hauptachsen beinhalten indirekt Informationen über Ausdehnung und Ausrichtung der Punktwolke. Können also zur Grundlage für die Dimensionierung und Ausrichtung der Bounding Box dienen.

Zunächst setzen wir voraus, dass das Objekt digitalisiert vorliegt und durch ein Set von N charakteristischen Punkten beschrieben ist (). Diese charakteristischen Punkte dienen zunächst der Berechnung der geometrischen Mitte dieser Punktwolke. Also werden im ersten Schritt die arithmetischen Mittel der x- bzw. y-Koordinaten dieser Punkte gebildet (a) und b)):

(a)

\bar{x} = \frac{1}{N} \cdot \sum_{n = 1}^{N} x_{n}

(b)

\bar{y} = \frac{1}{N} \cdot \sum_{n = 1}^{N} y_{n}

(In der Welt der Statistik werden diese Werte Erwartungswerte genannt). Die geometrische Mitte dient im Weiteren der Positionierung des Objektes, zunächst aber zur Bestimmung der Kovarianzmatrix C. In der 2D-Welt handelt es sich hier um eine quadratische, 2-dimensonale Matrix, in 3D um eine quadratische, 3-dimensonale Matrix. Im folgenden betrachten wir nur den 2D-Fall, der unproblematisch auf den 3D-Fall erweitert werden kann.

Im zweiten Schritt ist die Berechnung der Varianzen var(x) und var(y) (a) und b))

(a)

v a r (x) = \frac{1}{N-1} \cdot \sum_{n = 1}^{N} {(x_{n} - \bar{x})}^{2}

(b)

v a r (y) = \frac{1}{N-1} \cdot \sum_{n = 1}^{N} {(y_{n} - \bar{y})}^{2}

Abb. chakteristische Punkte eine 2D-Objektes (N = 7)

sowie der Kovarianzen cov(x, y) () erforderlich. Da die Kovarianzen cov(x, y) und cov(y, x) einander gleich sind, handelt es sich bei allen Kovarianzmatrizen um symmetrische Matrizen.

()

c o v (x, y) = \frac{1}{N-1} \cdot \sum_{n = 1}^{N} (x_{n} - \bar{x}) \cdot (y_{n} - \bar{y})

So lautet die Kovarianzmatrix C ():

()

C = (\begin{matrix} v a r (x) c o v (x, y) \\ c o v (x, y) v a r (y) \end{matrix})

Die Kovarianzmatrix ist vorteilhafter Weise eine symmetrische Matrix, deren Eigenwerte λ stets reell und positiv sind. Interpretiert man das Ergebnis der Eigenwertberechnung als implizite Ellipsengleichung, bilden die Eigenwerte die Hauptachsen dieser Ellipse. Eine 2D_Matrix hat dem zufolge zwei Hauptachsen für die je ein Eigenwert existiert. Im 2D-Fall wenden wir den Wurzelsatz von VIETA an, der je eine Lösung für die Eigenwerte λ_i liefert:

Wie werden Eigenwerte ermittelt? Betrachten wir den 2D-Fall.
Gibt es einen Vektor E, der mit einer gegebenen Matrix C multipliziert, bis auf einen konstanten Faktor sich selbst ergibt?

C \cdot E = λ \cdot I \cdot E

Worin I die Einheitsmatrix ist.
Existiert ein solcher Vektor, heißt er Eigenvektor von C. Und der Faktor λ wird Eigenwert zu C genannt.

Zur Lösung dieser Aufgabe wird die Bestimmungsgleichung umgestellt:

(C - λ \cdot I) \cdot E = 0

Wenn der Vektor E von Null verschieden ist (nichttriviale Lösung), muss

C - λ \cdot I = 0

sein. Diese Matrix verschwindet, wenn auch ihre Determinante verschwindet:

| \begin{matrix} v a r (x) - λ & c o v (x, y) \\ c o v (x, y) & v a r (y) - λ \end{matrix} | = 0

Also

(v a r (x) - λ) \cdot (v a r (y) - λ) - {(c o v (x, y))}^{2} = 0

Nach dem Auflösen der Determinante entsteht ein Polynom in λ, das charakteristische Polynom, dessen Grad mit dem Rang der Matrix übereinstimmt:

λ^{2} - (v a r (x) + v a r (y)) \cdot λ + v a r (x) \cdot v a r (y) - {(c o v (x, y))}^{2} = 0

Die Nullstellen des charakteristischen Polynoms sind die gesuchten Eigenwerte der Matrix C.

()

λ_{1,2} = \frac{1}{2} \cdot (v a r (x) + v a r (y)) \pm \sqrt{\frac{{(v a r (x) + v a r (y))}^{2}}{4} - v a r (x) \cdot v a r (y) + {(c o v (x, y))}^{2}}

Aus geht hervor, dass der Eigenwert λ₁ stets größer ist als der Eigenwert λ₂.

Setzen wir die Eigenwerte in die Bestimmungsgleichung ein, erhalten wir

()

(\begin{matrix} v a r (x) - λ_{i} & c o v (x, y) \\ c o v (x, y) & v a r (y) - λ_{i} \end{matrix}) \cdot (\begin{matrix} e_{x, i} \\ e_{y, i} \end{matrix}) = (\begin{matrix} 0 \\ 0 \end{matrix}) i = 1,2

Da alle Werte der rechten Seite des Gleichungssystems verschwinden (homogenes Gleichungssystem), ist das Gleichungssystem überbestimmt. Zur Lösung darf daher eine Gleichung gestrichen und je ein Wert e_x,i oder auch e_y,i für i = 1 bzw. i = 2 frei gewählt werden. Dann ist dieses Gleichungssystem lösbar und liefert die gesuchten Eigenvektoren E_i zu den Eigenwerten λ_i.

Nun sind zwei Fälle zu unterscheiden:

cov(x,y) ≠ 0:
Wählen wir aus Zweckmäßigkeitsgründen zum Beispiel e_x,1 = e_y,2 = 1 und ermitteln dann e_y,1 bzw. e_x,2. Dazu streichen wir die 2. bzw. 1. Bestimmungsgleichung:

(a)

$e_{y, 1} = - \frac{(v a r (x) - λ_{1})}{c o v (x, y)} \cdot e_{x, 1} e_{x, 1} = 1$

(b)

$e_{x, 2} = - \frac{(v a r (y) - λ_{2})}{c o v (x, y)} \cdot e_{y, 2} e_{y, 2} = 1$

Diese Wahl ist deshalb zweckmäßig, weil so die Matrix der Eigenvektoren als Rotationsmatrix für die Parallelisierung des Objektes (also die optimale Ausrichtung parallel zur x-Achse) ohne größere Vorzeichen bedingte Testaufwendungen erfolgen kann. Da im nächsten Schritt die Eigenvektoren ohnehin auf ihre Beträge normiert werden, ist der absolute Wert für die e_x,i bzw. e_y,i unerheblich.
cov(x,y) = 0:
Dann würde in a) bzw. b) eine Division durch 0 erfolgen. D.h. es kann kein brauchbares Ergebnis berechnet werden. Schauen wir uns aber einen solchen Fall an, dann stellen wir fest, dass ein solches Objekt bereits in parallel zu den x- bzw. y-Achsen ausgerichtet ist. Sich also die Bestimmung einer OBB erübrigt.

Übrigens haben die Eigenvektoren dank ihrer Herkunft aus einer symmetrischen Matrix eine bemerkenswerte Eigenschaft: sie stehen senkrecht aufeinander. Das trifft sowohl auf die Eigenvektoren im 2D- als auch im 3D-Raum zu!

Zunächst sind die Eigenvektoren E auf ihre Beträge zu normieren:

()

{\tilde{E}}_{i} = \frac{E_{i}}{| E_{i} |} i = 1,2

Geordnet nach der Größe der normierten Eigenwerte, ergibt sich die Eigenvektor-Matrix:

()

\tilde{E} = (\begin{matrix} {\tilde{e}}_{x, 1} & {\tilde{e}}_{x, 2} \\ {\tilde{e}}_{y, 1} & {\tilde{e}}_{y, 2} \end{matrix})

Was haben wir jetzt gewonnen? Mit den Eigenvektoren liegen die Richtungsinformationen der Haupt- und der Nebenkomponente (2D) vor. Damit ist die Orientierung der oriented bounding Box vorgegeben. Nun müssen im nächsten Schritt die Maße der passenden Box bestimmt werden. Hier wird in der Literatur das Verfahren Rotating Calipers (rotierende Schiebelehre) angeboten. Dies ist jedoch recht aufwändig. Der Lösungsweg, den ich vorschlage, geht den umgekehrten Weg: nicht die Schiebelehre wird gedreht, sondern das Objekt, dessen Hülle bestimmt werden soll.

Darum ist die Parallelisierung des Objektes mit Hilfe der Richtungsinformation, die in den Eigenvektoren vorliegen, zu einer axis aligned bounding box (AABB) einfacher. Die Maße der Box erhalten wir auf einfache Weise durch mini-max-Vergleiche.

Nun könnte eingewendet werden, dass die optimalen Abmaße der umhüllenden Box auch aus der Eigenvektor-Matrix und den Faktorladungen gewonnen werden können. Das trifft zu, geht aber an unserer Zielstellung vorbei. Die so gewonnene Box wäre nämlich auf den geometrischen Mittelpunkt des Objektes bezogen. Das bedeutet aber, dass diese Box die ggf. im Objekt enthaltene Asymmetrie nicht mehr repräsentiert. In einem solchen Fall wäre das Flächenträgheitsmoment stets minimal. Unter diesen Voraussetzungen wären rotatorische Bewegungen, z.B. in Folge eines asymmetrischen Stoßes, fehlerhaft!

So geht es dann weiter: Wir finden die parallelisierten Punkte des Objektes durch linksseitige Multiplikation der transponierten Eigenvektor-Matrix mit den auf die geometrische Mitte bezogenen Konturpunkte:

()

{(\begin{matrix} P_{x} \\ P_{y} \end{matrix})}_{rot} = {(\begin{matrix} {\tilde{e}}_{x, 1} & {\tilde{e}}_{x, 2} \\ {\tilde{e}}_{y, 1} & {\tilde{e}}_{y, 2} \end{matrix})}^{T} \cdot (\begin{matrix} P_{x} - \bar{x} \\ P_{y} - \bar{y} \end{matrix})

Jetzt können entlang der x- bzw. y-Achse die Extrempunkte der Kontur durch den erwähnten mini-max Vergleich gefunden werden. Anschließend wird die so dimensionierte Box mit Hilfe einer Rotations-Matrix um den Winkel ψ () gedreht und zurück in die geometrische Mitte des Objektes verschoben. So umhüllt die OBB das Objekt.

()

ψ = - \arctan (\frac{e_{y, 1}}{e_{x, 1}})

Alternativ wäre auch die Anwendung einer Rotationsmatrix, deren Drehwinkel dem negativen Orientierungswinkel ψ der Hauptachse (2D) entspricht. Neben der einfachen Handhabung hat diese Lösung noch den Vorteil des geringeren Rechenaufwandes, da die Berechnung eines Eigenvektors, nämlich des Eigenvektors mit dem kleinsten Eigenwert, und die Normierung aller Eigenvektoren auf ihre Beträge entfallen kann.
Der 3D-Fall ist analog zu behandeln. Statt einer quadratischen, charakteristischen Gleichung ist dann eine 3. Grades zu lösen. Und die Rotationsmatrix hat dann den Rang = 3. Weil die Eigenvektoren senkrecht zu einander angeordnet sind, würden bei der alternativen Lösungsmethode zwei Winkel erforderlich sein: der der Hauptachse und ein weiterer, nämlich der Winkel der Achse, deren Eigenvektor dem nächst kleineren Eigenwert entspricht.

Das nebenstehende Beispielprogramm simuliert ein Objekt, dessen Orientierung (z.B. durch eine Rotation verursacht) beliebig ist. Hier wird dies per Scrollbar im Bereich von -90° bis +90° eingestellt. Hinzu kommt eine Auswahl unterschiedlicher Konturen, die mit dem Button Profil ausgewählt werden können. Der Button Debug erlaubt die grafische Darstellung von Zwischenschritten der Berechnung. Zum einen werden die normierten Eigenvektoren der Hauptachse (blau) und der Nebenachse (rot) sowie die parallelisierte Kontur des Objektes (grün) dargestell. Zur besseren Sichtbarkeit werden die Längen der Achsenvektoren durch ihre Faktorladungen bestimmt.
Ebenfalls dargestellt werden die numerischen Resultate verschiedener Zwischenschritte, unter anderem die Eigenwerte

λ_{1,} λ_{2}

und die dazugehörigen normierten Eigenvektoren

{\tilde{e}}_{x, 1}, {\tilde{e}}_{x, 2}

.

Das Beispielprogramm verfügt über die prinzipielle Möglichkeit (im Code durch die Wahl der Variablen nStart und N), nur ausgewählte Abschnitte der Kontur in eine OBB umzurechnen. Das erleichtert den Aufbau eines (OBB-Trees).

Zusammenfassung: Das Beispielprogramm nimmt keine Rücksicht auf die Rechenzeit-Ökonomie. So werden beispielsweise die Kovarianzmatrix, die Eigenwerte und -vektoren, die Maße der bounding Box bei jeder Programm-Schleife neu berechnet. Hier dient diese Ausführlichkeit der Veranschaulichung der Berechnung. Ist die Orientierung der bounding Box einmal gefunden, bleibt sie relativ zum Objekt immer erhalten. Eine stete Wiederholung der Berechnungen ist nicht erforderlich! In der praktischen Anwendung wird das daher für jedes Objekt nur einmal gemacht. Bounding box und Objekt werden von da an gemeinsam bewegt oder gedreht.
Zur Demonstration der Wirkungsweise des Algorithmus werden im Beispielprogramm einfache geometrische Figuren (Dreieck, Rechteck) zur Auswahl angeboten.

Bei der Berechnung der Eigenvektoren ist insbesondere für die Wahl der "freien" Variablen Sorgfalt zu beachten. Es gibt Anfangswerte, unglücklicher Weise in Abhängigkeit von den das Objekt beschreibenden Datensätzen, die zu Spiegelungen statt zu Drehungen bei der Parallelisierung führen. Um diese Vielfalt zu reduzieren, habe ich als die unabhängigen Größe des kleineren Eigenvektors nach b) gewählt. Ein weiterer Effekt ist im Debbuging Modus zu beobachten, wenn das Objekt per scrollbar sehr stark gedreht wird. Dann wird die Kontur des parallelisierten Objektes an der x-Achse gespiegelt. Für die Bestimmung der Abmaße der bounding Box bleibt das ohne Folgen. In der praktischen Anwendung werden die Maße der Box ohnehin nur einmalig berechnet, egal wie das Objekt im Original orientiert ist.

Kollisionserkennung

Eigentlich ist die Erkennung von Kollisionen bei solch einfachen Objekten, wie das Rechtecke oder Quader sind, recht trivial. Die Crux besteht darin, dass wenn Eckpunkt für Eckpunkt abgetestet werden müssen, der Aufwand potentiell steigt. So z.B. sind allein bei zwei Rechtecken 4 x 4 = 4² Abstandsmessungen vorzunehmen. Bei drei Objekten müssen schon 4³ Tests ausgeführt werden. D.h. die Herausforderung besteht darin, ein ökonomisches Verfahren für die Kollisionsbestimmung zu finden.

Ein solches Verfahren wird in OBB-OBB-Kollisionstest vorgestellt und auch mit einer Erläuterung des Codes unterlegt. Mir scheint dieses Verfahren sehr aufwändig, deshalb schlage ich ein deutlich einfacheres Verfahren vor.

Dieses Verfahren beruht auf der Anwendung der vektoriellen Parameter-Darstellung einer Fläche im 3D-Raum. Existieren zwei Vektoren (hier

{\vec{s V}}_{1}

und

{\vec{s V}}_{2}

genannt), die nicht parallel zueinander verlaufen, so spannen sie eine ebene Fläche auf (). Werden diese Vektoren als Segmentvektoren aus drei benachbarten Punkten (i = 1, 2 und 3) der k-ten OBB bezogen, dann beschreiben sie genau die Fläche der OBB. Nun gilt es zu prüfen, ob ein (oder auch mehrere) Eckpunkt der l-ten OBB auf dem Rand oder innerhalb der k-ten OBB liegt. Ist dies der Fall, liegt eine Kollision vor! Dieser Test ist für alle Eckpunkte der l-ten OBB durchzuführen.
Solche Tests gehören zum Standard-Werkzeug der Vektor-Geometrie. In einem ersten Schritt werden die zwei benötigten Segmentvektoren der k-ten OBB bestimmt:

(a)

{\vec{s V}}_{1} = {\vec{P}}_{k, 2} - {\vec{P}}_{k, 1}

(b)

{\vec{s V}}_{2} = {\vec{P}}_{k, 3} - {\vec{P}}_{k, 1}

Dabei ist es egal, welcher Eckpunkt zum Ausgangspunkt der Berechnung der Segmentvektoren bestimmt wird. Aus Gründen der Bequemlichkeit habe ich die Eckpunkte der OBB's in Arrays nicht in vier sondern in sechs Zellen gespeichert. Der jeweils erste und der letzte Punkt eines OBB wiederholen sich; das erleichtert die Arbeit mit den for()-Schleifen z.B. bei der Erstellung der Segmentvektoren.
Der Vektor

\vec{X}

stellt die parametrische Beschreibung der Fläche der k-ten OBB dar:

()

\vec{X} = {\vec{P}}_{k, 1} + λ \cdot {\vec{s V}}_{1} + μ \cdot {\vec{s V}}_{2}

Abb. Kollisionserkennung im 2D-Fall

Mit den beiden Parametern λ und μ ist jeder Punkt der Ebene erreichbar. Sind aber 0 ≤ λ ≤ 1 bzw. 0 ≤ μ ≤ 1 befindet sich der Punkt

\vec{X}

genau in der Fläche der OBB oder auf einem ihrer Ränder!
Damit ist klar, wie es weiter geht. Wird nämlich der Vektor

\vec{X}

mit einem der Eckpunkte der l-ten OBB geladen, kann geprüft werden, ob dieser Punkt in oder auf der Fläche der k-ten OBB liegt, indem die Werte von λ bzw. μ den oben genannten Bedingungen genügen.

()

(\begin{matrix} x_{l, i} \\ y_{l, i} \\ z_{l, i} \end{matrix}) = (\begin{matrix} x_{k, 1} \\ y_{k, 1} \\ z_{k, 1} \end{matrix}) + λ \cdot (\begin{matrix} s V_{x, 1} \\ s V_{y, 1} \\ s V_{z, 1} \end{matrix}) + μ \cdot (\begin{matrix} s V_{x, 2} \\ s V_{y, 2} \\ s V_{z, 2} \end{matrix})

Das führt in einer 3D-Anwendung auf ein Gleichungssystem bestehend aus drei Gleichungen mit zwei Unbekannten. D.h. eine Gleichung kann zunächst gestrichen werden:

()

\begin{matrix} λ \cdot s V_{x, 1} + μ \cdot s V_{x, 2} = x_{l, i} - x_{k, 1} \\ λ \cdot s V_{y, 1} + μ \cdot s V_{y, 2} = y_{l, i} - y_{k, 1} \end{matrix}

Für 2D-Anwendungen genügt die Lösung dieses Gleichungspaares. Das Gleichungssystem wird mittels CRAMERscher Regel gelöst. Dies erfordert 2 Multiplikationen für die Berechnung der Determinante und weitere 4 Multiplikationen und zwei Divisionen für jeden der vier Eckpunkte je OBB. Der Rest ist einfachste Logik!
Im 3D-Fall eines flächigen Objektes muss zusätzlich geprüft werden, ob die gefundenen Werte für λ und μ auch der dritten Gleichung genügen:

()

z_{l, i} - z_{k, 1} - (λ \cdot s V_{z, 1} + μ \cdot s V_{z, 2}) = 0

Erst dann ist sicher, dass der Punkt P_l,i in der Fläche der k-ten OBB liegt.
Wie sieht die Lösung aber im 3D-Fall für Quader als OBB aus? Ganz einfach: Die und folgende werden um einen dritten Vektor und einen dritten Parameter ν erweitert. Dann ist für jeden Eckpunkt ein Gleichungssystem aus drei Gleichungen mit drei Unbekannten λ, μ, ν zu lösen. Genügen alle drei Werte der Bedingung 0 ≤ λ (μ, ν) ≤ 1 liegt der untersuchte Punkt auf oder innerhalb des Quaders! zwischen

Das nebenstehende Beispielprogramm zeigt ein Spielfeld mit zwei festen Hindernissen (Indize 1, 2) und einem beweglichen Objekt (Index 0). Während die Hindernisse selbst nicht sondern nur ihre OBB's dargestellt werden, können für das bewegliche Objekt unterschiedliche Objekte ausgewählt werden (Button Profil). Der große rote Punkt in dieser OBB ermöglicht eine translatorische, der gelbe hingegen eine rotatorische Bewegung des ausgewählten Objektes. Dessen OBB wird bei jeder Bewegung aktualisiert!
Bewegst Du nun das Objekt 0 an oder in eine der festen OBB's, dann werden die Kontaktpunkte (touchPoints) angezeigt. Eine weiter gehende Auswertung, z.B. ob die Kontaktlinien parallel verlaufen, erfolgt mit diesem Programm nicht. Jeder Eckpunkt, der im Inneren eines anderen Objektes liegt, wird als Kollision gewertet!

Approximation eines Objektes mittels mehrerer OBB's

Für feinere Approximationen kann das Objekt auch von mehreren Boxen umhüllt werden. Diese Boxen bilden dann in ihrer Gesamtheit einen Boxenbaum. Dann:

werden statt eines Rchtecks mehrere Rechtecke (2D) bzw. eines Quaders mehrere Quader (3D) zur Approximation verwendet und
die Hüllkörper sind nicht mehr achsenparallel, sondern orientieren sich an der Hauptausrichtung des zu approximierenden Teils der Körperoberfläche ().

Dabei ist es evident, dass je mehr OBB's zur Approximation verwendet werden, desto besser ist sie, aber um so höher ist auch der Aufwand.
Wie gehen wir vor? Wir gehen davon aus, dass das als Polygon digitalisierte Objekt vorliegt. Dann stehen zwei Wege zur Auswahl:

Es werden geegnete (also willkürlich gewählte) Eckpunkte, die schmale Approximationen erlauben, also keine großen Krümmungen markieren, zu einer OBB zusammengefasst. So wird schließlich das gesamte Objekt in einzelne OBB's erfasst. Diese Lösung erfordert eine händische Ausführung.
Es werden die erfassten Eckpunkte des Objektes in mehrere Sets mit einer vorgegebenen Anzahl von Punkten zu OBB's zusammengefasst. Je größer die Anzahl der Sets, desto weniger Eckpunkte enthält jedes Set. Um so genauer die Approximation, aber desto höher der Aufwand. Diese Lösung kann leicht automatisiert werden.

Abb. 2D_Approximation mittels mehrerer orientierter Rechtecke

Das Beispielprogramm zeigt die gleiche Ausgangssituation wie im Kapitel Berechnung der Maße und Orientierung der OBB: mit Hilfe des Schiebereglers können verschiedene Objekte simuliert werden! Es werden also stets neue OBB's berechnet.
Im Beispiel habe ich mich für den Weg der willkürlichen Festlegung der Teilstück der in OBB's zu wandelnden Kontur entschieden. Zunächst (Index = 0) wird die gesamte Kontur in eine Basis-OBB gewandelt (grünes Rechteck). Das Zentrum dieser OBB kann künftig als Flächenschwerpunkt der gesamten Kontur (Centroid) verstanden werden. Der Flächenschwerpunkt ist der Punkt, der bei einer Translation bzw. Rotation die Lage der Punktmasse repräsentiert. Scharz werden die OBB's dargestellt, die die ausgewählten Teilkonturen umfassen (Index > 0).
Mit dem Button Index kann die Anzeige der Zwischenergebnisse je Teil-OBB ausgewählt werden. Mit dem Button Debug werden die parallelisierten Teilabschnitte, aus denen die Teil-OBB's berechnet werden, dargestellt (hellgrün).

Bounding sphere Verfahren

Im Grunde entspricht dieses Verfahren dem oben beschriebenen Standardverfahren. Der Unterschied besteht darin, dass statt eines Kreises (2D) bzw. einer Kugel (3D) mehrere Kreise oder Kugeln zur Approximation der Hülle verwendet werden. Gegenüber den Oriented bounding boxes hat diese Verfahren den Vorteil, die Testung auf Kollisionen einfach und Rechenzeit ökonomisch auszuführen. Allerdings auf Kosten einer relativ hohen Welligkeit der so gebildeten Hülle um das Objekt.

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 I_K Kreise approximiert wurde. Allerdings wird die Distanz nicht nur einmal zwischen zwei Kreisen bestimmt, sondern sie wird von allen I_K Kreisen zu allen anderen Kreisen der anderen Objekte bestimmt. zeigt die Situation für zwei Objekte. Die Distanzen zwischen den i = 0...I_K einzelnen Kreisen des Kten Objekts zu den j = 0...J_L Kreisen des Lten Objekts berechnen sich dann allgemein zu:

()

und die Kollisionsbedingung lautet demnach:

()

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

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

()

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:

()

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!

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 K_max 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.

Symbol	Bedeutung
P_i	Punkte bzw. Ortsvektoren [m]
$\bar{x}, \bar{y}$	Erwartungswert (geom. Mitte) [m]
λ_i	hier: Eigenwerte
E_i	Eigenvektoren
${\tilde{E}}_{i}$	normierte Eigenvektoren
ψ	Orientierung der Oriented Bounding Box
sV_i	Segmentvektoren
λ, μ	hier: Parameter der vektoriellen Flächenbeschreibung
dist_i	Abstandsbeträge zwischen den Punkten [m]
r_i	Radius des i-ten approximierenden Kreises [m]