Videospiel-Physik-Tutorial - Teil II: Kollisionserkennung für feste Objekte

Dies ist Teil II unserer dreiteiligen Serie zur Physik von Videospielen. Den Rest dieser Serie finden Sie unter:

Teil I: Eine Einführung in die Dynamik starrer Körper
Teil III: Simulation starrer Körper mit Zwangsbedingungen

In Teil I dieser Serie haben wir starre Körper und ihre Bewegungen untersucht. In dieser Diskussion interagierten die Objekte jedoch nicht miteinander. Ohne zusätzlichen Aufwand können sich die simulierten starren Körper gegenseitig durchdringen bzw. „durchdringen“, was in den meisten Fällen unerwünscht ist.

Um das Verhalten fester Objekte realistischer zu simulieren, müssen wir prüfen, ob sie bei jeder Bewegung miteinander kollidieren, und wenn ja, müssen wir etwas dagegen tun, z. B. indem wir Kräfte anwenden, die ihre Geschwindigkeit ändern dass sie sich in die entgegengesetzte Richtung bewegen. Hier ist das Verständnis der Kollisionsphysik für Spieleentwickler besonders wichtig.

In Teil II behandeln wir den Kollisionserkennungsschritt, der darin besteht, Körperpaare zu finden, die unter einer möglicherweise großen Anzahl von Körpern kollidieren, die in einer 2D- oder 3D-Welt verstreut sind. Im nächsten und letzten Teil werden wir mehr über das „Auflösen“ dieser Kollisionen sprechen, um gegenseitige Durchdringungen zu eliminieren.

Einen Überblick über die Konzepte der linearen Algebra, auf die in diesem Artikel verwiesen wird, finden Sie im Crashkurs zur linearen Algebra in Teil I.

Kollisionsphysik in Videospielen

Im Zusammenhang mit Starrkörpersimulationen tritt eine Kollision auf, wenn sich die Formen zweier starrer Körper schneiden oder wenn der Abstand zwischen diesen Formen eine kleine Toleranz unterschreitet.

Wenn wir n Körper in unserer Simulation haben, ist die rechnerische Komplexität der Erkennung von Kollisionen mit paarweisen Tests O ( n 2 ) , eine Zahl, die Informatiker zusammenzucken lässt. Die Anzahl der paarweisen Tests steigt quadratisch mit der Anzahl der Körper, und die Bestimmung, ob zwei Formen in beliebigen Positionen und Orientierungen kollidieren, ist bereits nicht billig. Um den Kollisionserkennungsprozess zu optimieren, teilen wir ihn im Allgemeinen in zwei Phasen auf: breite Phase und schmale Phase .

Die breite Phase ist dafür verantwortlich, Paare von starren Körpern zu finden, die möglicherweise kollidieren, und Paare auszuschließen, die sicherlich nicht kollidieren, aus dem gesamten Satz von Körpern, die sich in der Simulation befinden. Dieser Schritt muss sich wirklich gut mit der Anzahl starrer Körper skalieren lassen, um sicherzustellen, dass wir gut unter der Zeitkomplexität von O ( n 2 ) bleiben. Um dies zu erreichen, verwendet diese Phase im Allgemeinen eine Raumpartitionierung in Verbindung mit Begrenzungsvolumina , die eine Obergrenze für Kollisionen festlegen.

Die schmale Phase wirkt auf die Paare von starren Körpern, die von der breiten Phase gefunden werden, die möglicherweise kollidieren. Es ist ein Verfeinerungsschritt, bei dem wir feststellen, ob die Kollisionen tatsächlich stattfinden, und für jede gefundene Kollision berechnen wir die Kontaktpunkte, die verwendet werden, um die Kollisionen später zu lösen.

In den nächsten Abschnitten werden wir über einige Algorithmen sprechen, die in der breiten Phase und in der engen Phase verwendet werden können.

Breite Phase

In der breiten Phase der Kollisionsphysik für Videospiele müssen wir identifizieren, welche Paare starrer Körper möglicherweise kollidieren. Diese Körper können komplexe Formen wie Polygone und Polyeder haben, und was wir tun können, um dies zu beschleunigen, besteht darin, eine einfachere Form zu verwenden, um das Objekt zu umfassen. Wenn sich diese Begrenzungsvolumina nicht schneiden, dann schneiden sich auch die tatsächlichen Formen nicht. Wenn sie sich schneiden, können sich die tatsächlichen Formen schneiden .

Einige beliebte Arten von Begrenzungsvolumen sind orientierte Begrenzungsrahmen (OBB), Kreise in 2D und Kugeln in 3D. Schauen wir uns eines der einfachsten Bounding Volumes an: achsenausgerichtete Bounding Boxes (AABB) .

