DGL Wiki - Benutzerbeiträge [de]

Tutorial Separating Axis Theorem

2011-10-23T20:34:58Z

Seth: Link zum englischen Tutorial aktualisiert.

Tutorial Separating Axis Theorem

2008-03-11T16:07:14Z

Seth:

Tutorial Separating Axis Theorem

2008-03-11T16:05:30Z

Seth: normalisiert durch normiert ersetzt

Tutorial Separating Axis Theorem

2008-03-11T16:03:36Z

Seth:

Tutorial Separating Axis Theorem

2008-03-11T16:02:49Z

Seth: Code für Rotation hinzugefügt

Tutorial Separating Axis Theorem

2008-03-03T13:10:58Z

Seth: Ergänzung (Rotation) hinzugefügt

Tutorial Separating Axis Theorem

2008-02-20T15:07:59Z

Seth: Kleine Ergänzung und Rechtschreibung

Tutorial Separating Axis Theorem

2007-12-22T12:10:35Z

Seth:

Tutorial Separating Axis Theorem

2007-09-22T09:43:52Z

Seth:

Tutorial Separating Axis Theorem

2007-09-22T09:42:24Z

Seth: Entgültig Geraden durch Achsen ersetzt (und ein paar Kleinigkeiten)

Tutorial Separating Axis Theorem

2007-09-19T18:56:56Z

Seth: Anmerkung zum MTD hinzugefügt (skalarprodukt)

Tutorial Separating Axis Theorem

2007-09-19T18:52:12Z

Seth: noch mehr code entfernt

Tutorial Separating Axis Theorem

2007-09-19T18:51:00Z

Seth:

Tutorial Separating Axis Theorem

2007-09-19T18:49:25Z

Seth:

Tutorial Separating Axis Theorem

2007-09-19T18:45:07Z

Seth:

Tutorial Separating Axis Theorem

2007-09-19T18:44:01Z

Seth: Viel Code entfernt (liegt den Beispielen bei), kleine Fehler entfernt, Gerade wird nun stehts mit Achse betitelt

Tutorial Separating Axis Theorem

2007-04-09T11:28:18Z

Seth:

=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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Kollision zweier Polygone ==

=== Die Theorie ===

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// 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.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
// 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;</pascal>
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:
<pascal>
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;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

[[Bild:SAT_Kreis_Quadrat.jpg]]

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:
<pascal>
TCircle = class
private
fposition: TVector2f;
fradius: extended;
public
property position: TVector2f read fposition write fposition;
property radius: extended read fradius write fradius;
end;
</pascal>
Die Kollision zweier Kreise kann dann gleich mit implementiert werden:
<pascal>
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;
</pascal>
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.
<pascal>
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;
</pascal>

== 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 ('''M'''inimum '''T'''ranslation '''D'''istance). 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:
<pascal>
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;
</pascal>
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:
<pascal>
depth := min(abs(d1), abs(d2));
</pascal>
ganz einfach:
<pascal>
depth := max(d1, d2);
</pascal>
schreiben. Die neue PolyPolyIntersect Funktion sieht so aus:
<pascal>
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;
</pascal>
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:
<pascal>
if v2f_dotproduct(voffset, MTD) < 0 then
MTD := v2f_scale(MTD, -1);
</pascal>

== 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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
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:
<pascal>
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;
</pascal>

'''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:
<pascal>
C := TCircle.Create;
</pascal>
wird zunächst ein Kreis erzeugt und mit position und radius bekommt er seine Werte zugewiesen.
Gezeichnet wird er mittels:
<pascal>
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;
</pascal>

'''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:
<pascal>
B.position := v2f_sub(B.position, MTD);
</pascal>
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

Tutorial Separating Axis Theorem

2007-04-08T10:06:27Z

Seth: Anm. zu Punkten + Hinz. "Demnächst Tortenstücke"

=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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Kollision zweier Polygone ==

=== Die Theorie ===

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// 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.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
// 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;</pascal>
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:
<pascal>
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;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

