So erstellen Sie eine benutzerdefinierte 2D-Physik-Engine: Grundlagen und Impulsauflösung

Es gibt viele Gründe, warum Sie eine benutzerdefinierte Physik-Engine erstellen möchten: Erstens sind das Erlernen und Verfeinern Ihrer Fähigkeiten in Mathematik, Physik und Programmierung gute Gründe, ein solches Projekt zu versuchen; Zweitens kann eine benutzerdefinierte Physik-Engine jede Art von technischen Effekt bewältigen, zu deren Erstellung der Schöpfer die Fähigkeit hat. In diesem Artikel möchte ich eine solide Einführung in die Erstellung einer benutzerdefinierten Physik-Engine von Grund auf geben.

Physik bietet ein wunderbares Mittel, um es einem Spieler zu ermöglichen, in ein Spiel einzutauchen. Es macht Sinn, dass die Beherrschung einer Physik-Engine für jeden Programmierer von großem Vorteil wäre. Durch ein tiefes Verständnis des Innenlebens der Physik-Engine sind jederzeit Optimierungen und Spezialisierungen möglich.

Am Ende dieses Tutorials werden die folgenden Themen in zwei Dimensionen behandelt:

• Einfache Kollisionserkennung
• Einfache Verteilergenerierung
• Impulsauflösung

Hier ist eine kurze Demo:

Hinweis: Obwohl dieses Tutorial in C++ geschrieben wurde, sollten Sie in der Lage sein, dieselben Techniken und Konzepte in fast jeder Spielentwicklungsumgebung zu verwenden.

Voraussetzungen

Dieser Artikel beinhaltet eine beträchtliche Menge an Mathematik und Geometrie und in viel geringerem Maße tatsächliches Codieren. Einige Voraussetzungen für diesen Artikel sind:

• Ein grundlegendes Verständnis der einfachen Vektormathematik
• Die Fähigkeit, algebraische Mathematik durchzuführen

Kollisionserkennung

Es gibt eine ganze Reihe von Artikeln und Tutorials im Internet, einschließlich hier auf Tuts+, die sich mit der Kollisionserkennung befassen. In diesem Wissen möchte ich das Thema sehr schnell durcharbeiten, da dieser Abschnitt nicht im Mittelpunkt dieses Artikels steht.

Achsenausgerichtete Begrenzungsrahmen

Eine achsenausgerichtete Begrenzungsbox (AABB) ist eine Box, deren vier Achsen auf das Koordinatensystem ausgerichtet sind, in dem sie sich befindet. Dies bedeutet, dass es sich um eine Box handelt, die sich nicht drehen kann und immer im 90-Grad-Winkel (normalerweise am Bildschirm ausgerichtet) ist. Im Allgemeinen wird es als "Bounding Box" bezeichnet, da AABBs verwendet werden, um andere komplexere Formen zu begrenzen.

Der AABB einer komplexen Form kann als einfacher Test verwendet werden, um festzustellen, ob sich komplexere Formen innerhalb der AABBs möglicherweise überschneiden. Bei den meisten Spielen wird das AABB jedoch als grundlegende Form verwendet und bindet eigentlich nichts anderes. Die Struktur Ihres AABB ist wichtig. Es gibt verschiedene Möglichkeiten, ein AABB darzustellen, aber dies ist mein Favorit:

1

struct AABB

2

{

3

  Vec2 min;

4

  Vec2 max;

5

};

Diese Form ermöglicht die Darstellung eines AABB durch zwei Punkte. Der min-Punkt stellt die unteren Grenzen der x- und y-Achse dar, und max repräsentiert die oberen Grenzen – mit anderen Worten, sie repräsentieren die obere linke und untere rechte Ecke. Um festzustellen, ob sich zwei AABB-Formen schneiden, benötigen Sie ein grundlegendes Verständnis des Separating Axis Theorem (SAT).

Hier ist ein kurzer Test aus der Echtzeit-Kollisionserkennung von Christer Ericson, der das SAT verwendet:

1

bool AABBvsAABB( AABB a, AABB b )

2

{

3

  // Exit with no intersection if found separated along an axis

4

  if(a.max.x < b.min.x or a.min.x > b.max.x) return false

5

  if(a.max.y < b.min.y or a.min.y > b.max.y) return false

6

7

  // No separating axis found, therefor there is at least one overlapping axis

8

  return true

9

}

Kreise

Ein Kreis wird durch einen Radius und einen Punkt dargestellt. So sollte Ihre Kreisstruktur aussehen:

1

struct Circle

2

{

3

  float radius

4

  Vec position

5

};

Der Test, ob sich zwei Kreise schneiden oder nicht, ist sehr einfach: Nehmen Sie die Radien der beiden Kreise und addieren Sie sie, dann prüfen Sie, ob diese Summe größer ist als der Abstand zwischen den beiden Kreisen.

Eine wichtige Optimierung, die hier vorgenommen werden muss, besteht darin, den Quadratwurzeloperator nicht mehr zu verwenden:

1

float Distance( Vec2 a, Vec2 b )

2

{

3

  return sqrt( (a.x - b.x)^2 + (a.y - b.y)^2 )

4

}

5

6

bool CirclevsCircleUnoptimized( Circle a, Circle b )

7

{

8

  float r = a.radius + b.radius

9

  return r < Distance( a.position, b.position )

10

}

11

12

bool CirclevsCircleOptimized( Circle a, Circle b )

13

{

14

  float r = a.radius + b.radius

15

  r *= r

16

  return r < (a.x + b.x)^2 + (a.y + b.y)^2

17

}

Im Allgemeinen ist die Multiplikation eine viel billigere Operation als das Ziehen der Quadratwurzel eines Wertes.

Impulsauflösung

Die Impulsauflösung ist eine besondere Art der Kollisionsauflösungsstrategie. Kollisionsauflösung ist der Vorgang, bei dem zwei sich kreuzende Objekte genommen und so modifiziert werden, dass sie sich nicht kreuzen.

Im Allgemeinen hat ein Objekt innerhalb einer Physik-Engine drei Hauptfreiheitsgrade (in zwei Dimensionen): Bewegung in der xy-Ebene und Rotation. In diesem Artikel beschränken wir implizit die Rotation und verwenden nur AABBs und Circles, sodass der einzige Freiheitsgrad, den wir wirklich berücksichtigen müssen, die Bewegung entlang der xy-Ebene ist.

Durch das Auflösen erkannter Kollisionen schränken wir die Bewegung so ein, dass Objekte sich nicht überschneiden können. Die Idee hinter der Impulsauflösung besteht darin, einen Impuls (eine sofortige Änderung der Geschwindigkeit) zu verwenden, um kollidierende Objekte zu trennen. Dazu müssen Masse, Position und Geschwindigkeit jedes Objekts irgendwie berücksichtigt werden: Wir möchten, dass sich große Objekte, die mit kleineren kollidieren, bei der Kollision ein wenig bewegen und die kleinen Objekte davonfliegen. Wir wollen auch, dass sich Objekte mit unendlicher Masse überhaupt nicht bewegen.

Um solche Effekte zu erzielen und der natürlichen Intuition des Verhaltens von Objekten zu folgen, verwenden wir starre Körper und ein bisschen Mathematik. Ein starrer Körper ist nur eine vom Benutzer (d. h. von Ihnen, dem Entwickler) definierte Form, die implizit als nicht verformbar definiert ist. Sowohl AABBs als auch Kreise in diesem Artikel sind nicht verformbar und werden immer entweder ein AABB oder ein Kreis sein. Kein Quetschen oder Dehnen erlaubt.

Die Arbeit mit starren Körpern ermöglicht es, viele Mathematik und Ableitungen stark zu vereinfachen. Aus diesem Grund werden in Spielsimulationen häufig starre Körper verwendet, und wir werden sie in diesem Artikel verwenden.

Unsere Objekte kollidierten – was nun?

