Poprawa symulacji i wydajności dzięki zaawansowanemu solwerowi fizycznemu

W 2016 roku dodaliśmy obsługę szerokiego zestawu nowych ograniczeń fizycznych, zachęcając programistów do migracji do nowego solwera i rozszerzając możliwości kreatywne silnika fizycznego. Wszystkie nowe lokacje domyślnie korzystały z solwera PGS, z opcją powrotu do klasycznego solwera.

W połowie 2018 roku rozwiązaliśmy pewne problemy ze stabilnością związane z dużymi różnicami mas i złożonymi mechanizmami, wprowadzając hybrydowy solwer LDL-PGS. To sprawiło, że stary solwer stał się przestarzały i został całkowicie wyłączony w 2019 roku, co spowodowało automatyczną migrację wszystkich lokacji do PGS.

W 2019 roku wydajność została jeszcze bardziej poprawiona dzięki zastosowaniu wielowątkowości, która dzieli symulację na zadania składające się z połączonych wysp symulowanych części. Nadal mieliśmy problemy z wydajnością związane z LDL, które ostatecznie rozwiązaliśmy na początku 2020 roku.

Silnik fizyczny jest nadal ulepszany i optymalizowany pod kątem wydajności, a w najbliższej przyszłości planujemy dodać nowe funkcje.

Wdrażanie praw fizyki

Głównym celem silnika fizycznego jest symulacja ruchu ciał w środowisku wirtualnym. W naszym silniku fizycznym zajmujemy się ciałami sztywnymi, które zderzają się i są ze sobą powiązane.

Silnik fizyczny dzieli się na dwie fazy: wykrywanie zderzeń i rozwiązywanie. Wykrywanie zderzeń polega na znalezieniu punktów przecięcia między geometriami powiązanymi z ciałami sztywnymi, generując odpowiednie informacje o zderzeniu, takie jak punkty zderzenia, normalne i głębokości penetracji. Następnie solwer aktualizuje ruch ciał sztywnych pod wpływem wykrytych zderzeń i ograniczeń podanych przez użytkownika.

Ruch jest wynikiem interpretacji przez solwer praw fizyki, takich jak zachowanie energii i pędu. Jednak wykonanie tego z 100% dokładnością jest zbyt kosztowne, a sztuczka polegająca na symulacji w czasie rzeczywistym polega na przybliżeniu w celu zwiększenia wydajności, o ile wynik jest fizycznie realistyczny. O ile podstawowe prawa ruchu są zachowane w rozsądnych granicach tolerancji, ten kompromis jest całkowicie akceptowalny w przypadku symulacji w grze komputerowej.

Małe kroki

Główną ideą silnika fizycznego jest dyskretyzacja ruchu za pomocą kroków czasowych. Równania ruchu ciał sztywnych, zarówno ograniczonych, jak i nieograniczonych, są bardzo trudne do bezpośredniego i dokładnego zintegrowania. Dyskretyzacja dzieli ruch na małe przyrosty czasu, w których równania są upraszczane i liniaryzowane, co umożliwia ich przybliżone rozwiązanie. Oznacza to, że podczas każdego kroku czasowego ruch odpowiednich części ciał sztywnych, które są objęte ograniczeniem, jest przybliżany liniowo.

Chociaż problem zlinearyzowany jest łatwiejszy do rozwiązania, powoduje on dryft w symulacji zawierającej zachowania nieliniowe, takie jak ruch obrotowy. Później przyjrzymy się metodom łagodzenia, które pomagają zmniejszyć dryft i uczynić symulację bardziej wiarygodną.

Rozwiązywanie

Ta animacja pokazuje, jak solwer PGS zmienia pozycje ciał na każdym etapie procesu iteracji, a celem jest znalezienie pozycji, które spełniają ograniczenia przegubu kulistego, zachowując jednocześnie środek masy na każdym etapie (jest to rodzaj solwera pozycyjnego używanego przez moduł IK dragger). Chociaż ten przykład ma proste rozwiązanie analityczne, dobrze ilustruje ideę stojącą za PGS. Na każdym etapie solwer ustala jedno z ograniczeń, a drugie pozwala na jego naruszenie. Po kilku iteracjach ciała znajdują się bardzo blisko swoich prawidłowych pozycji. Cechą charakterystyczną tej metody jest to, że niektóre ciała sztywne wydają się wibrować wokół swojej końcowej pozycji, zwłaszcza podczas sprzężenia oddziaływań z cięższymi ciałami. Jeśli nie wykonamy wystarczającej liczby iteracji, żółta część może pozostać w widocznie nieprawidłowym stanie, w którym jedno z dwóch ograniczeń jest drastycznie naruszone. Nazywa się to problemem wysokiego współczynnika masy i jest zmorą silników fizycznych, ponieważ powoduje niestabilność i eksplozje. Jeśli wykonamy zbyt wiele iteracji, solwer stanie się zbyt wolny, a jeśli nie, stanie się niestabilny. Równoważenie tych dwóch aspektów było bolesnym i długim procesem.