AABBs werden von Physikprogrammierern sehr geliebt, weil sie einfach sind und gute Kompromisse bieten. Ein zweidimensionales AABB kann durch eine Struktur wie diese in der C-Sprache dargestellt werden:

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

Das min -Feld stellt die Position der unteren linken Ecke der Box dar und das max -Feld stellt die obere rechte Ecke dar.

Um zu testen, ob sich zwei AABBs schneiden, müssen wir nur herausfinden, ob sich ihre Projektionen auf allen Koordinatenachsen schneiden:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Dieser Code hat dieselbe Logik wie die b2TestOverlap Funktion der Box2D-Engine (Version 2.3.0). Es berechnet die Differenz zwischen dem Minimum und dem max beider min , in beiden Achsen, in beiden Ordnungen. Wenn einer dieser Werte größer als Null ist, überschneiden sich die AABBs nicht.

Obwohl ein AABB-Überlappungstest billig ist, hilft es nicht viel, wenn wir immer noch paarweise Tests für jedes mögliche Paar durchführen, da wir immer noch die unerwünschte O ( n 2 ) -Zeitkomplexität haben. Um die Anzahl der AABB-Überlappungstests zu minimieren, können wir eine Art Speicherplatzpartitionierung verwenden, die nach denselben Prinzipien funktioniert wie Datenbankindizes, die Abfragen beschleunigen. (Geografische Datenbanken wie PostGIS verwenden tatsächlich ähnliche Datenstrukturen und Algorithmen für ihre räumlichen Indizes.) In diesem Fall bewegen sich die AABBs jedoch ständig, sodass wir im Allgemeinen nach jedem Schritt der Simulation Indizes neu erstellen müssen.

Es gibt viele Raumpartitionierungsalgorithmen und Datenstrukturen, die dafür verwendet werden können, wie z. B. einheitliche Gitter, Quadtrees in 2D, Octrees in 3D und räumliches Hashing. Lassen Sie uns einen genaueren Blick auf zwei beliebte räumliche Partitionierungsalgorithmen werfen: Sort and Sweep und Bounding Volume Hierarchies (BVH).

Der Sort-and-Sweep-Algorithmus

Die Sort-and-Sweep -Methode (auch bekannt als Sweep and Prune ) ist eine der beliebtesten Methoden unter Physikprogrammierern für die Verwendung in der Starrkörpersimulation. Die Bullet Physics-Engine hat beispielsweise eine Implementierung dieser Methode in der Klasse btAxisSweep3 .

Die Projektion eines AABB auf eine einzelne Koordinatenachse ist im Wesentlichen ein Intervall [ b , e ] (d. h. Anfang und Ende). In unserer Simulation haben wir viele starre Körper und somit viele AABBs, und das bedeutet viele Intervalle. Wir wollen herausfinden, welche Intervalle sich schneiden.

Beim Sort-and-Sweep-Algorithmus fügen wir alle b- und e -Werte in eine einzige Liste ein und sortieren sie aufsteigend nach ihren Skalarwerten. Dann fegen oder durchlaufen wir die Liste. Immer wenn ein b -Wert angetroffen wird, wird sein entsprechendes Intervall in einer separaten Liste aktiver Intervalle gespeichert, und immer wenn ein e -Wert angetroffen wird, wird sein entsprechendes Intervall aus der Liste aktiver Intervalle entfernt. Zu jedem Zeitpunkt schneiden sich alle aktiven Intervalle. (Einzelheiten finden Sie in David Baraffs Ph. D. Thesis, S. 52. Ich schlage vor, dieses Online-Tool zu verwenden, um die Postscript-Datei anzuzeigen.) Die Liste der Intervalle kann bei jedem Schritt der Simulation wiederverwendet werden, wo wir effizient neu sortieren können diese Liste mit Insertion Sort, was sich gut zum Sortieren fast sortierter Listen eignet.

In zwei und drei Dimensionen reduziert das Ausführen des Sortierens und Sweepens, wie oben beschrieben, über eine einzige Koordinatenachse die Anzahl der direkten AABB-Schnittpunkttests, die durchgeführt werden müssen, aber die Auszahlung kann über einer Koordinatenachse besser sein als über einer anderen. Daher werden ausgefeiltere Variationen des Sortier- und Sweep-Algorithmus implementiert. In seinem Buch Echtzeit-Kollisionserkennung (Seite 336) stellt Christer Ericson eine effiziente Variante vor, bei der er alle AABBs in einem einzigen Array speichert und für jeden Durchlauf des Sortierens und Sweepens eine Koordinatenachse ausgewählt und das Array sortiert wird den Mindestwert der min in der gewählten Achse mit Quicksort. Dann wird das Array durchlaufen und AABB-Überlappungstests werden durchgeführt. Um die nächste Achse zu bestimmen, die zum Sortieren verwendet werden sollte, wird die Varianz der Mitte der AABBs berechnet, und die Achse mit größerer Varianz wird für den nächsten Schritt ausgewählt.

