7 days of WordPress themes, graphics & videos - for free!* Unlimited asset downloads! Start 7-Day Free Trial
Advertisement
  1. Game Development
  2. Programming

So erstellen Sie eine benutzerdefinierte 2D-Physik-Engine: Orientierte starre Körper

Scroll to top
Read Time: 16 mins
This post is part of a series called How to Create a Custom Physics Engine.
How to Create a Custom 2D Physics Engine: Friction, Scene and Jump Table

German (Deutsch) translation by Alex Grigorovich (you can also view the original English article)

Bisher haben wir die Impulsauflösung, die Kernarchitektur und Reibung behandelt. In diesem letzten Tutorial dieser Reihe werden wir ein sehr interessantes Thema behandeln: Orientierung.

In diesem Artikel besprechen wir folgende Themen:

  • Rotationsmathematik
  • Orientierte Formen
  • Kollisionserkennung
  • Kollisionsauflösung

Ich empfehle dringend, die vorherigen drei Artikel der Serie zu lesen, bevor Sie versuchen, diesen anzugehen. Viele der Schlüsselinformationen in den vorherigen Artikeln sind Voraussetzungen für den Rest dieses Artikels.


Beispielcode

Ich habe eine kleine Beispiel-Engine in C++ erstellt und empfehle Ihnen, während des gesamten Lesens dieses Artikels den Quellcode zu durchsuchen und darauf zu verweisen, da viele praktische Implementierungsdetails nicht in den Artikel selbst passen.

Dieses GitHub-Repository enthält die Beispiel-Engine selbst sowie ein Visual Studio 2010-Projekt. GitHub ermöglicht es Ihnen, die Quelle anzuzeigen, ohne die Quelle selbst herunterladen zu müssen.


Orientierung Math

Die Mathematik mit Rotationen in 2D ist ziemlich einfach, obwohl eine Beherrschung des Themas erforderlich ist, um etwas Wertvolles in einer Physik-Engine zu erstellen. Newtons zweites Gesetz besagt:

\[ Equation \: 1:\\ F = ma\]

Es gibt eine ähnliche Gleichung, die sich speziell auf die Winkelkraft und die Winkelbeschleunigung bezieht. Bevor diese Gleichungen gezeigt werden können, ist jedoch eine kurze Beschreibung des Kreuzprodukts in 2D erforderlich.

Kreuzprodukt

Das Kreuzprodukt in 3D ist eine bekannte Operation. Allerdings kann das Kreuzprodukt in 2D recht verwirrend sein, da es keine wirklich solide geometrische Interpretation gibt.

Das 2D-Kreuzprodukt gibt im Gegensatz zur 3D-Version keinen Vektor, sondern einen Skalar zurück. Dieser Skalarwert repräsentiert tatsächlich die Größe des orthogonalen Vektors entlang der z-Achse, wenn das Kreuzprodukt tatsächlich in 3D durchgeführt würde. In gewisser Weise ist das 2D-Kreuzprodukt nur eine vereinfachte Version des 3D-Kreuzprodukts, da es eine Erweiterung der 3D-Vektormathematik ist.

Wenn dies verwirrend ist, machen Sie sich keine Sorgen: Ein gründliches Verständnis des 2D-Kreuzprodukts ist nicht unbedingt erforderlich. Sie müssen nur genau wissen, wie die Operation ausgeführt wird, und dass die Reihenfolge der Operationen wichtig ist: \(a \times b\) ist nicht dasselbe wie \(b \times a\). In diesem Artikel wird das Kreuzprodukt intensiv genutzt, um die Winkelgeschwindigkeit in die Lineargeschwindigkeit umzuwandeln.

Es ist jedoch sehr wichtig zu wissen, wie das Kreuzprodukt in 2D durchgeführt wird. Zwei Vektoren können gekreuzt werden, ein Skalar kann mit einem Vektor gekreuzt werden und ein Vektor kann mit einem Skalar gekreuzt werden. Hier sind die Operationen:

Drehmoment und Winkelgeschwindigkeit