[[Bild:SAT_Kreis_Quadrat.jpg]]

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:
<pascal>
TCircle = class
private
fposition: TVector2f;
fradius: extended;
public
property position: TVector2f read fposition write fposition;
property radius: extended read fradius write fradius;
end;
</pascal>
Die Kollision zweier Kreise kann dann gleich mit implementiert werden:
<pascal>
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;
</pascal>
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.
<pascal>
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;
</pascal>

== 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 ('''M'''inimum '''T'''ranslation '''D'''istance). 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:
<pascal>
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;
</pascal>
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:
<pascal>
depth := min(abs(d1), abs(d2));
</pascal>
ganz einfach:
<pascal>
depth := max(d1, d2);
</pascal>
schreiben. Die neue PolyPolyIntersect Funktion sieht so aus:
<pascal>
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;
</pascal>
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:
<pascal>
if v2f_dotproduct(voffset, MTD) < 0 then
MTD := v2f_scale(MTD, -1);
</pascal>

== 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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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:
<pascal>
C := TCircle.Create;
</pascal>
wird zunächst ein Kreis erzeugt und mit position und radius bekommt er seine Werte zugewiesen.
Gezeichnet wird er mittels:
<pascal>
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;
</pascal>

'''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:
<pascal>
B.position := v2f_sub(B.position, MTD);
</pascal>
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

Tutorial Separating Axis Theorem

2007-04-05T11:56:24Z

Seth:

=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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Kollision zweier Polygone ==

=== Die Theorie ===

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// 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.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
// 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;</pascal>
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:
<pascal>
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;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

[[Bild:SAT_Kreis_Quadrat.jpg]]

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:
<pascal>
TCircle = class
private
fposition: TVector2f;
fradius: extended;
public
property position: TVector2f read fposition write fposition;
property radius: extended read fradius write fradius;
end;
</pascal>
Die Kollision zweier Kreise kann dann gleich mit implementiert werden:
<pascal>
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;
</pascal>
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.
<pascal>
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;
</pascal>

== 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 ('''M'''inimum '''T'''ranslation '''D'''istance). 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:
<pascal>
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;
</pascal>
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:
<pascal>
depth := min(abs(d1), abs(d2));
</pascal>
ganz einfach:
<pascal>
depth := max(d1, d2);
</pascal>
schreiben. Die neue PolyPolyIntersect Funktion sieht so aus:
<pascal>
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;
</pascal>
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:
<pascal>
if v2f_dotproduct(voffset, MTD) < 0 then
MTD := v2f_scale(MTD, -1);
</pascal>

== 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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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:
<pascal>
C := TCircle.Create;
</pascal>
wird zunächst ein Kreis erzeugt und mit position und radius bekommt er seine Werte zugewiesen.
Gezeichnet wird er mittels:
<pascal>
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;
</pascal>

'''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:
<pascal>
B.position := v2f_sub(B.position, MTD);
</pascal>
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

Tutorial Separating Axis Theorem

2007-04-05T11:51:47Z

Seth:

=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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Kollision zweier Polygone ==

=== Die Theorie ===

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// 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.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
// 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;</pascal>
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:
<pascal>
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;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

[[Bild:SAT_Kreis_Quadrat.jpg]]

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:
<pascal>
TCircle = class
private
fposition: TVector2f;
fradius: extended;
public
property position: TVector2f read fposition write fposition;
property radius: extended read fradius write fradius;
end;
</pascal>
Die Kollision zweier Kreise kann dann gleich mit implementiert werden:
<pascal>
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;
</pascal>
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.
<pascal>
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;
</pascal>

== 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 ('''M'''inimum '''T'''ranslation '''D'''istance). 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:
<pascal>
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
result := true;
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));
end;
</pascal>
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:
<pascal>
depth := min(abs(d1), abs(d2));
</pascal>
ganz einfach:
<pascal>
depth := max(d1, d2);
</pascal>
schreiben. Die neue PolyPolyIntersect Funktion sieht so aus:
<pascal>
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;
</pascal>
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:
<pascal>
if v2f_dotproduct(voffset, MTD) < 0 then
MTD := v2f_scale(MTD, -1);
</pascal>

