Kollisionsauflösung bei Kollision mit mehreren Objekten

15

Ich habe statische und bewegliche Objekte. Die Kollisionen werden mit dem Trennachsensatz erfasst.

In dieser Situation habe ich zum Beispiel zwei statische Objekte (in rot):

Bildbeschreibung hier eingeben

und ein bewegliches Objekt zwischen den beiden:

Bildbeschreibung hier eingeben

Mein Algorithmus ist in der Lage, die Kollision zwischen zwei dieser Objekte zu berechnen und spuckt außerdem einen Vektor mit perfekter Auflösung (dh einen Vektor mit minimaler Verschiebung) aus.

Wenn ich zum Beispiel die Kollision zwischen dem grünen und dem rechten roten Rechteck überprüfe, spuckt der Algorithmus einen Vektor aus, der mir sagt, wie ich das grüne Rechteck verschieben muss, um die Kollision aufzulösen:

Bildbeschreibung hier eingeben

Beachten Sie, dass ich dies in MSPaint gerade schnell gezeichnet habe, so dass es in diesem Bild tatsächlich sein kann, dass der Minimum-Übersetzungsvektor das grüne Rechteck oben herausdrückt, aber ich gehe hier davon aus, dass es nach links herausdrückt / rechts ist eigentlich kürzer.

Der allgemeine Weg, dies zu erreichen, besteht darin, nur die Kollision einer Kollision pro Frame aufzulösen, anstatt alle auf einmal. In meinem Fall würde dies jedoch zu Flip-Flops führen:

Zunächst erkennt der Solver zwei Kollisionen, löst jedoch nur die Kollision zwischen dem rechten und dem grünen Rechteck auf:

Bildbeschreibung hier eingeben

Im nächsten Frame erkennt es dann nur eine Kollision zwischen dem linken roten und dem grünen Rechteck und löst sie auf:

Bildbeschreibung hier eingeben

Wie Sie sehen, wird die Kollision dadurch nicht behoben (z. B. indem das grüne Rechteck nach oben gedrückt wird), sondern es werden einfach die Flops unendlich zwischen den beiden Zuständen gewechselt.

Wie kann ich das lösen?

TravisG
quelle
In Ihrem Beispiel verwenden Sie Rechtecke. Löst Ihr Kollisionsalgorithmus Kollisionen nur auf einer Achse auf? In diesem Fall ist es sinnvoll, dass das von Ihnen beschriebene Verhalten auftritt.
ChaosTechnician
Nein, es kann sie mit jeder Art von Form auf allen möglichen Achsen auflösen (nicht nur mit Rechtecken, sondern am einfachsten mit MS paint: P zu zeichnen) und es wird immer der kürzeste Vektor gefunden, der existiert, der die beiden Objekte auseinander drückt .
TravisG
+1 Gute Frage. Ich habe das (2D) "Tag" aus dem Titel entfernt, das sollten Sie vermeiden (siehe Meta ).
Bummzack

Antworten:

7

Abhängig davon, was Sie erreichen möchten (hohe physikalische Genauigkeit oder eine hinreichend genaue Echtzeitsimulation), können Sie versuchen, spekulative Kontakte zu verwenden.

Hier sind die Details: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

Er beschreibt in diesem Artikel, was Sie wissen müssen, um es zu implementieren, und es ist sehr einfach im Vergleich zu anderen Ansätzen (wie Kugelwurf und anschließendes Sortieren von Kollisionsauflösungen nach Aufprallzeit).

Wenn Sie mehr brauchen / wollen, können Sie seinen Quellcode für (IIRC) $ 7 kaufen.

Hier ist ein Video meiner Implementierung in 3D: http://www.youtube.com/watch?v=JvT2H1RmOas

Beachten Sie, wie stabil die Simulation mit nur einer einzigen Iteration ist. Sie können problemlos mehrere Iterationen pro Frame verwenden, um mehrere Kollisionen in einen stabilen Zustand aufzulösen, der genauer wäre.

Olhovsky
quelle
2

Sie können zuerst alle Vektoren berechnen, die zum Lösen jeder Kollision erforderlich sind, und dann daraus eine Resultierende berechnen.

Der einzige Fall, in dem dies ein Byte sein kann, besteht darin, dass sich diese Vektoren gegenseitig aufheben, genau wie in Ihrem Beispiel. In diesem Fall kann die Kollision nicht gelöst werden.

Mihai Maruseac
quelle
Addiere einen kleinen zufälligen Vektor mit einer Größe von ungefähr 10 epsilon * zu den Kollisionen? Fließkomma-Arithmetik sollte den Rest erledigen.
Martin Sojka
2
Ja, das kann funktionieren, denke ich. Es kann aber auch zu zitternden Bewegungen kommen.
Mihai Maruseac
1
Ich hoffe, ich kann immer noch eine Antwort auf diese Frage bekommen: Das Berechnen eines Resultats behebt das Problem der "Endlosschleife", führt aber das "Riss" -Problem erneut ein, bei dem das Bewegen auf einer Wand aus Fliesen gleicher Größe den Körper zum Erhalten bringt zwischen den "Rissen" der Fliesen stecken. Gibt es eine Möglichkeit, diese beiden Probleme zu lösen?
Vittorio Romeo
Einverstanden ... es gibt keine beste "richtige Antwort", um eine solche unmögliche Starrkörperkollision zu lösen. Entweder zittert es, oder Sie lassen in einem oder mehreren Objekten etwas "Mushiness" zu.
David van Brink
0

Wenn Sie genau hinschauen, ist (oder sollte) dieser Zustand von Objekten unerreichbar.

Die am weitesten links stehende rote Form sei Form R1, und die am weitesten rechts stehende rote Form sei Form R2. Die grüne Form sei G.

Das heißt, wenn die Größe und Geometrie aller drei Objekte gegeben ist und nicht alle Objekte durchdringbar sind:

 (1) G could not have been just directly to the left of R2, since R1 has been there 
     already. Consequently, the translation of G from left to right, penetrating R2
     could not have occurred.
 (2) G could not have been just directly to the right of R1 since R2 has been there 
     already. Consquence of which is the same as that from (1).
 (3) Had G come from the top, the movement will be blocked by both R1 and R2, given
     that their geometry and Y coordinate is the same.

Fazit: Wenn Ihr Algorithmus Ihre Objekte nacheinander abfragt, handelt es sich um eine Nebenläufigkeit. In gewissem Sinne soll der Algorithmus ALLE Objekte gleichzeitig prüfen, aber der Algorithmus schränkt Sie ein Objekte und verarbeiten sie nacheinander ...

Wenn G gegen R1 geprüft wird, nachdem es gegen R2 geprüft wurde, scheint G legal rechts von R1 zu sein (wenn G sich R1 mit der Richtung des Vektors <-1, -1> mit beliebiger Größe (oder Entfernung) nähert) ), weil die Überprüfung zwischen R1 und G dies erlaubt und die zuvor durchgeführte Überprüfung zwischen R2 und G vergisst.

Eine mögliche Lösung besteht darin, alle Vektoren mit minimaler Verschiebung in einem Array oder einer beliebigen Datenstruktur zu sammeln und eine zu wählen, die für ALLE Objekte zulässig ist.

Beachten Sie, dass das Objekt (z. B. G) in einem bestimmten Frame nur EINE Richtung haben kann. (Oh Mann, hört sich an wie die Boyband ...)

Liu Mao Hsing
quelle