Dynamische Begrenzungsvolumenbäume

Eine weitere nützliche räumliche Partitionierungsmethode ist der Dynamic Bounding Volume Tree , auch bekannt als Dbvt . Dies ist eine Art Bounding-Volume-Hierarchie .

Das Dbvt ist ein binärer Baum, in dem jeder Knoten einen AABB hat, der alle AABBs seiner Kinder begrenzt. Die AABBs der starren Körper selbst befinden sich in den Blattknoten. Typischerweise wird ein Dbvt „abgefragt“, indem der AABB angegeben wird, für den wir Schnittpunkte erkennen möchten. Diese Operation ist effizient, da die Kinder von Knoten, die das abgefragte AABB nicht schneiden, nicht auf Überlappung getestet werden müssen. Als solche beginnt eine AABB-Kollisionsabfrage von der Wurzel und setzt sich rekursiv durch den Baum nur für AABB-Knoten fort, die sich mit dem abgefragten AABB schneiden. Der Baum kann wie bei einem AVL-Baum durch Baumrotationen ausbalanciert werden.

Box2D hat eine ausgeklügelte Implementierung von Dbvt in der b2DynamicTree -Klasse. Die b2BroadPhase -Klasse ist für die Durchführung der breiten Phase verantwortlich und verwendet eine Instanz von b2DynamicTree , um AABB-Abfragen durchzuführen.

Schmale Phase

Nach der breiten Phase der Videospiel-Kollisionsphysik haben wir eine Reihe von Paaren starrer Körper, die möglicherweise kollidieren. Daher müssen wir für jedes Paar angesichts der Form, Position und Ausrichtung beider Körper herausfinden, ob sie tatsächlich kollidieren; wenn sie sich schneiden oder wenn ihr Abstand einen kleinen Toleranzwert unterschreitet. Wir müssen auch wissen, welche Berührungspunkte zwischen den kollidierenden Körpern bestehen, da dies später zur Auflösung der Kollisionen benötigt wird.

Konvexe und konkave Formen

Als allgemeine Regel der Videospielphysik ist es nicht trivial festzustellen, ob sich zwei beliebige Formen schneiden, oder den Abstand zwischen ihnen zu berechnen. Eine Eigenschaft, die jedoch von entscheidender Bedeutung für die Bestimmung der Härte ist, ist die Konvexität der Form. Formen können entweder konvex oder konkav sein und mit konkaven Formen ist schwieriger zu arbeiten, daher brauchen wir einige Strategien, um damit umzugehen.

Bei einer konvexen Form fällt ein Liniensegment zwischen zwei beliebigen Punkten innerhalb der Form immer vollständig in die Form. Für eine konkave (oder „nicht konvexe“) Form gilt dies jedoch nicht für alle möglichen Liniensegmente, die Punkte in der Form verbinden. Wenn Sie mindestens ein Liniensegment finden, das außerhalb der Form liegt, ist die Form konkav.

Aus rechnerischer Sicht ist es wünschenswert, dass alle Formen in einer Simulation konvex sind, da wir viele leistungsstarke Entfernungs- und Schnittpunkttestalgorithmen haben, die mit konvexen Formen arbeiten. Nicht alle Objekte sind jedoch konvex, und normalerweise umgehen wir sie auf zwei Arten: konvexe Hülle und konvexe Zerlegung.

Die konvexe Hülle einer Form ist die kleinste konvexe Form, die sie vollständig enthält. Bei einem konkaven Polygon in zwei Dimensionen wäre es so, als würde man einen Nagel auf jeden Scheitelpunkt hämmern und ein Gummiband um alle Nägel wickeln. Um die konvexe Hülle für ein Polygon oder Polyeder oder allgemeiner für eine Reihe von Punkten zu berechnen, ist der Quickhull- Algorithmus ein guter Algorithmus, der eine durchschnittliche Zeitkomplexität von O ( n log n ) hat.

Wenn wir eine konvexe Hülle verwenden, um ein konkaves Objekt darzustellen, verliert es offensichtlich seine konkaven Eigenschaften. Unerwünschtes Verhalten wie „Geister“-Kollisionen können sichtbar werden, da das Objekt immer noch eine konkave grafische Darstellung hat. Zum Beispiel hat ein Auto normalerweise eine konkave Form, und wenn wir eine konvexe Hülle verwenden, um es physisch darzustellen, und dann eine Kiste darauf legen, scheint die Kiste im darüber liegenden Raum zu schweben.

