Version vom 4. April 2007, 08:40 Uhr

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 Vektorrechnung zu haben.

Die Theorie

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

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

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

Auf dem linken Bild sieht man, wie beide Polygone auf die Gerade projeziert werden, der pinke Bereich zeigt die Schnittmenge an. In diesem Fall ist die Gerade die Normale der linken oder rechten Seite des Quadrats. Auf dem Bild rechts ist der Fall dargestellt, dass keine Kollision stattfindet, demzufolge gibt es auch keine Schnittmenge auf der Geraden. Dazu ist allerdings zu sagen, dass die Gerade keine räumliche Position hat. So wie Vektoren auch keine Positionen haben, Vektoren sind lediglich verschiebungsanweisungen und unsere "Gerade" wie ich sie hier nenne, ist auch nur ein Vektor, denn wo sie liegt ist letzten endes egal, da wir ja ein eindimensionales Ergebnis anstreben.

Für die Projektion eines Vektors auf einen anderen verwenden wir das Skalarprodukt, bei diesem kommt ein Zahlenwert heraus, der die Position des Eckpunktes auf unserer 1D-Geraden darstellt. Haben wir sämtliche Punkte projeziert, so müssen wir für die jeweiligen Polygone noch jeweils den kleinsten und größten Wert heraussuchen, damit wir zwei Strecken erhalten. Diese werden dann auf Schnitt geprüft und das wars.

Zusammenfassung

• Jedes der beiden Polygone durchgehen und alle nötigen Geraden aus den Normalen der Seitenflächen bestimmen
  • Jeden Eckpunkt jedes Polygons auf diese Geraden Projezieren
  • Die kleinsten und größten Werte ermitteln und auf Schnitt prüfen
• Tritt der Fall auf, dass kein Schnitt statt findet, so kann sofort abgebrochen werden, es findet keine Kollision statt.

Der Code

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

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

- Enthält: TVector2f

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

unit Vectors;

interface

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

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

implementation

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

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

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

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

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

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

  if L = 0 then
    L := 1;

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

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

end.

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

type
  TV2fArray = array of TVector2f;

Dann folgt die Definition unseres Polygons:

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

Unser Polygon hat jetzt eine Position und Eckpunkte, ebenfalls können wir auf absolute, sowie relative Koordinaten zugreifen. Count liefert uns die Anzahl der Ecken. [size=9][i](Eine Ecke bezeichnet man auch als Vertex, der Plural von Vertex ist Vertices.)[/i][/size] Hier sind die entsprechenden Funktionen:

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

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

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

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

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

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

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

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

function PolyPolyIntersect(A, B: TPolygon): boolean;
var
  i, j, l: integer;
  tmp, proj, voffset: TVector2f;
  dp, amin, amax, bmin, bmax, d1, d2, foffset: extended;
begin
  // Offset berechnen
  voffset := v2f_sub(A.position, B.position);
// A - alle Projektionsgeraden ermitteln und projezieren
  for i := 0 to (a.count - 1) do
  begin
    l := i + 1;
    if l > (a.count - 1) then
      l := 0;
    // Berechnung der Seitenfläche
    tmp := v2f_sub(a.vertices[l], a.vertices[i]);
    // Berechnet die Normale der Seitenfläche
    proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
    // Projeziert den ersten Wert
    amin := v2f_dotproduct(a.vertices[0], proj);
    amax := amin;
    // Findet den kleinsten und größten projezierten Wert für die Gerade für A
    for j := 1 to (a.count - 1) do
    begin
      // projezieren
      dp := v2f_dotproduct(a.vertices[j], proj);
      if dp < amin then
        amin := dp;
      if dp > amax then
        amax := dp;
    end;
    // s.o.
    bmin := v2f_dotproduct(b.vertices[0], proj);
    bmax := bmin;
    // B
    for j := 1 to (b.count - 1) do
    begin
      dp := v2f_dotproduct(b.vertices[j], proj);
      if dp < bmin then
        bmin := dp;
      if dp > bmax then
        bmax := dp;
    end;
    // 1D Kollision
    foffset := v2f_dotproduct(voffset, proj);
    amin := amin + foffset;
    amax := amax + foffset;
    d1 := amin - bmax;
    d2 := bmin - amax;
    // Wenn es keine Überschneidung gibt, abbrechen -> keine Kollision
    if (d1 > 0) or (d2 > 0) then
    begin
      result := false;
      exit;
    end;
  end;
// B - alle Projektionsgeraden ermitteln und projezieren (s.o.)
  for i := 0 to (b.count - 1) do
  begin
    l := i + 1;
    if l > (b.count - 1) then
      l := 0;
    tmp := v2f_sub(b.vertices[l], b.vertices[i]);
    proj := v2f_normalize(to_v2f(-tmp.y, tmp.x));
    amin := v2f_dotproduct(a.vertices[0], proj);
    amax := amin;
    for j := 1 to (a.count - 1) do
    begin
      dp := v2f_dotproduct(a.vertices[j], proj);
      if dp < amin then
        amin := dp;
      if dp > amax then
        amax := dp;
    end;
    bmin := v2f_dotproduct(b.vertices[0], proj);
    bmax := bmin;
    for j := 1 to (b.count - 1) do
    begin
      dp := v2f_dotproduct(b.vertices[j], proj);
      if dp < bmin then
        bmin := dp;
      if dp > bmax then
        bmax := dp;
    end;
    foffset := v2f_dotproduct(voffset, proj);
    amin := amin + foffset;
    amax := amax + foffset;
    d1 := amin - bmax;
    d2 := bmin - amax;
    if (d1 > 0) or (d2 > 0) then
    begin
      result := false;
      exit;
    end;
  end;
  // Kollision
  result := true;
end;

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

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

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

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

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

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

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

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

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

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

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

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

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

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:

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).

Zeichnen kann man das Polygon 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

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