== 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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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:
<pascal>
C := TCircle.Create;
</pascal>
wird zunächst ein Kreis erzeugt und mit position und radius bekommt er seine Werte zugewiesen.
Gezeichnet wird er mittels:
<pascal>
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;
</pascal>

'''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:
<pascal>
B.position := v2f_sub(B.position, MTD);
</pascal>
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

Tutorial Separating Axis Theorem

2007-04-04T15:51:24Z

Seth: Hinzugefügt: Kreis <> Polygon Kollision | Neue Struktur

=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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Kollision zweier Polygone ==

=== Die Theorie ===

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// 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.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
// 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;</pascal>
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:
<pascal>
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;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

[[Bild:SAT_Kreis_Quadrat.jpg]]

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:
<pascal>
TCircle = class
private
fposition: TVector2f;
fradius: extended;
public
property position: TVector2f read fposition write fposition;
property radius: extended read fradius write fradius;
end;
</pascal>
Die Kollision zweier Kreise kann dann gleich mit implementiert werden:
<pascal>
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;
</pascal>
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.
<pascal>
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;
</pascal>

== 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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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:
<pascal>
C := TCircle.Create;
</pascal>
wird zunächst ein Kreis erzeugt und mit position und radius bekommt er seine Werte zugewiesen.
Gezeichnet wird er mittels:
<pascal>
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;
</pascal>

'''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

== 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

Datei:SAT Kreis Quadrat.jpg

2007-04-04T15:33:32Z

Seth: *Beschreibung: Anwendung von SAT bei einem Kreis und einem Polygon

*Beschreibung: Anwendung von SAT bei einem Kreis und einem Polygon

Tutorial Separating Axis Theorem

2007-04-04T07:40:49Z

Seth: Vectors Unit komplett auf Extended umgestellt

=Kollisionserkennung=
''zweier Polygone 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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Die Theorie ==

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// 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.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
// 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;</pascal>
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:
<pascal>
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;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

==Das Beispielprojekt ==

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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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

== 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

Tutorial Separating Axis Theorem

2007-04-03T18:00:22Z

Seth:

=Kollisionserkennung=
''zweier Polygone 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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Die Theorie ==

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// Unit Vectors
(**************************************************

- Enthält: TVector2f

**************************************************)

unit Vectors;

interface

type
// 2D Vektor
TVector2f = record
X, Y: Extended;
end;

// Zwei Singles in einen TVector2f umwandeln
function To_v2f(X, Y: Single): 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: Single): TVector2f;
// Ermittelt die Länge eines Vektors
function v2f_Length(V: TVector2f): Single;
// Normalisiert einen Vektor (sodass v2f_length = 1)
function v2f_Normalize(V: TVector2f): TVector2f;
// Ermittelt ds Skalarprodukt
function v2f_DotProduct(V1, V2: TVector2f): Single;

implementation

function To_v2f(X, Y: Single): 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: Single): TVector2f;
begin
Result.X := V.X * Scalar;
Result.Y := V.Y * Scalar;
end;

function v2f_Length(V: TVector2f): Single;
begin
Result := sqrt(V.X * V.X + V.Y * V.Y);
end;

function v2f_Normalize(V: TVector2f): TVector2f;
var
L: Single;
begin
L := v2f_Length(V);

if L = 0 then
L := 1;

Result := v2f_Scale(V, 1 / L);
end;

function v2f_DotProduct(V1, V2: TVector2f): Single;
begin
Result := V1.X * V2.X + V1.Y * V2.Y;
end;

end.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
// 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;</pascal>
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:
<pascal>
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;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

==Das Beispielprojekt ==

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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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

== 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

Tutorial Separating Axis Theorem

2007-04-03T17:59:12Z

Seth:

=Kollisionserkennung=
''zweier Polygone 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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Die Theorie ==

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// Unit Vectors
(**************************************************

- Enthält: TVector2f

**************************************************)