Im Allgemeinen sind konvexe Hüllen oft gut genug, um konkave Objekte darzustellen, entweder weil die unrealistischen Kollisionen nicht sehr auffällig sind oder weil ihre konkaven Eigenschaften für das, was simuliert wird, nicht wesentlich sind. In einigen Fällen möchten wir jedoch, dass sich das konkave Objekt physikalisch wie eine konkave Form verhält. Wenn wir beispielsweise eine konvexe Hülle verwenden, um eine Schale physisch darzustellen, können wir nichts hineinlegen. Objekte schweben einfach darauf. In diesem Fall können wir eine konvexe Zerlegung der konkaven Form verwenden.

Konvexe Zerlegungsalgorithmen empfangen eine konkave Form und geben einen Satz konvexer Formen zurück, deren Vereinigung mit der ursprünglichen konkaven Form identisch ist. Einige konkave Formen können nur durch eine große Anzahl konvexer Formen dargestellt werden, und die Berechnung und Verwendung dieser kann unerschwinglich teuer werden. Eine Annäherung ist jedoch oft gut genug, und so erzeugen Algorithmen wie V-HACD aus einem konkaven Polyeder eine kleine Menge konvexer Polyeder.

In vielen Fällen der Kollisionsphysik kann die konvexe Zerlegung jedoch von einem Künstler von Hand durchgeführt werden. Dadurch entfällt die Notwendigkeit, die Leistung mit Zerlegungsalgorithmen zu besteuern. Da die Leistung einer der wichtigsten Aspekte bei Echtzeitsimulationen ist, ist es im Allgemeinen eine gute Idee, sehr einfache physikalische Darstellungen für komplexe grafische Objekte zu erstellen. Das Bild unten zeigt eine mögliche konvexe Zerlegung eines 2D-Autos mit neun konvexen Formen.

Testen auf Schnittpunkte - The Separating Axis Theorem

Das Trennungsachsentheorem (SAT) besagt, dass sich zwei konvexe Formen genau dann nicht schneiden, wenn es mindestens eine Achse gibt, bei der sich die orthogonalen Projektionen der Formen auf dieser Achse nicht schneiden.

Es ist jedoch normalerweise visuell intuitiver, eine Linie in 2D oder eine Ebene in 3D zu finden, die die beiden Formen trennt, was im Grunde das gleiche Prinzip ist. Als "Trennachse" kann ein Vektor orthogonal zur Linie in 2D oder der Normalenvektor der Ebene in 3D verwendet werden.

Spielphysik-Engines haben eine Reihe verschiedener Klassen von Formen, wie Kreise (Kugeln in 3D), Kanten (ein einzelnes Liniensegment) und konvexe Polygone (Polyeder in 3D). Für jedes Formtyppaar haben sie einen spezifischen Kollisionserkennungsalgorithmus. Der einfachste von ihnen ist wahrscheinlich der Kreis-Kreis-Algorithmus:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

Auch wenn der SAT für Kreise gilt, ist es viel einfacher, einfach zu prüfen, ob der Abstand zwischen ihren Mittelpunkten kleiner ist als die Summe ihrer Radien. Aus diesem Grund wird der SAT im Kollisionserkennungsalgorithmus für bestimmte Paare von Formklassen verwendet, wie z. B. konvexes Polygon gegen konvexes Polygon (oder Polyeder in 3D).

Für jedes Paar von Formen gibt es eine unendliche Anzahl von Achsen, die wir auf Trennung testen können. Daher ist die Bestimmung, welche Achse zuerst getestet werden soll, entscheidend für eine effiziente SAT-Implementierung. Glücklicherweise können wir beim Testen, ob ein Paar konvexer Polygone kollidiert, die Kantennormalen als potenzielle Trennachsen verwenden. Der Normalenvektor n einer Kante steht senkrecht auf dem Kantenvektor und zeigt außerhalb des Polygons. Für jede Kante jedes Polygons müssen wir nur herausfinden, ob alle Scheitelpunkte des anderen Polygons vor der Kante liegen.

Wenn irgendein Test bestanden wird – das heißt, wenn für irgendeine Kante alle Scheitelpunkte des anderen Polygons davor liegen – dann schneiden sich die Polygone nicht. Die lineare Algebra liefert eine einfache Formel für diesen Test: Bei einer gegebenen Kante auf der ersten Form mit Scheitelpunkten a und b und einem Scheitelpunkt v auf der anderen Form, wenn ( v - a ) · n größer als Null ist, dann ist der Scheitelpunkt vorne des Randes.

