Version vom 14. April 2007, 00:19 Uhr

Kollisionserkennung

von Polygonen mit dem Separating Axis Theorem

Vorwort

In diesem Tutorial möchte ich eine schnelle Variante zur Kollision zweier konvexer Polygone erläutern. Diese kann nachträglich für konkave Polygone und andere Objekte wie Kreise und abgerundete Objekte verwendet werden. Um den mathematischen Hintergrund zu verstehen, ist es sinnvoll ein wenig Kenntnis in Vektorrechnung zu haben.

Kollision zweier Polygone

Die Theorie

Das Separating Axis Theorem (kurz: SAT) besagt, dass zwei Polygone sich nicht schneiden, wenn es möglich ist, eine Gerade zu finden, die zwischen den beiden liegt. Nun gibt es unendlich viele Geraden die man testen könnte... Glücklicherweise kann man sich hier auf eine überschaubare Zahl beschränken, denn man braucht nur die Anzahl der Seiten beider Polygone. Bei einem Viereck wären das vier, bei einem Dreieck drei, etc. Hat man die Eckpunkte des Polygons als Vektoren (Ortsvektoren) gegeben, kann man durch Subtraktion zweier Ortsvektoren den Vektor bestimmen der zu der Seite gehört, die von den beiden Vektoren aufgespannt wird.

Auf dem Bild rechts ist ein Beispiel zu sehen. Dort ist ein Quadrat, die grünen Striche bezeichnen die Ortsvektoren der Eckpunkte, der rote Strich ist die berechnete Seite. Was wir aber brauchen ist der blaue Strich, das ist die Normale der Seite. Die Normale berechnet sich folgendermaßen:

die Koordinaten werden vertauscht und eine von beiden wird negiert. Der Vektor muss dann noch normalisiert werden, sodass er die Länge 1 erhält. Jetzt müssen beide Polygone auf diesen Vektor projiziert werden, denn dadurch haben wir ein eindimensionales Abbild unserer Polygone und können mittels eines einfachen Vergleichs überprüfen, ob sich die beiden eindimensionalen Strecken schneiden. Sollte ein Fall eintreffen bei dem kein Schnitt stattfindet, dann kollidieren die beiden Polygone nicht und die Prozedur kann abgebrochen werden. Nun zur Projektion:

Auf dem linken Bild sieht man, wie beide Polygone auf die Gerade projiziert 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 letztenendes egal, da wir ja ein eindimensionales Ergebnis anstreben.

Für die Projektion eines Vektors auf einen anderen verwenden wir das Skalarprodukt, bei diesem kommt ein Zahlenwert heraus, der die Position des Eckpunktes auf unserer eindimensionale Geraden darstellt. Haben wir sämtliche Punkte projiziert, 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 projizieren
  • Die kleinsten und größten Werte ermitteln und auf Schnitt prüfen
• Tritt der Fall auf, dass kein Schnitt statt findet, so kann sofort abgebrochen werden, es findet keine Kollision statt.

Der Code

Um bei so vielen Vektoroperationen nicht völlig durcheinander zu geraten und die Übersicht zu verlieren (was dabei durchaus mal passieren kann), ist es es sinnvoll, sich eine Unit zu schreiben, die einem die Vektorrechnung abnimmt. Im weiteren Verlauf des Tutorials werde ich folgende Unit benutzen:

// Unit Vectors
(**************************************************

- Enthält: TVector2f

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

unit Vectors;

interface

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

  // Zwei extendeds in einen TVector2f umwandeln
  function To_v2f(X, Y: extended): TVector2f;
  // Zwei Vektoren addieren
  function v2f_Add(V1, V2: TVector2f): TVector2f;
  // Einen Vektor von einem anderen subtrahieren
  function v2f_Sub(V1, V2: TVector2f): TVector2f;
  // Einen Vektor skalieren
  function v2f_Scale(V: TVector2f; Scalar: extended): TVector2f;
  // Ermittelt die Länge eines Vektors
  function v2f_Length(V: TVector2f): extended;
  // Normalisiert einen Vektor (sodass v2f_length = 1)
  function v2f_Normalize(V: TVector2f): TVector2f;
  // Ermittelt ds Skalarprodukt
  function v2f_DotProduct(V1, V2: TVector2f): extended;

implementation

function To_v2f(X, Y: extended): TVector2f;
begin
  Result.X := X;
  Result.Y := Y;
end;

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

function v2f_Sub(V1, V2: TVector2f): TVector2f;
begin
  Result.X := V1.X - V2.X;
  Result.Y := V1.Y - V2.Y;
end;

function v2f_Scale(V: TVector2f; Scalar: extended): TVector2f;
begin
  Result.X := V.X * Scalar;
  Result.Y := V.Y * Scalar;
end;

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

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

  if L = 0 then
    L := 1;

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

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

end.

Jedoch schadet es nicht, sich eine eigene zu schreiben, um seine Kenntnisse in Sachen Vektorrechnung ein wenig zu festigen. Jetzt benötigen wir eine Klasse für unsere Polygone. Die einzelnen Eckpunkte der Polygone werden nicht etwa absolut (also in Weltkoordinaten), sondern relativ zu einem Punkt angegeben, so fällt es leichter, das Polygon zu verschieben. Der absolute Wert kann jedoch ganz nützlich sein, um z.B. ein Polygon zu zeichnen. Als erstes definieren wir ein Array von TVector2f, denn jeder Eckpunkt ist ein Vektor und unsere Polygone sollen ja beliebig viele davon besitzen können, also:

type
  TV2fArray = array of TVector2f;

Dann folgt die Definition unseres Polygons:

  // Polygon Klasse
  TPolygon = class
  private
    fposition: TVector2f;                             // Position
    fvertices: TV2fArray;                             // Vertices (Objektkoordinaten)
    function GetVertex(n: integer): TVector2f;        // Liefert die Objektkoordinaten
    function GetVertexAbs(n: integer): TVector2f;     // Liefert die absoluten Koordinaten
    procedure SetVertex(n: integer; Value: TVector2f);// Setzt die Objektkoordinaten
    function GetCount: integer;                       // Liefert length(fvertices)
  public
    procedure AddVertex(v: TVector2f);                // Fügt ein Vertex hinzu
    procedure AddVertexAbs(v: TVector2f);             // Fügt ein Vertex mit Weltkoordinaten hinzu
    procedure RemoveVertex(n: integer);               // Entfernt ein Vertex
    property position: TVector2f read fposition write fposition;             // Position
    property vertices[n: integer]: TVector2f read GetVertex write SetVertex; // Vertex Koordinaten
    property vertices_abs[n: integer]: TVector2f read GetVertexAbs;          // Vertex Weltkoordinaten
    property Count: integer read GetCount;                                   // siehe GetCount
  end;

Unser Polygon hat jetzt eine Position und Eckpunkte, ebenfalls können wir auf absolute, sowie relative Koordinaten zugreifen. Count liefert uns die Anzahl der Ecken.

Eine Ecke bezeichnet man auch als Vertex, der Plural von Vertex ist Vertices.

Hier sind die entsprechenden Funktionen:

procedure TPolygon.AddVertexAbs(v: TVector2f);
begin
  setlength(fvertices, length(fvertices) + 1);
  fvertices[high(fvertices)] := v2f_sub(v, position);
end;

procedure TPolygon.AddVertex(v: TVector2f);
begin
  setlength(fvertices, length(fvertices) + 1);
  fvertices[high(fvertices)] := v;
end;

procedure TPolygon.RemoveVertex(n: integer);
var
  i: integer;
begin
  for i := n to high(fvertices) - 1 do
    fvertices[i] := fvertices[i + 1];
  setlength(fvertices, length(fvertices) - 1);  
end;

function TPolygon.GetVertex(n: integer): TVector2f;
begin
  result := fvertices[n];
end;

function TPolygon.GetVertexAbs(n: integer): TVector2f;
begin
  result := v2f_add(fvertices[n], fposition);
end;

procedure TPolygon.SetVertex(n: integer; Value: TVector2f);
begin
  fvertices[n] := Value;
end;

function TPolygon.GetCount: integer;
begin
  result := length(fvertices);
end;

Mit AddVertex können wir unsere Vertices hinzufügen, aber dazu später mehr. Nun folgt die Kollisionserkennung an sich:

function PolyPolyIntersect(A, B: TPolygon): boolean;
var
  i, j, l: integer;
  tmp, proj, voffset: TVector2f;
  dp, amin, amax, bmin, bmax, d1, d2, foffset: extended;
begin
  // Offset berechnen
  voffset := v2f_sub(A.position, B.position);
// A - alle Projektionsgeraden ermitteln und projizieren
  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));
    // Projiziert den ersten Wert
    amin := v2f_dotproduct(a.vertices[0], proj);
    amax := amin;
    // Findet den kleinsten und größten projizierten Wert für die Gerade für A
    for j := 1 to (a.count - 1) do
    begin
      // projizieren
      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 projizieren (s.o.)
  for i := 0 to (b.count - 1) do
  begin
    l := i + 1;
    if l > (b.count - 1) then
      l := 0;
    tmp := v2f_sub(b.vertices[l], b.vertices[i]);
    proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
    amin := v2f_dotproduct(a.vertices[0], proj);
    amax := amin;
    for j := 1 to (a.count - 1) do
    begin
      dp := v2f_dotproduct(a.vertices[j], proj);
      if dp < amin then
        amin := dp;
      if dp > amax then
        amax := dp;
    end;
    bmin := v2f_dotproduct(b.vertices[0], proj);
    bmax := bmin;
    for j := 1 to (b.count - 1) do
    begin
      dp := v2f_dotproduct(b.vertices[j], proj);
      if dp < bmin then
        bmin := dp;
      if dp > bmax then
        bmax := dp;
    end;
    foffset := v2f_dotproduct(voffset, proj);
    amin := amin + foffset;
    amax := amax + foffset;
    d1 := amin - bmax;
    d2 := bmin - amax;
    if (d1 > 0) or (d2 > 0) then
    begin
      result := false;
      exit;
    end;
  end;
  // Kollision
  result := true;
