Verbesserung von Simulation und Leistung mit einem fortschrittlichen Physik-Solver
Im Jahr 2016 haben wir Unterstützung für eine Vielzahl neuer physikalischer Beschränkungen hinzugefügt, um Entwickler zur Umstellung auf den neuen Solver zu motivieren und die kreativen Möglichkeiten der Physik-Engine zu erweitern. Alle neuen Orte verwendeten standardmäßig den PGS-Solver, wobei die Option bestand, zum klassischen Solver zurückzukehren.
Durch die Einführung des hybriden LDL-PGS-Solvers Mitte 2018 konnten wir einige Stabilitätsprobleme beheben, die mit großen Massenunterschieden und komplexen Mechanismen zusammenhingen. Dadurch wurde der alte Solver überflüssig und 2019 vollständig deaktiviert, wodurch alle Orte automatisch auf den PGS migriert wurden.
Im Jahr 2019 wurde die Leistung durch Multithreading weiter verbessert, das die Simulation in Jobs aufteilt, die aus miteinander verbundenen Inseln simulierender Teile bestehen. Wir hatten weiterhin Leistungsprobleme im Zusammenhang mit dem LDL, die wir schließlich Anfang 2020 behoben haben.
Die Physik-Engine wird weiterhin verbessert und hinsichtlich der Leistung optimiert, und wir planen, in absehbarer Zukunft neue Funktionen hinzuzufügen.
Implementierung der Gesetze der Physik
Das Hauptziel einer Physik-Engine ist es, die Bewegung von Körpern in einer virtuellen Umgebung zu simulieren. In unserer Physik-Engine befassen wir uns mit starren Körpern, die miteinander kollidieren und gegenseitige Beschränkungen aufweisen.
Eine Physik-Engine ist in zwei Phasen unterteilt: Kollisionserkennung und Lösung. Die Kollisionserkennung ermittelt Schnittpunkte zwischen den mit den starren Körpern verbundenen Geometrien und generiert entsprechende Kollisionsinformationen wie Kollisionspunkte, Normalen und Eindringtiefen. Anschließend aktualisiert ein Solver die Bewegung der starren Körper unter dem Einfluss der erkannten Kollisionen und der vom Benutzer vorgegebenen Einschränkungen.
Die Bewegung ist das Ergebnis der Interpretation physikalischer Gesetze wie der Erhaltung von Energie und Impuls durch den Solver. Dies zu 100 % genau zu berechnen, ist jedoch unerschwinglich teuer, und der Trick bei der Echtzeitsimulation besteht darin, zur Leistungssteigerung Näherungswerte zu verwenden, solange das Ergebnis physikalisch realistisch ist. Solange die grundlegenden Bewegungsgesetze innerhalb einer angemessenen Toleranz eingehalten werden, ist dieser Kompromiss für eine Computerspielsimulation völlig akzeptabel.
Kleine Schritte
Die Grundidee der Physik-Engine besteht darin, die Bewegung mittels Zeitschritten zu diskretisieren. Die Bewegungsgleichungen von starren Körpern mit und ohne Einschränkungen lassen sich nur sehr schwer direkt und genau integrieren. Durch die Diskretisierung wird die Bewegung in kleine Zeitabschnitte unterteilt, in denen die Gleichungen vereinfacht und linearisiert werden, sodass sie näherungsweise gelöst werden können. Das bedeutet, dass während jedes Zeitschritts die Bewegung der relevanten Teile der starren Körper, die an einer Einschränkung beteiligt sind, linear approximiert wird.
Obwohl ein linearisiertes Problem leichter zu lösen ist, führt es in einer Simulation mit nichtlinearen Verhaltensweisen, wie beispielsweise Drehbewegungen, zu Abweichungen. Später werden wir Methoden zur Abmilderung dieser Abweichungen kennenlernen, die dazu beitragen, die Simulation plausibler zu gestalten.
Lösung
Diese Animation zeigt, wie ein PGS-Löser die Positionen der Körper bei jedem Schritt des Iterationsprozesses verändert, wobei das Ziel darin besteht, die Positionen zu finden, die die Kugelgelenk-Beschränkungen erfüllen und gleichzeitig den Schwerpunkt bei jedem Schritt beibehalten (dies ist eine Art Positionslöser, der vom IK-Dragger verwendet wird). Obwohl dieses Beispiel eine einfache analytische Lösung hat, ist es eine gute Veranschaulichung des Prinzips hinter dem PGS. Bei jedem Schritt fixiert der Solver eine der Beschränkungen und lässt die andere verletzt werden. Nach einigen Iterationen befinden sich die Körper sehr nahe an ihren korrekten Positionen. Ein Merkmal dieser Methode ist, dass einige starre Körper um ihre Endposition herum zu schwingen scheinen, insbesondere bei Wechselwirkungen mit schwereren Körpern. Wenn wir nicht genügend Iterationen durchführen, könnte das gelbe Teil in einem sichtbar ungültigen Zustand verbleiben, in dem eine seiner beiden Beschränkungen dramatisch verletzt wird. Dies wird als Problem des hohen Massenverhältnisses bezeichnet und ist seit jeher der Fluch von Physik-Engines, da es zu Instabilitäten und Explosionen führt. Wenn wir zu viele Iterationen durchführen, wird der Solver zu langsam; wenn wir zu wenige durchführen, wird er instabil. Das Abwägen dieser beiden Aspekte war ein mühsamer und langwieriger Prozess.
Strategien zur Risikominderung
Ein Solver hat zwei Hauptursachen für Ungenauigkeiten: Zeitschritte und iteratives Lösen (es gibt auch Gleitkommaabweichungen, diese sind jedoch im Vergleich zu den ersten beiden geringfügig). Diese Ungenauigkeiten führen zu Fehlern in der Simulation, wodurch diese vom korrekten Verlauf abweicht. Einige dieser Abweichungen sind tolerierbar, wie leicht unterschiedliche Geschwindigkeiten oder Energieverluste, andere jedoch nicht, wie Instabilitäten, große Energiegewinne oder verschobene Beschränkungen.
Daher rührt ein Großteil der Komplexität des Solvers von der Implementierung von Methoden her, die die Auswirkungen von Rechenungenauigkeiten minimieren sollen. Unsere endgültige Implementierung nutzt sowohl traditionelle als auch neuartige Strategien zur Minderung dieser Auswirkungen:
- Warmstart: Start mit der Lösung aus einem vorherigen Zeitschritt, um die Konvergenzrate des iterativen Solvers zu erhöhen
- Nachstabilisierung: Rückprojektion des Systems auf die Beschränkungsmannigfaltigkeit, um eine Beschränkungsdrift zu verhindern
- Regularisierung: Hinzufügen von Nachgiebigkeit zu den Nebenbedingungen, um sicherzustellen, dass eine Lösung existiert und eindeutig ist
- Vorkonditionierung: Verwendung einer exakten Lösung für ein lineares Teilsystem, um die Stabilität komplexer Mechanismen zu verbessern
Die Strategien 1, 2 und 3 sind recht traditionell, aber Strategie 3 wurde von uns verbessert und perfektioniert. Auch wenn Strategie 4 nicht unbekannt ist, haben wir bisher keine praktische Umsetzung davon gesehen. Wir verwenden eine originelle Faktorisierungsmethode für große spärliche Beschränkungsmatrizen und eine neue, effiziente Methode, diese mit der PGS zu kombinieren. Die daraus resultierende Implementierung ist im Vergleich zur reinen PGS nur geringfügig langsamer, stellt jedoch sicher, dass das aus den Gleichheitsbeschränkungen resultierende lineare System exakt gelöst wird. Folglich unterliegen die Gleichheitsbeschränkungen lediglich einer Drift, die aus der Zeitdiskretisierung resultiert. Details zu unseren Methoden sind in meinem Vortrag auf der GDC 2020 enthalten. Derzeit untersuchen wir direkte Methoden, die auf Ungleichheitsbeschränkungen und Kollisionen angewendet werden.
Weitere Details
Traditionell gibt es zwei mathematische Modelle für Gelenkmechanismen: die von Featherstone entwickelten reduzierten Koordinatenmethoden, die die Freiheitsgrade an jedem Gelenk parametrisieren, und die Vollkoordinatenmethoden, die eine Lagrange-Formulierung verwenden.
Wir verwenden die zweite Formulierung, da sie weniger restriktiv ist und eine wesentlich einfachere Mathematik sowie Implementierung erfordert.
Die Roblox-Engine verwendet analytische Methoden zur Berechnung der dynamischen Reaktion von Beschränkungen, im Gegensatz zu den zuvor verwendeten Penalty-Methoden. Analytische Methoden wurden ursprünglich von Baraff 1989 eingeführt, wo sie dazu dienen, sowohl Gleichheits- als auch Ungleichheitsbeschränkungen auf konsistente Weise zu behandeln. Baraff stellte fest, dass das Kontaktmodell mittels quadratischer Programmierung formuliert werden kann, und er lieferte eine heuristische Lösungsmethode (die nicht die Methode ist, die wir in unserem Solver verwenden).
Anstelle einer kraftbasierten Formulierung verwenden wir eine impulsbasierte Formulierung im Geschwindigkeitsraum, die ursprünglich von Mirtich-Canny 1995 eingeführt und von Stewart-Trinkle 1996 weiter verbessert wurde. Diese vereinheitlicht die Behandlung verschiedener Kontaktarten und garantiert die Existenz einer Lösung für Kontakte mit Reibung. Bei jedem Zeitschritt werden die Nebenbedingungen und Kollisionen durch die Anwendung momentaner Geschwindigkeitsänderungen aufgrund von Nebenbedingungenimpulsen aufrechterhalten. Eine hervorragende Erklärung dafür, warum die impulsbasierte Simulation überlegen ist, findet sich in der GDC-Präsentation von Catto 2014.
Die reibungsfreien Kontakte werden unter Verwendung eines linearen Komplementaritätsproblems (LCP) modelliert, wie in Baraff 1994 beschrieben. Reibung wird als nichtlineare Projektion auf den Reibungskegel hinzugefügt, die mit den Iterationen des Projected Gauss-Seidel-Verfahrens verschachtelt ist.
Die numerische Drift, die Positionsfehler in den Beschränkungen verursacht, wird mithilfe einer von Cline-Pai 2003 eingeführten Post-Stabilisierungstechnik unter Verwendung von Pseudogeschwindigkeiten behoben. Dabei wird ein zweites LCP im Positionsraum gelöst, das das System zurück auf die Beschränkungsmannigfaltigkeit projiziert.
Die LCPs werden unter Verwendung eines PGS-/Impuls-Lösers gelöst, der durch Catto 2005 bekannt wurde (siehe auch Catto 2009). Diese Methode ist iterativ und betrachtet jede einzelne Nebenbedingung nacheinander und löst sie unabhängig. Über viele Iterationen hinweg und unter idealen Bedingungen konvergiert das System zu einer globalen Lösung.
Zudem werden Probleme mit hohem Massenverhältnis in Gleichheitsbeschränkungen durch Vorkonditionierung des PGS unter Verwendung der spärlichen LDL-Zerlegung der Beschränkungsmatrix der Gleichheitsbeschränkungen beseitigt. Dichte Untermatrizen der Beschränkungsmatrix werden mithilfe einer Methode, die wir „Body Splitting“ nennen, spärlich gemacht. Dies ähnelt der in Baraff 1996 verwendeten LDL-Zerlegung, ermöglicht jedoch allgemeinere mechanische Systeme und löst das System im Beschränkungsraum. Weitere Informationen finden Sie in meiner Präsentation auf der GDC 2020.
Die Architektur unseres Solvers folgt dem Ansatz von Guendelman-Bridson-Fedkiw, bei dem die Geschwindigkeits- und Positionsschritte durch die Auflösungsphase der Nebenbedingungen getrennt sind. Unsere zeitliche Abfolge ist:
- Geschwindigkeiten vorwärts berechnen
- Auflösung der Nebenbedingungen im Geschwindigkeits- und Positionsraum
- Positionsfortschritt
Dieses Schema hat den Vorteil, dass nur gültige Geschwindigkeiten integriert werden und die Latenz bei der Anwendung externer Kräfte begrenzt wird, während gleichzeitig eine geringe wahrnehmbare Verletzung der Beschränkungen aufgrund numerischer Abweichungen zugelassen wird.
Eine hervorragende Referenz für die Simulation starrer Körper ist das Buch Erleben 2005, das kürzlich frei zugänglich gemacht wurde. Sie finden Online-Vorlesungen über physikbasierte Animation, einen Blog von Nilson Souto zum Aufbau einer Physik-Engine, eine sehr gute GDC-Präsentation von Erin Catto über moderne Solver-Methoden sowie Foren wie das Bullet Physics Forum und GameDev, die sich hervorragend zum Stellen von Fragen eignen.
Fazit
Der Bereich der Spielphysiksimulation bietet viele interessante Probleme, die sowohl spannend als auch herausfordernd sind. Es gibt Möglichkeiten, eine Menge cooler Mathematik und Physik zu lernen und moderne Optimierungstechniken anzuwenden. Es ist ein Bereich der Spieleentwicklung, der Mathematik, Physik und Softwareentwicklung eng miteinander verbindet.
Auch wenn Roblox über eine gute Physik-Engine für starre Körper verfügt, gibt es Bereiche, in denen sie verbessert und optimiert werden kann. Außerdem arbeiten wir an spannenden neuen Projekten wie Bruch, Verformung, Softbody, Stoff, Aerodynamik und Wassersimulation.
Weder die Roblox Corporation noch dieser Blog befürworten oder unterstützen bestimmte Unternehmen oder Dienste. Außerdem werden keine Garantien oder Zusagen hinsichtlich der Genauigkeit, Zuverlässigkeit oder Vollständigkeit der in diesem Blog enthaltenen Informationen gegeben.
Dieser Blogbeitrag wurde ursprünglich auf dem Roblox Tech Blog veröffentlicht.