Für Polyeder können wir die Flächennormalen und auch das Kreuzprodukt aller Kantenkombinationen aus jeder Form verwenden. Das klingt nach einer Menge zu testender Dinge; Um die Dinge jedoch zu beschleunigen, können wir die letzte verwendete Trennachse zwischenspeichern und versuchen, sie in den nächsten Schritten der Simulation erneut zu verwenden. Wenn die zwischengespeicherte Trennachse die Formen nicht mehr trennt, können wir ausgehend von Flächen oder Kanten, die an die vorherige Fläche oder Kante angrenzen, nach einer neuen Achse suchen. Das funktioniert, weil sich die Körper zwischen den Schritten oft nicht viel bewegen oder drehen.

Box2D verwendet SAT, um zu testen, ob sich zwei konvexe Polygone in seinem Polygon-Polygon-Kollisionserkennungsalgorithmus in b2CollidePolygon.cpp schneiden.

Berechnungsentfernung - Der Gilbert-Johnson-Keerthi-Algorithmus

In vielen Fällen der Kollisionsphysik möchten wir Objekte nicht nur dann als kollidierend betrachten, wenn sie sich tatsächlich schneiden, sondern auch, wenn sie sehr nahe beieinander liegen, was erfordert, dass wir den Abstand zwischen ihnen kennen. Der Gilbert-Johnson-Keerthi (GJK)-Algorithmus berechnet den Abstand zwischen zwei konvexen Formen und auch ihre nächsten Punkte. Es ist ein eleganter Algorithmus, der mit einer impliziten Darstellung konvexer Formen durch Stützfunktionen, Minkowski-Summen und Simplexe arbeitet, wie unten erläutert.

Unterstützungsfunktionen

Eine Stützfunktion s A ( d ) gibt einen Punkt auf der Grenze der Form A zurück, der die höchste Projektion auf den Vektor d hat. Mathematisch hat es mit d das höchste Skalarprodukt. Dies wird als Stützpunkt bezeichnet, und diese Operation wird auch als Support-Mapping bezeichnet. Geometrisch ist dieser Punkt der am weitesten entfernte Punkt auf der Form in Richtung von d .

Einen Stützpunkt auf einem Polygon zu finden ist relativ einfach. Für einen Stützpunkt für den Vektor d müssen Sie nur seine Scheitelpunkte durchlaufen und denjenigen finden, der das höchste Skalarprodukt mit d hat, wie folgt:

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

Die eigentliche Stärke einer Stützfunktion besteht jedoch darin, dass sie das Arbeiten mit Formen wie Kegeln, Zylindern und Ellipsen erleichtert. Es ist ziemlich schwierig, den Abstand zwischen solchen Formen direkt zu berechnen, und ohne einen Algorithmus wie GJK müssten Sie sie normalerweise in ein Polygon oder Polyeder diskretisieren, um die Dinge zu vereinfachen. Dies kann jedoch zu weiteren Problemen führen, da die Oberfläche eines Polyeders nicht so glatt ist wie beispielsweise die Oberfläche einer Kugel, es sei denn, das Polyeder ist sehr detailliert, was zu einer schlechten Leistung bei der Kollisionserkennung führen kann. Andere unerwünschte Nebenwirkungen können ebenfalls auftreten; Beispielsweise rollt eine „polyedrische“ Kugel möglicherweise nicht reibungslos.

Um einen Stützpunkt für eine auf den Ursprung zentrierte Kugel zu erhalten, müssen wir nur d normalisieren (d. h. d / || d || berechnen, was ein Vektor mit der Länge 1 (Einheitslänge) ist, der immer noch in die gleiche Richtung zeigt von d ) und dann multiplizieren wir es mit dem Kugelradius.

Sehen Sie sich den Artikel von Gino van den Bergen an, um weitere Beispiele für Stützfunktionen für Zylinder und Kegel sowie andere Formen zu finden.

Unsere Objekte werden natürlich vom Ursprung im Simulationsraum verschoben und gedreht, daher müssen wir in der Lage sein, Stützpunkte für eine transformierte Form zu berechnen. Wir verwenden eine affine Transformation T ( x ) = R x + c , um unsere Objekte zu verschieben und zu drehen, wobei c der Verschiebungsvektor und R die Rotationsmatrix ist . Diese Transformation dreht das Objekt zuerst um den Ursprung und verschiebt es dann. Die Stützfunktion für eine transformierte Form A ist:

Minkowski-Summen

Die Minkowski-Summe zweier Formen A und B ist definiert als:

Das heißt, wir berechnen die Summe für alle Punkte, die in A und B enthalten sind. Das Ergebnis ist wie das Aufblasen von A mit B .

In ähnlicher Weise definieren wir die Minkowski-Differenz als:

was wir auch als Minkowski-Summe von A mit -B schreiben können:

Für konvexes A und B ist auch A⊕B konvex.