unit Vectors;

interface

type
// 2D Vektor
TVector2f = record
X, Y: Extended;
end;

// Zwei Singles in einen TVector2f umwandeln
function To_v2f(X, Y: Single): 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: Single): TVector2f;
// Ermittelt die Länge eines Vektors
function v2f_Length(V: TVector2f): Single;
// Normalisiert einen Vektor (sodass v2f_length = 1)
function v2f_Normalize(V: TVector2f): TVector2f;
// Ermittelt ds Skalarprodukt
function v2f_DotProduct(V1, V2: TVector2f): Single;

implementation

function To_v2f(X, Y: Single): 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: Single): TVector2f;
begin
Result.X := V.X * Scalar;
Result.Y := V.Y * Scalar;
end;

function v2f_Length(V: TVector2f): Single;
begin
Result := sqrt(V.X * V.X + V.Y * V.Y);
end;

function v2f_Normalize(V: TVector2f): TVector2f;
var
L: Single;
begin
L := v2f_Length(V);

if L = 0 then
L := 1;

Result := v2f_Scale(V, 1 / L);
end;

function v2f_DotProduct(V1, V2: TVector2f): Single;
begin
Result := V1.X * V2.X + V1.Y * V2.Y;
end;

end.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
// 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;</pascal>
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:
<pascal>
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;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

==Das Beispielprojekt ==

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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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

== 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

Tutorial Separating Axis Theorem

2007-04-03T17:22:01Z

Seth:

=Kollisionserkennung=
''zweier Polygone 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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Die Theorie ==

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// Unit Vectors
(**************************************************

- Enthält: TVector2f

**************************************************)

unit Vectors;

interface

type
// 2D Vektor
TVector2f = record
X, Y: Extended;
end;

// Zwei Singles in einen TVector2f umwandeln
function To_v2f(X, Y: Single): 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: Single): TVector2f;
// Ermittelt die Länge eines Vektors
function v2f_Length(V: TVector2f): Single;
// Normalisiert einen Vektor (sodass v2f_length = 1)
function v2f_Normalize(V: TVector2f): TVector2f;
// Ermittelt ds Skalarprodukt
function v2f_DotProduct(V1, V2: TVector2f): Single;

implementation

function To_v2f(X, Y: Single): 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: Single): TVector2f;
begin
Result.X := V.X * Scalar;
Result.Y := V.Y * Scalar;
end;

function v2f_Length(V: TVector2f): Single;
begin
Result := sqrt(V.X * V.X + V.Y * V.Y);
end;

function v2f_Normalize(V: TVector2f): TVector2f;
var
L: Single;
begin
L := v2f_Length(V);

if L = 0 then
L := 1;

Result := v2f_Scale(V, 1 / L);
end;

function v2f_DotProduct(V1, V2: TVector2f): Single;
begin
Result := V1.X * V2.X + V1.Y * V2.Y;
end;

end.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
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
function GetCount: integer; // Liefert length(fvertices)
public
procedure AddVertex(v: TVector2f);
procedure RemoveVertex(n: integer);
property position: TVector2f read fposition write fposition; // Position
property vertices[n: integer]: TVector2f read GetVertex; // Vertex Koordinaten
property vertices_abs[n: integer]: TVector2f read GetVertexAbs;
property Count: integer read GetCount; // siehe GetCount
end;</pascal>
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:
<pascal>
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;

function TPolygon.GetCount: integer;
begin
result := length(fvertices);
end;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

==Das Beispielprojekt ==

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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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

== 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

Tutorial Separating Axis Theorem

2007-04-03T17:21:08Z

Seth:

=Kollisionserkennung=
''zweier Polygone 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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Die Theorie ==

[[Bild:SAT_Normale.jpg|right]]
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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// Unit Vectors
(**************************************************

- Enthält: TVector2f

**************************************************)

unit Vectors;

interface

type
// 2D Vektor
TVector2f = record
X, Y: Extended;
end;

