So erstellen Sie eine benutzerdefinierte 2D-Physik-Engine: Reibungs-, Szenen- und Sprungtabelle

In den ersten beiden Tutorials dieser Reihe habe ich die Themen Impulsauflösung und Kernarchitektur behandelt. Jetzt ist es an der Zeit, unserer impulsbasierten 2D-Physik-Engine den letzten Schliff zu geben.

Die Themen, die wir in diesem Artikel behandeln werden, sind:

• Reibung
• Szene
• Kollisionsspringtabelle

Ich habe dringend empfohlen, die beiden vorherigen Artikel der Reihe zu lesen, bevor ich versuche, diesen zu behandeln. Einige wichtige Informationen in den vorherigen Artikeln basieren auf diesem Artikel.

Hinweis: Obwohl dieses Tutorial mit C++ geschrieben wurde, sollten Sie in fast jeder Spieleentwicklungsumgebung dieselben Techniken und Konzepte verwenden können.

Video-Demo

Hier ist eine kurze Demo dessen, worauf wir in diesem Teil hinarbeiten:

Custom 2D Physics Engine: Friction, Scene and Jump Table

Reibung

Reibung ist ein Teil der Kollisionsauflösung. Reibung übt immer eine Kraft auf Objekte aus, die der Bewegung entgegengesetzt sind, in der sie sich bewegen sollen.

Im wirklichen Leben ist Reibung eine unglaublich komplexe Wechselwirkung zwischen verschiedenen Substanzen, und um sie zu modellieren, werden große Annahmen und Annäherungen getroffen. Diese Annahmen sind in der Mathematik impliziert und in der Regel so etwas wie "Die Reibung kann durch einen einzelnen Vektor angenähert werden" - ähnlich wie die Starrkörperdynamik reale Interaktionen simuliert, indem Körper mit gleichmäßiger Dichte angenommen werden, die sich nicht verformen können.

Werfen Sie einen kurzen Blick auf die Videodemo aus dem ersten Artikel dieser Reihe:

Custom Physics Engine Demo

Die Interaktionen zwischen den Körpern sind sehr interessant und das Hüpfen bei Kollisionen fühlt sich realistisch an. Sobald die Objekte jedoch auf der festen Plattform landen, drücken sie sich einfach weg und driften von den Rändern des Bildschirms ab. Dies ist auf einen Mangel an Reibungssimulation zurückzuführen.

Wieder Impulse?

Wie Sie sich aus dem ersten Artikel dieser Reihe erinnern sollten, repräsentiert ein bestimmter Wert j die Größe eines Impulses, der erforderlich ist, um das Eindringen zweier Objekte während einer Kollision zu trennen. Diese Größe kann als jnormal oder jN bezeichnet werden, da sie zum Ändern der Geschwindigkeit entlang der Kollisionsnormalen verwendet wird.

Das Einbeziehen einer Reibungsantwort beinhaltet das Berechnen einer anderen Größe, die als jtangent oder jT bezeichnet wird. Reibung wird als Impuls modelliert. Diese Größe ändert die Geschwindigkeit eines Objekts entlang des negativen Tangentenvektors der Kollision oder mit anderen Worten entlang des Reibungsvektors. In zwei Dimensionen ist das Lösen dieses Reibungsvektors ein lösbares Problem, aber in 3D wird das Problem viel komplexer.

Die Reibung ist recht einfach, und wir können unsere vorherige Gleichung für j verwenden, außer dass wir alle Instanzen der Normalen n durch einen Tangentenvektor t ersetzen.

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

Ersetzen Sie n durch t:

\[ Equation 2:\\ j = \frac{-(1 + e)((V^{B}-V^{A})\cdot t)} {\frac{1}{mass^A} + \frac{1}{mass^B}}\]

Obwohl in dieser Gleichung nur eine einzige Instanz von n durch t ersetzt wurde, müssen nach Einführung der Rotationen neben der einzelnen Instanz im Zähler von Gleichung 2 einige weitere Instanzen ersetzt werden.