Eine nützliche Eigenschaft der Minkowski-Differenz besteht darin, dass sich die Formen schneiden, wenn sie den Ursprung des Raums enthält, wie im vorherigen Bild zu sehen ist. Warum ist das so? Denn wenn sich zwei Formen schneiden, haben sie mindestens einen gemeinsamen Punkt, der an der gleichen Stelle im Raum liegt, und ihre Differenz ist der Nullvektor, der eigentlich der Ursprung ist.

Ein weiteres nettes Merkmal der Minkowski-Differenz ist, dass, wenn sie den Ursprung nicht enthält, der Mindestabstand zwischen dem Ursprung und der Minkowski-Differenz der Abstand zwischen den Formen ist.

Der Abstand zwischen zwei Formen ist definiert als:

Mit anderen Worten, der Abstand zwischen A und B ist die Länge des kürzesten Vektors, der von A nach B geht. Dieser Vektor ist in A⊖B enthalten und ist derjenige mit der kleinsten Länge, der folglich dem Ursprung am nächsten ist.

Es ist im Allgemeinen nicht einfach, die Minkowski-Summe zweier Formen explizit zu bilden. Glücklicherweise können wir auch hier Support-Mapping verwenden, denn:

Simplexe

Der GJK-Algorithmus sucht iterativ nach dem Punkt auf der Minkowski-Differenz, der dem Ursprung am nächsten liegt. Dies geschieht durch Erstellen einer Reihe von Simplexen , die in jeder Iteration näher am Ursprung liegen. Ein Simplex – oder genauer gesagt ein k-Simplex für eine ganze Zahl k – ist die konvexe Hülle von k + 1 affin unabhängigen Punkten in einem k-dimensionalen Raum. Das heißt, wenn sie bei zwei Punkten nicht zusammenfallen dürfen, dürfen sie bei drei Punkten zusätzlich nicht auf derselben Geraden liegen, und bei vier Punkten dürfen sie auch nicht auf derselben Ebene liegen. Daher ist der 0-Simplex ein Punkt, der 1-Simplex eine Strecke, der 2-Simplex ein Dreieck und der 3-Simplex ein Tetraeder. Wenn wir einen Punkt von einem Simplex entfernen, verringern wir seine Dimensionalität um eins, und wenn wir einem Simplex einen Punkt hinzufügen, erhöhen wir seine Dimensionalität um eins.

GJK in Aktion

Lassen Sie uns das alles zusammenfügen, um zu sehen, wie GJK funktioniert. Um den Abstand zwischen zwei Formen A und B zu bestimmen, nehmen wir zunächst ihre Minkowski-Differenz A⊖B . Wir suchen auf der resultierenden Form nach dem Punkt, der dem Ursprung am nächsten liegt, da der Abstand zu diesem Punkt der Abstand zwischen den beiden ursprünglichen Formen ist. Wir wählen einen Punkt v in A⊖B , der unsere Abstandsnäherung sein wird. Wir definieren auch eine leere Punktmenge W , die die Punkte im aktuellen Test-Simplex enthalten wird.

Dann betreten wir eine Schleife. Wir beginnen damit, den Stützpunkt w = s A⊖B (- v ) zu erhalten, den Punkt auf A⊖B , dessen Projektion auf v dem Ursprung am nächsten ist.

Wenn || w || ist nicht viel anders als || v || und der Winkel zwischen ihnen sich nicht wesentlich geändert hat (gemäß einigen vordefinierten Toleranzen), bedeutet dies, dass der Algorithmus konvergiert ist und wir || zurückgeben können v || als Abstand.

Andernfalls addieren wir w zu W . Wenn die konvexe Hülle von W (also der Simplex) den Ursprung enthält, schneiden sich die Formen, und das bedeutet auch, dass wir fertig sind. Andernfalls finden wir den Punkt im Simplex, der dem Ursprung am nächsten liegt, und setzen dann v auf diese neue engste Annäherung zurück. Schließlich entfernen wir alle Punkte in W , die nicht zur Berechnung des nächsten Punkts beitragen. (Wenn wir beispielsweise ein Dreieck haben und der Punkt, der dem Ursprung am nächsten liegt, in einer seiner Kanten liegt, können wir den Punkt von W entfernen, der kein Scheitelpunkt dieser Kante ist.) Dann wiederholen wir dieselben Schritte bis zum Algorithmus konvergiert.

Das nächste Bild zeigt ein Beispiel für vier Iterationen des GJK-Algorithmus. Das blaue Objekt repräsentiert die Minkowski-Differenz A⊖B und der grüne Vektor ist v . Sie können hier sehen, wie sich v auf den Punkt konzentriert, der dem Ursprung am nächsten liegt.