Strategie łagodzenia

Solwer ma dwa główne źródła niedokładności: krok czasowy i rozwiązywanie iteracyjne (istnieje również dryft zmiennoprzecinkowy, ale jest on niewielki w porównaniu z dwoma pierwszymi). Te niedokładności wprowadzają błędy do symulacji, powodując jej odchylenie od prawidłowej ścieżki. Niektóre z tych odchyleń są dopuszczalne, jak nieznacznie różne prędkości lub utrata energii, ale inne nie, jak niestabilności, duże przyrosty energii lub przemieszczone ograniczenia.

W związku z tym znaczna część złożoności solwera wynika z implementacji metod mających na celu zminimalizowanie wpływu niedokładności obliczeniowych. Nasza ostateczna implementacja wykorzystuje zarówno tradycyjne, jak i nowatorskie strategie łagodzenia skutków:

1. Rozruch na ciepło: rozpoczęcie od rozwiązania z poprzedniego kroku czasowego w celu zwiększenia szybkości zbieżności solwera iteracyjnego
2. Poststabilizacja: ponowne rzutowanie układu z powrotem na rozmaitość ograniczeń w celu zapobiegania dryfowi ograniczeń
3. Regularizacja: dodanie zgodności do ograniczeń, zapewniające istnienie i jednoznaczność rozwiązania
4. Wstępne kondycjonowanie: wykorzystanie dokładnego rozwiązania podsystemu liniowego w celu poprawy stabilności złożonych mechanizmów

Strategie 1, 2 i 3 są dość tradycyjne, ale strategia 3 została przez nas ulepszona i dopracowana. Ponadto, chociaż strategia 4 nie jest nieznana, nie widzieliśmy jej praktycznego wdrożenia. Wykorzystujemy oryginalną metodę faktoryzacji dla dużych rzadkich macierzy ograniczeń oraz nowy, wydajny sposób łączenia jej z PGS. Wynikowa implementacja jest tylko nieznacznie wolniejsza w porównaniu z czystym PGS, ale zapewnia dokładne rozwiązanie układu liniowego wynikającego z ograniczeń równości. W konsekwencji ograniczenia równości ulegają jedynie dryftowi wynikającemu z dyskretyzacji czasu. Szczegóły dotyczące naszych metod zawarte są w mojej prezentacji na konferencji GDC 2020. Obecnie badamy metody bezpośrednie stosowane do ograniczeń nierówności i kolizji.

Więcej szczegółów

Tradycyjnie istnieją dwa modele matematyczne dla mechanizmów przegubowych: metody współrzędnych zredukowanych, zapoczątkowane przez Featherstone'a, które parametryzują stopnie swobody w każdym przegubie, oraz metody współrzędnych pełnych, które wykorzystują sformułowanie lagrangowskie.

Korzystamy z drugiego sformułowania, ponieważ jest ono mniej restrykcyjne i wymaga znacznie prostszej matematyki oraz implementacji.

Silnik Roblox wykorzystuje metody analityczne do obliczania dynamicznej odpowiedzi ograniczeń, w przeciwieństwie do metod karnych, które były stosowane wcześniej. Metody analityczne zostały po raz pierwszy wprowadzone w pracy Baraffa z 1989 r., gdzie są one wykorzystywane do spójnego traktowania zarówno ograniczeń równościowych, jak i nierównościowych. Baraff zauważył, że model kontaktu można sformułować za pomocą programowania kwadratowego, i przedstawił heurystyczną metodę rozwiązywania (która nie jest metodą stosowaną w naszym solwerze).