// Zwei Singles in einen TVector2f umwandeln
function To_v2f(X, Y: Single): 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: Single): TVector2f;
// Ermittelt die Länge eines Vektors
function v2f_Length(V: TVector2f): Single;
// Normalisiert einen Vektor (sodass v2f_length = 1)
function v2f_Normalize(V: TVector2f): TVector2f;
// Ermittelt ds Skalarprodukt
function v2f_DotProduct(V1, V2: TVector2f): Single;

implementation

function To_v2f(X, Y: Single): 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: Single): TVector2f;
begin
Result.X := V.X * Scalar;
Result.Y := V.Y * Scalar;
end;

function v2f_Length(V: TVector2f): Single;
begin
Result := sqrt(V.X * V.X + V.Y * V.Y);
end;

function v2f_Normalize(V: TVector2f): TVector2f;
var
L: Single;
begin
L := v2f_Length(V);

if L = 0 then
L := 1;

Result := v2f_Scale(V, 1 / L);
end;

function v2f_DotProduct(V1, V2: TVector2f): Single;
begin
Result := V1.X * V2.X + V1.Y * V2.Y;
end;

end.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
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
function GetCount: integer; // Liefert length(fvertices)
public
procedure AddVertex(v: TVector2f);
procedure RemoveVertex(n: integer);
property position: TVector2f read fposition write fposition; // Position
property vertices[n: integer]: TVector2f read GetVertex; // Vertex Koordinaten
property vertices_abs[n: integer]: TVector2f read GetVertexAbs;
property Count: integer read GetCount; // siehe GetCount
end;</pascal>
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:
<pascal>
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;

function TPolygon.GetCount: integer;
begin
result := length(fvertices);
end;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

==Das Beispielprojekt ==

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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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

== 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

Tutorial Separating Axis Theorem

2007-04-03T17:20:26Z

Seth:

=Kollisionserkennung=
''zweier Polygone 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 [[Tutorial_Lineare_Algebra|Vektorrechnung]] zu haben.

== Die Theorie ==

[[Bild:SAT_Normale.jpg|right]]
Das Separating Axis Theorem (im folgenden mit SAT abgekürzt) 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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// Unit Vectors
(**************************************************

- Enthält: TVector2f

**************************************************)

unit Vectors;

interface

type
// 2D Vektor
TVector2f = record
X, Y: Extended;
end;

// Zwei Singles in einen TVector2f umwandeln
function To_v2f(X, Y: Single): 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: Single): TVector2f;
// Ermittelt die Länge eines Vektors
function v2f_Length(V: TVector2f): Single;
// Normalisiert einen Vektor (sodass v2f_length = 1)
function v2f_Normalize(V: TVector2f): TVector2f;
// Ermittelt ds Skalarprodukt
function v2f_DotProduct(V1, V2: TVector2f): Single;

implementation

function To_v2f(X, Y: Single): 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: Single): TVector2f;
begin
Result.X := V.X * Scalar;
Result.Y := V.Y * Scalar;
end;

function v2f_Length(V: TVector2f): Single;
begin
Result := sqrt(V.X * V.X + V.Y * V.Y);
end;

function v2f_Normalize(V: TVector2f): TVector2f;
var
L: Single;
begin
L := v2f_Length(V);

if L = 0 then
L := 1;

Result := v2f_Scale(V, 1 / L);
end;

function v2f_DotProduct(V1, V2: TVector2f): Single;
begin
Result := V1.X * V2.X + V1.Y * V2.Y;
end;

end.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
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
function GetCount: integer; // Liefert length(fvertices)
public
procedure AddVertex(v: TVector2f);
procedure RemoveVertex(n: integer);
property position: TVector2f read fposition write fposition; // Position
property vertices[n: integer]: TVector2f read GetVertex; // Vertex Koordinaten
property vertices_abs[n: integer]: TVector2f read GetVertexAbs;
property Count: integer read GetCount; // siehe GetCount
end;</pascal>
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:
<pascal>
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;