Eine detaillierte und ausführliche Erläuterung des GJK-Algorithmus finden Sie in dem Artikel A Fast and Robust GJK Implementation for Collision Detection of Convex Objects von Gino van den Bergen. Der Blog für die dyn4j-Physik-Engine hat auch einen großartigen Beitrag zu GJK.

Box2D hat eine Implementierung des GJK-Algorithmus in b2Distance.cpp, in der Funktion b2Distance . Es verwendet GJK nur während der Zeit der Aufprallberechnung in seinem Algorithmus zur kontinuierlichen Kollisionserkennung (ein Thema, das wir weiter unten besprechen werden).

Die Chimpunk-Physik-Engine verwendet GJK für die gesamte Kollisionserkennung, und ihre Implementierung befindet sich in cpCollision.c in der GJK -Funktion. Wenn der GJK-Algorithmus Schnittpunkte meldet, muss er neben der Eindringtiefe noch die Kontaktpunkte kennen. Dazu verwendet es den Expanding Polytope Algorithm, den wir als nächstes untersuchen werden.

Bestimmung der Eindringtiefe - Der Expanding-Polytope-Algorithmus

Wie oben erwähnt, erzeugt GJK, wenn sich die Formen A und B schneiden, einen Simplex W , der den Ursprung innerhalb der Minkowski-Differenz A⊖B enthält . In diesem Stadium wissen wir nur, dass sich die Formen schneiden, aber beim Entwurf vieler Kollisionserkennungssysteme ist es wünschenswert, berechnen zu können, wie viele Schnittpunkte wir haben und welche Punkte wir als Kontaktpunkte verwenden können Wir gehen realistisch mit der Kollision um. Der Expanding Polytope Algorithm (EPA) ermöglicht es uns, diese Informationen zu erhalten, beginnend dort, wo GJK aufgehört hat: mit einem Simplex, der den Ursprung enthält.

Die Eindringtiefe ist die Länge des minimalen Translationsvektors (MTV), der der kleinste Vektor ist, entlang dessen wir eine sich schneidende Form verschieben können, um sie von der anderen Form zu trennen.

Wenn sich zwei Formen schneiden, enthält ihre Minkowski-Differenz den Ursprung, und der Punkt auf der Grenze der Minkowski-Differenz, der dem Ursprung am nächsten liegt, ist der MTV. Der EPA-Algorithmus findet diesen Punkt, indem er den Simplex, den GJK uns gegeben hat, in ein Polygon erweitert; sukzessives Unterteilen der Kanten mit neuen Scheitelpunkten.

Zuerst finden wir die Kante des Simplex, die dem Ursprung am nächsten liegt, und berechnen den Stützpunkt in der Minkowski-Differenz in einer Richtung, die normal zur Kante ist (dh senkrecht dazu und außerhalb des Polygons). Dann teilen wir diese Kante, indem wir diesen Stützpunkt hinzufügen. Wir wiederholen diese Schritte, bis sich Länge und Richtung des Vektors nicht mehr stark ändern. Sobald der Algorithmus konvergiert, haben wir die MTV und die Eindringtiefe.

Durch die Verwendung von GJK in Kombination mit EPA erhalten wir eine detaillierte Beschreibung der Kollision, unabhängig davon, ob sich die Objekte bereits schneiden oder gerade nahe genug sind, um als Kollision betrachtet zu werden.

Der EPA-Algorithmus wird in dem ebenfalls von Gino van den Bergen verfassten Artikel Proximity Queries and Penetration Depth Computation on 3D Game Objects beschrieben. Der dyn4j-Blog hat auch einen Beitrag über EPA.

Kontinuierliche Kollisionserkennung

Die bisher vorgestellten Techniken der Videospielphysik führen eine Kollisionserkennung für einen statischen Schnappschuss der Simulation durch. Dies wird als diskrete Kollisionserkennung bezeichnet und ignoriert, was zwischen dem vorherigen und dem aktuellen Schritt passiert. Aus diesem Grund werden einige Kollisionen möglicherweise nicht erkannt, insbesondere bei sich schnell bewegenden Objekten. Dieses Problem wird als Tunneling bezeichnet.

Kontinuierliche Kollisionserkennungstechniken versuchen herauszufinden, wann zwei Körper zwischen dem vorherigen und dem aktuellen Schritt der Simulation kollidiert sind. Sie berechnen den Zeitpunkt des Aufpralls , sodass wir dann in der Zeit zurückgehen und die Kollision an diesem Punkt verarbeiten können.

Die Stoßzeit (oder Kontaktzeit) t c ist der Zeitpunkt, zu dem der Abstand zwischen zwei Körpern Null ist. Wenn wir eine Funktion für den zeitlichen Abstand zwischen zwei Körpern schreiben können, wollen wir die kleinste Wurzel dieser Funktion finden. Somit ist die Zeit der Auswirkungsberechnung ein Wurzelfindungsproblem .

