Zwei Körper schneiden sich genau dann, wenn es keine Linie gibt, die zwischen den beiden Körpern verläuft ohne einen der beiden Körper zu berühren.
Einleitung
Das „Separating Axis Theorem“ (kurz: SAT) baut auf genau dieser Erkenntnis auf. Wird auch nur eine Linie gefunden, die zwischen den beiden Körpern verläuft und keinen der beiden Körper berührt, können sich auch die beiden Körper nicht berühren.
Nun geht es ja bei der Kollisionsprüfung in Videospielen gerade darum, die Kollision zu erkennen statt eine Linie zu finden, die kontaktlos zwischen zwei Körpern verläuft.
Doch bei Videospielen geht es vor allem darum, schnelle und effiziente Algorithmen zu nutzen. Der SAT-Algorithmus ist so konzipiert, dass es viel wahrscheinlicher ist, eine solche Trennlinie zu finden und die Kollisionsprüfung somit vorzeitig abbrechen zu können. Bei hunderten von Objekten, die alle miteinander kollidieren können, ist dies ein entscheidender Vorteil.
Dieses Tutorial behandelt einen performanten Algorithmus zur Findung von Kollisionen zweier beliebig rotierter und skalierter Würfel (oriented bounding boxes).
Was wird pro Würfel benötigt?
- Die Eckpunkte des Würfels (acht Stück),
- die drei normalisierten Ebenenvektoren der Würfelseiten (eigentlich sechs, aber da die Ebenenvektoren von drei dieser Seiten nur negierte Varianten sind, reichen drei: oben, rechts, vorne) und
- der Mittelpunkt des Würfels.
Im obigen Bild ist zur Vereinfachung ein zweidimensionales Dreieck abgebildet. Dort kann man die Eckpunkte und die Ebenenvektoren der Kanten erkennen. Nicht eingezeichnet ist der Mittelpunkt des Dreiecks. Der Mittelpunkt des Dreiecks wird aber eh nicht für die Erkennung der Kollision, sondern nur für die Behandlung der Kollision benötigt.
Der eigentliche Algorithmus
- Projeziere mit Hilfe des Skalarprodukts nacheinander die Eckpunkte beider Würfel entlang aller Ebenenvektoren des Würfels A. Bei jeder Projektion muss sich nur der größte und kleinste Wert gemerkt werden.
Im Detail bedeutet das:
Mit dem Ebenenvektor n1 des Würfels A werden zunächst alle Punkte P des Würfels A kombiniert:
– Sn1AP1 = An1 ∘ AP1
– Sn1AP… = An1 ∘ AP…
– Sn1APn = An1 ∘ APn
Von den acht berechneten Skalarprodukten muss nur der kleinste und der größte Wert gespeichert werden. Sechs der acht Werte werden also verworfen.
Dann werden die nächsten acht Skalarprodukte erstellt – nur, dass dieses Mal die Eckpunkte des Würfels B verwendet werden:
– Sn1BP1 = An1 ∘ BP1
– Sn1BP… = An1 ∘ BP…
– Sn1BPn = An1 ∘ BPn - Nach Schritt 1 sollten jetzt 4 relevante Werte vorliegen: Die beiden Minimalwerte und die beiden Maximalwerte. Prüfe, ob sich diese Werte überlappen!
Beispiel:
Skalarproduktwerte (min/max) für Würfel A: [0,5 ; 5,2]
Skalarproduktwerte (min/max) für Würfel B: [0,1 ; 4,8]
In diesem Beispiel würden sich die Werte im Bereich von 0,5 bis 4,8 überschneiden. - Hier folgt nun eine Entscheidung:
Wenn es auch nur eine einzige Projektion gibt, die nicht zu einer Überlappung der Werte führte, wurde bereits eine Linie gefunden, die die beiden Körper voneinander trennt. Der Algorithmus kann hier also bereits vorzeitig beendet werden.
Wenn sich die Werte jedoch überschneiden, dann wird der nächste Ebenenvektor von Würfel A genommen und erneut die Skalarprodukte aus diesem Vektor mit allen Punkten beider Würfel gebildet. Dies wird wiederholt, solange Überschneidungen vorliegen und noch nicht alle Ebenenvektoren des Würfels A durch sind. - Wenn sich die Skalarproduktwerte entlang aller Ebenenvektoren des Würfels A überschneiden, muss nun Schritt 1 wiederholt werden – nur, dass jetzt die Eckpunkte beider Würfel entlang der Ebenenvektoren von Würfel B (statt wie zuvor Würfel A) für das Skalarprodukt verwendet werden.
- Siehe Schritte 2 bis 3.
- Überschneiden sich auch hier alle Skalarproduktwerte, kollidieren die beiden Würfel.
Im folgenden Bild kann diese Prüfung anhand von zwei Dreiecken nachvollzogen werden:
Kollisionsbehandlung
In Videospielen sind Kollisionen unausweichlich – und doch möchte man anschließend oft die Objekte wieder so ausrichten, dass sie nicht mehr kollidieren (z.B. wenn die Spielfigur den Boden berührt).
Hier kann im Anschluß an die Kollisionsprüfung der „minimale Translationsvektor (MTV)“ berechnet werden.
- Der Ebenenvektor, dessen Skalarprodukt mit den Eckpunkten die kleinste Überschneidung erzeugte (im obigen Bild: b3), ist die Richtung in die einer der beiden Würfel verschoben werden muss, um die Kollision rückgängig zu machen.
- Die Größe der Überschneidung ist die Strecke, um die einer der Würfel entlang des in Schritt 1 ermittelten Ebenenvektors verschoben werden muss.
Code
Diese Hitbox-Klasse ist eine Beispiellösung und muss ggf. an die eigenen Befürfnisse angepasst werden. Die Klasse verwendet die Mathe-Klassen Vector3 und Matrix4 aus dem OpenTK.Mathematics-Namespace.
So könnte innerhalb des Codes der Aufruf aussehen:
// Aufruf an einer beliebigen Stelle mit zwei gültigen
// und vorliegenden Instanzen A und B der Hitbox-Klasse.
// [Sowohl Instanz A als auch Instanz B müssen also zu diesem
// Zeitpunkt bereits über einzigartige Punkte (Vertices) und
// Ebenenvektoren (Normals) verfügen.]
bool hitboxesIntersect = TestIntersection(A, B, out Vector3 MTV);
if(hitboxesIntersect)
{
Console.WriteLine("Hitbox A schneidet Hitbox B und müsste sich " +
"um " + MTV.ToString() + " Einheiten bewegen, " +
"um nicht mehr mit B zu kollidieren.");
}
Und dies ist der Beispiel-Quellcode der dazu benötigten Hitbox-Klasse:
public class Hitbox
{
private Vector3 _centerCurrent;
private Vector3[] _verticesCurrent;
private Vector3[] _normalsCurrent;
private Vector3[] _centerMesh;
private Vector3[] _verticesMesh;
private Vector3[] _normalsMesh;
// Eine neue Hitbox bekommt alle einzigartigen Punkte
// des Mesh und alle einzigartigen Ebenenvektoren
// übergeben. Die Ebenenvektoren müssen normalisiert sein.
public Hitbox(Vector3[] uniqueVertices, Vector3[] uniqueNormals, Vector3 centerOfMesh)
{
// Übernehme die Punkte und Ebenenvektoren:
_verticesMesh = uniqueVertices;
_normalsMesh = uniqueNormals;
// Lege Speicher für Kopien der Punkte und
// Ebenenvektoren an:
_verticesCurrent = new Vector3[_verticesMesh.Length];
_normalsCurrent = new Vector3[_normalsMesh.Length];
// Das Zentrum ist der Durchschnittswert aller
// Punkte in _verticesMesh:
_centerMesh = centerOfMesh;
_centerCurrent = centerOfMesh;
}
// Aktualisiert die Eckpunkte und Ebenenvektoren
// der Hitbox gemäß der in der Model-Matrix
// enthaltenen Angaben zu Skalierung, Rotation
// und Position (Translation):
public void Update(Matrix4 modelMatrix)
{
// Aktualisiere alle Punkte und Ebenenvektoren in einer Schleife:
for(int i = 0; i < _verticesMesh.Length; i++)
{
if(i < _normalsMesh.Length)
{
Vector3.TransformNormal(_normalsMesh[i], modelMatrix, out _normalsCurrent[i]);
_normalsCurrent[i].Normalize();
}
Vector3.TransformPosition(_verticesMesh[i], modelMatrix, out _verticesCurrent[i]);
}
// Der Mittelpunkt der Hitbox muss ebenfalls aktualisiert werden:
Vector3.TransformPosition(_centerMesh, modelMatrix, out _centerCurrent);
}
// Diese Methode bekommt zwei beliebige Hitbox-Instanzen übergeben
// und gibt 'true' zurück, wenn sich diese Hitboxen überschneiden.
// Als zusätzlichen out-Parameter wird eine Vector3-Instanz zurück-
// gegeben, die den 'minimalen Translationsvektor' (MTV) abbildet.
// Der MTV gibt an, welche Bewegung Hitbox a ausführen müsste, um nicht
// mehr zu kollidieren.
public static bool TestIntersection(Hitbox a, Hitbox b, out Vector3 mtv)
{
// Hier wird später die kürzeste Distanz für den MTV gespeichert:
float mtvDistance = float.MaxValue;
// Falls keine Kollision gefunden wird, bleibt der MTV auf 0:
mtv = new Vector3(0, 0, 0);
// In der ersten Schleife werden alle Ebenenvektoren von Hitbox a
// verwendet, um die Punkte von Hitbox a und b zu projizieren und
// zu prüfen, ob sich die Projektionen überschneiden. Wenn ja,
// muss der Translationsvektor für diese Überschneidung ermittelt
// werden. Ist dieser Vektor der bisher kleinste Vektor, wird dieser
// automatisch (temporär) zum MTV:
for (int i = 0; i < a._normalsCurrent.Length; i++)
{
float shape1Min, shape1Max, shape2Min, shape2Max;
// Projektion durchführen und schauen, wo die projizierten
// Punkte entlang des Ebenenvektors landen:
SATTest(ref a._normalsCurrent[i], a._verticesCurrent, out shape1Min, out shape1Max);
SATTest(ref a._normalsCurrent[i], b._verticesCurrent, out shape2Min, out shape2Max);
// Wenn sich die Projektionen beider Formen nicht überlappen,
// schneiden sie sich nicht. Der Algorithmus kann also vorzeitig
// abgebrochen werden:
if (!DoesOverlap(shape1Min, shape1Max, shape2Min, shape2Max))
{
return false;
}
else
{
// Wenn sich die Projektionen doch schneiden, muss ermittelt
// werden, wie groß diese Überschneidung ist. Daraus entsteht
// der MTV für diese Projektion:
CalculateOverlap(
ref a._normals[i],
ref shape1Min,
ref shape1Max,
ref shape2Min,
ref shape2Max,
ref mtvDistance,
ref mtv,
ref a._centerCurrent,
ref b._centerCurrent
);
}
}
// Gleiches Spiel erneut, aber dieses mal für alle
// Ebenenvektoren von Hitbox b:
for (int i = 0; i < b._normalsCurrent.Length; i++)
{
float shape1Min, shape1Max, shape2Min, shape2Max;
SATTest(ref b._normalsCurrent[i], a._verticesCurrent, out shape1Min, out shape1Max);
SATTest(ref b._normalsCurrent[i], b._verticesCurrent, out shape2Min, out shape2Max);
if (!DoesOverlap(shape1Min, shape1Max, shape2Min, shape2Max))
{
return false;
}
else
{
CalculateOverlap(
ref b._normals[i],
ref shape1Min,
ref shape1Max,
ref shape2Min,
ref shape2Max,
ref mtvDistance,
ref mtv,
ref a._centerCurrent,
ref b._centerCurrent
);
}
}
return true;
}
// Helfermethode, die ermittelt, wie weit sich die beiden Hitbox-
// Projektionen überlappen:
private static bool CalculateOverlap(
ref Vector3 normal,
ref float shape1Min,
ref float shape1Max,
ref float shape2Min,
ref float shape2Max,
ref float mtvDistance,
ref Vector3 mtv,
ref Vector3 centerA,
ref Vector3 centerB)
{
// Beinhaltet nachher die Länge des Translationsvektors:
float intersectionDepthScaled;
// Diese if-Bedingungen prüfen verschiedene Fälle:
// (z.B.: "liegt eine der Projektionen komplett in der anderen?")
if (shape1Min < shape2Min)
{
if (shape1Max > shape2Max)
{
float diff1 = shape1Max - shape2Max;
float diff2 = shape2Min - shape1Min;
if (diff1 > diff2)
{
intersectionDepthScaled = shape2Max - shape1Min;
}
else
{
intersectionDepthScaled = shape2Min - shape1Max;
}
}
else
{
intersectionDepthScaled = shape1Max - shape2Min; // Standardfall
}
}
else
{
if (shape1Max < shape2Max)
{
float diff1 = shape2Max - shape1Max;
float diff2 = shape1Min - shape2Min;
if (diff1 > diff2)
{
intersectionDepthScaled = shape1Max - shape2Min;
}
else
{
intersectionDepthScaled = shape1Min - shape2Max;
}
}
else
{
intersectionDepthScaled = shape1Min - shape2Max; // Standardfall
}
}
// Hier wird die Überschneidungslänge ermittelt
// (allerdings das Quadrat davon, da es performanter ist):
float intersectionDepthSquared = (intersectionDepthScaled * intersectionDepthScaled);
// Wenn die ermittelte Länge kürzer ist als der bisher als
// kürzester Translationsvektor, dann ist das der neue MTV:
if (intersectionDepthSquared < mtvDistance || mtvDistance < 0)
{
mtvDistance = intersectionDepthSquared;
mtv = normal * intersectionDepthScaled;
float oppositeDirection = Vector3.Dot(centerA - centerB, mtv);
mtv = mtv * (oppositeDirection < 0 ? -1.0f : 1.0f);
return true;
}
return false;
}
// Helfermethode, die prüft, ob sich die Koordinaten überschneiden:
private static bool Overlaps(float min1, float max1, float min2, float max2)
{
return IsBetweenOrdered(min2, min1, max1) || IsBetweenOrdered(min1, min2, max2);
}
// Helfermethode zur Messung einer Überschneidung:
private static bool IsBetweenOrdered(float val, float lowerBound, float upperBound)
{
return lowerBound <= val && val <= upperBound;
}
// Projiziert die Punkte aus ptSet entlang des in axis angegebenen
// Ebenenvektors und gibt zurück, wie lang die Projektion ist:
private static void SATTest(ref Vector3 axis, Vector3[] ptSet, out float minAlong, out float maxAlong)
{
minAlong = float.MaxValue;
maxAlong = float.MinValue;
for (int i = 0; i < ptSet.Length; i++)
{
float dotVal = Vector3.Dot(ptSet[i], axis);
if (dotVal < minAlong) minAlong = dotVal;
if (dotVal > maxAlong) maxAlong = dotVal;
}
}
}
Weitere Informationen
Ein ausführlicheres Tutorial gibt es hier:
https://dyn4j.org/2010/01/sat/
Schreibe einen Kommentar