function TPolygon.GetCount: integer;
begin
result := length(fvertices);
end;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

==Das Beispielprojekt ==

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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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

== 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

Tutorial Separating Axis Theorem

2007-04-03T17:11:21Z

Seth:

=Kollisionserkennung=
''zweier Polygone 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 [wiki]Vektorrechnung[/wiki] zu haben.

== Die Theorie ==

[[Bild:SAT_Normale.jpg|right]]
Das Separating Axis Theorem (im folgenden mit SAT abgekürzt) 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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// Unit Vectors
(**************************************************

- Enthält: TVector2f

**************************************************)

unit Vectors;

interface

type
// 2D Vektor
TVector2f = record
X, Y: Extended;
end;

// Zwei Singles in einen TVector2f umwandeln
function To_v2f(X, Y: Single): 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: Single): TVector2f;
// Ermittelt die Länge eines Vektors
function v2f_Length(V: TVector2f): Single;
// Normalisiert einen Vektor (sodass v2f_length = 1)
function v2f_Normalize(V: TVector2f): TVector2f;
// Ermittelt ds Skalarprodukt
function v2f_DotProduct(V1, V2: TVector2f): Single;

implementation

function To_v2f(X, Y: Single): 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: Single): TVector2f;
begin
Result.X := V.X * Scalar;
Result.Y := V.Y * Scalar;
end;

function v2f_Length(V: TVector2f): Single;
begin
Result := sqrt(V.X * V.X + V.Y * V.Y);
end;

function v2f_Normalize(V: TVector2f): TVector2f;
var
L: Single;
begin
L := v2f_Length(V);

if L = 0 then
L := 1;

Result := v2f_Scale(V, 1 / L);
end;

function v2f_DotProduct(V1, V2: TVector2f): Single;
begin
Result := V1.X * V2.X + V1.Y * V2.Y;
end;

end.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
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
function GetCount: integer; // Liefert length(fvertices)
public
procedure AddVertex(v: TVector2f);
procedure RemoveVertex(n: integer);
property position: TVector2f read fposition write fposition; // Position
property vertices[n: integer]: TVector2f read GetVertex; // Vertex Koordinaten
property vertices_abs[n: integer]: TVector2f read GetVertexAbs;
property Count: integer read GetCount; // siehe GetCount
end;</pascal>
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:
<pascal>
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;

function TPolygon.GetCount: integer;
begin
result := length(fvertices);
end;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

==Das Beispielprojekt ==

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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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

== 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

Tutorial Separating Axis Theorem

2007-04-03T17:10:52Z

Seth: hat SAT nach Separating Axis Theorem verschoben

=Kollisionserkennung=
''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 [wiki]Vektorrechnung[/wiki] zu haben.

== Die Theorie ==

[[Bild:SAT_Normale.jpg|right]]
Das Separating Axis Theorem (im folgenden mit SAT abgekürzt) 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:

[[Bild:SAT_Normale_Formel.jpg]]

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:

[[Bild:SAT_Kollision.jpg]][[Bild:SAT_Keine_Kollision.jpg]]

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 [[Standard_Skalarprodukt|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:
<pascal>
// Unit Vectors
(**************************************************

- Enthält: TVector2f

**************************************************)

unit Vectors;

interface

type
// 2D Vektor
TVector2f = record
X, Y: Extended;
end;

// Zwei Singles in einen TVector2f umwandeln
function To_v2f(X, Y: Single): 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: Single): TVector2f;
// Ermittelt die Länge eines Vektors
function v2f_Length(V: TVector2f): Single;
// Normalisiert einen Vektor (sodass v2f_length = 1)
function v2f_Normalize(V: TVector2f): TVector2f;
// Ermittelt ds Skalarprodukt
function v2f_DotProduct(V1, V2: TVector2f): Single;

implementation

function To_v2f(X, Y: Single): 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: Single): TVector2f;
begin
Result.X := V.X * Scalar;
Result.Y := V.Y * Scalar;
end;

