Wie vermeide ich in einer 2D-Physik-Engine nutzlose Kollisionsauflösungen, wenn Objekte zur Ruhe kommen?

9

In einer Physik-Engine, die ich (zum Lernen) mit love-2d entwickle , habe ich Kollisionsauflösungen folgendermaßen implementiert:

FixedUpdate(dt)  // I use fixed timestep
 foreach collide c1 in allNotStaticColliders
   c1.integartePhysic // i.e. apply gravitational force..
   foreach collider c2 "near" c1 // "near"= I use spatial hashing 
      if collide(c1,c2)
        resolve collision (c1,c2)  // the heavy operation
        collison callbacks c1
        collison callbacks c2
        ...

Animation von Objekten, die fallen und zum Stillstand kommen

Wie Sie am Ende der GIF-Animation sehen können, kommt es zu einem FPS-Abfall, wenn alle Collider fast über einem statischen Objekt geerdet sind.

der statische Endzustand mit 2 FPS

Dies liegt daran, dass die Anzahl der Kollisionsauflösungen zunimmt, wenn Objekte mehr Zeit damit verbringen, sich zu berühren, während sie sich niederlassen. Viele der Berechnungen sind jedoch "nutzlos", da sich Objekte bereits in stabilen Positionen gegeneinander niedergelassen haben.

Was ist die beste Vorgehensweise (hoffentlich ohne Abschluss in Physik), um diese "nutzlosen" Kollisionserkennungen zu vermeiden?

Bearbeiten: DMGregory-Hinweise akzeptiert und zu diesem Ergebnis kommen (noch nicht optimal)

Geben Sie hier die Bildbeschreibung ein

(Rot = statisch, Blau = aktiv, Grün = schlafend)

2d collision-detection physics optimization love2d dnk drone.vs.drones
quelle
1
Der übliche Ansatz besteht darin, Objekte, die zur Ruhe kommen, zu "schlafen" und keine Interaktionen zwischen schlafenden / statischen Objekten zu berücksichtigen (ein schlafendes Objekt kann jedoch weiterhin durch eine Interaktion mit einem dynamischen Objekt geweckt werden, das noch wach ist und sich bewegt). Leider hilft dies nur, wenn ein Objekt vollständig in Ruhe ist. Wenn ich Ihr Beispiel richtig lese, scheinen Ihre Leistungsprobleme zu beginnen, wenn sich die Objekte noch beruhigen und leicht bewegen. Alles, was ich hier denken kann, ist, dem System mehr Reibung / Dämpfung hinzuzufügen (möglicherweise mit einer Geschwindigkeitsschwelle), damit kleine Bewegungen schneller zur wahren Ruhe abfallen.
DMGregory
@ DMGregory Das klingt nach einer guten Antwort. Hinzufügen?
Anko

Antworten:

9

Ich vermutete, dass OP diesen Ansatz bereits kannte, also erwähnte ich ihn in einem Kommentar nur als Ausgangspunkt, aber ich werde versuchen, ihn ein bisschen weiter zu konkretisieren ...

Die meisten Physik-Engines teilen dynamische Objekte in zwei Gruppen ein: " wach " und " schlafend ".

Objekte schlafen, wenn sie in Ruhe sitzen, und wachen auf, wenn sie durch äußere Einflüsse bewegt oder beschleunigt werden.

Ein schlafendes Objekt verhält sich in vielerlei Hinsicht wie ein statisches Objekt - seine Bewegung wird im Laufe der Zeit nicht integriert (weil es sich in Ruhe befindet, also keine Bewegung hat) und die Engine ignoriert Kollisionen zwischen schlafenden oder statischen Objekten.

Ein schlafendes Objekt, das auf einem statischen Boden sitzt, fällt trotz fehlender Kollisionsreaktion nicht durch, da die gesamte Bewegungsintegration für schlafende Objekte, einschließlich der Schwerkraft, übersprungen wird.

Daher müssen nur Kollisionen mit mindestens einem wachen dynamischen Objekt überprüft werden:

Collisions    Static          Sleeping           Awake
          ------------------------------------------------
Awake     |    Check        Check & Wake         Check
Sleeping  |     No               No
Static    |     No

Dies kann die Anzahl der Objekte, die eine aktive Simulation benötigen, drastisch reduzieren, insbesondere bei Pfählen, bei denen, wie in der Frage dargestellt, viele gegenseitige Kollisionen auftreten, um festzustellen, ob keine oder nur geringe Nettobewegungen vorliegen.

Das Schlafen hilft jedoch erst, wenn die Objekte tatsächlich zur Ruhe kommen, was eine Weile dauern kann.

Einige Dinge, die Sie tun können, um früher zur Ruhe zu kommen:

  • Haben Sie eine Mindestgeschwindigkeit oder einen Mindestimpuls ungleich Null und klemmen Sie alles, was darunter fällt, auf Null. (Dies ist im Grunde ein Epsilon, das üblicherweise beim Vergleichen von Schwimmern verwendet wird.)

  • Verwenden Sie Reibung, Dämpfung und unelastische Kollisionen, um Energie aus dem System abzusaugen und es insgesamt schneller zur Ruhe zu bringen.

  • Erhöhen Sie die Reibung / Dämpfung / Unelastizität bei sich langsam bewegenden Objekten selektiv , um ihnen den letzten Anstoß zum Ausruhen zu geben, ohne das Verhalten energetischerer Körper zu beeinträchtigen.

DMGregory
quelle
Gute Antwort. Sie weisen auf eine Reihe guter Ideen hin. Bei den Schlaf- / Wachprüfungen sehe ich zwei Schwachstellen: 1) Wenn das schlafende Objekt o1 unter dem Schlafobjekt o2 erwacht und sich von o2 wegbewegt, erwacht es nicht o2; 2) Wenn ich eine statische Plattform unter einem schlafenden Objekt entferne, erwacht dieses Objekt nicht (unter Gravitationskraft)
dnk drone.vs.drones
1
@ dnkdrone.vs.drones Gute Beobachtungen. Da ich selbst noch nie eine Physik-Engine geschrieben habe, bin ich mir nicht sicher, wie dies normalerweise gehandhabt wird. Wenn Sie ein Objekt in den Ruhezustand versetzen, speichern wir eine Liste der Objekte, die es berührt (oder fügen Sie sie einem lokalen Cluster von Objekten hinzu). Wenn wir ein schlafendes Objekt wecken, wecken wir auch alles in seiner Liste / seinem Cluster. Möglicherweise gibt es elegantere Optionen, z. B. die Suche nach Kontakten in der Nähe beim Aufwachen (bevor diese entfernt werden).
DMGregory