Nun stellt sich die Frage, wie t berechnet werden soll. Der Tangentenvektor ist ein Vektor senkrecht zur Kollisionsnormalen, der mehr zur Normalen zeigt. Das klingt vielleicht verwirrend - keine Sorge, ich habe ein Diagramm!

Unten sehen Sie den Tangentenvektor senkrecht zur Normalen. Der Tangentenvektor kann entweder nach links oder rechts zeigen. Links wäre "weiter weg" von der Relativgeschwindigkeit. Es ist jedoch definiert als die Senkrechte zur Normalen, die "mehr in Richtung" der Relativgeschwindigkeit zeigt.

Wie kurz zuvor erwähnt, ist Reibung ein Vektor, der dem Tangentenvektor gegenüberliegt. Dies bedeutet, dass die Richtung, in der Reibung angewendet werden soll, direkt berechnet werden kann, da der Normalenvektor während der Kollisionserkennung gefunden wurde.

In diesem Wissen ist der Tangentenvektor (wobei n die Kollisionsnormale ist):

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

Alles, was für jt, die Größe der Reibung, zu lösen bleibt, ist, den Wert direkt unter Verwendung der obigen Gleichungen zu berechnen. Nachdem dieser Wert berechnet wurde, gibt es einige sehr knifflige Teile, die in Kürze behandelt werden. Dies ist also nicht das Letzte, was in unserem Kollisionsauflöser benötigt wird:

1

// Re-calculate relative velocity after normal impulse

2

// is applied (impulse from first article, this code comes

3

// directly thereafter in the same resolve function)

4

Vec2 rv = VB - VA

5

6

// Solve for the tangent vector

7

Vec2 tangent = rv - Dot( rv, normal ) * normal

8

tangent.Normalize( )

9

10

// Solve for magnitude to apply along the friction vector

11

float jt = -Dot( rv, t )

12

jt = jt / (1 / MassA + 1 / MassB)

Der obige Code folgt direkt Gleichung 2. Auch hier ist es wichtig zu erkennen, dass der Reibungsvektor in die entgegengesetzte Richtung unseres Tangentenvektors zeigt. Daher müssen wir ein negatives Vorzeichen anwenden, wenn wir die Relativgeschwindigkeit entlang der Tangente punktieren, um die Relativgeschwindigkeit entlang des Tangentenvektors zu ermitteln. Dieses negative Vorzeichen dreht die Tangentengeschwindigkeit um und zeigt plötzlich in die Richtung, in die die Reibung angenähert werden soll.

Coulomb-Gesetz

Das Coulombsche Gesetz ist der Teil der Reibungssimulation, mit dem die meisten Programmierer Probleme haben. Ich selbst musste einiges lernen, um herauszufinden, wie man es richtig modelliert. Der Trick ist, dass Coulombs Gesetz eine Ungleichung ist.

Coulomb-Reibungszustände:

\[ Equation 3: \\ F_f <= \mu F_n \]

Mit anderen Worten ist die Reibungskraft immer kleiner oder gleich der Normalkraft multipliziert mit einer Konstanten μ (deren Wert von den Materialien der Objekte abhängt).

Die Normalkraft ist nur unsere alte j-Größe multipliziert mit der Kollisionsnormalen. Wenn also unser gelöstes jt (das die Reibungskraft darstellt) kleiner als das μ-fache der Normalkraft ist, können wir unsere jt-Größe als Reibung verwenden. Wenn nicht, müssen wir stattdessen unsere normalen Kraftzeiten μ verwenden. Dieser "else"-Fall ist eine Form der Klemmung unserer Reibung unter einen Maximalwert, wobei das Maximum die Normalkraft mal μ ist.

Der Sinn des Coulombschen Gesetzes besteht darin, dieses Klemmverfahren durchzuführen. Diese Klemmung stellt sich als der schwierigste Teil der Reibungssimulation für die impulsbasierte Auflösung heraus, um irgendwo Dokumentation zu finden - zumindest bis jetzt! Die meisten White Papers, die ich zu diesem Thema finden konnte, übersprangen entweder die Reibung vollständig oder hielten kurz an und implementierten unsachgemäße (oder nicht vorhandene) Klemmverfahren. Hoffentlich wissen Sie jetzt zu schätzen, dass es wichtig ist, diesen Teil richtig zu machen.