Wie wir alle aus den vorherigen Artikeln wissen sollten, stellt diese Gleichung eine Beziehung zwischen der auf einen Körper wirkenden Kraft mit der Masse dieses Körpers und der Beschleunigung dar. Es gibt ein Analogon für die Rotation:

\[ Equation \: 2:\\ T = r \: \times \: \omega\]

\(T\) steht für Drehmoment. Drehmoment ist Rotationskraft.

\(r\) ist ein Vektor vom Massenschwerpunkt (COM) zu einem bestimmten Punkt auf einem Objekt. \(r\) kann man sich als einen "Radius" von COM zu einem Punkt vorstellen. Jeder einzelne eindeutige Punkt auf einem Objekt erfordert einen anderen \(r\)-Wert, um in Gleichung 2 dargestellt zu werden.

\(\omega\) heißt "Omega" und bezieht sich auf die Rotationsgeschwindigkeit. Diese Beziehung wird verwendet, um die Winkelgeschwindigkeit eines starren Körpers zu integrieren.

Es ist wichtig zu verstehen, dass die Lineargeschwindigkeit die Geschwindigkeit der COM eines starren Körpers ist. Im vorherigen Artikel hatten alle Objekte keine Rotationskomponenten, sodass die Lineargeschwindigkeit des COM für alle Punkte auf einem Körper dieselbe Geschwindigkeit war. Wenn die Orientierung eingeführt wird, drehen sich weiter vom COM entfernte Punkte schneller als diejenigen in der Nähe des COM. Das bedeutet, dass wir eine neue Gleichung benötigen, um die Geschwindigkeit eines Punktes auf einem Körper zu bestimmen, da sich Körper jetzt gleichzeitig drehen und verschieben können.

Verwenden Sie die folgende Gleichung, um die Beziehung zwischen einem Punkt auf einem Körper und der Geschwindigkeit dieses Punktes zu verstehen:

\[ Equation \: 3:\\ \omega = r \: \times v \]

\(v\) repräsentiert die Lineargeschwindigkeit. Um die Lineargeschwindigkeit in die Winkelgeschwindigkeit umzuwandeln, kreuzen Sie den \(r\)-Radius mit \(v\).

In ähnlicher Weise können wir Gleichung 3 neu anordnen, um eine andere Version zu bilden:

\[ Equation \: 4:\\ v = \omega\: \times r \]

Die Gleichungen aus dem letzten Abschnitt sind nur dann recht aussagekräftig, wenn starre Körper eine gleichmäßige Dichte haben. Eine ungleichmäßige Dichte macht die Mathematik, die zur Berechnung der erforderlichen Rotation und des Verhaltens eines starren Körpers erforderlich ist, viel zu kompliziert. Wenn sich der Punkt, der einen starren Körper darstellt, nicht am COM befindet, werden die Berechnungen bezüglich \(r\) völlig ungenau.

Trägheit

In zwei Dimensionen dreht sich ein Objekt um die imaginäre z-Achse. Diese Drehung kann ziemlich schwierig sein, je nachdem, wie viel Masse ein Objekt hat und wie weit die Masse des Objekts vom COM entfernt ist. Ein Kreis mit der Masse eines langen dünnen Stabes lässt sich leichter drehen als der Stab. Dieser Faktor "Schwierigkeit beim Drehen" kann man sich als das Trägheitsmoment eines Objekts vorstellen.

Trägheit ist gewissermaßen die Rotationsmasse eines Objekts. Je mehr Trägheit etwas hat, desto schwieriger ist es, es zum Drehen zu bringen.

Wenn man dies weiß, könnte man die Trägheit eines Objekts im Körper als das gleiche Format wie Masse speichern. Es wäre ratsam, auch den Kehrwert dieses Trägheitswerts zu speichern, wobei darauf zu achten ist, dass keine Division durch Null durchgeführt wird. Weitere Informationen zu Masse und inverser Masse finden Sie in den vorherigen Artikeln dieser Serie.

Integration

Jeder starre Körper benötigt einige weitere Felder, um Rotationsinformationen zu speichern. Hier ist ein kurzes Beispiel für eine Struktur, die zusätzliche Daten enthält:

Die Integration von Winkelgeschwindigkeit und Orientierung eines Körpers ist der Integration von Geschwindigkeit und Beschleunigung sehr ähnlich. Hier ist ein kurzes Codebeispiel, um zu zeigen, wie es gemacht wird (Hinweis: Details zur Integration wurden in einem früheren Artikel behandelt):

Mit der geringen Menge an Informationen, die bisher angezeigt wurden, sollten Sie in der Lage sein, verschiedene Dinge auf dem Bildschirm ohne Probleme zu drehen. Mit nur wenigen Codezeilen kann etwas ziemlich Beeindruckendes konstruiert werden, indem möglicherweise eine Form in die Luft geworfen wird, während sie sich um den COM dreht, während die Schwerkraft sie nach unten zieht, um einen bogenförmigen Fahrweg zu bilden.

Mat22

Die Orientierung sollte als einzelner Bogenmaßwert gespeichert werden, wie oben gezeigt, obwohl die Verwendung einer kleinen Rotationsmatrix für bestimmte Formen oft eine viel bessere Wahl sein kann.

Ein gutes Beispiel ist die Oriented Bounding Box (OBB). Der OBB besteht aus einer Breiten- und Höhenausdehnung, die beide durch Vektoren dargestellt werden können. Diese beiden Ausdehnungsvektoren können dann durch eine Zwei-mal-Zwei-Rotationsmatrix gedreht werden, um die Achsen eines OBB darzustellen.

Ich schlage vor, eine Mat22-Matrixklasse zu erstellen, die zu jeder von Ihnen verwendeten Mathematikbibliothek hinzugefügt wird. Ich selbst verwende eine kleine benutzerdefinierte Mathematikbibliothek, die in der Open-Source-Demo enthalten ist. Hier ist ein Beispiel, wie ein solches Objekt aussehen kann:

Einige nützliche Operationen sind: Konstruktion aus Winkel, Konstruktion aus Spaltenvektoren, Transponieren, Multiplizieren mit Vec2, Multiplizieren mit einem anderen Mat22, Absolutwert.

Die letzte nützliche Funktion besteht darin, entweder die x- oder die y-Spalte aus einem Vektor abrufen zu können. Die Spaltenfunktion würde ungefähr so aussehen:

Diese Technik ist nützlich zum Abrufen eines Einheitsvektors entlang einer Rotationsachse, entweder der x- oder y-Achse. Außerdem kann eine Zwei-mal-Zwei-Matrix aus zwei orthogonalen Einheitsvektoren konstruiert werden, da jeder Vektor direkt in die Zeilen eingefügt werden kann. Obwohl diese Konstruktionsmethode für 2D-Physik-Engines etwas ungewöhnlich ist, kann es dennoch sehr nützlich sein, zu verstehen, wie Rotationen und Matrizen im Allgemeinen funktionieren.

Dieser Konstruktor könnte etwa so aussehen:

Da die wichtigste Operation einer Rotationsmatrix darin besteht, Drehungen basierend auf einem Winkel durchzuführen, ist es wichtig, eine Matrix aus einem Winkel zu konstruieren und einen Vektor mit dieser Matrix zu multiplizieren (um den Vektor gegen den Uhrzeigersinn um den Winkel zu drehen Matrix wurde konstruiert mit):

Der Kürze halber werde ich nicht herleiten, warum die Rotationsmatrix gegen den Uhrzeigersinn die Form hat:

Es ist jedoch wichtig, zumindest zu wissen, dass dies die Form der Rotationsmatrix ist. Weitere Informationen zu Rotationsmatrizen finden Sie auf der Wikipedia-Seite.


Verwandeln in eine Basis

Es ist wichtig, den Unterschied zwischen Modell- und Weltraum zu verstehen. Der Modellraum ist das lokale Koordinatensystem einer physikalischen Form. Der Ursprung liegt am COM und die Ausrichtung des Koordinatensystems ist an den Achsen der Form selbst ausgerichtet.