Für die Berechnung des Aufprallzeitpunkts betrachten wir den Zustand (Position und Ausrichtung) des Körpers im vorherigen Schritt zum Zeitpunkt t i –1 und im aktuellen Schritt zum Zeitpunkt t i . Der Einfachheit halber gehen wir von einer linearen Bewegung zwischen den Schritten aus.

Vereinfachen wir das Problem, indem wir annehmen, dass es sich bei den Formen um Kreise handelt. Für zwei Kreise C 1 und C 2 mit den Radien r 1 und r 2 , deren Massenmittelpunkte x 1 und x 2 mit ihrem Schwerpunkt zusammenfallen (dh sie rotieren natürlich um ihren Massenmittelpunkt), können wir die Abstandsfunktion schreiben als:

Unter Berücksichtigung einer linearen Bewegung zwischen Schritten können wir die folgende Funktion für die Position von C 1 von t i –1 bis t i schreiben

Es ist eine lineare Interpolation von x 1 ( t i –1 ) nach x 1 ( t i ) . Dasselbe kann für x 2 gemacht werden. Für dieses Intervall können wir eine weitere Abstandsfunktion schreiben:

Setzen Sie diesen Ausdruck gleich Null und Sie erhalten eine quadratische Gleichung für t . Die Wurzeln können direkt mit der quadratischen Formel gefunden werden. Wenn sich die Kreise nicht schneiden, hat die quadratische Formel keine Lösung. Wenn dies der Fall ist, kann dies zu einer oder zwei Wurzeln führen. Wenn es nur eine Wurzel hat, ist dieser Wert der Zeitpunkt des Aufpralls. Wenn es zwei Wurzeln hat, ist die kleinste der Zeitpunkt des Aufpralls und die andere der Zeitpunkt, an dem sich die Kreise trennen. Beachten Sie, dass die Aufprallzeit hier eine Zahl von 0 bis 1 ist. Es ist keine Zeit in Sekunden; Es ist nur eine Zahl, die wir verwenden können, um den Zustand der Körper auf den genauen Ort zu interpolieren, an dem die Kollision stattgefunden hat.

Kontinuierliche Kollisionserkennung für Nicht-Kreise

Das Schreiben einer Abstandsfunktion für andere Arten von Formen ist schwierig, hauptsächlich weil ihre Entfernung von ihrer Ausrichtung abhängt. Aus diesem Grund verwenden wir im Allgemeinen iterative Algorithmen, die die Objekte bei jeder Iteration näher und näher bewegen, bis sie nahe genug sind, um als kollidierend betrachtet zu werden.

Der konservative Fortschrittsalgorithmus bewegt die Körper iterativ vorwärts (und dreht sie). In jeder Iteration berechnet es eine Obergrenze für die Verschiebung. Der ursprüngliche Algorithmus wird in Brian Mirtichs Doktorarbeit (Abschnitt 2.3.2) vorgestellt, der die ballistische Bewegung von Körpern betrachtet. Dieses Papier von Erwin Coumans (dem Autor der Bullet Physics Engine) stellt eine einfachere Version vor, die konstante Linear- und Winkelgeschwindigkeiten verwendet.

Der Algorithmus berechnet die nächstgelegenen Punkte zwischen den Formen A und B , zeichnet einen Vektor von einem Punkt zum anderen und projiziert die Geschwindigkeit auf diesen Vektor, um eine Obergrenze für die Bewegung zu berechnen. Es garantiert, dass sich keine Punkte am Körper über diese Projektion hinaus bewegen. Dann schiebt es die Körper um diesen Betrag nach vorne und wiederholt es, bis der Abstand unter einen kleinen Toleranzwert fällt.

Es kann in einigen Fällen zu viele Iterationen erfordern, um zu konvergieren, beispielsweise wenn die Winkelgeschwindigkeit eines der Körper zu hoch ist.

Kollisionen lösen

Sobald eine Kollision erkannt wurde, ist es notwendig, die Bewegungen der kollidierenden Objekte auf realistische Weise zu ändern, indem sie beispielsweise dazu gebracht werden, dass sie aneinander abprallen. Im nächsten und letzten Teil dieser Theorien werden wir einige beliebte Methoden zur Auflösung von Kollisionen in Videospielen diskutieren.

Verweise

Wenn Sie daran interessiert sind, ein tieferes Verständnis der Kollisionsphysik wie Kollisionserkennungsalgorithmen und -techniken zu erlangen, ist das Buch Real-Time Collision Detection von Christer Ericson ein Muss.

Da die Kollisionserkennung stark auf Geometrie angewiesen ist, ist Toptals Artikel Computational Geometry in Python: From Theory to Application eine hervorragende Einführung in das Thema.