Lassen Sie uns einfach die Klemme auf einmal austeilen, bevor wir etwas erklären. Dieser nächste Codeblock ist das vorherige Codebeispiel mit dem fertigen Klemmvorgang und der Reibungsimpulsanwendung zusammen:

1

// Re-calculate relative velocity after normal impulse

2

// is applied (impulse from first article, this code comes

3

// directly thereafter in the same resolve function)

4

Vec2 rv = VB - VA

5

6

// Solve for the tangent vector

7

Vec2 tangent = rv - Dot( rv, normal ) * normal

8

tangent.Normalize( )

9

10

// Solve for magnitude to apply along the friction vector

11

float jt = -Dot( rv, t )

12

jt = jt / (1 / MassA + 1 / MassB)

13

14

// PythagoreanSolve = A^2 + B^2 = C^2, solving for C given A and B

15

// Use to approximate mu given friction coefficients of each body

16

float mu = PythagoreanSolve( A->staticFriction, B->staticFriction )

17

18

// Clamp magnitude of friction and create impulse vector

19

Vec2 frictionImpulse

20

if(abs( jt ) < j * mu)

21

  frictionImpulse = jt * t

22

else

23

{

24

  dynamicFriction = PythagoreanSolve( A->dynamicFriction, B->dynamicFriction )

25

  frictionImpulse = -j * t * dynamicFriction

26

}

27

28

// Apply

29

A->velocity -= (1 / A->mass) * frictionImpulse

30

B->velocity += (1 / B->mass) * frictionImpulse

Ich entschied mich, diese Formel zu verwenden, um die Reibungskoeffizienten zwischen zwei Körpern zu ermitteln, wobei für jeden Körper ein Koeffizient angegeben wurde:

\[ Equation 4: \\ Friction = \sqrt[]{Friction^2_A + Friction^2_B} \]

Ich habe tatsächlich gesehen, wie jemand anderes dies in seiner eigenen Physik-Engine tat, und das Ergebnis hat mir gefallen. Ein Durchschnitt der beiden Werte würde einwandfrei funktionieren, um die Verwendung der Quadratwurzel zu vermeiden. In der Tat funktioniert jede Form der Auswahl des Reibungskoeffizienten. das ist genau das, was ich bevorzuge. Eine andere Option wäre die Verwendung einer Nachschlagetabelle, in der der Typ jedes Körpers als Index für eine 2D-Tabelle verwendet wird.

Es ist wichtig, dass der Absolutwert von jt für den Vergleich verwendet wird, da der Vergleich theoretisch die Rohgrößen unter einen bestimmten Schwellenwert klemmt. Da j immer positiv ist, muss es umgedreht werden, um einen geeigneten Reibungsvektor darzustellen, falls dynamische Reibung verwendet wird.

Statische und dynamische Reibung

Im letzten Code-Snippet wurden statische und dynamische Reibung ohne Erklärung eingeführt! Ich werde diesen ganzen Abschnitt der Erklärung des Unterschieds und der Notwendigkeit dieser beiden Arten von Werten widmen.

Mit Reibung passiert etwas Interessantes: Es erfordert eine "Aktivierungsenergie", damit sich Objekte in völliger Ruhe bewegen können. Wenn zwei Objekte im wirklichen Leben aufeinander ruhen, ist eine angemessene Menge an Energie erforderlich, um auf eines zu drücken und es in Bewegung zu setzen. Sobald Sie jedoch etwas rutschen lassen, ist es oft einfacher, es von da an gleiten zu lassen.

Dies liegt daran, wie Reibung auf mikroskopischer Ebene funktioniert. Ein anderes Bild hilft hier:

Wie Sie sehen können, sind die kleinen Deformitäten zwischen den Oberflächen wirklich der Hauptschuldige, der in erster Linie Reibung erzeugt. Wenn ein Objekt auf einem anderen ruht, ruhen mikroskopische Deformitäten zwischen den Objekten und greifen ineinander. Diese müssen zerbrochen oder getrennt werden, damit die Objekte gegeneinander gleiten können.

Wir brauchen einen Weg, dies in unserem Motor zu modellieren. Eine einfache Lösung besteht darin, jedem Materialtyp zwei Reibungswerte bereitzustellen: einen für statische und einen für dynamische.

Die Haftreibung wird verwendet, um unsere jt-Größe zu klemmen. Wenn die gelöste jt-Größe niedrig genug ist (unter unserer Schwelle), können wir annehmen, dass sich das Objekt in Ruhe befindet oder fast so ruht, und das gesamte jt als Impuls verwenden.

Wenn auf der anderen Seite unser gelöstes jt über dem Schwellenwert liegt, kann angenommen werden, dass das Objekt die "Aktivierungsenergie" bereits gebrochen hat, und in einer solchen Situation wird ein niedrigerer Reibungsimpuls verwendet, der durch einen kleineren Reibungskoeffizienten dargestellt wird und eine etwas andere Impulsberechnung.

Szene

Angenommen, Sie haben keinen Teil des Reibungsabschnitts übersprungen, gut gemacht! Sie haben den schwierigsten Teil dieser gesamten Serie abgeschlossen (meiner Meinung nach).

Die Scene-Klasse fungiert als Container für alles, was ein Physik-Simulationsszenario betrifft. Es ruft die Ergebnisse einer breiten Phase auf und verwendet sie, enthält alle starren Körper, führt Kollisionsprüfungen durch und ruft die Auflösung auf. Es integriert auch alle lebenden Objekte. Die Szene ist auch mit dem Benutzer verbunden (wie beim Programmierer, der die Physik-Engine verwendet).

Hier ist ein Beispiel dafür, wie eine Szenenstruktur aussehen kann:

1

class Scene

2

{

3

public:

4

  Scene( Vec2 gravity, real dt );

5

  ~Scene( );

6

7

  void SetGravity( Vec2 gravity )

8

  void SetDT( real dt )

9

10

  Body *CreateBody( ShapeInterface *shape, BodyDef def )

11

12

  // Inserts a body into the scene and initializes the body (computes mass).

13

  //void InsertBody( Body *body )

14

15

  // Deletes a body from the scene

16

  void RemoveBody( Body *body )

17

18

  // Updates the scene with a single timestep

19

  void Step( void )

20

21

  float GetDT( void )

22

  LinkedList *GetBodyList( void )

23

  Vec2 GetGravity( void )

24

  void QueryAABB( CallBackQuery cb, const AABB& aabb )

25

  void QueryPoint( CallBackQuery cb, const Point2& point )

26

27

private:

28

  float dt     // Timestep in seconds

29

  float inv_dt // Inverse timestep in sceonds

30

  LinkedList body_list

31

  uint32 body_count

32

  Vec2 gravity

33

  bool debug_draw

34

  BroadPhase broadphase

35

};

An der Scene-Klasse ist nichts besonders Komplexes. Die Idee ist, dem Benutzer das einfache Hinzufügen und Entfernen von starren Körpern zu ermöglichen. Das BodyDef ist eine Struktur, die alle Informationen über einen starren Körper enthält und verwendet werden kann, damit der Benutzer Werte als eine Art Konfigurationsstruktur einfügen kann.

Die andere wichtige Funktion ist Step(). Diese Funktion führt eine einzelne Runde von Kollisionsprüfungen, Auflösung und Integration durch. Dies sollte innerhalb der im zweiten Artikel dieser Reihe beschriebenen Zeitüberschreitungsschleife aufgerufen werden.

Beim Abfragen eines Punkts oder AABB muss überprüft werden, welche Objekte tatsächlich mit einem Zeiger oder AABB innerhalb der Szene kollidieren. Auf diese Weise kann die spielerische Logik leicht erkennen, wie die Dinge in der Welt platziert sind.

Sprungtabelle