Angenommen, wir haben zwei sich überschneidende Formen, wie trennt man die beiden eigentlich? Nehmen wir an, unsere Kollisionserkennung hat uns zwei wichtige Informationen geliefert:

• Kollision normal
• Eindringtiefe

Um einen Impuls auf beide Objekte auszuüben und sie auseinander zu bewegen, müssen wir wissen, in welche Richtung und wie stark sie geschoben werden sollen. Die Kollisionsnormale ist die Richtung, in die der Impuls angewendet wird. Die Eindringtiefe (zusammen mit einigen anderen Dingen) bestimmt, wie groß ein Impuls verwendet wird. Das bedeutet, dass der einzige Wert, nach dem gelöst werden muss, die Größe unseres Impulses ist.

Lassen Sie uns nun eine lange Wanderung unternehmen, um herauszufinden, wie wir nach dieser Impulsgröße auflösen können. Wir beginnen mit unseren beiden Objekten, die sich überschneiden:

\[ V^{AB} = V^B - V^A \] Beachten Sie, dass Sie Folgendes tun müssen, um einen Vektor von Position A zu Position B zu erstellen: endpoint - startpoint. \(V^{AB}\) ist die Relativgeschwindigkeit von A nach B. Diese Gleichung sollte durch die Kollisionsnormale \(n\) ausgedrückt werden - das heißt, wir möchten die Relativgeschwindigkeit von A nach kennen B entlang der Richtung der Kollisionsnormalen:

\[ V^{AB} \cdot n = (V^B - V^A) \cdot n \]

Wir verwenden jetzt das Punktprodukt. Das Punktprodukt ist einfach; es ist die Summe der komponentenweisen Produkte:

\[ V_1 = \begin{bmatrix}x_1 \\y_1\end{bmatrix}, V_2 = \begin{bmatrix}x_2 \\y_2\end{bmatrix} \\ V_1 \cdot V_2 = x_1 * x_2 + y_2 * y_2 \]

Der nächste Schritt ist die Einführung des sogenannten Restitutionskoeffizienten. Restitution ist ein Begriff, der Elastizität oder Sprungkraft bedeutet. Jedes Objekt in Ihrer Physik-Engine hat eine Restitution, die als Dezimalwert dargestellt wird. Bei der Impulsberechnung wird jedoch nur ein Dezimalwert verwendet.

Um zu entscheiden, welche Restitution verwendet werden soll (gekennzeichnet durch \(e\) für Epsilon), sollten Sie für intuitive Ergebnisse immer die niedrigste an der Kollision beteiligte Restitution verwenden:

1

// Given two objects A and B

2

e = min( A.restitution, B.restitution )

Sobald \(e\) erfasst ist, können wir es in unsere Gleichung einsetzen, die nach der Impulsgröße auflöst.

Das Newtonsche Restitutionsgesetz besagt Folgendes:

\[V' = e * V\]

All dies sagt aus, dass die Geschwindigkeit nach einer Kollision gleich der Geschwindigkeit davor ist, multipliziert mit einer Konstanten. Diese Konstante repräsentiert einen "Bounce-Faktor". Mit diesem Wissen wird es ziemlich einfach, die Restitution in unsere aktuelle Ableitung zu integrieren:

\[ V^{AB} \cdot n = -e * (V^B - V^A) \cdot n \]

Beachten Sie, wie wir hier ein negatives Vorzeichen eingeführt haben. Im Newtonschen Restitutionsgesetz geht \(V'\), der resultierende Vektor nach dem Abprallen, tatsächlich in die entgegengesetzte Richtung von V. Wie stellen wir also in unserer Ableitung entgegengesetzte Richtungen dar? Führen Sie ein negatives Vorzeichen ein.

So weit, ist es gut. Jetzt müssen wir in der Lage sein, diese Geschwindigkeiten unter dem Einfluss eines Impulses auszudrücken. Hier ist eine einfache Gleichung zum Modifizieren eines Vektors durch einen Impulsskalar \(j\) entlang einer bestimmten Richtung \(n\):

\[ V' = V + j * n \]

Hoffentlich ist die obige Gleichung sinnvoll, da es sehr wichtig ist, sie zu verstehen. Wir haben einen Einheitsvektor \(n\), der eine Richtung repräsentiert. Wir haben einen Skalar \(j\), der angibt, wie lang unser \(n\)-Vektor sein wird. Dann addieren wir unseren skalierten \(n\)-Vektor zu \(V\), um \(V'\) zu erhalten. Dies ist nur das Addieren eines Vektors zu einem anderen, und wir können diese kleine Gleichung verwenden, um einen Impuls eines Vektors auf einen anderen anzuwenden.

Hier ist noch etwas zu tun. Formal wird ein Impuls als Impulsänderung definiert. Impuls ist mass * velocity. Wenn wir dies wissen, können wir einen Impuls darstellen, wie er formal wie folgt definiert ist:

\[ Impulse = mass * Velocity \\ Velocity = \frac{Impulse}{mass} \therefore V' = V + \frac{j * n}{mass}\]

Bisher sind gute Fortschritte gemacht worden! Wir müssen jedoch in der Lage sein, einen Impuls mit \(j\) in Bezug auf zwei verschiedene Objekte auszudrücken. Bei einer Kollision mit Objekt A und B wird A in die entgegengesetzte Richtung von B geschoben:

\[ V'^A = V^A + \frac{j * n}{mass^A} \\ V'^B = V^B - \frac{j * n}{mass^B} \]

Diese beiden Gleichungen werden A entlang des Richtungseinheitsvektors \(n\) durch Impulsskalar (Größe von \(n\)) \(j\) von B wegschieben.

Jetzt müssen Sie nur noch die Gleichungen 8 und 5 zusammenführen. Unsere resultierende Gleichung sieht ungefähr so ​​​​aus:

\[ (V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = -e * (V^B - V^A) \cdot n \\ \therefore \\ (V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0 \]

Wenn Sie sich erinnern, war das ursprüngliche Ziel, unsere Größe zu isolieren. Dies liegt daran, dass wir wissen, in welche Richtung die Kollision aufgelöst werden muss (von der Kollisionserkennung angenommen) und nur noch die Größe dieser Richtung zu lösen ist. Die in unserem Fall unbekannte Größe ist \(j\); wir müssen \(j\) isolieren und danach auflösen.

\[ (V^B - V^A) \cdot n + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0 \\ \therefore \\ (1 + e)((V^B - V^A) \cdot n) + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = 0 \\ \therefore \\ j = \frac{-(1 + e)((V^B - V^A) \cdot n)}{\frac{1}{mass^A} + \frac{1}{mass^B}} \]

Wütend! Das war ordentlich Mathe! Es ist aber vorerst vorbei. Es ist wichtig zu beachten, dass in der endgültigen Version von Gleichung 10 links \(j\) (unsere Größe) steht und rechts alles bekannt ist. Das bedeutet, dass wir ein paar Zeilen Code schreiben können, um nach unserem Impulsskalar \(j\) aufzulösen. Und Junge ist der Code viel lesbarer als die mathematische Notation!

1

void ResolveCollision( Object A, Object B )

2

{

3

  // Calculate relative velocity

4

  Vec2 rv = B.velocity - A.velocity

5

6

  // Calculate relative velocity in terms of the normal direction

7

  float velAlongNormal = DotProduct( rv, normal )

8

9

  // Do not resolve if velocities are separating

10

  if(velAlongNormal > 0)

11

    return;

12

13

  // Calculate restitution

14

  float e = min( A.restitution, B.restitution)

15

16

  // Calculate impulse scalar

17

  float j = -(1 + e) * velAlongNormal

18

  j /= 1 / A.mass + 1 / B.mass

19

20

  // Apply impulse

21

  Vec2 impulse = j * normal

22

  A.velocity -= 1 / A.mass * impulse

23

  B.velocity += 1 / B.mass * impulse

24

}

Im obigen Codebeispiel sind einige wichtige Dinge zu beachten. Das erste ist die Prüfung auf Zeile 10, if(VelAlongNormal > 0). Diese Prüfung ist sehr wichtig; Es stellt sicher, dass Sie eine Kollision nur auflösen, wenn sich die Objekte aufeinander zu bewegen.

Wenn sich Objekte voneinander entfernen, wollen wir nichts tun. Dadurch wird verhindert, dass Objekte, die eigentlich nicht als kollidierend betrachtet werden sollten, voneinander weg aufgelöst werden. Dies ist wichtig, um eine Simulation zu erstellen, die der menschlichen Intuition folgt, was während der Objektinteraktion passieren soll.

Der zweite Punkt ist, dass die inverse Masse ohne Grund mehrmals berechnet wird. Am besten speichern Sie einfach Ihre inverse Masse in jedem Objekt und berechnen sie einmal:

1

A.inv_mass = 1 / A.mass

Als letztes ist zu beachten, dass wir unseren Impulsskalar \(j\) intelligent über die beiden Objekte verteilen. Wir möchten, dass kleine Objekte von großen Objekten mit einem großen Anteil von \(j\) abprallen und die Geschwindigkeit der großen Objekte durch einen sehr kleinen Anteil von \(j\) modifiziert wird.

Um dies zu tun, könnten Sie Folgendes tun:

1

float mass_sum = A.mass + B.mass

2

float ratio = A.mass / mass_sum

3

A.velocity -= ratio * impulse

4

5

ratio = B.mass / mass_sum

6

B.velocity += ratio * impulse

Es ist wichtig zu wissen, dass der obige Code der Beispielfunktion ResolveCollision() von zuvor entspricht. Wie bereits erwähnt, sind inverse Massen in einer Physik-Engine sehr nützlich.

Versenken von Objekten

Wenn wir fortfahren und den Code verwenden, den wir bisher haben, laufen Objekte ineinander und prallen ab. Das ist großartig, aber was passiert, wenn eines der Objekte unendliche Masse hat? Nun, wir brauchen eine gute Möglichkeit, die unendliche Masse in unserer Simulation darzustellen.

Ich schlage vor, Null als unendliche Masse zu verwenden - obwohl wir, wenn wir versuchen, die inverse Masse eines Objekts mit Null zu berechnen, eine Division durch Null haben. Um dies zu umgehen, gehen Sie bei der Berechnung der inversen Masse wie folgt vor:

1

if(A.mass == 0)

2

  A.inv_mass = 0

3

else

4

  A.inv_mass = 1 / A.mass

Ein Wert von Null führt zu korrekten Berechnungen während der Impulsauflösung. Das ist noch in Ordnung. Das Problem des Versinkens von Objekten entsteht, wenn etwas aufgrund der Schwerkraft in ein anderes Objekt zu sinken beginnt. Vielleicht prallt etwas mit geringer Restitution gegen eine Wand mit unendlicher Masse und beginnt zu sinken.

Dieses Absinken ist auf Gleitkommafehler zurückzuführen. Bei jeder Gleitkommaberechnung wird hardwarebedingt ein kleiner Gleitkommafehler eingeführt. (Für weitere Informationen, Google [Gleitkommafehler IEEE754].) Mit der Zeit summiert sich dieser Fehler zu Positionsfehlern, wodurch Objekte ineinander versinken.

Um diesen Fehler zu korrigieren, muss er berücksichtigt werden. Um diesen Positionsfehler zu korrigieren, zeige ich Ihnen eine Methode namens lineare Projektion. Die lineare Projektion reduziert die Durchdringung zweier Objekte um einen kleinen Prozentsatz, und dies erfolgt nach dem Anlegen des Impulses. Die Positionskorrektur ist sehr einfach: Bewegen Sie jedes Objekt entlang der Kollisionsnormalen \(n\) um einen Prozentsatz der Eindringtiefe:

1

void PositionalCorrection( Object A, Object B )

2

{

3

  const float percent = 0.2 // usually 20% to 80%

4

  Vec2 correction = penetrationDepth / (A.inv_mass + B.inv_mass)) * percent * n

5

  A.position -= A.inv_mass * correction

6

  B.position += B.inv_mass * correction

7

}

Beachten Sie, dass wir die penetrationDepth mit der Gesamtmasse des Systems skalieren. Dies ergibt eine Positionskorrektur, die proportional zu der Masse ist, mit der wir es zu tun haben. Kleine Gegenstände werden schneller weggedrückt als schwerere Gegenstände.

Bei dieser Implementierung gibt es ein kleines Problem: Wenn wir unseren Positionsfehler immer auflösen, werden Objekte hin und her zittern, während sie aufeinander liegen. Um dies zu verhindern, muss etwas Spielraum gegeben werden. Wir führen nur eine Positionskorrektur durch, wenn die Penetration über einem beliebigen Schwellenwert liegt, der als "Slop" bezeichnet wird:

1

void PositionalCorrection( Object A, Object B )

2

{

3

  const float percent = 0.2 // usually 20% to 80%

4

  const float slop = 0.01 // usually 0.01 to 0.1

5

  Vec2 correction = max( penetration - k_slop, 0.0f ) / (A.inv_mass + B.inv_mass)) * percent * n

6

  A.position -= A.inv_mass * correction

7

  B.position += B.inv_mass * correction

8

}

Dadurch können Objekte ganz leicht eindringen, ohne dass die Positionskorrektur einsetzt.

Einfache Verteilergenerierung

Das letzte Thema, das in diesem Artikel behandelt wird, ist die einfache Mannigfaltigkeitsgenerierung. Eine Mannigfaltigkeit in mathematischer Hinsicht ist so etwas wie "eine Ansammlung von Punkten, die eine Fläche im Raum darstellt". Wenn ich mich jedoch auf den Begriff Mannigfaltigkeit beziehe, beziehe ich mich auf ein kleines Objekt, das Informationen über eine Kollision zwischen zwei Objekten enthält.

Hier ist ein typischer Verteileraufbau:

1

struct Manifold

2

{

3

  Object *A;

4

  Object *B;

5

  float penetration;

6

  Vec2 normal;

7

};

Während der Kollisionserkennung sollten sowohl die Penetration als auch die Kollisionsnormale berechnet werden. Um diese Informationen zu finden, müssen die ursprünglichen Kollisionserkennungsalgorithmen aus dem Anfang dieses Artikels erweitert werden.

Kreis gegen Kreis

Beginnen wir mit dem einfachsten Kollisionsalgorithmus: Circle vs Circle. Dieser Test ist meist trivial. Können Sie sich vorstellen, in welche Richtung die Kollision gelöst werden soll? Es ist der Vektor von Kreis A zu Kreis B. Dies kann durch Subtrahieren der Position von B von der Position von A erhalten werden.

Die Eindringtiefe hängt von den Radien und dem Abstand der Kreise voneinander ab. Die Überlappung der Kreise kann berechnet werden, indem die summierten Radien um den Abstand von jedem Objekt subtrahiert werden.

Hier ist ein vollständiger Beispielalgorithmus zum Erzeugen der Mannigfaltigkeit einer Kreis-Kreis-Kollision:

1

bool CirclevsCircle( Manifold *m )

2

{

3

  // Setup a couple pointers to each object

4

  Object *A = m->A;

5

  Object *B = m->B;

6

7

  // Vector from A to B

8

  Vec2 n = B->pos - A->pos

9

10

  float r = A->radius + B->radius

11

  r *= r

12

13

  if(n.LengthSquared( ) > r)

14

    return false

15

16

  // Circles have collided, now compute manifold

17

  float d = n.Length( ) // perform actual sqrt

18

19

  // If distance between circles is not zero

20

  if(d != 0)

21

  {

22

    // Distance is difference between radius and distance

23

    m->penetration = r - d

24

25

    // Utilize our d since we performed sqrt on it already within Length( )

26

    // Points from A to B, and is a unit vector

27

    c->normal = t / d

28

    return true

29

  }

30

31

  // Circles are on same position

32

  else

33

  {

34

    // Choose random (but consistent) values

35

    c->penetration = A->radius

36

    c->normal = Vec( 1, 0 )

37

    return true

38

  }

39

}

Die bemerkenswertesten Dinge hier sind: Wir führen keine Quadratwurzeln durch, bis dies erforderlich ist (Objekte kollidieren) und wir überprüfen, ob die Kreise nicht an derselben genauen Position sind. Wenn sie sich an derselben Position befinden, wäre unser Abstand Null, und wir müssen eine Division durch Null vermeiden, wenn wir t / d berechnen.

AABB vs AABB

Der AABB-zu-AABB-Test ist etwas komplexer als Circle vs Circle. Die Kollisionsnormale ist nicht der Vektor von A nach B, sondern eine Flächennormale. Ein AABB ist eine Kiste mit vier Gesichtern. Jedes Gesicht hat eine Normalität. Diese Normale stellt einen Einheitsvektor dar, der senkrecht zur Fläche steht.

Untersuchen Sie die allgemeine Gleichung einer Geraden in 2D:

\[ ax + by + c = 0 \\ normal = \begin{bmatrix}a \\b\end{bmatrix} \]

In der obigen Gleichung sind a und b die Normalenvektoren für eine Linie, und es wird angenommen, dass der Vektor (a, b) normalisiert ist (die Länge des Vektors ist null). Auch hier liegt unsere Kollisionsnormale (Richtung zur Auflösung der Kollision) in Richtung einer der Flächennormalen.

Jetzt müssen Sie nur noch herausfinden, welches Gesicht auf einem der Objekte mit dem anderen Objekt kollidiert, und wir haben unsere Normalität. Manchmal können sich jedoch mehrere Flächen von zwei AABBs überschneiden, beispielsweise wenn sich zwei Ecken schneiden. Dies bedeutet, dass wir die Achse der geringsten Durchdringung finden müssen.

Hier ist ein vollständiger Algorithmus für die Generierung von AABB-zu-AABB-Manifolds und die Kollisionserkennung:

1

bool AABBvsAABB( Manifold *m )

2

{

3

  // Setup a couple pointers to each object

4

  Object *A = m->A

5

  Object *B = m->B

6

7

  // Vector from A to B

8

  Vec2 n = B->pos - A->pos

9

10

  AABB abox = A->aabb

11

  AABB bbox = B->aabb

12

13

  // Calculate half extents along x axis for each object

14

  float a_extent = (abox.max.x - abox.min.x) / 2

15

  float b_extent = (bbox.max.x - bbox.min.x) / 2

16

17

  // Calculate overlap on x axis

18

  float x_overlap = a_extent + b_extent - abs( n.x )

19

20

  // SAT test on x axis

21

  if(x_overlap > 0)

22

  {

23

    // Calculate half extents along x axis for each object

24

    float a_extent = (abox.max.y - abox.min.y) / 2

25

    float b_extent = (bbox.max.y - bbox.min.y) / 2

26

27

    // Calculate overlap on y axis

28

    float y_overlap = a_extent + b_extent - abs( n.y )

29

30

    // SAT test on y axis

31

    if(y_overlap > 0)

32

    {

33

      // Find out which axis is axis of least penetration

34

      if(x_overlap > y_overlap)

35

      {

36

        // Point towards B knowing that n points from A to B

37

        if(n.x < 0)

38

          m->normal = Vec2( -1, 0 )

39

        else

40

          m->normal = Vec2( 0, 0 )

41

        m->penetration = x_overlap

42

        return true

43

      }

44

      else

45

      {

46

        // Point toward B knowing that n points from A to B

47

        if(n.y < 0)

48

          m->normal = Vec2( 0, -1 )

49

        else

50

          m->normal = Vec2( 0, 1 )

51

        m->penetration = y_overlap

52

        return true

53

      }

54

    }

55

  }

56

}

Kreis gegen AABB

Der letzte Test, den ich behandeln werde, ist der Circle vs AABB-Test. Die Idee hier ist, den dem Kreis am nächsten liegenden Punkt auf dem AABB zu berechnen; von dort aus geht der Test in etwas über, das dem Kreis-gegen-Kreis-Test ähnlich ist. Sobald der nächste Punkt berechnet und eine Kollision erkannt wurde, ist die Normale die Richtung des nächsten Punktes zum Kreismittelpunkt. Die Eindringtiefe ist die Differenz zwischen dem Abstand des nächsten Punktes zum Kreis und dem Radius des Kreises.

Es gibt einen kniffligen Sonderfall; Wenn der Mittelpunkt des Kreises innerhalb des AABB liegt, muss der Mittelpunkt des Kreises auf die nächste Kante des AABB zugeschnitten und die Normale gespiegelt werden.

1

bool AABBvsCircle( Manifold *m )

2

{

3

  // Setup a couple pointers to each object

4

  Object *A = m->A

5

  Object *B = m->B

6

7

  // Vector from A to B

8

  Vec2 n = B->pos - A->pos

9

10

  // Closest point on A to center of B

11

  Vec2 closest = n

12

13

  // Calculate half extents along each axis

14

  float x_extent = (A->aabb.max.x - A->aabb.min.x) / 2

15

  float y_extent = (A->aabb.max.y - A->aabb.min.y) / 2

16

17

  // Clamp point to edges of the AABB

18

  closest.x = Clamp( -x_extent, x_extent, closest.x )

19

  closest.y = Clamp( -y_extent, y_extent, closest.y )

20

21

  bool inside = false

22

23

  // Circle is inside the AABB, so we need to clamp the circle's center

24

  // to the closest edge

25

  if(n == closest)

26

  {

27

    inside = true

28

29

    // Find closest axis

30

    if(abs( n.x ) > abs( n.y ))

31

    {

32

      // Clamp to closest extent

33

      if(closest.x > 0)

34

        closest.x = x_extent

35

      else

36

        closest.x = -x_extent

37

    }

38

39

    // y axis is shorter

40

    else

41

    {

42

      // Clamp to closest extent

43

      if(closest.y > 0)

44

        closest.y = y_extent

45

      else

46

        closest.y = -y_extent

47

    }

48

  }

49

50

  Vec2 normal = n - closest

51

  real d = normal.LengthSquared( )

52

  real r = B->radius

53

54

  // Early out of the radius is shorter than distance to closest point and

55

  // Circle not inside the AABB

56

  if(d > r * r && !inside)

57

    return false

58

59

  // Avoided sqrt until we needed

60

  d = sqrt( d )

61

62

  // Collision normal needs to be flipped to point outside if circle was

63

  // inside the AABB

64

  if(inside)

65

  {

66

    m->normal = -n

67

    m->penetration = r - d

68

  }

69

  else

70

  {

71

    m->normal = n

72

    m->penetration = r - d

73

  }

74

75

  return true

76

}

Abschluss

Hoffentlich haben Sie inzwischen ein oder zwei Dinge über Physiksimulation gelernt. Dieses Tutorial reicht aus, um eine einfache benutzerdefinierte Physik-Engine einzurichten, die vollständig von Grund auf neu erstellt wurde. Im nächsten Teil werden wir alle notwendigen Erweiterungen behandeln, die alle Physik-Engines benötigen, einschließlich:

• Sortierung und Aussonderung von Kontaktpaaren
• Breite Phase
• Schichtung
• Integration
• Zeitraffer
• Halbraumschnittpunkt
• Modularer Aufbau (Werkstoffe, Masse und Kräfte)

Ich hoffe, Ihnen hat dieser Artikel gefallen und ich freue mich darauf, Fragen in den Kommentaren zu beantworten.