Um eine Form in einen Weltraum zu verwandeln, muss sie gedreht und übersetzt werden. Die Drehung muss zuerst erfolgen, da immer um den Ursprung gedreht wird. Da sich das Objekt im Modellbereich befindet (Ursprung bei COM), dreht sich die Drehung um den COM der Form. Eine Drehung würde mit einer Mat22-Matrix erfolgen. Im Beispielcode haben Orientierungsmatrizen den Namen u.

Nachdem die Drehung durchgeführt wurde, kann das Objekt dann durch Vektoraddition in seine Position in der Welt verschoben werden.

Sobald sich ein Objekt im Weltraum befindet, kann es durch inverse Transformationen in den Modellraum eines völlig anderen Objekts übersetzt werden. Dazu wird eine inverse Rotation gefolgt von einer inversen Translation verwendet. So viel Mathematik wird bei der Kollisionserkennung vereinfacht!

Inverse transformation from world space to model space of the red polygon.Inverse transformation from world space to model space of the red polygon.Inverse transformation from world space to model space of the red polygon.
Inverse Transformation (von links nach rechts) vom Weltraum zum Modellraum des roten Polygons.

Wenn die inverse Transformation des roten Objekts sowohl auf das rote als auch auf das blaue Polygon angewendet wird, wie in der obigen Abbildung zu sehen ist, kann ein Kollisionserkennungstest auf die Form eines AABB- vs. OBB-Tests reduziert werden, anstatt eine komplexe Mathematik zwischen zwei zu berechnen orientierte Formen.

In einem Großteil des Beispielquellcodes werden Vertices aus allen möglichen Gründen ständig von Modell zu Welt und wieder zurück zum Modell transformiert. Sie sollten genau wissen, was dies bedeutet, um den Code für die Erkennung von Beispielkollisionen zu verstehen.


Kollisionserkennung und Verteilergenerierung

In diesem Abschnitt werde ich kurze Umrisse von Polygon- und Kreiskollisionen vorstellen. Ausführlichere Implementierungsdetails finden Sie im Beispielquellcode.

Polygon zu Polygon

Beginnen wir mit der komplexesten Kollisionserkennungsroutine in dieser gesamten Artikelserie. Die Idee, die Kollision zwischen zwei Polygonen zu überprüfen, wird (meiner Meinung nach) am besten mit dem Separating Axis Theorem (SAT) durchgeführt.

Anstatt die Ausdehnungen jedes Polygons aufeinander zu projizieren, gibt es jedoch eine etwas neuere und effizientere Methode, wie von Dirk Gregorius in seiner GDC-Lecture 2013 beschrieben (Folien hier kostenlos erhältlich).

Das erste, was gelernt werden muss, ist das Konzept der Stützpunkte.

Support-Punkte

Der Stützpunkt eines Polygons ist der Scheitelpunkt, der in einer bestimmten Richtung am weitesten entfernt ist. Wenn zwei Scheitelpunkte entlang der angegebenen Richtung gleiche Abstände haben, ist einer von beiden akzeptabel.

Um einen Stützpunkt zu berechnen, muss das Skalarprodukt verwendet werden, um einen vorzeichenbehafteten Abstand entlang einer bestimmten Richtung zu finden. Da dies sehr einfach ist, zeige ich in diesem Artikel ein kurzes Beispiel:

Das Punktprodukt wird an jedem Scheitelpunkt verwendet. Das Skalarprodukt stellt einen vorzeichenbehafteten Abstand in eine gegebene Richtung dar, sodass der Scheitelpunkt mit dem größten projizierten Abstand der Scheitelpunkt wäre, der zurückgegeben werden soll. Diese Operation wird im Modellraum des gegebenen Polygons innerhalb der Beispiel-Engine durchgeführt.

Trennungsachse finden

Durch das Konzept der Stützpunkte kann eine Suche nach der Trennachse zwischen zwei Polygonen (Polygon A und Polygon B) durchgeführt werden. Die Idee dieser Suche besteht darin, alle Flächen des Polygons A zu durchlaufen und den Stützpunkt in der negativen Normalen zu dieser Fläche zu finden.

