Tutorial Separating Axis Theorem
Inhaltsverzeichnis
Kollisionserkennung
von Polygonen mit dem Separating Axis Theorem
Vorwort
In diesem Tutorial möchte ich eine schnelle Variante zur Kollision zweier konvexer Polygone erläutern. Diese kann nachträglich für konkave Polygone und andere Objekte wie Kreise und abgerundete Objekte verwendet werden. Um den mathematischen Hintergrund zu verstehen, ist es sinnvoll ein wenig Kenntnis in Vektorrechnung zu haben.
Kollision zweier Polygone
Die Theorie
Das Separating Axis Theorem (kurz: SAT) besagt, dass zwei Polygone sich nicht schneiden, wenn es möglich ist, eine Gerade zu finden, die zwischen den beiden liegt. Nun gibt es unendlich viele Geraden die man testen könnte... Glücklicherweise kann man sich hier auf eine überschaubare Zahl beschränken, denn man braucht nur die Anzahl der Seiten beider Polygone. Bei einem Viereck wären das vier, bei einem Dreieck drei, etc. Hat man die Eckpunkte des Polygons als Vektoren (Ortsvektoren) gegeben, kann man durch Subtraktion zweier Ortsvektoren den Vektor bestimmen der zu der Seite gehört, die von den beiden Vektoren aufgespannt wird.
Auf dem Bild rechts ist ein Beispiel zu sehen. Dort ist ein Quadrat, die grünen Striche bezeichnen die Ortsvektoren der Eckpunkte, der rote Strich ist die berechnete Seite. Was wir aber brauchen ist der blaue Strich, das ist die Normale der Seite. Die Normale berechnet sich folgendermaßen:
die Koordinaten werden vertauscht und eine von beiden wird negiert. Der Vektor muss dann noch normalisiert werden, sodass er die Länge 1 erhält. Jetzt müssen beide Polygone auf diesen Vektor projeziert werden, denn dadurch haben wir ein Eindimensionales Abbild unserer Polygone und können mittels eines einfachen Vergleichs überprüfen, ob sich die beiden 1D-Strecken schneiden. Sollte ein Fall eintreffen bei dem kein Schnitt stattfindet, dann kollidieren die beiden Polygone nicht und die Prozedur kann abgebrochen werden. Nun zur Projektion:
Auf dem linken Bild sieht man, wie beide Polygone auf die Gerade projeziert werden, der pinke Bereich zeigt die Schnittmenge an. In diesem Fall ist die Gerade die Normale der linken oder rechten Seite des Quadrats. Auf dem Bild rechts ist der Fall dargestellt, dass keine Kollision stattfindet, demzufolge gibt es auch keine Schnittmenge auf der Geraden. Dazu ist allerdings zu sagen, dass die Gerade keine räumliche Position hat. So wie Vektoren auch keine Positionen haben, Vektoren sind lediglich verschiebungsanweisungen und unsere "Gerade" wie ich sie hier nenne, ist auch nur ein Vektor, denn wo sie liegt ist letzten endes egal, da wir ja ein eindimensionales Ergebnis anstreben.
Für die Projektion eines Vektors auf einen anderen verwenden wir das Skalarprodukt, bei diesem kommt ein Zahlenwert heraus, der die Position des Eckpunktes auf unserer 1D-Geraden darstellt. Haben wir sämtliche Punkte projeziert, so müssen wir für die jeweiligen Polygone noch jeweils den kleinsten und größten Wert heraussuchen, damit wir zwei Strecken erhalten. Diese werden dann auf Schnitt geprüft und das wars.
Zusammenfassung
- Jedes der beiden Polygone durchgehen und alle nötigen Geraden aus den Normalen der Seitenflächen bestimmen
- Jeden Eckpunkt jedes Polygons auf diese Geraden Projezieren
- Die kleinsten und größten Werte ermitteln und auf Schnitt prüfen
- Tritt der Fall auf, dass kein Schnitt statt findet, so kann sofort abgebrochen werden, es findet keine Kollision statt.
Der Code
Um bei so vielen Vektoroperationen nicht völlig durcheinander zu geraten und die Übersicht zu verlieren (was dabei durchaus mal passieren kann), ist es es sinnvoll, sich eine Unit zu schreiben, die einem die Vektorrechnung abnimmt. Im weiteren Verlauf des Tutorials werde ich folgende Unit benutzen:
// Unit Vectors
(**************************************************
- Enthält: TVector2f
**************************************************)
unit Vectors;
interface
type
// 2D Vektor
TVector2f = record
X, Y: Extended;
end;
// Zwei extendeds in einen TVector2f umwandeln
function To_v2f(X, Y: extended): TVector2f;
// Zwei Vektoren addieren
function v2f_Add(V1, V2: TVector2f): TVector2f;
// Einen Vektor von einem anderen subtrahieren
function v2f_Sub(V1, V2: TVector2f): TVector2f;
// Einen Vektor skalieren
function v2f_Scale(V: TVector2f; Scalar: extended): TVector2f;
// Ermittelt die Länge eines Vektors
function v2f_Length(V: TVector2f): extended;
// Normalisiert einen Vektor (sodass v2f_length = 1)
function v2f_Normalize(V: TVector2f): TVector2f;
// Ermittelt ds Skalarprodukt
function v2f_DotProduct(V1, V2: TVector2f): extended;
implementation
function To_v2f(X, Y: extended): TVector2f;
begin
Result.X := X;
Result.Y := Y;
end;
function v2f_Add(V1, V2: TVector2f): TVector2f;
begin
Result.X := V1.X + V2.X;
Result.Y := V1.Y + V2.Y;
end;
function v2f_Sub(V1, V2: TVector2f): TVector2f;
begin
Result.X := V1.X - V2.X;
Result.Y := V1.Y - V2.Y;
end;
function v2f_Scale(V: TVector2f; Scalar: extended): TVector2f;
begin
Result.X := V.X * Scalar;
Result.Y := V.Y * Scalar;
end;
function v2f_Length(V: TVector2f): extended;
begin
Result := sqrt(V.X * V.X + V.Y * V.Y);
end;
function v2f_Normalize(V: TVector2f): TVector2f;
var
L: extended;
begin
L := v2f_Length(V);
if L = 0 then
L := 1;
Result := v2f_Scale(V, 1 / L);
end;
function v2f_DotProduct(V1, V2: TVector2f): extended;
begin
Result := V1.X * V2.X + V1.Y * V2.Y;
end;
end.
Jedoch schadet es nicht, sich eine eigene zu schreiben, um seine Kenntnisse in Sachen Vektorrechnung ein wenig zu festigen. Jetzt benötigen wir eine Klasse für unsere Polygone. Die einzelnen Eckpunkte der Polygone werden nicht etwa absolut (also in Weltkoordinaten), sondern relativ zu einem Punkt angegeben, so fällt es leichter, das Polygon zu verschieben. Der absolute Wert kann jedoch ganz nützlich sein, um z.B. ein Polygon zu zeichnen. Als erstes definieren wir ein Array von TVector2f, denn jeder Eckpunkt ist ein Vektor und unsere Polygone sollen ja beliebig viele davon besitzen können, also:
type TV2fArray = array of TVector2f;
Dann folgt die Definition unseres Polygons:
// Polygon Klasse
TPolygon = class
private
fposition: TVector2f; // Position
fvertices: TV2fArray; // Vertices (Objektkoordinaten)
function GetVertex(n: integer): TVector2f; // Liefert die Objektkoordinaten
function GetVertexAbs(n: integer): TVector2f; // Liefert die absoluten Koordinaten
procedure SetVertex(n: integer; Value: TVector2f);// Setzt die Objektkoordinaten
function GetCount: integer; // Liefert length(fvertices)
public
procedure AddVertex(v: TVector2f); // Fügt ein Vertex hinzu
procedure AddVertexAbs(v: TVector2f); // Fügt ein Vertex mit Weltkoordinaten hinzu
procedure RemoveVertex(n: integer); // Entfernt ein Vertex
property position: TVector2f read fposition write fposition; // Position
property vertices[n: integer]: TVector2f read GetVertex write SetVertex; // Vertex Koordinaten
property vertices_abs[n: integer]: TVector2f read GetVertexAbs; // Vertex Weltkoordinaten
property Count: integer read GetCount; // siehe GetCount
end;
Unser Polygon hat jetzt eine Position und Eckpunkte, ebenfalls können wir auf absolute, sowie relative Koordinaten zugreifen. Count liefert uns die Anzahl der Ecken. [size=9][i](Eine Ecke bezeichnet man auch als Vertex, der Plural von Vertex ist Vertices.)[/i][/size] Hier sind die entsprechenden Funktionen:
procedure TPolygon.AddVertexAbs(v: TVector2f);
begin
setlength(fvertices, length(fvertices) + 1);
fvertices[high(fvertices)] := v2f_sub(v, position);
end;
procedure TPolygon.AddVertex(v: TVector2f);
begin
setlength(fvertices, length(fvertices) + 1);
fvertices[high(fvertices)] := v;
end;
procedure TPolygon.RemoveVertex(n: integer);
var
i: integer;
begin
for i := n to high(fvertices) - 1 do
fvertices[i] := fvertices[i + 1];
setlength(fvertices, length(fvertices) - 1);
end;
function TPolygon.GetVertex(n: integer): TVector2f;
begin
result := fvertices[n];
end;
function TPolygon.GetVertexAbs(n: integer): TVector2f;
begin
result := v2f_add(fvertices[n], fposition);
end;
procedure TPolygon.SetVertex(n: integer; Value: TVector2f);
begin
fvertices[n] := Value;
end;
function TPolygon.GetCount: integer;
begin
result := length(fvertices);
end;
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr. Nun folgt die Kollisionserkennung an sich:
function PolyPolyIntersect(A, B: TPolygon): boolean;
var
i, j, l: integer;
tmp, proj, voffset: TVector2f;
dp, amin, amax, bmin, bmax, d1, d2, foffset: extended;
begin
// Offset berechnen
voffset := v2f_sub(A.position, B.position);
// A - alle Projektionsgeraden ermitteln und projezieren
for i := 0 to (a.count - 1) do
begin
l := i + 1;
if l > (a.count - 1) then
l := 0;
// Berechnung der Seitenfläche
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
// Berechnet die Normale der Seitenfläche
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
// Projeziert den ersten Wert
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
// Findet den kleinsten und größten projezierten Wert für die Gerade für A
for j := 1 to (a.count - 1) do
begin
// projezieren
dp := v2f_dotproduct(a.vertices[j], proj);
if dp < amin then
amin := dp;
if dp > amax then
amax := dp;
end;
// s.o.
bmin := v2f_dotproduct(b.vertices[0], proj);
bmax := bmin;
// B
for j := 1 to (b.count - 1) do
begin
dp := v2f_dotproduct(b.vertices[j], proj);
if dp < bmin then
bmin := dp;
if dp > bmax then
bmax := dp;
end;
// 1D Kollision
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
// Wenn es keine Überschneidung gibt, abbrechen -> keine Kollision
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
end;
// B - alle Projektionsgeraden ermitteln und projezieren (s.o.)
for i := 0 to (b.count - 1) do
begin
l := i + 1;
if l > (b.count - 1) then
l := 0;
tmp := v2f_sub(b.vertices[l], b.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
for j := 1 to (a.count - 1) do
begin
dp := v2f_dotproduct(a.vertices[j], proj);
if dp < amin then
amin := dp;
if dp > amax then
amax := dp;
end;
bmin := v2f_dotproduct(b.vertices[0], proj);
bmax := bmin;
for j := 1 to (b.count - 1) do
begin
dp := v2f_dotproduct(b.vertices[j], proj);
if dp < bmin then
bmin := dp;
if dp > bmax then
bmax := dp;
end;
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
end;
// Kollision
result := true;
end;
Wie man sieht, ist der zweite Teil des Codes, mit dem ersten sogut wie identisch, der einzige Unterschied besteht darin, dass dort die Geraden aus den Vertices von B berechnet werden. Nehmen wir den Code mal auseinander:
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
Hier wird zunächst der Vektor berechnet, der für die Seitenfläche steht, durch die Schleife wird dies für alle Seitenflächen gemacht. Danach wird die Normale berechnet. proj ist dann der Vektor auf den wir unsere Vertices projezieren.
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
for j := 1 to (a.count - 1) do
begin
dp := v2f_dotproduct(a.vertices[j], proj);
if dp < amin then
amin := dp;
if dp > amax then
amax := dp;
end;
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert. Das gleiche wird für B wiederholt.
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
Da es sich bei unseren Vertexkoordinaten um Objektkoordinaten handelt, müssen die projezierten Vertices nun um die Differenz beider Polygonpositionen verschoben werden. Dies klingt zunächst einmal kompliziert, macht aber sinn. Die Alternative wäre, jeden Punkt in Weltkoordinaten (also absolute Koordinaten) umzuwandeln. Dadurch, dass wir am Anfang den Vektor zwischen den beiden Polygonen berechnen:
voffset := v2f_sub(A.position, B.position);
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
Ohne einen Vergleich kommt auch diese Kollisionsabfrage nicht aus, hier jedoch nur auf eindimensionaler Ebene. Gibt es keine Überschneidung der beiden 1D-Strecken, so kann die Prozedur abgebrochen werden, denn es gibt keine Kollision. Ist die komplette Prozedur durchgelaufen ohne abzubrechen, so wird result auf true gesetzt und eine Kollision ist bestätigt.
Kollision eines Kreises und eines Polygons
Theorie
Das Prinzip für die Kollision zweier Polygone ist denke ich jetzt klar geworden, doch was ist, wenn wir einen Kreis haben, der mit einem Polygon kollidiert ? Dieser Fall ist leicht abzuhandeln, ein Kreis hat unendlich viele Normalen, die man testen könnte, uns reichen aber die, die die Vertices des Polygons schneiden würden, sprich: die Geraden, die vom Kreismittelpunkt zu den Ecken unseres Polygons führen.
Die blauen Linien auf dem Bild sind wieder einmal die Geraden, bzw. die Achsen auf die wir projezieren, diese kommen zu den, die wir aus dem Polygon berechnen hinzu.
Zusammenfassung
- Wir berechnen also den Vektor vom Kreis-Mittelpunkt zum Vertex, dieser wird normalisiert.
- Dann projezieren wir das Polygon wie gehabt
- Der Kreis wird projeziert, indem der Vektor auf den wir multiplizieren mit dem Radius des Kreises skaliert (also skalar multipliziert) wird. Mit diesem wird dann genauso weiter verfahren. Dies ist dann der Max-Wert für unseren Kreis, der Min-Wert ist einfach der Max-Wert * -1, also -max.
Der Code
Der Code bietet noch viel Spielraum für Optimierungen, so ist es zum Beispiel nicht nötig, für jedes Vertex eine Projektionsachse zu berechnen, sondern es reicht aus, das Vertex, bzw die Kante zu nutzen, die sich auch in Reichweite des Kreises befindet, da diese zwangsläufig geschnitten werden müssen. Natürlich benötigen wir zunächst eine Kreis-Klasse:
TCircle = class
private
fposition: TVector2f;
fradius: extended;
public
property position: TVector2f read fposition write fposition;
property radius: extended read fradius write fradius;
end;
Die Kollision zweier Kreise kann dann gleich mit implementiert werden:
function CircleCircleIntersect(A, B: TCircle): boolean; begin result := (sqr(A.position.x - B.position.x) + sqr(A.position.y - B.position.y)) < sqr(A.radius + B.radius); end;
Das sollte denke ich, soweit klar sein. Nun folgt der Code zur Berechnung der Kreis <> Polygon Kollision. Es gibt nur eine äußere Schleife, da die Berechnungen für den Kreis gleich mit in dieser vorgenommen werden können. Ein bisschen Code ließe sich sicherlich auch noch auslagern, ich habe den Code so gelassen, weil ich denke, dass es der Übersicht sicherlich förderlich ist.
function CirclePolyIntersect(P: TPolygon; C: TCircle): boolean;
var
i, j, l: integer;
tmp, proj, voffset: TVector2f;
dp, pmin, pmax, cmin, cmax, d1, d2, foffset: extended;
begin
// Offset berechnen
voffset := v2f_sub(P.position, C.position);
// P - alle Projektionsgeraden ermitteln und projezieren
for i := 0 to (P.count - 1) do
begin
l := i + 1;
if l > (P.count - 1) then
l := 0;
// Berechnung der Seitenfläche
tmp := v2f_sub(P.vertices[l], P.vertices[i]);
// Berechnet die Normale der Seitenfläche
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
// Projeziert den ersten Wert
pmin := v2f_dotproduct(P.vertices[0], proj);
pmax := pmin;
// Findet den kleinsten und größten projezierten Wert für die Gerade für A
for j := 1 to (P.count - 1) do
begin
// projezieren
dp := v2f_dotproduct(P.vertices[j], proj);
if dp < pmin then
pmin := dp;
if dp > pmax then
pmax := dp;
end;
cmax := v2f_dotproduct(v2f_scale(proj, C.radius), proj);
cmin := -cmax;
// 1D Kollision
foffset := v2f_dotproduct(voffset, proj);
pmin := pmin + foffset;
pmax := pmax + foffset;
d1 := pmin - cmax;
d2 := cmin - pmax;
// Wenn es keine Überschneidung gibt, abbrechen -> keine Kollision
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
//C - Alle Projektionsgeraden ermitteln und projezieren
proj := v2f_normalize(v2f_sub(C.position, P.vertices_abs[i]));
// s.o.
pmin := v2f_dotproduct(P.vertices[0], proj);
pmax := pmin;
for j := 1 to (P.count - 1) do
begin
dp := v2f_dotproduct(P.vertices[j], proj);
if dp < pmin then
pmin := dp;
if dp > pmax then
pmax := dp;
end;
cmax := v2f_dotproduct(v2f_scale(proj, C.radius), proj);
cmin := -cmax;
foffset := v2f_dotproduct(voffset, proj);
pmin := pmin + foffset;
pmax := pmax + foffset;
d1 := pmin - cmax;
d2 := cmin - pmax;
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
end;
result := true;
end;
Kollision eines Punktes und eines Polygons
Theorie
Ganz am Rande möchte ich noch erwähnen, dass es ebenso möglich ist, zu prüfen, ob sich ein Punkt in einem Polygon befindet. Hierzu wird einfach der Punkt auf die Achsen projeziert und geprüft ob er größer als das Minimum und kleiner als das Maximum des Polygons auf dieser Achse ist.
Kollision eines Tortenstücks und eines Polygons
Hier folgt demnächst eine Anleitung für die Kollision von beliebigen Tortenstücken mit einem Polygon.
Polygone trennen
Theorie
Damit unsere Kollisionserkennung praxistauglich wird, müssen die Polygone, wenn sie kollidieren auch wieder getrennt werden können. Hierzu benötigen wir einen Vektor, der Unsere beiden Polygone wieder auseinander "schiebt". Selbstverständlich könnte man einen beliebigen Vektor nehmen, aber das Ergebnis wäre eher realtitätsfern, deshalb brauchen wir den Vektor, der den kürzesten Weg beschreibt, um die beiden Polygone zu trennen. Dieser Vektor wird auch MTD-Vektor genannt (Minimum Translation Distance). Hier kommt ein weiterer Vorteil des Separating Axis Theorems zum tragen, denn den Vektor den wir suchen, haben wir schon so gut wie berechnet. Wir multiplizieren alle unsere Projektionsachsen mit den Differenzen, die wir bei den 1D Kollisionen herausbekommen haben, somit erhalten wir Vektoren, die für das Außeinander-Schieben unserer Polygone geeignet sind. Nun müssen wir nur noch den kürzesten davon finden, dies ist unser MTD.
Der Code
Der bisherige Code sollte soweit verstanden sein, deshalb habe ich mir die Freiheit genommen ein wenig Code auszulagern:
function CreateAxis(P: TPolygon): TV2fArray;
var
i, l: integer;
tmp: TVector2f;
begin
for i := 0 to (P.count - 1) do
begin
l := i + 1;
if l > (P.count - 1) then
l := 0;
// Berechnung der Seitenfläche
tmp := v2f_sub(P.vertices[l], P.vertices[i]);
// Berechnet die Normale der Seitenfläche
setlength(result, length(result) + 1);
result[high(result)] := v2f_normalize(to_v2f(-tmp.y, tmp.x));
end;
end;
procedure ProjectOntoAxis(P: TPolygon; proj: TVector2f; var pmin, pmax: extended);
var
i: integer;
dp: extended;
begin
// Projeziert den ersten Wert
pmin := v2f_dotproduct(P.vertices[0], proj);
pmax := pmin;
// Findet den kleinsten und größten projezierten Wert für die Gerade für P
for i := 1 to (P.count - 1) do
begin
// projezieren
dp := v2f_dotproduct(P.vertices[i], proj);
if dp < pmin then
pmin := dp;
if dp > pmax then
pmax := dp;
end;
end;
function CollisionCheck(A, B: TPolygon; var axis: TVector2f; voffset: TVector2f): boolean;
var
foffset,
amin, amax,
bmin, bmax,
d1, d2, depth: extended;
begin
ProjectOntoAxis(A, axis, amin, amax);
ProjectOntoAxis(B, axis, bmin, bmax);
foffset := v2f_dotproduct(voffset, axis);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
// Wenn es keine Überschneidung gibt, abbrechen -> keine Kollision
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
// Ansonsten den Verschiebungsvektor bestimmen
depth := max(d1, d2);
axis := v2f_scale(axis, abs(depth));
result := true;
end;
Die ersten beiden Funktionen sollten klar sein, bei der dritten gibt es eine kleine Neuerung. Wenn eine Kollision stattfindet, bricht diese Funktion nicht ab und die Projektionsachse wird mit der Differenz multipliziert, deren Betrag am kleinsten ist. Da es sich um negative Werte handelt kann man statt:
depth := min(abs(d1), abs(d2));
ganz einfach:
depth := max(d1, d2);
schreiben. Die neue PolyPolyIntersect Funktion sieht so aus:
function PolyPolyIntersect(A, B: TPolygon; var MTD: TVector2f): boolean;
var
axis: TV2fArray;
voffset: TVector2f;
i: integer;
begin
MTD := to_v2f(0, 0);
// Offset berechnen
voffset := v2f_sub(A.position, B.position);
// Alle Achsen für A
axis := CreateAxis(A);
// Alle Achsen für B
axis := CreateAxis(B);
// Projezieren der Polygone
for i := 0 to high(axis) do
if CollisionCheck(A, B, axis[i], voffset) = false then
begin
result := false;
exit;
end;
// MTD bestimmen
MTD := axis[0];
for i := 1 to high(axis) do
if v2f_length(axis[i]) < v2f_length(MTD) then
MTD := axis[i];
if v2f_dotproduct(voffset, MTD) < 0 then
MTD := v2f_scale(MTD, -1);
// Kollision
result := true;
end;
Hier werden zunächst alle Achsen ermittelt und dann projeziert, dabei werden die Achsen mit sämtlichen potentiellen MTDs überschrieben und daraus der kleinste berechnet. Diesen Vektor übergeben wir einfach mittels Var-Parameter und können dann unsere Polygone trennen, indem wir den MTD-Vektor von ihrer derzeitigen Position abziehen.
Dieser Code hier sorgt dafür, dass das Polygon auch wirklich von dem anderen getrennt und nicht noch weiter hineingeschoben wird:
if v2f_dotproduct(voffset, MTD) < 0 then
MTD := v2f_scale(MTD, -1);
Das Beispielprojekt
Beispiel 1 - Polygon <> Polygon
Was wäre ein Tutorial doch ohne Beispiel ;) Ich werde hier nur kurz die Verwendung des Codes erläutern und ein kleines Beispielprogramm anhängen. Ein Polygon muss natürlich erst einmal erzeugt werden:
A := TPolygon.Create;
Die einfachste Möglichkeit es zu gestalten funktioniert so:
with A do
begin
position := to_v2f(200, 200);
AddVertex(to_v2f(50, -50));
AddVertex(to_v2f(50, 50));
AddVertex(to_v2f(-50, 50));
AddVertex(to_v2f(-50, -50));
end;
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200). Die Koordinaten der Vertices werden absolut zur Position und entgegen des Uhrzeigersinns angegeben.
Zeichnen kann man das Polygon dann ganz einfach so:
procedure TMainForm.DrawPolygon(A: TPolygon);
var
i, l: integer;
begin
for i := 0 to A.Count - 1 do
begin
l := i + 1;
if l > (A.Count - 1) then
l := 0;
Image1.Canvas.MoveTo(round(A.vertices_abs[l].x), round(A.vertices_abs[l].y));
Image1.Canvas.LineTo(round(A.vertices_abs[i].x), round(A.vertices_abs[i].y));
end;
end;
Und hier das Beispielprojekt:
Exe: http://www.exec-dev.de/SAT_Tutorial/SAT_exe.zip
Source: http://www.exec-dev.de/SAT_Tutorial/SAT_src.zip
Beispiel 2 - Kreis <> Polygon
Für den Kreis ist die Verwendung im Prinzip die selbe, mit:
C := TCircle.Create;
wird zunächst ein Kreis erzeugt und mit position und radius bekommt er seine Werte zugewiesen. Gezeichnet wird er mittels:
procedure TMainForm.DrawCircle(C: TCircle; aColor: TColor);
begin
with Image1.Canvas do
begin
Pen.Color := aColor;
Ellipse(round(C.position.x - C.radius), round(C.position.y - C.radius),
round(C.position.x + C.radius), round(C.position.y + C.radius));
end;
end;
Und hier das Beispielprojekt für die Kollision Kreis <> Polygon:
Exe: http://www.exec-dev.de/SAT_Tutorial/SAT_Kreis_exe.zip
Source: http://www.exec-dev.de/SAT_Tutorial/SAT_Kreis_src.zip
Beispiel 3 - Trennung von Polygonen
In diesem Beispiel wird ein Polygon mittels:
B.position := v2f_sub(B.position, MTD);
verschoben, sodass die beiden Polygone sich nicht schneiden. Es ließen sich auch beide um die hälfte des Vektors verschieben, dies hängt von der Anwendung ab.
Hier gibt es die Exe und den Code für die Trennung von Polygonen:
Exe: http://www.exec-dev.de/SAT_Tutorial/SAT_Trennung_exe.zip
Source: http://www.exec-dev.de/SAT_Tutorial/SAT_Trennung_src.zip
Links
Separating Axis Theorem
SAT-Tutorial(Eng): http://www.harveycartel.org/metanet/tutorials/tutorialA.html
SAT-Tutorial(Eng / VB): http://gpwiki.org/index.php/VB:Tutorials:Building_A_Physics_Engine:Basic_Intersection_Detection
Nachwort
Ich hoffe das Tutorial war nicht zu trocken und hat vielleicht auch ein wenig Spass gemacht und weitergeholfen. Für Fragen, Vorschläge, Ergänzungen, etc. bin ich selbstverständlich offen.
mfg