end;

Wie man sieht, ist der zweite Teil des Codes, mit dem ersten sogut wie identisch, der einzige Unterschied besteht darin, dass dort die Geraden aus den Vertices von B berechnet werden. Nehmen wir den Code mal auseinander:

    tmp := v2f_sub(a.vertices[l], a.vertices[i]);
    proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));

Hier wird zunächst der Vektor berechnet, der für die Seitenfläche steht, durch die Schleife wird dies für alle Seitenflächen gemacht. Danach wird die Normale berechnet. proj ist dann der Vektor auf den wir unsere Vertices projizieren.

    amin := v2f_dotproduct(a.vertices[0], proj);
    amax := amin;

Hier projizieren wir das erste Vertex von A und haben somit den ersten Punkt unserer Strecke.

    for j := 1 to (a.count - 1) do
    begin
      dp := v2f_dotproduct(a.vertices[j], proj);
      if dp < amin then
        amin := dp;
      if dp > amax then
        amax := dp;
    end;

Hier werden alle weiteren Vertices projiziert und der kleinste, sowie größte Wert gespeichert. Das Gleiche wird für B wiederholt.

    foffset := v2f_dotproduct(voffset, proj);
    amin := amin + foffset;
    amax := amax + foffset;
    d1 := amin - bmax;
    d2 := bmin - amax;

Da es sich bei unseren Vertexkoordinaten um Objektkoordinaten handelt, müssen die projizierten Vertices nun um die Differenz beider Polygonpositionen verschoben werden. Dies klingt zunächst einmal kompliziert, macht aber Sinn. Die Alternative wäre, jeden Punkt in Weltkoordinaten (also absolute Koordinaten) umzuwandeln. Dadurch, dass wir am Anfang den Vektor zwischen den beiden Polygonen berechnen:

voffset := v2f_sub(A.position, B.position);

und ihn danach projizieren, können wir diese Verschiebung auf unserer Geraden nachträglich vornehmen und haben somit alles in einem Abwasch erledigt.

    if (d1 > 0) or (d2 > 0) then
    begin
      result := false;
      exit;
    end;

Ohne einen Vergleich kommt auch diese Kollisionsabfrage nicht aus, hier jedoch nur auf eindimensionaler Ebene. Gibt es keine Überschneidung der beiden eindimensionalen Strecken, so kann die Prozedur abgebrochen werden, denn es gibt keine Kollision. Ist die komplette Prozedur durchgelaufen ohne abzubrechen, so wird result auf true gesetzt und eine Kollision ist bestätigt.

Kollision eines Kreises und eines Polygons

Theorie

