Simulatie en prestaties verbeteren met een geavanceerde fysicasolver

In 2016 hebben we ondersteuning toegevoegd voor een breed scala aan nieuwe fysica-beperkingen, waardoor ontwikkelaars werden gestimuleerd om over te stappen op de nieuwe solver en de creatieve mogelijkheden van de fysica-engine werden uitgebreid. Alle nieuwe locaties maakten standaard gebruik van de PGS-solver, met de optie om terug te keren naar de klassieke solver.

We hebben enkele stabiliteitsproblemen in verband met grote massaverschillen en complexe mechanismen opgelost door de introductie van de hybride LDL-PGS-oplosser medio 2018. Hierdoor werd de oude oplosser overbodig en werd deze in 2019 volledig uitgeschakeld, waarbij alle locaties automatisch naar de PGS werden gemigreerd.

In 2019 werden de prestaties verder verbeterd door middel van multithreading, waarbij de simulatie wordt opgesplitst in taken die bestaan uit onderling verbonden eilandjes van simulerende onderdelen. We hadden nog steeds prestatieproblemen met betrekking tot de LDL, die we uiteindelijk begin 2020 hebben opgelost.

De physics-engine wordt nog steeds verbeterd en geoptimaliseerd voor betere prestaties, en we zijn van plan om in de nabije toekomst nieuwe functies toe te voegen.

Implementatie van de wetten van de fysica

Het belangrijkste doel van een physics-engine is het simuleren van de beweging van lichamen in een virtuele omgeving. In onze physics-engine richten we ons op stijve lichamen die met elkaar in botsing komen en onderling beperkingen hebben.

Een physics engine bestaat uit twee fasen: botsingsdetectie en het oplossen van botsingen. Botsingsdetectie zoekt naar snijpunten tussen geometrieën die bij de starre lichamen horen, en genereert de juiste botsingsinformatie, zoals botsingspunten, normaalvectoren en penetratiedieptes. Vervolgens werkt een solver de beweging van de starre lichamen bij onder invloed van de gedetecteerde botsingen en de beperkingen die door de gebruiker zijn opgegeven.

De beweging is het resultaat van de solver die de wetten van de fysica interpreteert, zoals behoud van energie en impuls. Maar om dit 100% nauwkeurig te doen is onbetaalbaar, en de truc om het in realtime te simuleren is om te approximeren om de prestaties te verhogen, zolang het resultaat maar fysisch realistisch is. Zolang de basiswetten van de beweging binnen een redelijke tolerantie worden gehandhaafd, is deze afweging volkomen acceptabel voor een computerspelsimulatie.

Kleine stapjes

Het belangrijkste idee van de physics-engine is om de beweging te discretiseren met behulp van tijdstappen. De bewegingsvergelijkingen van starre lichamen met en zonder beperkingen zijn erg moeilijk om direct en nauwkeurig te integreren. De discretisatie verdeelt de beweging in kleine tijdstappen, waarbij de vergelijkingen worden vereenvoudigd en gelineariseerd, waardoor het mogelijk wordt om ze bij benadering op te lossen. Dit betekent dat tijdens elke tijdstap de beweging van de relevante delen van starre lichamen die bij een beperking betrokken zijn, lineair wordt benaderd.

Hoewel een lineair probleem gemakkelijker op te lossen is, veroorzaakt het afwijkingen in een simulatie met niet-lineair gedrag, zoals rotatiebewegingen. Later zullen we mitigatiemethoden bekijken die helpen de afwijkingen te verminderen en de simulatie plausibeler te maken.

Oplossen

Deze animatie laat zien hoe een PGS-oplosser de posities van de lichamen bij elke stap van het iteratieproces verandert, met als doel de posities te vinden die voldoen aan de kogelgewrichtbeperkingen en tegelijkertijd het zwaartepunt bij elke stap behouden (dit is een type positionele oplosser die door de IK-dragger wordt gebruikt). Hoewel dit voorbeeld een eenvoudige analytische oplossing heeft, is het een goede demonstratie van het idee achter de PGS. Bij elke stap legt de solver één van de beperkingen vast en laat de andere worden overschreden. Na een paar iteraties bevinden de lichamen zich zeer dicht bij hun juiste posities. Een kenmerk van deze methode is hoe sommige starre lichamen lijken te trillen rond hun eindpositie, vooral bij koppelingsinteracties met zwaardere lichamen. Als we niet genoeg iteraties uitvoeren, kan het gele deel in een zichtbaar ongeldige toestand achterblijven, waarbij een van de twee beperkingen drastisch wordt overschreden. Dit wordt het probleem van de hoge massaverhouding genoemd, en het is de vloek van physics-engines omdat het instabiliteit en explosies veroorzaakt. Als we te veel iteraties uitvoeren, wordt de solver te traag; als we dat niet doen, wordt hij onstabiel. Het vinden van een evenwicht tussen beide is een moeizaam en langdurig proces geweest.

