SAT-Tutorial: 2D-Kollision mit Seperations-Achsen

[.chicken]

Während der Arbeit an meiner 2D-Sprite-Engine stiess ich auf das Problem der Kollision:
Ich brauchte also eine schnelle und einfache Möglichkeit meine rechteckigen (rotierten!) Sprites auf eine Kollision zu prüfen.
Ich stiess auf das sogenannte "Seperation Axis Theorem". Trotz einigen (meist englischsprachigen) Tutorials, verstand ich das Prinzip aber nur zur Hälfte und wusste nicht wie ich es umsetzen sollte.
Um Leuten nach mir die lange Suche nach Erklärungen zu ersparen, möchte ich im folgenden also eine kurze Erklärung liefern.

Hierbei werde ich keine Codebeispiele liefern, sondern nur versuchen die Theorie dahinter möglichst simpel zu veranschaulichen. Habt ihr das System allerdings einmal verstanden, ist eine entsprechende Funktion sehr schnell geschrieben.

Die Idee
Die Idee hinter der Kollisionserkennung ist, dass zwei Objekte die durch eine Ebene voneinander getrennt werden können nicht kollidieren!
Bedeutet: Wenn ich zwischen zwei Rechtecke (oder auch andere Polygone) eine Linie malen kann, ohne dass sie die Rechtecke berührt, dann kollidieren diese Rechtecke nicht.
Es wird also versucht diese Ebene zu finden.

Die Durchführung
Was müssen wir also tun? Grob gesagt, gehen wir von beiden Rechtecken/Polygonen alle Seiten durch, bilden die Normalen der Seiten (also die Geraden, die im rechten Winkel zu der Seite verlaufen), und testen dann, ob die Polygone sich, wenn man nur ihre Länge auf der Normalen betrachtet (Projektion genannt), überschneiden.
Sofern sich die Polygone auf allen getesteten Normalen überschneiden, findet eine Kollision statt, wird nur eine Normale gefunden, auf der kein Schnitt stattfindet, gibt es auch keine Kollision und der Test kann sofort abgebrochen werden. Durch den häufig frühen Abbruch wird dieser Algorithmus sehr schnell.
Ich habe zwei Beispielbilder angehängt.

Wie genau machen wir das nun?
Die Lösung ist erstaunlich simpel:
Zuerst müssen wir die Seiten des Polygons berechnen. Das machen wir, indem wir die beiden Vektoren/Punkte, die die Seite begrenzen, voneinander subtrahieren.

Zitat:

V1 = (0/10)
V2 = (4/-5)
V2 - V1 = (4 - 0/ -5 - 10) = (4 / - 15)

So, nun haben wir die Seite. Die Normale berechnen wir folgendermassen:

Zitat:

V = (0/10)
N = -(10/0)

Richtig. Wir kehren den Vektor einfach um und negativieren ihn.

Ok, als nächstes müssen wir nurnoch die Polygone auf die Normale projezieren und auf Schnitt prüfen.
Ist simpler als es sich anhört. Es reicht nämlich, wenn wir dazu das sogenannte DotProduct (sorry, den deutschen Namen habe ich nicht zur Hand ^^) jedes Vektors beider Polygone mit dem Vektor der Normalen bilden.
Außerdem brauchen wir für jedes Polygon nur die minimale und maximale Projektion um den Schnitt zu prüfen.

Zitat:

DotProduct (DP) = V1.X * V2.X + V1.Y * V2.Y

V2 ist hierbei die Normale und V1 ein Vektor eines Polygons.
Wir bilden also einen Max und einen Min-Wert für beide Polygone und prüfen für jeden Vektor ob er größer/kleiner ist als der bisherige Max/Min-Wert.

Haben wir diese beiden Werte für beide Polygone, dann prüfen wir einfach ob

Zitat:

Polygon1-Min > Polygon2-Max

oder

Zitat:

Polygon1-Max < Polygon2-Min

Dann würden die Polygone sicht nicht überschneiden und der Test könnte abgebrochen werden. Gibt diese Prüfung "False" zurück, dann überschneiden sich die Polygone auf der Normalen und der Test muss weitergeführt werden, bis alle Normalen getestet, oder einmal False zurückgegeben wurde.

Klingt nach ziemlich viel Arbeit um nur eine der Normalen zu testen, mit einer Schleife lässt sich das aber sehr schnell auch für die kompletten beiden Polygone testen. Nicht vergessen mit "Exit" den Test zu beenden, wenn kein Schnitt gefunden wird. Die Performance wird sich dadurch merklich steigern.

Das Ergebnis:
Als Ergebnis kann man sich einfach eine Boolean Variable übergeben lassen. Man kann die Funktion aber auch noch erweitern und sich als Rückgabe genaue Schnittpunkte oder ähnliches zurückgeben lassen.
Das überlasse ich aber euch.

Damit wär der Test beendet :)

So, ich hoffe euch mit diesem Tutorial geholfen zu haben. Ich würde mich über Feedback wirklich freuen.
Wenn ihr noch Fragen habt, dann stellt sie bitte. Ich habe versucht es möglichst simpel zu erklären, aber das ist mir sicher nicht immer gelungen.