Das Prinzip für die Kollision zweier Polygone ist denke ich jetzt klar geworden, doch was ist, wenn wir einen Kreis haben, der mit einem Polygon kollidiert? Dieser Fall ist leicht abzuhandeln, ein Kreis hat unendlich viele Normalen, die man testen könnte, uns reichen aber die, die die Vertices des Polygons schneiden würden, sprich: die Geraden, die vom Kreismittelpunkt zu den Ecken unseres Polygons führen.

Die blauen Linien auf dem Bild sind wieder einmal die Geraden, bzw. die Achsen auf die wir projizieren, 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 projizieren wir das Polygon wie gehabt
• Der Kreis wird projiziert, indem der Vektor, auf den wir multiplizieren, mit dem Radius des Kreises skaliert (also skalar multipliziert) wird. Mit diesem wird dann genauso weiter verfahren. Dies ist dann der Max-Wert für unseren Kreis, der Min-Wert ist einfach der Max-Wert * -1, also -max.

Der Code

Der Code bietet noch viel Spielraum für Optimierungen, so ist es zum Beispiel nicht nötig, für jedes Vertex eine Projektionsachse zu berechnen, sondern es reicht aus, das Vertex, bzw die Kante zu nutzen, die sich auch in Reichweite des Kreises befindet, da diese zwangsläufig geschnitten werden müssen. Natürlich benötigen wir zunächst eine Kreis-Klasse:

  TCircle = class
  private
    fposition: TVector2f;
    fradius: extended;
  public
    property position: TVector2f read fposition write fposition;
    property radius: extended read fradius write fradius;
  end;

Die Kollision zweier Kreise kann dann gleich mit implementiert werden:

function CircleCircleIntersect(A, B: TCircle): boolean;
begin
  result := (sqr(A.position.x - B.position.x) + sqr(A.position.y - B.position.y)) < sqr(A.radius + B.radius);
end;

Das sollte denke ich, soweit klar sein. Nun folgt der Code zur Berechnung der Kreis <> Polygon Kollision. Es gibt nur eine äußere Schleife, da die Berechnungen für den Kreis gleich mit in dieser vorgenommen werden können. Ein bisschen Code ließe sich sicherlich auch noch auslagern, ich habe den Code so gelassen, weil ich denke, dass es der Übersicht sicherlich förderlich ist.

function CirclePolyIntersect(P: TPolygon; C: TCircle): boolean;
var
  i, j, l: integer;
  tmp, proj, voffset: TVector2f;
  dp, pmin, pmax, cmin, cmax, d1, d2, foffset: extended;
begin
  // Offset berechnen
  voffset := v2f_sub(P.position, C.position);
// P - alle Projektionsgeraden ermitteln und projizieren
  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));
    // Projiziert den ersten Wert
    pmin := v2f_dotproduct(P.vertices[0], proj);
    pmax := pmin;
    // Findet den kleinsten und größten projizierten Wert für die Gerade für A
    for j := 1 to (P.count - 1) do
    begin
      // projizieren
      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 projizieren
    proj := v2f_normalize(v2f_sub(C.position, P.vertices_abs[i]));
    // s.o.
    pmin := v2f_dotproduct(P.vertices[0], proj);
    pmax := pmin;
    for j := 1 to (P.count - 1) do
    begin
      dp := v2f_dotproduct(P.vertices[j], proj);
      if dp < pmin then
        pmin := dp;
      if dp > pmax then
        pmax := dp;
    end;
    cmax := v2f_dotproduct(v2f_scale(proj, C.radius), proj);
    cmin := -cmax;
    foffset := v2f_dotproduct(voffset, proj);
    pmin := pmin + foffset;
    pmax := pmax + foffset;
    d1 := pmin - cmax;
    d2 := cmin - pmax;
    if (d1 > 0) or (d2 > 0) then
    begin
      result := false;
      exit;
    end;
  end;
  result := true;
end;

Kollision eines Punktes und eines Polygons

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 projiziert und geprüft ob er größer als das Minimum und kleiner als das Maximum des Polygons auf dieser Achse ist.

Kollision eines Tortenstücks und eines Polygons

Hier folgt demnächst eine Anleitung für die Kollision von beliebigen Tortenstücken mit einem Polygon.

Polygone trennen

Theorie

