Game-Physik - Kollisionserkennung in 2D: Schnittpunktbestimmung zweier Körper im R3?

29.08.2009, 18:48

Lufti

Game-Physik - Kollisionserkennung in 2D: Schnittpunktbestimmung zweier Körper im R3?

Hallo!

Ich suche jetzt schon seit Tagen eine Lösung und das, wie ihr seht, ohne Erfolg. Vielleicht könnt ihr mir helfen!

Mein Ziel ist es, für eine Kollisionserkennung in meinem freien 2D Java-Spiel den zeitlich ersten Schnittpunkt von zwei sich bewegenden 2D Polygonen zu finden.

Das Spiel steht ganz am Anfang seiner Entwicklung und ihr könnte es hier finden (Linux, Windows, Mac):
http://luftis-world.de/~web2_monochrome/

Das Scenario:
Das Spiel berechnet mir alle paar Millisekunden einen Schnappschuss der Positionen zweier Polygone.
Iin jedem Schnappschuss kenne ich von jedem Polygon die Punkte aus denen es aufgebaut ist - Einmal von seiner vorherigen Position aus dem vorigen "Schnappschuss" und einmal die Punkte, an seiner aktuellen Position.
Desweiteren habe ich auch den Bewegungsvektor und die vergangene Zeit, seit dem letzten Bild.
Eine Kollision zweier Polygone sehe ich so erst dann, wenn sie bereits ineinander stecken.

Eine Bewegung sieht folgendermaßen aus:

http://img526.imageshack.us/img526/6392/simulation.png

Jedes Polygon zieht während seiner Bewegung bildlich eine Schleifspur, welche im Grunde auch ein Polygon darstellt.
Erleutert durch folgendes Bild.

http://img36.imageshack.us/img36/6408/sweptshapes.png

Schneiden sich zwei solcher Schleifspuren, weiß ich, dass in der Zeit seit dem letzten Schnappschuss eine Kollision stattgefunden haben kann. Theoretisch könnten beide Polygone auch aneinander vorbei geflogen sein, ohne zu kollidieren. Schneiden sich aber sogar die beiden enthaltenen Polygone an der aktuellen, neuen Position kann ich mit Sicherheit sagen, dass eine Kollision stattgefunden hat.

Dies effizient zu programmieren stellt kein Problem dar. Anders sieht es mit dem nächsten Schritt aus, in dem es darum geht, den Kollisionspunkt zu ermitteln.

Das Ziel:
Um auf eine vergangene Kollision zu reagieren, muss ich den Punkt finden, an dem die zwei Polygone kollidiert sind.
Da ich eine Kollision, wie oben erwähnt, erst erkenne, wenn die Polygone sich schneiden, muss ich schlussendlich die beiden Polygone nur noch auf ihrer Zeitachse zum Kollisionspunkt zurückbewegen und spieltechnisch darauf reagieren, damit im nächsten Schnappschuss die selbe Kollision nicht erneut berechnet wird.

Die Idee:
Die Idee, den Kollisionspunkt zu finden, ist folgende:

Durch eine Überschneidung zweier Schleifspuren (die logischerweise auch Polygone darstellen) weiß ich ja, dass eine Kollision stattgefunden haben könnte, aber nicht haben muss, wie bereits erklärt.

Betrachtet man die Bewegung zweier 2D Polygone (x,y) in einem 3D Koordinatensystem, in dem die dritte Achse (z) die Zeit zwischen den berechneten Schnapschüssen führt, ergibt sich folgende anschauliche Grafik.

http://img137.imageshack.us/img137/893/timesweptshapes.png

Man sieht, dass sich die zwei Polygone (hier einfache Quadrate) im vorgen Schnappschuss (ganz oben bei t=0) noch nicht überschneiden, im aktuellen Schnappschuss (ganz unten) jedoch schon.
Der Einfachheit und wegen der vernachlässigbar kurzen Zeitspanne seit dem letzten Schnappschuss, wird so jede Bewegung linear dargestellt.

Eine nützliche Eigenschaft von Polygonen ist, dass sie bei ihrer Kollision praktisch immer so kollidieren, dass eine Ecke auf eine Kante trifft. Erweitert auf die 3D-Interpretation der Bewegung wäre das eine Kantenlinie mit einer Fläche (Ebene).
Suche ich mir jetzt alle Schnittpunkte jeder Seitenfläche eines der entstandenen 3D-Körper mit jeder Kantenlinie des anderen Körpers und umgekehrt, muss ich mir davon nur noch den Punkt aussuchen, der den niedrigsten Zeitwert (z-Achse) hat und dies ist dann mein Kollisionspunkt.