Beperkende strategieën

Een solver kent twee belangrijke bronnen van onnauwkeurigheden: tijdstappen en iteratief oplossen (er is ook drijvende-kommadrift, maar die is verwaarloosbaar in vergelijking met de eerste twee). Deze onnauwkeurigheden introduceren fouten in de simulatie, waardoor deze afwijkt van het juiste pad. Sommige van deze afwijkingen zijn aanvaardbaar, zoals licht verschillende snelheden of energieverlies, maar andere zijn dat niet, zoals instabiliteiten, grote energiewinst of ontwrichte beperkingen.

Daarom komt een groot deel van de complexiteit in de solver voort uit de implementatie van methoden om de impact van rekenfouten te minimaliseren. Onze uiteindelijke implementatie maakt gebruik van enkele traditionele en enkele nieuwe mitigatiestrategieën:

1. Warm starten: beginnen met de oplossing van een vorige tijdstap om de convergentiesnelheid van de iteratieve solver te verhogen
2. Post-stabilisatie: het systeem opnieuw projecteren naar de beperkingsmanifold om beperkingsafwijking te voorkomen
3. Regularisatie: het toevoegen van conformiteit aan de beperkingen om ervoor te zorgen dat er een oplossing bestaat en dat deze uniek is
4. Pre-conditioning: gebruik van een exacte oplossing voor een lineair subsysteem, waardoor de stabiliteit van complexe mechanismen wordt verbeterd

Strategieën 1, 2 en 3 zijn vrij traditioneel, maar 3 is door ons verbeterd en geperfectioneerd. Ook al is 4 niet onbekend, hebben we er nog geen praktische implementatie van gezien. We gebruiken een originele factorisatiemethode voor grote, dunbevolkte beperkingsmatrices en een nieuwe, efficiënte manier om deze te combineren met de PGS. De resulterende implementatie is slechts iets langzamer in vergelijking met pure PGS, maar zorgt ervoor dat het lineaire systeem dat voortkomt uit gelijkheidsbeperkingen exact wordt opgelost. Bijgevolg hebben de gelijkheidsbeperkingen alleen last van afwijkingen die voortkomen uit de tijdsdiscretisatie. Details over onze methoden zijn te vinden in mijn GDC 2020-presentatie. Momenteel onderzoeken we directe methoden die worden toegepast op ongelijkheidsbeperkingen en botsingen.

Meer details

Traditioneel zijn er twee wiskundige modellen voor gelede mechanismen: er zijn gereduceerde coördinatenmethoden, onder leiding van Featherstone, die de vrijheidsgraden bij elk gewricht parametriseren, en er zijn volledige coördinatenmethoden die gebruikmaken van een Lagrangiaanse formulering.

Wij gebruiken de tweede formulering, omdat deze minder beperkend is en veel eenvoudigere wiskunde en implementatie vereist.

De Roblox-engine gebruikt analytische methoden om de dynamische respons van beperkingen te berekenen, in tegenstelling tot de strafmethoden die voorheen werden gebruikt. Analytische methoden werden voor het eerst geïntroduceerd in Baraff 1989, waar ze worden gebruikt om zowel gelijkheids- als ongelijkheidsbeperkingen op een consistente manier te behandelen. Baraff merkte op dat het contactmodel kan worden geformuleerd met behulp van kwadratische programmering, en hij gaf een heuristische oplossingsmethode (wat niet de methode is die we in onze solver gebruiken).