Damit unsere Kollisionserkennung praxistauglich wird, müssen die Polygone, wenn sie kollidieren auch wieder getrennt werden können. Hierzu benötigen wir einen Vektor, der unsere beiden Polygone wieder auseinander "schiebt". Selbstverständlich könnte man einen beliebigen Vektor nehmen, aber das Ergebnis wäre eher realtitätsfern, deshalb brauchen wir den Vektor, der den kürzesten Weg beschreibt, um die beiden Polygone zu trennen. Dieser Vektor wird auch MTD-Vektor genannt (Minimum Translation Distance). Hier kommt ein weiterer Vorteil des Separating Axis Theorems zum tragen, denn den Vektor den wir suchen, haben wir schon so gut wie berechnet. Wir multiplizieren alle unsere Projektionsachsen mit den Differenzen, die wir bei den eindimensionalen Kollisionen herausbekommen haben, somit erhalten wir Vektoren, die für das Außeinander-Schieben unserer Polygone geeignet sind. Nun müssen wir nur noch den kürzesten davon finden, dies ist unser MTD.

Der Code

Der bisherige Code sollte soweit verstanden sein, deshalb habe ich mir die Freiheit genommen ein wenig Code auszulagern:

function CreateAxis(P: TPolygon): TV2fArray;
var
  i, l: integer;
  tmp: TVector2f;
begin
  for i := 0 to (P.count - 1) do
  begin
    l := i + 1;
    if l > (P.count - 1) then
      l := 0;
    // Berechnung der Seitenfläche
    tmp := v2f_sub(P.vertices[l], P.vertices[i]);
    // Berechnet die Normale der Seitenfläche
    setlength(result, length(result) + 1);
    result[high(result)] := v2f_normalize(to_v2f(-tmp.y, tmp.x));
  end;
end;

procedure ProjectOntoAxis(P: TPolygon; proj: TVector2f; var pmin, pmax: extended);
var
  i: integer;
  dp: extended;
begin
  // Projiziert den ersten Wert
  pmin := v2f_dotproduct(P.vertices[0], proj);
  pmax := pmin;
  // Findet den kleinsten und größten projizierten Wert für die Gerade für P
  for i := 1 to (P.count - 1) do
  begin
    // projizieren
    dp := v2f_dotproduct(P.vertices[i], proj);
    if dp < pmin then
      pmin := dp;
    if dp > pmax then
      pmax := dp;
  end;
end;

function CollisionCheck(A, B: TPolygon; var axis: TVector2f; voffset: TVector2f): boolean;
var
  foffset,
  amin, amax,
  bmin, bmax,
  d1, d2, depth: extended;
begin
  ProjectOntoAxis(A, axis, amin, amax);
  ProjectOntoAxis(B, axis, bmin, bmax);
  foffset := v2f_dotproduct(voffset, axis);
  amin := amin + foffset;
  amax := amax + foffset;
  d1 := amin - bmax;
  d2 := bmin - amax;
  // Wenn es keine Überschneidung gibt, abbrechen -> keine Kollision
  if (d1 > 0) or (d2 > 0) then
  begin
    result := false;
    exit;
  end;
  // Ansonsten den Verschiebungsvektor bestimmen
  depth := max(d1, d2);
  axis := v2f_scale(axis, abs(depth));
  result := true;
end;

Die ersten beiden Funktionen sollten klar sein, bei der dritten gibt es eine kleine Neuerung. Wenn eine Kollision stattfindet, bricht diese Funktion nicht ab und die Projektionsachse wird mit der Differenz multipliziert, deren Betrag am kleinsten ist. Da es sich um negative Werte handelt kann man statt:

  depth := min(abs(d1), abs(d2));

ganz einfach:

  depth := max(d1, d2);

schreiben. Die neue PolyPolyIntersect Funktion sieht so aus:

function PolyPolyIntersect(A, B: TPolygon; var MTD: TVector2f): boolean;
var
  axis: TV2fArray;
  voffset: TVector2f;
  i: integer;
begin
  MTD := to_v2f(0, 0);
  // Offset berechnen
  voffset := v2f_sub(A.position, B.position);
  // Alle Achsen für A
  axis := CreateAxis(A);
  // Alle Achsen für B
  axis := CreateAxis(B);
  // Projizieren der Polygone
  for i := 0 to high(axis) do
    if CollisionCheck(A, B, axis[i], voffset) = false then
    begin
      result := false;
      exit;
    end;
  // MTD bestimmen
  MTD := axis[0];
  for i := 1 to high(axis) do
    if v2f_length(axis[i]) < v2f_length(MTD) then
      MTD := axis[i];
  if v2f_dotproduct(voffset, MTD) < 0 then
    MTD := v2f_scale(MTD, -1);
  // Kollision
  result := true;