Wir brauchen eine einfache Möglichkeit, um herauszufinden, welche Kollisionsfunktion aufgerufen werden soll, basierend auf dem Typ von zwei verschiedenen Objekten.

In C++ gibt es zwei wichtige Möglichkeiten, die mir bekannt sind: Doppelversand und eine 2D-Sprungtabelle. In meinen persönlichen Tests fand ich die 2D-Sprungtabelle überlegen, daher werde ich detailliert darauf eingehen, wie dies implementiert werden kann. Wenn Sie eine andere Sprache als C oder C++ verwenden möchten, kann ein Array von Funktionen oder Funktorobjekten sicher ähnlich wie eine Tabelle mit Funktionszeigern erstellt werden (ein weiterer Grund, warum ich mich für Sprungtabellen und nicht für andere Optionen entschieden habe das sind spezifischer für C++).

Eine Sprungtabelle in C oder C++ ist eine Tabelle mit Funktionszeigern. Indizes, die beliebige Namen oder Konstanten darstellen, werden verwendet, um in die Tabelle zu indizieren und eine bestimmte Funktion aufzurufen. Die Verwendung könnte für eine 1D-Sprungtabelle ungefähr so aussehen:

1

enum Animal

2

{

3

  Rabbit

4

  Duck

5

  Lion

6

};

7

8

const void (*talk)( void )[] = {

9

  RabbitTalk,

10

  DuckTalk,

11

  LionTalk,

12

};

13

14

// Call a function from the table with 1D virtual dispatch

15

talk[Rabbit]( ) // calls the RabbitTalk function

Der obige Code ahmt tatsächlich nach, was die C ++ - Sprache selbst mit virtuellen Funktionsaufrufen und Vererbung implementiert. C++ implementiert jedoch nur eindimensionale virtuelle Aufrufe. Eine 2D-Tabelle kann von Hand erstellt werden.

Hier ist ein Pseudocode für eine 2D-Sprungtabelle zum Aufrufen von Kollisionsroutinen:

1

collisionCallbackArray = {

2

  AABBvsAABB

3

  AABBvsCircle

4

  CirclevsAABB

5

  CirclevsCircle

6

}

7

8

// Call a collsion routine for collision detection between A and B

9

// two colliders without knowing their exact collider type

10

// type can be of either AABB or Circle

11

collisionCallbackArray[A->type][B->type]( A, B )

Und da haben wir es! Die tatsächlichen Typen jedes Colliders können verwendet werden, um in ein 2D-Array zu indizieren und eine Funktion zum Auflösen der Kollision auszuwählen.

Beachten Sie jedoch, dass AABBvsCircle und CirclevsAABB fast Duplikate sind. Das ist notwendig! Das Normale muss für eine dieser beiden Funktionen umgedreht werden, und das ist der einzige Unterschied zwischen ihnen. Dies ermöglicht eine konsistente Kollisionsauflösung, unabhängig von der Kombination der zu lösenden Objekte.

Abschluss

Inzwischen haben wir eine Vielzahl von Themen behandelt, um eine benutzerdefinierte Starrkörperphysik-Engine von Grund auf neu einzurichten! Kollisionsauflösung, Reibung und Motorarchitektur sind alle Themen, die bisher behandelt wurden. Mit dem bisher in dieser Serie vorgestellten Wissen kann eine völlig erfolgreiche Physik-Engine konstruiert werden, die für viele zweidimensionale Spiele auf Produktionsebene geeignet ist.

Mit Blick auf die Zukunft plane ich, einen weiteren Artikel zu schreiben, der sich ganz einem sehr wünschenswerten Merkmal widmet: Rotation und Orientierung. Orientierte Objekte sind äußerst attraktiv, um zu sehen, wie sie miteinander interagieren, und sie sind das letzte Stück, das unsere benutzerdefinierte Physik-Engine benötigt.

Die Auflösung der Rotation stellt sich als recht einfach heraus, obwohl die Kollisionserkennung einen Komplexitätsverlust aufweist. Viel Glück bis zum nächsten Mal, und bitte stellen Sie Fragen oder posten Sie Kommentare unten!