In plaats van een op kracht gebaseerde formulering gebruiken we een op impuls gebaseerde formulering in de snelheidsruimte, oorspronkelijk geïntroduceerd door Mirtich-Canny 1995 en verder verbeterd door Stewart-Trinkle 1996, die de behandeling van verschillende contacttypes verenigt en het bestaan van een oplossing voor contacten met wrijving garandeert. Bij elke tijdstap worden de beperkingen en botsingen gehandhaafd door onmiddellijke veranderingen in snelheden toe te passen als gevolg van beperkingsimpulsen. Een uitstekende uitleg van waarom op impulsen gebaseerde simulatie superieur is, is te vinden in de GDC-presentatie van Catto uit 2014.

De wrijvingsloze contacten worden gemodelleerd met behulp van een lineair complementariteitsprobleem (LCP), zoals beschreven in Baraff 1994. Wrijving wordt toegevoegd als een niet-lineaire projectie op de wrijvingskegel, afgewisseld met de iteraties van de Projected Gauss-Seidel.

De numerieke drift die positionele fouten in de beperkingen veroorzaakt, wordt opgelost met behulp van een post-stabilisatietechniek waarbij gebruik wordt gemaakt van pseudo-snelheden, geïntroduceerd door Cline-Pai 2003. Dit houdt in dat een tweede LCP in de positieruimte wordt opgelost, waardoor het systeem terug wordt geprojecteerd naar de beperkingsvariëteit.

De LCP's worden opgelost met behulp van een PGS / Impulse Solver, gepopulariseerd door Catto 2005 (zie ook Catto 2009). Deze methode is iteratief en beschouwt elke afzonderlijke beperking achtereenvolgens en lost deze onafhankelijk op. Na vele iteraties, en onder ideale omstandigheden, convergeert het systeem naar een globale oplossing.

Bovendien worden problemen met hoge massaverhoudingen in gelijkheidsbeperkingen opgelost door de PGS voor te conditioneren met behulp van de sparse LDL-decompositie van de beperkingsmatrix van gelijkheidsbeperkingen. Dichte submatrices van de beperkingsmatrix worden gesparsificeerd met behulp van een methode die we Body Splitting noemen. Dit is vergelijkbaar met de LDL-decompositie die in Baraff 1996 wordt gebruikt, maar maakt meer algemene mechanische systemen mogelijk en lost het systeem op in de beperkingsruimte. Voor meer informatie kunt u mijn GDC 2020-presentatie bekijken.

De architectuur van onze solver volgt het idee van Guendelman-Bridson-Fedkiw, waarbij de snelheids- en positie-stappen worden gescheiden door de beperkingsresolutie. Onze tijdsvolgorde is:

1. Snelheden vooruit
2. Oplossen van beperkingen in snelheidsruimte en positieruimte
3. Posities vooruit

Dit schema heeft het voordeel dat alleen geldige snelheden worden geïntegreerd en dat de latentie bij het uitoefenen van externe krachten wordt beperkt, maar dat een kleine hoeveelheid waargenomen beperkingsschendingen als gevolg van numerieke drift wordt toegestaan.

Een uitstekende referentie voor simulatie van starre lichamen is het boek Erleben 2005, dat onlangs gratis beschikbaar is gesteld. U kunt online colleges vinden over op fysica gebaseerde animatie, een blog van Nilson Souto over het bouwen van een physics-engine, een zeer goede GDC-presentatie van Erin Catto over moderne solver-methoden, en forums zoals het Bullet Physics Forum en GameDev, die uitstekende plekken zijn om vragen te stellen.

Conclusie

Het gebied van game-fysicasimulatie biedt veel interessante problemen die zowel spannend als uitdagend zijn. Er zijn mogelijkheden om een aanzienlijke hoeveelheid coole wiskunde en natuurkunde te leren en om moderne optimalisatietechnieken te gebruiken. Het is een gebied van game-ontwikkeling dat wiskunde, natuurkunde en software-engineering nauw met elkaar verbindt.

Ook al heeft Roblox een goede physics-engine voor starre lichamen, er zijn gebieden waarop deze kan worden verbeterd en geoptimaliseerd. Daarnaast werken we aan spannende nieuwe projecten zoals breuken, vervorming, softbody, stoffen, aerodynamica en watersimulatie.

Roblox Corporation noch deze blog onderschrijft of ondersteunt enig bedrijf of enige dienst. Ook worden er geen garanties of beloften gedaan met betrekking tot de nauwkeurigheid, betrouwbaarheid of volledigheid van de informatie in deze blog.

Dit blogbericht is oorspronkelijk gepubliceerd op de Roblox Tech Blog.