function v2f_Length(V: TVector2f): Single;
begin
Result := sqrt(V.X * V.X + V.Y * V.Y);
end;

function v2f_Normalize(V: TVector2f): TVector2f;
var
L: Single;
begin
L := v2f_Length(V);

if L = 0 then
L := 1;

Result := v2f_Scale(V, 1 / L);
end;

function v2f_DotProduct(V1, V2: TVector2f): Single;
begin
Result := V1.X * V2.X + V1.Y * V2.Y;
end;

end.
</pascal>
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:
<pascal>
type
TV2fArray = array of TVector2f;
</pascal>
Dann folgt die Definition unseres Polygons:
<pascal>
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
function GetCount: integer; // Liefert length(fvertices)
public
procedure AddVertex(v: TVector2f);
procedure RemoveVertex(n: integer);
property position: TVector2f read fposition write fposition; // Position
property vertices[n: integer]: TVector2f read GetVertex; // Vertex Koordinaten
property vertices_abs[n: integer]: TVector2f read GetVertexAbs;
property Count: integer read GetCount; // siehe GetCount
end;</pascal>
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:
<pascal>
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;

function TPolygon.GetCount: integer;
begin
result := length(fvertices);
end;
</pascal>
Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr.
Nun folgt die Kollisionserkennung an sich:
<pascal>
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;
</pascal>
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:
<pascal>
tmp := v2f_sub(a.vertices[l], a.vertices[i]);
proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
</pascal>
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.
<pascal>
amin := v2f_dotproduct(a.vertices[0], proj);
amax := amin;
</pascal>
Hier projezieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.
<pascal>
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;
</pascal>
Hier werden alle weiteren Vertices projeziert und der kleinste, sowie größte Wert gespeichert.
Das gleiche wird für B wiederholt.
<pascal>
foffset := v2f_dotproduct(voffset, proj);
amin := amin + foffset;
amax := amax + foffset;
d1 := amin - bmax;
d2 := bmin - amax;
</pascal>
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:
<pascal>
voffset := v2f_sub(A.position, B.position);
</pascal>
und ihn danach Projezieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.
<pascal>
if (d1 > 0) or (d2 > 0) then
begin
result := false;
exit;
end;
</pascal>
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.

==Das Beispielprojekt ==

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:
<pascal>
A := TPolygon.Create;
</pascal>
Die einfachste Möglichkeit es zu gestalten funktioniert so:
<pascal>
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;
</pascal>
Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200).

Zeichnen kann man das Polygon ganz einfach so:
<pascal>
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;
</pascal>

'''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

== 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

SAT

2007-04-03T17:10:52Z

Seth: hat SAT nach Separating Axis Theorem verschoben

#REDIRECT [[Separating Axis Theorem]]

Tutorial Separating Axis Theorem

2007-04-03T17:10:24Z

Seth: Kollisionserkennung zweier 2D-Polygone

Datei:SAT Keine Kollision.jpg

2007-04-03T16:59:24Z

Seth: *Beschreibung: Dargestellt ist der Fall, dass beim Separating Axis Theorem keine Kollision auftritt

*Beschreibung: Dargestellt ist der Fall, dass beim Separating Axis Theorem keine Kollision auftritt

Datei:SAT Kollision.jpg

2007-04-03T16:58:47Z

Seth: *Beschreibung: Dargestellt ist der Fall einer Kollision beim Separating Axis Theorem

*Beschreibung: Dargestellt ist der Fall einer Kollision beim Separating Axis Theorem

Datei:SAT Normale Formel.jpg

2007-04-03T16:57:45Z

Seth: *Beschreibung: Dargestellt ist die Formel zur Berechnung der Normale eines Vektors

*Beschreibung: Dargestellt ist die Formel zur Berechnung der Normale eines Vektors

Datei:SAT Normale.jpg

2007-04-03T16:56:42Z

Seth: *Beschreibung: Dargestellt ist die Normale einer Seite des Polygons

*Beschreibung: Dargestellt ist die Normale einer Seite des Polygons