SupportPoints

Im obigen Bild werden zwei Stützpunkte angezeigt: einer an jedem Objekt. Die blaue Normale würde dem Stützpunkt auf dem anderen Polygon als dem am weitesten entfernten Scheitelpunkt in der entgegengesetzten Richtung der blauen Normalen entsprechen. In ähnlicher Weise würde die rote Normale verwendet, um den Stützpunkt am Ende des roten Pfeils zu finden.

Der Abstand von jedem Stützpunkt zur aktuellen Wand wäre die vorzeichenbehaftete Durchdringung. Durch Speichern der größten Entfernung kann eine mögliche minimale Eindringachse aufgezeichnet werden.

Hier ist eine Beispielfunktion aus dem Beispielquellcode, die die mögliche Achse der minimalen Penetration mithilfe der GetSupport-Funktion ermittelt:

Da diese Funktion die größte Durchdringung zurückgibt, bedeutet dies, dass sich die beiden Formen nicht überlappen, wenn diese Durchdringung positiv ist (eine negative Durchdringung würde bedeuten, dass keine Trennachse vorhanden ist).

Diese Funktion muss zweimal aufgerufen werden, wobei A- und B-Objekte bei jedem Aufruf umgedreht werden.

Clipping-Vorfall und Referenzfläche

Von hier aus müssen die Einfalls- und Referenzfläche identifiziert werden, und die Einfallsfläche muss an den Seitenebenen der Referenzfläche beschnitten werden. Dies ist eine ziemlich nicht triviale Operation, obwohl Erin Catto (Erfinder von Box2D und der gesamten Physik, die derzeit von Blizzard verwendet wird) einige großartige Folien erstellt hat, die dieses Thema im Detail behandeln.

Dieses Clipping erzeugt zwei potentielle Kontaktpunkte. Alle Kontaktpunkte hinter der Referenzfläche können als Kontaktpunkte betrachtet werden.

Neben den Folien von Erin Catto sind in der Sample-Engine auch die Clipping-Routinen als Beispiel implementiert.

Kreis zu Polygon

Die Kreis-Polygon-Kollisionsroutine ist viel einfacher als die Polygon-Polygon-Kollisionserkennung. Zunächst wird die dem Mittelpunkt des Kreises am nächsten liegende Fläche des Polygons auf ähnliche Weise berechnet wie die Verwendung von Stützpunkten aus dem vorherigen Abschnitt: Durch Schleifen über jede Flächennormale des Polygons und Ermitteln des Abstands vom Mittelpunkt des Kreises zur Fläche.

Befindet sich der Kreismittelpunkt hinter dieser nächstgelegenen Fläche, können spezifische Kontaktinformationen generiert und die Routine sofort beendet werden.

Nachdem die nächstgelegene Fläche identifiziert wurde, geht der Test in einen Liniensegment-gegen-Kreis-Test über. Ein Liniensegment hat drei interessante Regionen, die Voronoi-Regionen genannt werden. Untersuchen Sie das folgende Diagramm:

Voronoi regions of a line segment.Voronoi regions of a line segment.Voronoi regions of a line segment.
Voronoi-Regionen eines Liniensegments.

Intuitiv lassen sich je nach Lage des Kreismittelpunkts unterschiedliche Kontaktinformationen ableiten. Stellen Sie sich vor, der Mittelpunkt des Kreises liegt auf einem der Scheitelpunkte. Dies bedeutet, dass der dem Mittelpunkt des Kreises am nächsten liegende Punkt ein Kantenscheitelpunkt ist und die richtige Kollisionsnormale ein Vektor von diesem Scheitelpunkt zum Kreismittelpunkt ist.

Wenn sich der Kreis innerhalb des Flächenbereichs befindet, ist der dem Kreismittelpunkt am nächsten liegende Punkt des Segments die Mittelpunktprojektion des Kreises auf das Segment. Die Kollisionsnormale ist nur die Gesichtsnormale.

