Was ist der beste Weg, um mit gleichzeitigen Kollisionen in einer Physik-Engine umzugehen?

13

Ich schreibe eine 2D-Physik-Engine in Javascript, damit ich mehr über Physik in Videospielen erfahren kann. Ich habe es richtig funktioniert für Starrkörperkollisionen, außer wenn ein Körper gleichzeitig mit zwei oder mehr anderen Körpern kollidiert.

Gegenwärtig ändere ich für jedes Paar kollidierender Körper (A, B) ihre Geschwindigkeiten und Winkelgeschwindigkeiten basierend auf dem Kollisionsimpuls und stoße sie gegeneinander aus, damit sie nicht eindringen. Dann sind Kollisionserkennung und Impulsberechnung für andere Kollisionen mit A jedoch falsch.

Welche Ansätze kann ich untersuchen, um meine Engine für 3+ Objekte zum Kollidieren zu bringen?

2d collision-detection javascript physics Nocken
quelle
2
Verwandte Themen : gamedev.stackexchange.com/questions/15836/… und gamedev.stackexchange.com/questions/26181/… und ich bin mir sicher, dass es noch mehr gibt, ich kann das gerade nicht finden.
MichaelHouse

Antworten:

11

Ich benutze den folgenden Ansatz (ähnlich dem Massensplitting-Algorithmus von Tonge http://www.richardtonge.com/ ):

  • Finde alle kollidierenden Paare in deiner Szene / deinem Kontext. Sei (A, B) ein solches Paar. Wenden Sie eine Idee zur Aufspaltung von Geistern / Massen an: Wenn A mit M Körpern in Kontakt steht und B mit N anderen Körpern in Kontakt steht, setzen Sie die Masse von A auf und die von B vorübergehendm_A/M aufm_B/N
  • Berechnen Sie die Reaktions- / Rückgabekraftbeiträge für jedes Paar (A, B) und speichern Sie diese Beiträge in den eigenen Akkumulatoren von A und B
  • Berechnen Sie die Restitutionsgeschwindigkeiten aus Impulsen (wie Sie angegeben haben) und speichern Sie sie auf die gleiche Weise (als DeltaV- Geschwindigkeitsreste in ihren eigenen Akkumulatoren für jedes (A, B) Paar).
  • Strafverschiebungen berechnen (wieder Verschiebungen akkumulieren, nicht sofort anwenden!)
    • die Massen aller zuvor als Parteien in Kollisionspaaren bezeichneten Körper zurücksetzen ( m_A = m_A * Mund m_B = m_B * N)

Dieser Ansatz ähnelt der Arbeitsweise des Jacobi-Iterationsalgorithmus mit linearen simultanen Gleichungssystemen. Und es ist nicht garantiert, dass es konvergiert, aber in meinem Simulator funktioniert es ganz reibungslos. In 3D (ja, eine zusätzliche Dimension fügt die doppelte Schwierigkeit hinzu!).

Vorsichtsmaßnahme : Korrigieren Sie Positionen und Geschwindigkeiten erst, nachdem die Phase der Kollisionserkennung / -behandlung beendet ist! Auf diese Weise aktualisieren Sie gleichzeitig Ihre kollidierenden Schauspieler. Auch die Restitutionskräfte müssen beim nächsten Integrieren für Positionen und Geschwindigkeiten berücksichtigt werden.

EDIT: Nun, ich vermute, Sie verwenden die bereits missbräuchliche Verlet-Integrationsmethode (diese ist unter Gamedev-Enthusiasten ein Begriff geworden). In diesem Bereich der Kollisionsbehandlung und -integration möchten Sie vielleicht einen Blick hier werfen .

UPDATE: Einige Informationen zur Vorgehensweise bei Kollisionen (und zur Selbstkollision) finden Sie in den folgenden Abhandlungen:

Der von mir vorgeschlagene Ansatz ist bei weitem kein Originalbeitrag, viele Spiele verwenden ihn mit plausiblen Ergebnissen, und Jakobsen hat ihn am besten in seiner Hitman-Game-Engine eingesetzt.

Aus einer etwas praktischen Erfahrung heraus lösen Strafkräfte (ähnlich wie lineare oder exponentielle Federn, die ihren Input aus der Eindringdistanz erhalten) Penetrationen nicht richtig, wenn andere Kräfte von den Körpern, die kollidieren, es schaffen, größer als sie zu sein. Deshalb habe ich drei (fast redundante) Ansätze kombiniert: Newtonsche Reaktionskräfte (Sie drücken die Wand, die Wand drückt zurück), impulsabgeleitete Geschwindigkeiten (Snooker-Bälle kollidieren) und eine nicht-natürliche "Bewegung der Körper geometrisch voneinander weg" "lösung. Zusammen scheinen sie alles zu bieten: die meisten loszuwerdenhässliche Durchdringungsartefakte, kollidierende Körper neigen dazu, auf lange Sicht miteinander zu interagieren (aufgrund von Rückgabegeschwindigkeiten und Kräften - zumindest werden die Kräfte, die dazu neigten, die Körper in einem Kollisionsszenario zu ziehen, aufgehoben und die Körper prallen voneinander ab) . Zum besseren Verständnis dieser einfachen, aber gebräuchlichen Konzepte schlage ich vor, diese Folien zu analysieren .

Mein Epitheton "Missbrauchte Methode", das die Verlet-Integrationsschritte beschreibt, zielt auf eine populärkulturelle Überzeugung ab, dass dies der Heilige Gral der Integrationsmethoden ist. Es ist nur unwesentlich besser als sein Cousin Symplectic Euler (auch von einem halb-impliziten Euler genannt). Es gibt weitaus kompliziertere Integrationsmethoden (und alle tragen den impliziten Namen in sich). Leistungsstarke Spiele-Engines nutzen sie, aber Indie-Entwickler haben nicht die Zeit, mit ihnen zu experimentieren, da Verlet, wenn es auf ein bestimmtes Szenario abgestimmt ist, wirklich Wunder vollbringt. Außerdem gibt es absolut keine Integrationsmethode, die mit harten Einschränkungen umgehen kann, ohne dass ein wenig betrogen wird (der Link kann nicht gefunden werden, aber das von mir erwähnte Papier sollte "X.Provot -" Deformationsbeschränkungen in einer Masse heißen -Federmodell zur Beschreibung des starren Stoffverhaltens

Teodron
quelle
Danke (+1)! Was sind "Wiedergutmachungsgeschwindigkeit" und "Strafverschiebungen"? Warum wird Verlet-Integration Ihrer Meinung nach "missbraucht"? Halten Sie es für eine schlechte Methode?
Cam
Wiederherstellungsgeschwindigkeiten sind genau die Geschwindigkeiten, die Sie von Impulsen erhalten. Der einzige Unterschied besteht darin, dass ich sie als Reste berechne (dh ich speichere die Differenz zwischen dieser impulsbasierten Geschwindigkeit und der aktuellen Geschwindigkeit, während die aktuelle Geschwindigkeit für weitere Berechnungen unberührt bleibt). Strafverschiebungen sind Vektoren mit einer Länge, die davon abhängt, wie viele Objekte sich gegenseitig durchdringen, und es ist der minimale Längenvektor, der ein Objekt vollständig außerhalb des anderen verschieben kann. Normalerweise addiere ich eine solche Verschiebung zu jedem Objekt, indem ich die Länge durch 2) teile.
Teodron
1
Geniale Antwort! Ich habe aber noch eine andere Frage. Angenommen, ich akkumuliere die Rückgabegeschwindigkeiten. Addieren sich diese nicht zu einer sehr unrealistischen Zahl? Wenn ich jede Kollision mit Objekt A separat behandle und nur die Auswirkungen auf jedes Objekt aufsummiere, verteilt sich der Impuls von A dann nicht zwischen den Objekten? Stattdessen wird jeder mit vollem Impuls beaufschlagt, was mir intuitiv falsch erscheint
Cam
Das ist eine sehr gute Frage. Aus der Sicht scheint es plausibel, dass Impulse additiv zur resultierenden Geschwindigkeit beitragen. Hier ist meine (vielleicht fehlerhafte!) Argumentation: Stell dir vor, drei Billardkugeln kollidieren. Einer von ihnen sollte auf diese additive Weise Beiträge von den anderen beiden erhalten. Anfangs dachte ich, diese Beiträge abzuwägen und einen gewichteten Durchschnitt für die Endgeschwindigkeit zu berechnen, aber da ich schnelle Ergebnisse wollte, ließ ich diese Idee aus. Alles in allem muss der kollidierende Ball Geschwindigkeitsbeiträge von den verbleibenden beiden erhalten. Vielleicht kann ein Schulbuch helfen.
Teodron
3
Vielleicht verstehe ich nicht, was Sie erklärt haben, weil mich das folgende Beispiel immer noch beschäftigt: Stellen Sie sich ein horizontal langes Rechteck vor, das gerade nach unten fällt, und nehmen Sie an, dass der Boden gezackt ist (also aus mehreren nebeneinander liegenden Dreiecken besteht). Wenn es n Dreiecke gibt, springt das Rechteck mit Ihrer Akkumulationsmethode mit der n-fachen Geschwindigkeit zurück, die es sollte! Wie kann diese Situation behoben werden?
Cam
1

Ich schlage vor, dass Sie die auf ein Objekt einwirkenden Kräfte ändern, anstatt die Geschwindigkeiten zu ändern . Schieben Sie sie nicht raus, sondern machen Sie es reibungslos und verwenden Sie bereits vorhandenen Code. Auf diese Weise ändern die Körper nicht sofort (und vermutlich auch schnell) ihre Geschwindigkeiten.

Schauen Sie sich Box2DJS als Beispiel an: http://box2d-js.sourceforge.net/index2.html .

jcora
quelle
-1

Ich habe die Impulsgleichung für Gruppen kollidierender Körper analytisch gelöst. Das einzige Problem, mit dem ich konfrontiert war, war der Mangel an Variablen, um die relative Interaktionsstärke zwischen Kontakten in einer Gruppe zu finden, die ich mit der Tiefe der Körperschnittpunkte gefüllt habe.

Die Lösung für Gruppenkontakte ist nicht viel schwieriger als für Einzelkontakte. Leider habe ich eine Arbeit mit Berechnungen verloren und kann sie hier nicht weitergeben.

Edit: Wahrscheinlich habe ich mir so etwas ausgedacht: /physics/296767/multiple-colliding-balls

George Vinokhodov
quelle