Verbesserte Simulation und Leistung mit einem fortgeschrittenen Physics-Solver
Erhöhte Genauigkeit durch den Punkt-Gauß-Seidel-Solver.
2016 fingen wir an, diverse neue physikalische Einschränkungen zu unterstützen und boten Entwicklern einen Anreiz, zum neuen Solver zu wechseln, wobei wir die kreativen Kapazitäten der Physik-Engine erweiterten. Alle neuen Orte benutzten automatisch den PGS-Solver, wobei die Option offenblieb, zurück zum klassischen Solver zu wechseln.
Wir behoben einige Stabilitätsprobleme im Zusammenhang mit hohen Massenunterschieden und komplexen Mechanismen durch die Einführung des hybriden LDL-PGS-Solvers Mitte 2018. Dadurch wurde der alte Solver obsolet und 2019 komplett abgeschaltet. Alle Orte wurden automatisch zum neuen PGS migriert.
2019 wurde die Leistung weiter verbessert mit der Einführung von Multithreading, das die Simulation in Jobs aufteilt, die aus verbundenen Inseln simulierter Teile bestehen. Wir hatten noch ein paar Leistungsprobleme im Zusammenhang mit dem LDL, die Anfang 2020 letztendlich behoben werden konnten.
Die Physik-Engine wird fortwährend verbessert und auf Leistung optimiert. Wir werden in der vorhersehbaren Zukunft weitere neue Funktionen hinzufügen.
Gesetze der Physik implementieren
Das oberste Ziel der Physik-Engine ist die Bewegungssimulation von Körpern in einer virtuellen Umgebung. In unserer Physik-Engine kümmern wir uns um starre Körper, die zusammenstoßen und sich gegenseitig einschränken.
Die Physik-Engine ist in zwei Phasen eingeteilt: Kollisionserkennung und Lösung. Die Kollisionserkennung findet die Schnittstellen zwischen den Geometrien, die mit den starren Körpern zusammenhängen, und generiert die entsprechenden Kollisionsinformationen wie Kollisionspunkte, Normal-Verteilungen und Eindringtiefen. Dann passt der Solver die Bewegungen der starren Körper unter Einfluss der erkannten Kollision und unter Berücksichtigung der vom Benutzer festgelegten Einschränkungen an.
Die Bewegung ist das Ergebnis des Solvers, der die Gesetze der Physik, wie Energieeinsparung und Impuls, interpretiert. Eine 100-prozentig genaue Umsetzung dieses ist jedoch untragbar aufwendig. Der Trick beim Simulieren in Echtzeit ist, sich der erhöhten Leistung anzunähern, solange das Ergebnis physikalisch realistisch ist. Solange die fundamentalen Gesetze der Physik innerhalb eines tolerablen Spielraums eingehalten werden, ist dieser Kompromiss für Computerspiel-Simulationen absolut akzeptabel.
Kleine Schritte
Der Grundgedanke bei der Physik-Engine ist die Diskretisierung von Bewegung mithilfe des Zeitschrittverfahrens. Die Bewegungsgleichungen von eingeschränkten und uneingeschränkten Körpern lassen sich nur sehr schwer direkt und akkurat integrieren. Die Diskretisierung unterteilt die Bewegung in kleinere Zeitschrittlängen, für die Gleichungen vereinfacht und linearisiert werden und somit näherungsweise gelöst werden können. Das bedeutet, dass bei jeder Zeitschrittlänge die Bewegung der betreffenden starren Körperteile, die an Einschränkungen beteiligt sind, linear angenähert wird.
[gallery link="none" size="full" columns="2" ids="eyJ1cmwiOiJodHRwOlwvXC9sb2NhbGhvc3RcL3dwLWNvbnRlbnRcL3VwbG9hZHNcLzIwMjBcLzA4XC9wZ3Mtc29sdmVyLXRlY2g0LmdpZiIsInRpdGxlIjoicGdzLXNvbHZlci10ZWNoNCIsImNhcHRpb24iOiIiLCJhbHQiOiIiLCJkZXNjcmlwdGlvbiI6IiJ9,eyJ1cmwiOiJodHRwOlwvXC9sb2NhbGhvc3RcL3dwLWNvbnRlbnRcL3VwbG9hZHNcLzIwMjBcLzA4XC9wZ3Mtc29sdmVyLXRlY2g1YS0xLnBuZyIsInRpdGxlIjoicGdzLXNvbHZlci10ZWNoNWEiLCJjYXB0aW9uIjoiIiwiYWx0IjoiIiwiZGVzY3JpcHRpb24iOiIifQ=="]
Obwohl eine lineare Gleichung einfacher zu lösen ist, erzeugt sie bei der Simulation mit nicht-linearen Verhalten, wie Rotationsbewegungen, auch Drift. Später gehen wir auf Methoden ein, die dabei helfen, den Drift zu reduzieren und die Simulation plausibler zu machen.
Lösungen
Nach der Linearisierung der Bewegungsgleichungen für eine Zeitschrittlänge müssen wir ein lineares Gleichungssystem oder ein lineares Komplementaritätsproblem (LCP) lösen. Diese Systeme können jegliche Größe annehmen und es kann immer noch sehr aufwendig sein, eine genaue Lösung zu berechnen. Auch hier gilt es, eine Näherungslösung mit einer schnelleren Methode zu finden. Eine moderne Methode für die Näherungslösung eines LCP mit guten Konvergenzeigenschaften ist das Punkt-Gauß-Seidel-Verfahren (PGS). Es handelt sich hierbei um eine iterative Methode, bei der sich die Näherungslösung mit jeder Iteration der echten Lösung annähert. Die letztendliche Lösung hängt von der Anzahl der Wiederholungen ab.
In dieser Animation ist zu sehen, wie ein PGS-Solver die Positionen der Körper bei jedem Schritt des Iterationsverfahrens ändert. Das Ziel ist es, die Positionen zu finden, die die Kugel-Pfannen-Einschränkungen einhalten und gleichzeitig das Massenzentrum bewahren (dies ist eine Art Positions-Solver, der vom IK-Dragger benutzt wird). Obwohl es bei diesem Beispiel eine einfache analytische Lösung gibt, verdeutlicht es sehr gut das Konzept des PGS. Bei jedem Schritt wird eine Einschränkung repariert und eine andere Einschränkung verletzt. Nach wenigen Iterationen kommen die Körper ihren korrekten Positionen sehr nahe. Ein Merkmal dieser Methode ist, wie einige starre Körper um ihre endgültige Position herum vibrieren zu scheinen, besonders, wenn sie mit schwereren Körpern interagieren. Wenn ungenügend Iterationen laufen, kann es passieren, dass der gelbe Teil in einem sichtbar unzulässigen Zustand versetzt wird, bei dem ein oder zwei seiner Einschränkungen drastisch verletzt werden. Das heißt hohes Massenverhältnis-Problem und ist der Fluch der Physik-Engine, da es Instabilität und Explosionen verursacht. Wenn wir zu viele Iterationen durchführen, dann wird der Solver zu langsam und wenn nicht, haben wir das Problem der Instabilität. Diese beiden Seiten auszubalancieren war ein langer, mühevoller Prozess.
Minderungsstrategien
Deshalb liegt ein Großteil der Komplexität des Solvers in der Implementierung der Methoden, die die Auswirkungen der rechnerischen Ungenauigkeiten minimieren. Unsere endgültige Implementierung greift auf traditionelle als auch einige neue Minderungsstrategien zurück:
- Warmstart: Das Beginnen mit einer Lösung von einem vorherigen Zeitschritt, um die Konvergenzrate des iterativen Solvers zu erhöhen
- Nachstabilisierung: Projektion des Systems zurück zum Einschränkungsverteiler, um Einschränkungs-Drift zu verhindern
- Regularisierung: Hinzufügen von Einschränkungserfüllungen, was gewährleistet, dass eine Lösung existiert und einzigartig ist
- Vorkonditionierung: Nutzung einer genauen Lösung für ein lineares Teilsystem, wodurch die Stabilität komplexer Mechanismen verbessert wird
Die ersten drei Strategien sind relativ traditionell, die dritte Strategie wurde jedoch von uns verbessert und perfektioniert. Und obwohl die vierte Strategie nicht unbekannt ist, haben wir noch keine praktische Anwendung davon gesehen. Wir benutzen eine originale Faktorisierungsmethode für große, dünnbesetzte Matrizen und eine neue, effiziente Methode für dessen Kombinierung mit dem PGS. Die resultierende Implementierung ist nur ein bisschen langsamer als alleiniges PGS, stellt aber sicher, dass das lineare System, das von den Gleichheitseinschränkungen ausgeht, exakt gelöst wird. Folglich leiden die Gleichheitseinschränkungen nur unter dem Drift der Zeitdiskretisierung. Nähere Information zu unseren Methoden sind in meiner GDC 2020-Präsentationen zu finden. Wir untersuchen gerade direkte Methoden für die Anwendung an Ungleichheitseinschränkungen und Kollisionen.
Weitere Einzelheiten
Traditionell gibt es zwei mathematische Modelle für Gelenkmechanismen: Das Featherstone-Verfahren, das die Freiheitsgrade für jedes Gelenk parametrisiert, sowie vollständige Koordinatenmethoden, die den Lagrange-Ansatz benutzen.
Wir benutzen den zweiten Ansatz, da er weniger restriktiv ist und dessen Mathematik und Implementierung viel einfacher umzusetzen ist.
Die Roblox-Engine verwendet analytische Methoden zur Berechnung der dynamischen Reaktion auf Einschränkungen, anstelle der zuvor genutzten Strafmethoden. Analysemethoden wurden erstmals im Baraff 1989 vorgestellt, wo sie verwendet wurden, um Gleichheits- und Ungleichheitseinschränkungen in konsistenter Weise zu behandeln. Baraff beobachtete, dass das Kontaktmodell durch quadratische Programmierung formuliert werden kann, und entwickelte einen heuristischen Lösungsansatz (dieser wird nicht von unserem Solver verwendet).
Anstelle von kraftbasierten Formeln benutzen wir eine impulsbasierte Formel im Geschwindigkeitsraum, die erstmalig von Mirtich-Canny 1995 vorgestellt und von Stewart-Trinkle 1996 weiter entwickelt wurde. Dies vereinheitlicht die Aufarbeitung verschiedener Kontaktarten und garantiert die Existenz einer Lösung für Kontakte mit Reibung. Bei jeder Zeitschrittlänge bleiben die Kollisionen durch die Anwendung von sofortigen Geschwindigkeitsänderungen aufgrund von Einschränkungsimpulsen erhalten. Eine ausgezeichnete Erklärung dafür, warum impulsbasierte Simulationen überlegen sind, ist in der CDC-Präsentation von Catto 2014 aufgeführt.
Die reibungsfreien Kontakte sind, wie im Baraff 1994 beschrieben, nach dem linearen Komplementaritätsproblem (LCP) modelliert. Reibung wird dem Reibungskegel als nichtlineare Projektion hinzugefügt in Kombination mit den Iterationen des Punkt-Gauß-Seidel-Verfahrens.
Der numerische Drift, der Positionsfehler in den Einschränkungen verursacht, wird mit einer Nachstabilisierungstechnik mithilfe von Pseudo-Geschwindigkeiten gelöst, was von Cline-Pai 2003 eingeführt wurde. Dazu wird ein zweiter LCP im Positionsraum gelöst, was das System wieder zurück in den Einschränkungsverteiler projiziert.
Die LCPs werden mit einem PGS- / Impuls-Solver gelöst, was von Catto 2005 popularisiert wurde (siehe auch Catto 2009). Diese Methode ist iterativ und betrachtet jede Einschränkung in Folge und löst sie einzeln. Im Verlauf vieler Iterationen und mit idealen Voraussetzungen, nähert sich das System einer globalen Lösung an.
Zusätzlich werden hohe Massenverhältnis-Probleme in Gleichheitseinschränkungen bereinigt, indem das PGS vorkonditioniert wird mithilfe der dünnbesetzten LDL-Dekomposition der Einschränkungsmatrix der Gleichheitseinschränkungen. Dichtbesetzte Submatrizen der Einschränkungsmatrix werden ausgedünnt mit einer Methode, die wir Body-Splitting nennen. Dies ist der LDL-Dekomposition in Baraff 1996 ähnlich, lässt jedoch mehr generelle mechanische Systeme zu und löst das System innerhalb des Einschränkungsraums. Weitere Informationen dazu findest du in meiner GDC 2020-Präsentation.
Die Architektur unseres Solvers folgt der Idee von Guendelman-Bridson-Fedkiw, bei der die Geschwindigkeit und Positionsschrittverfahren durch die Einschränkungslösung getrennt sind. Unsere zeitliche Sequenzierung ist:
- Geschwindigkeiten voranbringen
- Einschränkungslösung im Geschwindigkeitsraum und Positionsraum
- Positionen voranbringen
Dieses Schema hat den Vorteil, dass es nur zulässige Geschwindigkeiten integriert und Latenz in externer Kraftanwendung einschränkt, jedoch ein wenig wahrnehmbare Einschränkungsverletzungen aufgrund von numerischem Drift zulässt.
Ein sehr empfehlenswertes Buch über sie Simulation von starren Körpern ist Erleben 2005 , das seit kurzer Zeit kostenlos erhältlich ist. Im Internet findest du auch Vorlesungen über physikbasierte Animation, einen Blog von Nilson Souto über die Erstellung der Physik-Engine, eine sehr gute GDC-Präsentation von Erin Catto über moderne Solver-Methoden und Foren wie das Bullet Physics Forum und GameDev, in denen du deine Fragen loswerden kannst.
Fazit
Das Gebiet der Spiele-Physik-Simulationen weist viele interessante Probleme auf, die gleichzeitig spannend und sehr herausfordernd sind. Es gibt viele Möglichkeiten, coole Mathematik und Physik zu lernen und sie für moderne Optimierungstechniken anzuwenden. Es ist ein Bereich der Spieleentwicklung, der Mathematik, Physik und Software-Engineering zusammenführt.
Auch wenn Roblox eine gute Physik-Engine für starre Körper hat, hat sie einige Aspekte, die weiterhin verbessert und optimiert werden können. Zusätzlich arbeiten wir an spannenden neuen Projekten wie Brüchen, Verformungen, Weichkörperdynamik, Stoffen, Aerodynamik und Wassersimulation.
Weder die Roblox Corporation noch dieser Blog unterstützt jegliche anderen Unternehmen oder Dienste. Wir machen auch keine Garantien oder Versprechen in Hinsicht auf die Genauigkeit, Zuverlässigkeit und Vollständigkeit der Informationen in diesem Blog.
Dieser Blog wurde ursprünglich auf dem Roblox Tech Blog veröffentlicht.