Tutorial Separating Axis Theorem - Versionsgeschichte

Openglerf: Rechtschreibfehler ausgebessert

2013-09-25T14:32:58Z

Rechtschreibfehler ausgebessert

Seth: Link zum englischen Tutorial aktualisiert.

2011-10-23T20:34:58Z

Link zum englischen Tutorial aktualisiert.

DGLBot: Der Ausdruck ''\{\{DateiLink\|'' wurde ersetzt mit ''{{ArchivLink|''.

2009-05-17T09:02:19Z

Der Ausdruck ''\{\{DateiLink\|'' wurde ersetzt mit ''{{ArchivLink|''.

Flash: /* Das Beispielprojekt */

2009-05-02T19:04:32Z

‎Das Beispielprojekt

Flo: Neue Datei Links

2009-05-02T16:23:18Z

Neue Datei Links

DGLBot: Der Ausdruck ''(.*?)'' wurde ersetzt mit ''$1''.

2009-03-10T18:14:49Z

Der Ausdruck ''<pascal>(.*?)</pascal>'' wurde ersetzt mit ''<source lang="pascal">$1</source>''.

Seth am 11. März 2008 um 16:07 Uhr

2008-03-11T16:07:14Z

Seth: normalisiert durch normiert ersetzt

2008-03-11T16:05:30Z

normalisiert durch normiert ersetzt

Seth am 11. März 2008 um 16:03 Uhr

2008-03-11T16:03:36Z

Seth: Code für Rotation hinzugefügt

2008-03-11T16:02:49Z

Code für Rotation hinzugefügt

@@ Zeile 159: / Zeile 159: @@
 == 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.
+Ich hoffe das Tutorial war nicht zu trocken und hat vielleicht auch ein wenig Spaß gemacht und weitergeholfen. Für Fragen, Vorschläge, Ergänzungen, etc. bin ich selbstverständlich offen.
 mfg

@@ Zeile 153: / Zeile 153: @@
 == Links ==
-SAT-Tutorial(Eng) [http://www.harveycartel.org/metanet/tutorials/tutorialA.html]
+SAT-Tutorial(Eng) [http://www.metanetsoftware.com/technique/tutorialA.html]
 SAT-Tutorial(Eng / VB) [http://gpwiki.org/index.php/VB:Tutorials:Building_A_Physics_Engine:Basic_Intersection_Detection]

@@ Zeile 106: / Zeile 106: @@
 '''Und hier das Beispielprojekt:'''
-* {{DateiLink|file=tut_SAT_exe|text=Windows-Binary}}
+* {{ArchivLink|file=tut_SAT_exe|text=Windows-Binary}}
-* {{DateiLink|file=tut_SAT_src|text=Delphi-Quelltext}}
+* {{ArchivLink|file=tut_SAT_src|text=Delphi-Quelltext}}
 === Beispiel 2 - Kreis <> Polygon ===
@@ Zeile 118: / Zeile 118: @@
 '''Und hier das Beispielprojekt für die Kollision Kreis <> Polygon:'''
-* {{DateiLink|file=tut_SAT_Kreis_exe|text=Windows-Binary}}
+* {{ArchivLink|file=tut_SAT_Kreis_exe|text=Windows-Binary}}
-* {{DateiLink|file=tut_SAT_Kreis_src|text=Delphi-Quelltext}}
+* {{ArchivLink|file=tut_SAT_Kreis_src|text=Delphi-Quelltext}}
 === Beispiel 3 - Trennung von Polygonen ===
@@ Zeile 131: / Zeile 131: @@
 '''Hier gibt es die Exe und den Code für die Trennung von Polygonen:'''
-* {{DateiLink|file=tut_SAT_Trennung_exe|text=Windows-Binary}}
+* {{ArchivLink|file=tut_SAT_Trennung_exe|text=Windows-Binary}}
-* {{DateiLink|file=tut_SAT_Trennung_src|text=Delphi-Quelltext}}
+* {{ArchivLink|file=tut_SAT_Trennung_src|text=Delphi-Quelltext}}
 === Beispiel 4 - Rotation ===
@@ Zeile 149: / Zeile 149: @@
 '''Hier gibt es den Code für die Behandlung von Rotation:'''
-* {{DateiLink|file=tut_SAT_Rotation_src|text=Delphi-Quelltext}}
+* {{ArchivLink|file=tut_SAT_Rotation_src|text=Delphi-Quelltext}}
 == Links ==

@@ Zeile 106: / Zeile 106: @@
 '''Und hier das Beispielprojekt:'''
-* [[Datei:tut_SAT_exe|Windows-Binary]]
+* {{DateiLink|file=tut_SAT_exe|text=Windows-Binary}}
-* [[Datei:tut_SAT_src|Delphi-Quelltext]]
+* {{DateiLink|file=tut_SAT_src|text=Delphi-Quelltext}}
 === Beispiel 2 - Kreis <> Polygon ===
@@ Zeile 118: / Zeile 118: @@
 '''Und hier das Beispielprojekt für die Kollision Kreis <> Polygon:'''
-* [[Datei:tut_SAT_Kreis_exe|Windows-Binary]]
+* {{DateiLink|file=tut_SAT_Kreis_exe|text=Windows-Binary}}
-* [[Datei:tut_SAT_Kreis_src|Delphi-Quelltext]]
+* {{DateiLink|file=tut_SAT_Kreis_src|text=Delphi-Quelltext}}
 === Beispiel 3 - Trennung von Polygonen ===
@@ Zeile 131: / Zeile 131: @@
 '''Hier gibt es die Exe und den Code für die Trennung von Polygonen:'''
-* [[Datei:tut_SAT_Trennung_exe|Windows-Binary]]
+* {{DateiLink|file=tut_SAT_Trennung_exe|text=Windows-Binary}}
-* [[Datei:tut_SAT_Trennung_src|Delphi-Quelltext]]
+* {{DateiLink|file=tut_SAT_Trennung_src|text=Delphi-Quelltext}}
 === Beispiel 4 - Rotation ===
@@ Zeile 149: / Zeile 149: @@
 '''Hier gibt es den Code für die Behandlung von Rotation:'''
-* [[Datei:tut_SAT_Rotation_src|Delphi-Quelltext]]
+* {{DateiLink|file=tut_SAT_Rotation_src|text=Delphi-Quelltext}}
 == Links ==

@@ Zeile 106: / Zeile 106: @@
 '''Und hier das Beispielprojekt:'''
+* [[Datei:tut_SAT_exe|Windows-Binary]]
-''Exe:'' [http://files.delphigl.com/download/tut_SAT_exe.zip tut_SAT_exe.zip]
+* [[Datei:tut_SAT_src|Delphi-Quelltext]]
 === Beispiel 2 - Kreis <> Polygon ===
@@ Zeile 120: / Zeile 118: @@
 '''Und hier das Beispielprojekt für die Kollision Kreis <> Polygon:'''
+* [[Datei:tut_SAT_Kreis_exe|Windows-Binary]]
-''Exe:'' [http://files.delphigl.com/download/tut_SAT_Kreis_exe.zip tut_SAT_Kreis_exe.zip]
+* [[Datei:tut_SAT_Kreis_src|Delphi-Quelltext]]
 === Beispiel 3 - Trennung von Polygonen ===
@@ Zeile 135: / Zeile 131: @@
 '''Hier gibt es die Exe und den Code für die Trennung von Polygonen:'''
+* [[Datei:tut_SAT_Trennung_exe|Windows-Binary]]
-''Exe:'' [http://files.delphigl.com/download/tut_SAT_Trennung_exe.zip tut_SAT_Trennung_exe.zip]
+* [[Datei:tut_SAT_Trennung_src|Delphi-Quelltext]]
 === Beispiel 4 - Rotation ===
@@ Zeile 155: / Zeile 149: @@
 '''Hier gibt es den Code für die Behandlung von Rotation:'''
+* [[Datei:tut_SAT_Rotation_src|Delphi-Quelltext]]
 == Links ==

@@ Zeile 88: / Zeile 88: @@
 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>
+<source lang="pascal">
 A := TPolygon.Create;
-</pascal>
+</source>
 Die einfachste Möglichkeit es zu gestalten funktioniert so:
-<pascal>
+<source lang="pascal">
    with A do
    begin
@@ Zeile 101: / Zeile 101: @@
      AddVertex(to_v2f(-50, -50));
    end;
-</pascal>
+</source>
 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.
@@ Zeile 114: / Zeile 114: @@
 Für den Kreis ist die Verwendung im Prinzip die selbe, mit:
-<pascal>
+<source lang="pascal">
    C := TCircle.Create;
-</pascal>
+</source>
 wird zunächst ein Kreis erzeugt und mit Position und Padius bekommt er seine Werte zugewiesen.
@@ Zeile 128: / Zeile 128: @@
 In diesem Beispiel wird ein Polygon mittels:
-<pascal>
+<source lang="pascal">
    B.position := v2f_sub(B.position, MTD);
-</pascal>
+</source>
 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.
@@ Zeile 143: / Zeile 143: @@
 Die Rotation des Polygons erfolgt beim Auslesen der Vertex Koordinaten mittels einer Rotationsmatrix:
-<pascal>
+<source lang="pascal">
 function TPolygon.GetVertex(n: integer): TVector2f;
 var
@@ Zeile 152: / Zeile 152: @@
    result.y := fvertices[n].x * asin + fvertices[n].y * acos;
 end;
-</pascal>
+</source>
 '''Hier gibt es den Code für die Behandlung von Rotation:'''

@@ Zeile 72: / Zeile 72: @@
 == Polygone trennen ==
-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 (für '''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.
+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 die Normale der Kollision oder '''MTD'''-Vektor genannt (für '''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 eindimensionalen Kollisionen herausbekommen haben, somit erhalten wir Vektoren, die für das Außeinander-Schieben unserer Polygonein in Frage kommen. Nun müssen wir nur noch den kürzesten davon finden, dies ist unser MTD. Allerdings sollte man vor der Verwendung sicherstellen, dass dieser Vektor vom Polygon wegzeigt. Hierzu können wir ebenfalls das Skalarprodukt nutzen.

@@ Zeile 23: / Zeile 23: @@
 die Koordinaten werden vertauscht und eine von beiden wird negiert, so erhält man einen Vektor der senkrecht zu dem original Vektor ist. Da es zwei Möglichkeiten gibt, spricht man von der linken oder rechten Normale (aus der Sicht des Vektors).
-Der Vektor muss dann noch normalisiert werden, sodass er die Länge 1 erhält,.
+Der Vektor muss dann noch normiert werden, sodass er die Länge 1 erhält,.
 Jetzt müssen beide Polygone auf diesen Vektor projiziert werden, denn dadurch erhalten 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. Dies ist auch  der Grund, warum dieses Verfahren recht schnell ist, da im besten Fall schon im ersten
@@ Zeile 60: / Zeile 60: @@
 === Zusammenfassung ===
-*Wir berechnen also den Vektor vom Kreis-Mittelpunkt zum Vertex, dieser wird normalisiert.
+*Wir berechnen also den Vektor vom Kreis-Mittelpunkt zum Vertex, dieser wird normiert.
 *Dann projizieren wir das Polygon wie gehabt
 *Der Kreis wird projiziert, indem der Vektor, auf den wir projizieren, 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.

@@ Zeile 140: / Zeile 140: @@
 ''Source:'' [http://files.delphigl.com/download/tut_SAT_Trennung_src.zip tut_SAT_Trennung_src.zip]
-== Quellen ==
+=== Beispiel 4 - Rotation ===
 SAT-Tutorial(Eng) [http://www.harveycartel.org/metanet/tutorials/tutorialA.html]