Um zu berechnen, in welcher Voronoi-Region der Kreis liegt, verwenden wir das Skalarprodukt zwischen ein paar Scheitelpunkten. Die Idee besteht darin, ein imaginäres Dreieck zu erstellen und zu testen, ob der Winkel der mit dem Scheitelpunkt des Segments konstruierten Ecke über oder unter 90 Grad liegt. Für jeden Scheitelpunkt des Liniensegments wird ein Dreieck erstellt.

Projecting vector from edge vertex to circle center onto the edge.Projecting vector from edge vertex to circle center onto the edge.Projecting vector from edge vertex to circle center onto the edge.
Projizieren des Vektors vom Kantenscheitelpunkt zum Kreismittelpunkt auf die Kante.

Ein Wert über 90 Grad bedeutet, dass ein Kantenbereich identifiziert wurde. Wenn keiner der Kantenscheitelwinkel eines Dreiecks über 90 Grad liegt, muss der Mittelpunkt des Kreises auf das Segment selbst projiziert werden, um vielfältige Informationen zu erzeugen. Wie im Bild oben zu sehen ist, ist die Voronoi-Region, in der der Kreis liegt, bekannt, wenn der Vektor vom Kantenscheitelpunkt zum Kreismittelpunkt, der mit dem Kantenvektor selbst gepunktet ist, negativ ist.

Glücklicherweise kann das Punktprodukt verwendet werden, um eine Projektion mit Vorzeichen zu berechnen, und dieses Vorzeichen ist negativ, wenn es über 90 Grad liegt, und positiv, wenn es darunter liegt.


Kollisionsauflösung

Es ist wieder soweit: Wir kehren zum dritten und letzten Mal zu unserem Impulsauflösungscode zurück. Inzwischen sollten Sie sich damit wohlfühlen, einen eigenen Auflösungscode zu schreiben, der Auflösungsimpulse zusammen mit Reibungsimpulsen berechnet und auch eine lineare Projektion durchführen kann, um die Restpenetration aufzulösen.

Sowohl zur Reibungs- als auch zur Eindringungsauflösung müssen Rotationskomponenten hinzugefügt werden. Etwas Energie wird in Winkelgeschwindigkeit umgewandelt.

Hier ist unsere Impulsauflösung, wie wir sie aus dem vorherigen Artikel über Reibung hinterlassen haben:

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

Wenn wir Rotationskomponenten hinzufügen, sieht die endgültige Gleichung wie folgt aus:

\[ Equation 6: \\ j = \frac{-(1 + e)((V^{A} - V^{B}) * t)}{\frac{1}{mass^{A}} + \frac{1}{mass^{B}} + \frac{(r^{A} \times t)^{2}}{I^{A}} + \frac{(r^{B} \times t)^{2}}{I^{B}}} \]

In der obigen Gleichung ist \(r\) wieder ein "Radius", wie in einem Vektor vom COM eines Objekts zum Kontaktpunkt. Eine ausführlichere Ableitung dieser Gleichung finden Sie auf Chris Heckers Website.

Es ist wichtig zu wissen, dass die Geschwindigkeit eines bestimmten Punktes auf einem Objekt ist:

\[ Equation 7: \\ V' = V + \omega \times r \]

Die Anwendung von Impulsen ändert sich geringfügig, um die Rotationsterme zu berücksichtigen:


Abschluss

Damit ist der letzte Artikel dieser Reihe abgeschlossen. Inzwischen wurden einige Themen behandelt, darunter impulsbasierte Auflösung, Mannigfaltigkeitserzeugung, Reibung und Orientierung, alles in zwei Dimensionen.

Wenn Sie es bis hierher geschafft haben, muss ich Ihnen gratulieren! Die Programmierung von Physik-Engines für Spiele ist ein äußerst schwieriges Studiengebiet. Ich wünsche allen Lesern viel Glück, und bitte zögern Sie nicht, unten Kommentare zu schreiben oder Fragen zu stellen.

Advertisement
Did you find this post useful?
Want a weekly email summary?
Subscribe below and we’ll send you a weekly email summary of all new Game Development tutorials. Never miss out on learning about the next big thing.
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.