Zamiast formułowania opartego na sile, stosujemy formułowanie oparte na impulsach w przestrzeni prędkości, pierwotnie wprowadzone przez Mirtich-Canny'ego w 1995 r. i udoskonalone przez Stewarta-Trinkle'a w 1996 r., które ujednolica traktowanie różnych typów kontaktu i gwarantuje istnienie rozwiązania dla kontaktów z tarciem. W każdym kroku czasowym ograniczenia i kolizje są utrzymywane poprzez zastosowanie chwilowych zmian prędkości wynikających z impulsów ograniczeń. Doskonałe wyjaśnienie, dlaczego symulacja oparta na impulsach jest lepsza, znajduje się w prezentacji GDC autorstwa Catto z 2014 r.

Kontakty bez tarcia są modelowane przy użyciu liniowego problemu komplementarności (LCP), jak opisano w Baraff 1994. Tarcie jest dodawane jako nieliniowa projekcja na stożek tarcia, przeplatana iteracjami metody Projected Gauss-Seidel.

Odchylenie numeryczne, które wprowadza błędy pozycyjne w ograniczeniach, jest rozwiązywane za pomocą techniki poststabilizacji wykorzystującej prędkości pozorne wprowadzone przez Cline-Pai 2003. Polega to na rozwiązaniu drugiego LCP w przestrzeni pozycyjnej, co rzutuje układ z powrotem na rozmaitość ograniczeń.

LCP są rozwiązywane przy użyciu solwera PGS / Impulse Solver spopularyzowanego przez Catto 2005 (zob. również Catto 2009). Metoda ta jest iteracyjna i rozpatruje każde ograniczenie z osobna w kolejności, rozwiązując je niezależnie. Po wielu iteracjach i w idealnych warunkach układ zbiega się do rozwiązania globalnego.

Dodatkowo problemy związane z wysokim współczynnikiem masy w ograniczeniach równościowych są eliminowane poprzez wstępne uwarunkowanie PGS przy użyciu rzadkiej dekompozycji LDL macierzy ograniczeń równościowych. Gęste podmacierze macierzy ograniczeń są rozrzedzane przy użyciu metody, którą nazywamy Body Splitting. Jest to podobne do dekompozycji LDL użytej w Baraff 1996, ale pozwala na bardziej ogólne układy mechaniczne i rozwiązuje układ w przestrzeni ograniczeń. Więcej informacji można znaleźć w mojej prezentacji z konferencji GDC 2020.

Architektura naszego solwera opiera się na koncepcji Guendelmanna-Bridsona-Fedkiwa, w której kroki prędkości i położenia są oddzielone przez rozwiązanie ograniczeń. Nasza sekwencja czasowa wygląda następująco:

1. Przyspieszenie prędkości
2. Rozwiązanie ograniczeń w przestrzeni prędkości i przestrzeni pozycji
3. Przesunięcie pozycji

Schemat ten ma tę zaletę, że uwzględnia tylko prawidłowe prędkości i ogranicza opóźnienia w działaniu sił zewnętrznych, ale pozwala na niewielkie naruszenie ograniczeń wynikające z dryftu numerycznego.

Doskonałym źródłem informacji na temat symulacji ciał sztywnych jest książka Erleben 2005, która została niedawno udostępniona bezpłatnie. W Internecie można znaleźć wykłady na temat animacji opartej na fizyce, blog Nilsona Souto poświęcony tworzeniu silnika fizycznego, bardzo dobrą prezentację Erin Catto z konferencji GDC na temat nowoczesnych metod solwerów oraz fora, takie jak Bullet Physics Forum i GameDev, które są doskonałym miejscem do zadawania pytań.

Podsumowanie

Dziedzina symulacji fizyki w grach przedstawia wiele interesujących problemów, które są zarówno ekscytujące, jak i wymagające. Istnieją możliwości nauki znacznej ilości ciekawej matematyki i fizyki oraz wykorzystania nowoczesnych technik optymalizacji. Jest to obszar tworzenia gier, który ściśle łączy matematykę, fizykę i inżynierię oprogramowania.

Nawet jeśli Roblox ma dobry silnik fizyki ciał sztywnych, są obszary, w których można go ulepszyć i zoptymalizować. Pracujemy też nad nowymi, ekscytującymi projektami, takimi jak pękanie, deformacja, ciała miękkie, tkaniny, aerodynamika i symulacja wody.

Ani firma Roblox Corporation, ani niniejszy blog nie promują ani nie wspierają żadnej firmy ani usługi. Ponadto nie udziela się żadnych gwarancji ani obietnic dotyczących dokładności, wiarygodności lub kompletności informacji zawartych w niniejszym blogu.

Ten wpis na blogu został pierwotnie opublikowany na blogu technicznym Roblox.