Das Problem:
Ansich ist die Idee toll! Allerdings hat sie einen Haken: Der Rechenaufwand.
Nimmt man nämlich zwei Polygone mit jeweils 20 Punkten, dann muss man 2 * 20 * 20 = 800 mal eine Kante mit einer Ebene schneiden. Das kostet viel zu viel teure Rechenzeit, da es ja jedesmal ein LGS ist, was ich lösen muss.
Eine andere Lösung muss also her!

Die Lösung?
Nun zu der eigentlichen Frage:
Habt ihr eine Idee, wie ich den Rechenaufwand senken kann? 800 Berechnungen für zwei Objekte sind zu viel.
Vielleicht kann man ja irgendwie logisch die Berechnungen reduzieren, oder Ähnliches?
Vielleicht ein ganz anderer Ansatz? Schätzung?

Meine Fachabi-Mathekenntnisse können mir hier leider nicht weiter helfen.
Ich hoffe sehr, dass ihr eine Idee für mich habt!

Vielen Dank im Voraus!
Falls ihr etwas nicht verstanden habt, fragt einfach nach.

29.08.2009, 19:50

Draos

Auf diesen Beitrag antworten »

Stelle mir grade 2 Kreise vor. Bei denen es Zonen gibt wo keine Kollision möglich wäre aufgrund der Lage und Richtung der Körper. Schau mal Anhang. Hier meine Vorstellungen.

http://imgbox.de/?pr=Draos-Kreise.png

Weiterhin kann man die Polygone optimieren. Sprich sehr nah aneinanderliegende Punkte zu einen zusammenfassen.

Den Algorithmus versuchen in asm umzuwandeln um eine sehr optimierte Version zubekommen, der mehr Zeit spart.

Oder die Polygone auf Grundkörper wie Kreise zurückführen (Approxation)

Oder die einfachste Methode mit versuchen, ob sie sich schneiden und wenn ja Schritt zurück und Schrittgröße verkleinern.

30.08.2009, 02:10

Lufti

Auf diesen Beitrag antworten »

Zitat:

Stelle mir grade 2 Kreise vor. Bei denen es Zonen gibt wo keine Kollision möglich wäre aufgrund der Lage und Richtung der Körper. Schau mal Anhang. Hier meine Vorstellungen.

http://imgbox.de/?pr=Draos-Kreise.png

Ich kapiere es nicht! Meinst du nicht vielleicht Kugeln?
In 2D kann ich schnell überprüfen, ob die Polygone sich überschneiden. In 3D, also mit der Zeitachse ist es ein Problem.
Vielleicht kannst du das noch etwas genauer erklären?

Zitat:

Weiterhin kann man die Polygone optimieren. Sprich sehr nah aneinanderliegende Punkte zu einen zusammenfassen.

Die Polygone sind schon optimiert. Alle Punkte sind gleichmäßig verteilt und nur die nötigsten verwendet.

Zitat:

Den Algorithmus versuchen in asm umzuwandeln um eine sehr optimierte Version zubekommen, der mehr Zeit spart.

Dadurch würde meine Platformunabhängig flöten gehen. Auch so wäre es die aller letzte Lösung.

Zitat:

Oder die Polygone auf Grundkörper wie Kreise zurückführen (Approxation)

Kreise oder Kugeln?

Zitat:

Oder die einfachste Methode mit versuchen, ob sie sich schneiden und wenn ja Schritt zurück und Schrittgröße verkleinern.

Darüber habe ich auch schon nachgedacht. Successive Aproximation, oder wie das heißt. Wie digitalen Messgeräten. Das wäre die vorletzte Lösung.

Gibt es da vielleicht irgend ein tolles Gauß-Verfahren? Der Gauß hat doch für alles was gemacht. Augenzwinkern

Trotzdem vielen Dank für deine Hilfe!!!

30.08.2009, 02:19

frank09

Auf diesen Beitrag antworten »