end;

Hier werden zunächst alle Achsen ermittelt und dann projiziert, dabei werden die Achsen mit sämtlichen potentiellen MTDs überschrieben und daraus der kleinste berechnet. Diesen Vektor übergeben wir einfach mittels Var-Parameter und können dann unsere Polygone trennen, indem wir den MTD-Vektor von ihrer derzeitigen Position abziehen.

Dieser Code hier sorgt dafür, dass das Polygon auch wirklich von dem anderen getrennt und nicht noch weiter hineingeschoben wird:

  if v2f_dotproduct(voffset, MTD) < 0 then
    MTD := v2f_scale(MTD, -1);

Das Beispielprojekt

Beispiel 1 - Polygon <> Polygon

Was wäre ein Tutorial doch ohne Beispiel ;) Ich werde hier nur kurz die Verwendung des Codes erläutern und ein kleines Beispielprogramm anhängen. Ein Polygon muss natürlich erst einmal erzeugt werden:

A := TPolygon.Create;

Die einfachste Möglichkeit es zu gestalten funktioniert so:

  with A do
  begin
    position := to_v2f(200, 200);
    AddVertex(to_v2f(50, -50));
    AddVertex(to_v2f(50, 50));
    AddVertex(to_v2f(-50, 50));
    AddVertex(to_v2f(-50, -50));
  end;

Dies liefert ein Quadrat mit den Maßen 100*100 an der Position (200|200). Die Koordinaten der Vertices werden absolut zur Position und entgegen des Uhrzeigersinns angegeben.

Zeichnen kann man das Polygon dann ganz einfach so:

procedure TMainForm.DrawPolygon(A: TPolygon);
var
  i, l: integer;
begin
  for i := 0 to A.Count - 1 do
  begin
    l := i + 1;
    if l > (A.Count - 1) then
      l := 0;
    Image1.Canvas.MoveTo(round(A.vertices_abs[l].x), round(A.vertices_abs[l].y));
    Image1.Canvas.LineTo(round(A.vertices_abs[i].x), round(A.vertices_abs[i].y));
  end;
end;

Und hier das Beispielprojekt:

Exe: http://www.exec-dev.de/SAT_Tutorial/SAT_exe.zip

Source: http://www.exec-dev.de/SAT_Tutorial/SAT_src.zip

Beispiel 2 - Kreis <> Polygon

Für den Kreis ist die Verwendung im Prinzip die selbe, mit:

  C := TCircle.Create;

wird zunächst ein Kreis erzeugt und mit Position und Padius bekommt er seine Werte zugewiesen. Gezeichnet wird er mittels:

procedure TMainForm.DrawCircle(C: TCircle; aColor: TColor);
begin
  with Image1.Canvas do
  begin
    Pen.Color := aColor;
    Ellipse(round(C.position.x - C.radius), round(C.position.y - C.radius),
                          round(C.position.x + C.radius), round(C.position.y + C.radius));
  end;
end;

Und hier das Beispielprojekt für die Kollision Kreis <> Polygon:

Exe: http://www.exec-dev.de/SAT_Tutorial/SAT_Kreis_exe.zip

Source: http://www.exec-dev.de/SAT_Tutorial/SAT_Kreis_src.zip

Beispiel 3 - Trennung von Polygonen

In diesem Beispiel wird ein Polygon mittels:

  B.position := v2f_sub(B.position, MTD);

verschoben, sodass die beiden Polygone sich nicht schneiden. Es ließen sich auch beide um die Hälfte des Vektors verschieben, dies hängt von der Anwendung ab.

Hier gibt es die Exe und den Code für die Trennung von Polygonen:

Exe: http://www.exec-dev.de/SAT_Tutorial/SAT_Trennung_exe.zip

Source: http://www.exec-dev.de/SAT_Tutorial/SAT_Trennung_src.zip

Quellen

SAT-Tutorial(Eng) [1]

SAT-Tutorial(Eng / VB) [2]

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