Kollisionsprüfung zweier konvexer Körper (SAT)

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.
Eckpunkte eines Dreiecks inkl. Kantenvektoren in 2D

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

  1. 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
  2. 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.
  3. 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.
  4. 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.
  5. Siehe Schritte 2 bis 3.
  6. Überschneiden sich auch hier alle Skalarproduktwerte, kollidieren die beiden Würfel.

Im folgenden Bild kann diese Prüfung anhand von zwei Dreiecken nachvollzogen werden:

Projektionen der Eckpunkte entlang aller Kantenvektoren (2D): Alle Skalarproduktwerte überschneiden sich (grün/braun außen).

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.

  1. 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.
  2. 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

Der Code (inklusive Nutzungsbeispiel) ist unter folgender URL zu finden:
https://github.com/KWEngine/KWEngine2/wiki/3D-Engine-Math-Part-02:-Collision-detection-for-oriented-bounding-boxes-(OBBs)

Ein ausführlicheres Tutorial gibt es hier:
https://dyn4j.org/2010/01/sat/

Ein Kommentar

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.