Der Einfachheit halber stelle ich mir zwei Polygone P und Q vor, bei denen sich nur P auf Q zubewegt. Sei der Bewegungsvektor $\begin{eqnarray*} \vec{v} =\begin{pmatrix} 9 \\ 4 \end{pmatrix} \end{eqnarray*}$ . Bild 1 stellt den letzten Schnappschuss vor der Kollision dar.
Es ist naheliegend, dass für eine Kollision nur die beiden Eckpunkte infrage kommen, die in Bewegungsrichtung am weitesten nach rechts (Polygon P) bzw. links (Polygon Q) hinausragen. Um diese zu ermitteln dreht man die Ebene so, dass der Bewegungsvektor waagerecht liegt. Um dir eine orthogonale Drehmatrix
zu ersparen schreibe ich es so: Sei Bewegungsvektor allgem. $\begin{eqnarray*} \vec{v} =\begin{pmatrix} v_1 \\ v_2 \end{pmatrix}, |\vec{v}|= \sqrt {v_1^2+v_2^2} \end{eqnarray*}$ dann wird durch die Drehung $\begin{eqnarray*} P(x|y) \end{eqnarray*}$ auf $\begin{eqnarray*} P'(x'|y') \end{eqnarray*}$ wie folgt abgebildet:
$\begin{eqnarray*} x'=\frac{v_1x+v_2y}{|\vec{v}|} \end{eqnarray*}$

$\begin{eqnarray*} y'=\frac{-v_2x+v_1y}{|\vec{v}|} \end{eqnarray*}$

Bild 2 wurde gedreht, also wurde etwa $\begin{eqnarray*} P2(19|22) \end{eqnarray*}$ so abgebildet( $\begin{eqnarray*} \vec{v} =\begin{pmatrix} 9 \\ 4 \end{pmatrix}|\vec{v}|= \sqrt {9^2+4^2}=9,85 \end{eqnarray*}$ )
$\begin{eqnarray*} x'=\frac{9\cdot19+4\cdot22}{9,85} = 26,3 \end{eqnarray*}$

$\begin{eqnarray*} y'=\frac{-4\cdot19+9\cdot22}{9,85}= 12,4 \end{eqnarray*}$

Nun bestimmt man den Punkt mit dem größten x-Wert bei P $\begin{eqnarray*} (=P2) \end{eqnarray*}$ und den mit dem kleinsten bei Q $\begin{eqnarray*} (=Q5) \end{eqnarray*}$ . Das wären die potentiellen Kollisionspunkte. Jetzt überprüft man noch, ob diese Punkte überhaupt auf eine Gerade treffen können.
Sie müssen gegenüber jeweils mindesten einen höheren und einen tieferen Punkt haben. Wäre dies nicht der Fall, ersetzt man ihn durch den mit der zweigrößten/-geringsten x-Koord. Um abschließend zu klären, ob eher $\begin{eqnarray*} Q5 \end{eqnarray*}$ auf die Kante $\begin{eqnarray*} P2P3 \end{eqnarray*}$ oder $\begin{eqnarray*} P2 \end{eqnarray*}$ auf $\begin{eqnarray*} Q5Q1 \end{eqnarray*}$ trifft, vergleicht man die Steigungen. Die steilere Kante wird zuerst getroffen. Die beiden Kanten, die in "Konkurrenz" stehen, ergeben sich aus der Verbindungslinie zwischen möglichem Kollisionspunkt und dem höheren/tieferen Nachbarpunkt. Genauer Ort/Zeit wäre also Schnittpunkt zwischen Kollisionspunkt-Bewegungslinie und der entsprechenden Kante.
Um das Ganze noch zu beschleunigen, kann man sich bei der Drehung auch die Division durch $\begin{eqnarray*} |v| \end{eqnarray*}$ sparen. Es wäre dann zwar ein Drehung mit Streckung, aber größter x-Wert bliebe größter x-Wert. Nur zur Schnittpunktberechnung dann die Original-Koord. benutzen.

30.08.2009, 10:39

Draos

Auf diesen Beitrag antworten »

Frank darf doch sicher mal deine Bilder nehmen.

Was ich meinte mit meinen 1. Punkt. Schau dir mal Franks 1. Bild an. Theoretisch ist es unmöglich, dass $\begin{eqnarray*} P_4, Q_2, Q_3 \end{eqnarray*}$ die Kollisionspunkte sind, da diese im Objektschatten (hinteranderen Punkten) liegen. Kreise hab ich nur genommen, da ich es mir damit besser vorstellen konnte als mit 10 Punkten im Kopf verwirrt

Oft werden bei Kollisionen mit großen Körpern. Die Körper elliptisch oder kugelförmig abgeschätzt um Rechenaufwand zu sparen. Oder nen extrem detailgenauer Grundkörper mit Einbuchtungen und co. als Quader gesehen. (Deshalb kann ich bei manchen Spielen durch Antennen fliegen oder explodiere beim Vorbeiflug traurig

)

Neue Frage »

Antworten »

Game-Physik - Kollisionserkennung in 2D: Schnittpunktbestimmung zweier Körper im R3?

Verwandte Themen