Posts Tagged ‘verlet integration’

PostHeaderIcon 6. Komentarze i wnioski

Ta sekcja zawiera różne uwagi, które nie pasują nigdzie indziej.

Kontrola ruchu

Aby mieć wpływ na ruch symulowanego obiektu, musimy po prostu przenosić odpowiednio cząstki. Jeżeli osoba jest trafiona w ramię, przenosimy cząstki ramienia do tyłu na odległość proporcjonalną do siły uderzenia. Całkowanie Verleta będzie wtedy automatycznie ustawiać ruch ramienia.

To również ułatwia symulację „dziedziczenia” prędkości z podstawowego systemu animacji tradycyjnej. Wystarczy zapisać pozycje cząstek dla dwóch klatek, a następnie podać je do całkowania Verleta, które następnie automatycznie kontynuuje ruch. Bomby mogą być realizowane przez wypchnięcie każdej cząstki daleko od wybuchu na odległość odwrotnie proporcjonalną do kwadratu odległości między cząstkami i centrum bomby.

Jest możliwe, aby ograniczyć się do konkretnej kończyny, powiedzmy ręki, do stałego miejsca w przestrzeni. W ten sposób można zaimplementować kinematykę odwrotną: wewnątrz pętli relaksacyjnej zachowaj ustawienia pozycji danej cząsteczki (lub kilku cząstek) do pozycji wymaganej. Nadanie nieskończonej masy cząsteczce (invmass = 0) uczyni ją nieruchomą. W Hitmanie, strategia ta jest używana podczas przenoszenia korpusu; ręka (lub szyja lub stopa) jest ograniczona do podążania za ręką gracza.

Obsługa tarcia

Temat tarcia nie została jeszcze przez nas podjęty. Oznacza to, że jeżeli nie zrobimy czegoś więcej, cząstki będą ślizgać się po podłodze, jakby ta była wykonana z lodu. Zgodnie z modelem tarcia Coulomba, siły tarcia zależą od zwykłych sił działających między obiektami będącymi w kontakcie (?). Aby to zaimplementować, badamy głębokość przenikania d,,p,, kiedy przenikanie wystąpi (przed planowaniem punkt przenikania jest poza przeszkodą). Po projekcji cząsteczek na powierzchnię, prędkość styczna **v,,t,,** jest następnie zredukowana o wartość proporcjonalną do d,,p,, (współczynnik proporcji zostaje stałą tarcia). Odbywa się to przez odpowiednie modyfikowanie x^^*^^. Patrz rys. 10. Należy uważać, żeby prędkość styczna nie odwracała kierunku prędkości – w tym przypadku należy ją po prostu ustawić na zero, ponieważ oznacza to, że punkt przenikania został ustawiony do przemieszenia się stycznie. Pozostałe i być może lepsze modele tarcia mogą i powinny być zaimplementowane.

Detekcja kolizji

Jednym z wąskich gardeł w zaprezentowanej tutaj symulacji fizyki jest wykrywanie kolizji, które potencjalnie przeprowadzane jest kilkakrotnie wewnątrz pętli relaksacyjnej. Możliwe jest jednak, aby iterować inną ilość razy względem różnych ograniczeń i nadal uzyskiwać dobre wyniki.

W Hitmanie, system detekcji kolizji działa poprzez umieszczenie wszystkich trójkątów wewnątrz pudła znajdującego się wokół symulowanego obiektu (odbywa się to przy użyciu drzewa ósemkowego). Dla każdego trójkąta (statycznego, będącego elementem tła) struktura szybkiego sprawdzania kolizji z zamkniętymi cylindrami jest następnie konstruowana i umieszczana w cache’u. Strategia ta przyniosła całkiem przyzwoite zwiększenie prędkości.

Aby zapobiec sytuacji, w której obiekty przemieszczają się bardzo szybko przechodząc przez przeszkody (ze względu na zbyt duży krok czasowy), wykonywany jest prosty test. Wyobraźmy sobie linię (lub zamknięty cylinder z ustalonym promieniem) mającą swój początek w punkcie środkowym obiektu w ostatniej klatce i koniec w punkcie środkowym obiektu podczas obecnej klatki. Jeśli ta linia uderza w cokolwiek, wtedy obiekt ustawiany jest na pozycji punktu zderzenia. Choć teoretycznie może wydawać się to problematyczne, w praktyce działa dobrze.

Inny rodzaj „oszustwa” jest używany do symulowania martwych ciał. Jeśli coś niespodziewanego dzieje się w momencie, gdy szybko poruszająca się kończyna kończy się będąc umieszczana w końcach zamkniętego cylindra po obu stronach muru, cylinder jest przekazywany na tę stronę ścianki cylindra, gdzie cylinder połączony jest z tułowiem.

Rozmaitości ;)

Liczba iteracji relaksacyjnych użytych w Hitmanie mieści się między 1 i 10 w zależności od symulowanego obiektu. Chociaż nie jest to wystarczające do dokładnego rozwiązania globalnego systemu ograniczeń, wystarcza, aby sprawić wrażenie naturalnego ruchu. Miłą rzeczą dotyczącą tego schematu jest to, że nieprawidłowości nie akumulują się lub utrzymują się wizualnie w systemie będąc przyczyną np. ślizgania się obiektu – w pewnym sensie kombinacja projekcji i algorytmu Verleta zarządza systemem do ‚distribute’ skomplikowanych obliczeń w ciągu kilku klatek (inne schematy muszą użyć dalszych technik stabilizacji technik, takich jak stabilizacji Baumgarte’a). Na szczęście, nieścisłości są najmniejsze lub nawet nie istnieją, gdy istnieje niewiele ruchu i największe, gdy istnieje dużo ruchu – to jest ładne, ponieważ szybki lub złożony ruch maskuje nieco drobne nieścisłości dla ludzkiego oka.

Rodzaj miękkich ciał może także być zaimplementowany za pomocą „miękkich” ograniczeń, tj. ograniczeń, które mogą mieć tylko pewien procent odchyleń „naprawiony” w każdej klatce (tzn. jeśli pozostała długość pręta między dwiema cząstkami wynosi 100, ale faktyczna odległość wynosi 60, kod relaksacyjny może najpierw ustawić odległość na 80 zamiast 100, w następnej klatce 90, 95, 97,5 itd.).

Jak wspomniano, celowo zdecydowaliśmy się zrezygnować z użycia ciężkiej matematycznej notacji, aby dotrzeć do szerszego grona odbiorców. Oznacza to, że nawet jeśli przedstawione metody są oparte na mocnych podstawach matematycznych, ich pochodzenie może wydawać się niejasne, a nawet magiczne.

W rozumieniu matematycznym, to, co robimy, to wybór ‚czasokrokowego’ podejścia do inkluzji różniczkowych (rodzaj równań różniczkowych) za pomocą prostego wyboru algorytmu punktu wnętrza (patrz [((Stewart))]), gdzie dyskutowane jest podobne podejście). Podczas próby spełnienia ograniczeń, tak naprawdę ‚are projecting’ stan systemu na ‚manifold’ opisany przez ograniczenia. To z kolei jest wykonywane przez system rozwiązywania równań liniowych. Równania liniowe lub kod w celu rozwiązania ograniczeń można uzyskać poprzez korzystanie z Jacobianu z ograniczeniem funkcji. W niniejszym artykule relaksacja została omówiona jako domniemany sposób rozwiązywania systemu. Choć nie poruszyliśmy tutaj tego tematu, to jest czasami przydatne do zmiany współczynnika relaksacji lub nawet do korzystania z nadrelaksacji (patrz [((bibcite Press))] dla wyjaśnienia). Ponieważ rozwiązywanie relaksacji czasami zbiega wolno, można również wybrać inny sposób konstruowania równania systemu i korzystać z innych metod rozwiązywania (na przykład rozwiązywanie metodą gradientu sprzężonego macierzy rzadkiej z wykorzystaniem wyników z poprzedniej klatki (wykorzystanie spójności)).

Należy pamiętać, że całkowanie Verleta istnieje w wielu wariantach, np. całkowanie Leapfroga i całkowanie prędkości Verleta (velocity Verlet integrator). Poprzez ich wykorzystanie można zwiększyć dokładność.

Niepożądane zachowania (dzielenie przez zero zazwyczaj spowodowane przez zachodzenie na siebie cząsteczek) mogą być obsługiwane przez losowe drobne dyslokacje cząstek.

Jako optymalizacja, ciała powinny otrzymać przerwę, kiedy odpoczywają.

Aby spróbować zabawy z animacją systemu martwych postaci w grze Hitman: Codename 47, otwórz plik Hitman.ini i dodaj dwie linie „enableconsole 1” i „consolecmd ip_debug 1” na dole samym dole. Wskazanie kursorem na wroga i naciśnięcie Shift + F12 spowoduje niewielki wybuch bomby w jego pobliżu i sprawi, że odleci. Naciśnij K, aby przełączyć tryb wolnej kamery (kamera jest kontrolowana przez klawisze kursorów, Shift i Ctrl).

Należy pamiętać, że ponieważ wszystkie operacje odbywają się w zasadzie na poziomie cząsteczek, algorytmy mogą się nadawać do przetwarzania wektorowego (np. Playstation 2).

Wnioski

Niniejszy dokument opisuje, w jaki sposób został zaimplementowany system fizyki w grze Hitman. Leżąca u podstaw filozofia łącząca metody iteracyjne ze stabilnym całkowaniem okazała się być skuteczna i przydatna do realizacji w grach komputerowych. Most notably, the unified particle-based framework, which handles both collisions and contact, and the ability to trade off speed vs. accuracy without accumulating visually obvious errors are powerful features. W szczególności, jednolity, oparty na cząsteczkach framework, który obsługuje zarówno kolizje jak i ‚contact’, a także zdolność docierania do handlu od prędkości vs dokładności bez akumulacją wizualnie oczywiste błędy są potężne funkcje. Oczywiście, istnieje nadal wiele miejsc, które można poprawić. W szczególności, czworościenny model ciała sztywnego wymaga pracy. Jest to w trakcie pracy.

Przeprowadziliśmy ostatnio w IO Interactive kilka eksperymentów z interaktywną symulacją wody i gazu z wykorzystaniem pełnego równania Naviera-Stokesa. Pracujemy obecnie nad zastosowaniem technik podobnych do tych zademonstrowanych w niniejszym dokumencie z zamiarem stworzenia szybszej i bardziej stabilnej symulacji wody.

Podziękowania

Autor pragnie podziękować Jeroen Wagenaar za owocną dyskusję i całej załodze IO Interactive za współpracę i stworzenie wspaniałego środowiska pracy.

Opinie i komentarze mile widziane: tj@ioi.dk.

[[bibliography]]
: Baraff : Baraff, David //Dynamic Simulation of Non-Penetrating Rigid Bodies//, Ph.D. thesis, Dept. of Computer Science, Cornell University, 1992. http://www.cs.cmu.edu/~baraff/papers/index.html
: Mirtich : Mirtich, Brian V. //Impulse-base Dynamic Simulation of Rigid Body Systems//, Ph.D. thesis, University of California at Berkeley, 1996. http://www.merl.com/people/mirtich/papers/thesis/thesis.html
: Press : Press, William H. et al, //Numerical Recipes//, Cambridge University Press, 1993. http://www.nr.com/nronline_switcher.html
: Stewart : Stewart, D. E., and J. C. Trinkle, “An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Inelastic Collisions and Coulomb Friction”, //International Journal of Numerical Methods in Engineering//, to appear. http://www.cs.tamu.edu/faculty/trink/Papers/ijnmeStewTrink.ps
: Verlet : Verlet, L. „Computer experiments on classical fluids. I. Thermodynamical properties of Lennard-Jones molecules”, //Phys. Rev.//, 159, 98-103 (1967).
: Witkin : Witkin, Andrew and David Baraff, //Physically Based Modeling: Principles and Practice//, Siggraph ’97 course notes, 1997. http://www.cs.cmu.edu/~baraff/sigcourse/index.html
[[/bibliography]]

Autor

Thomas Jakobsen jest szefem badań i rozwoju w IO Interactive, gdzie rozwija nowe technologie dla firmowego (in-house) silnika Glacier. Stworzył symulator fizyki i algorytm wyszukiwania ścieżki w 3D (‚pathfinder 3D’) na potrzeby gry Hitman: Codename 47. Jakobsen zdobył tytuł magistra inżyniera na The Technical University of Denmark, gdzie również obronił swój doktorat w dziedzinie matematyki. Spędził wiele lat w środowisku akademickim i opublikował szereg artykułów naukowych dotyczących kryptoanalizy.

PostHeaderIcon 5. Łączenie ciał

Możliwe jest łączenie wielu ciał sztywnych używając stawów, bolców, zawiasów, itp. Po prostu niech oba ciała sztywne współdzielą cząstkę – w ten sposób będą połączone bolcem. Gdy współdzielą dwie cząstki, będą połączone zawiasem. Patrz rys. 7.

Możliwe jest również, aby połączyć dwa ciała sztywne za pomocą pręta lub jakiegokolwiek innego rodzaju ograniczenia – aby to zrobić, po prostu dodaj odpowiednią poprawkę do kodu do pętli relaksacyjnej.

Takie podejście pozwala na skonstruowanie kompletnego modelu ludzkiego ciała. Aby uzyskać dodatkowy realizm będą także musiały zostać wprowadzone ograniczenia kątowe. Można to osiągnąć różnymi sposobami. Prostym sposobem jest użycie pręta, który wymusza ograniczenia, jeśli tylko odległość pomiędzy dwoma cząstkami spada poniżej pewnego progu (matematycznie mamy jednostronne ograniczenie odległości (nierówność), |x_2 – x_1| > 100). W efekcie, dwie cząstki nigdy nie będą się znajdować zbyt blisko siebie. Patrz rys. 8.

Inną metodą ograniczania kątów jest spełnienie ograniczenia iloczynu skalarnego:

 (x_2-x_0) \cdot (x_1-x_0) < \alpha

Cząsteczki mogą mieć ograniczony zakres ruchu, na przykład w obrębie określonych płaszczyzn. Po raz kolejny, cząstki z pozycjami nie spełniającymi wyżej wymienionych ograniczeń powinny zostać przeniesione – decydowanie w jaki dokładnie sposób jest nieco bardziej skomplikowane, w związku z ograniczeniami pręta.

W Hitmanie korpusy nie składają się ze sztywnych ciał wzorowanych na czworościanach. Są jeszcze prostsze, gdyż składają się z cząsteczek połączonych przez ograniczający pręt w efekcie tworząc prętowe kształty ( :) Stick Figures). Patrz rys. 9. Położenie i orientacja dla każdej kończyny (wektora i macierzy) są następnie uzyskane dla celów renderingu z pozycji cząstek przy użyciu różnych iloczynów wektorowych i normalizacji wektorów (sprawiając, że kolana i łokcie zginają się naturalnie).

Innymi słowy, każda widziana pojedyncza kończyna nie jest ciałem sztywnym ze zwykłymi 6 stopniami swobody. Oznacza to, że fizycznie rotacja wokół osi kończyny nie jest symulowana. Zamiast tego, system animacji szkieletowych użyty do instalacji wielobocznej siatki postaci jest zmuszony do ustalania pozycji nogi, na przykład takiego, że kolana wydają się zginać naturalnie. Ponieważ rotacja nóg i ramion wokół osi nie obejmuje zasadniczego ruchu z upadającego ludzkiego ciała, to działa w porządku i faktycznie w ogromnym stopniu optymalizuje szybkość.

Ograniczenia kątowe są realizowane w celu egzekwowania ograniczeń ludzkiej anatomii. Prosty test sprawdzania kolizji jest spełniany przez strategiczne wprowadzenie ograniczenia nierówności na odległość, jak wspomniano powyżej, na przykład między dwoma kolanami – upewniając się, że nogi nigdy się nie krzyżują.

W przypadku kolizji z otoczeniem, które składa się z trójkątów, każdy pręt jest reprezentowany jako zamknięty cylinder. Gdzieś w systemie kolizji, a ‚subroutine’ obsługują kolizje między cylindrem a trójkątami. Po wykryciu kolizji, głębokość przenikania i punkty są wyodrębniane, a zderzenie jest traktowane jak pręt ( handled for the offending stick), dokładnie tak, jak opisano na początku sekcji 5.

Oczywiście, wiele dodatkowych ulepszeń było koniecznych, aby uzyskać poprawne wyniki.

PostHeaderIcon 4. Ciała sztywne

Równania opisujące ruch ciał sztywnych odkryto na długo przed wynalezieniem nowoczesnych komputerów. Aby móc wyrazić coś przydatnego w tym czasie, matematycy zmuszeni byli do manipulowania wyrażeniami symbolicznymi. W teorii ciał sztywnych, prowadzi to do przydatnych pojęć i narzędzi, takich jak tensory bezwładności, moment pędu, moment obrotowy, kwaterniony reprezentujące kierunki itp. Jednak, z obecną zdolnością do numerycznego przetwarzania ogromnych ilości danych, korzystne byłoby nawet w niektórych przypadkach rozbić obliczenia na prostsze elementy podczas uruchamiania symulacji. W przypadku trójwymiarowych ciał sztywnych, może to oznaczać modelowanie ciała sztywnego przez cztery cząstki i sześć ograniczeń (podając właściwą ilość stopni swobody, 4*3 – 6 = 6). To ułatwia wiele aspektów i jest to dokładnie tym, czym będziemy się dalej zajmować.

Rozważmy czworościan i umieśćmy cząstki w każdym z jego czterech wierzchołków. Ponadto, dla każdej z sześciu krawędzi czworościanu utworzymy ograniczenie na odległość takie jak pręt ograniczeń omówiony w poprzednim rozdziale. Jest to właściwie wystarczające do symulacji ciała sztywnego. Czworościan może zostać uwolniony wcześniej wewnątrz kostki i całkowanie Verleta pozwoli umieścić go prawidłowo. Funkcja SatisfyConstraints() powinna zadbać o dwie rzeczy: 1) cząstki są przechowywane wewnątrz kostki (jak wcześniej) i 2) sześć ograniczeń dotyczących odległości jest spełnionych. Znowu, można to zrobić za pomocą podejścia relaksacyjnego; trzy lub cztery powtórzenia (ew. z aproksymacją funkcji kwadratowej) powinny wystarczyć.

Powiedzmy wyraźnie, sztywne organy w ogóle nie zachowują się jak czworościany kolizyjnie mądre (choć może to zrobić kinetically). Istnieje też inny problem: obecnie wykrywanie kolizji między ciałem sztywnym i światem zewnętrznym bazuje tylko na wierzchołkach, tzn. jeśli wierzchołek znajduje się na zewnątrz świata jest przerzucany ponownie do wewnątrz. Działa to dobrze tak długo, jak długo wnętrze świata jest wypukłe. Jeśli świat nie jest wypukły, wtedy czworościan i świat na zewnątrz rzeczywiście mogą wzajemnie się przenikać, bez żadnego z wierzchołków czworościanu znajdującego się w nielegalnym regionie (patrz rys. 3, gdzie trójkąt reprezentuje w 2D analogię z czworościanu). Ten problem jest podejmowany dalej.

Zajmijmy się najpierw prostszą wersję problemu. Rozważmy wcześniejszy przykład pręta i załóżmy, że świat zewnętrzny przeżywa mały wstrząs. Pręt może teraz przeniknąć na zewnątrz świata, mimo, że żadna z cząstek pręta nie opuszcza świata (patrz rys. 4). Nie będziemy zagłębiać się w tajniki budowy silnika wykrywania kolizji, gdyż jest to nauka sama w sobie. Zamiast tego założymy, że istnieje już dostępny podsystem, który pozwala nam na wykrywanie kolizji. Ponadto zakładamy, że podsystem może ujawnić nam głębokość przenikania i zidentyfikować punkty przenikania w każdym z dwóch kolidujących obiektów. (Jedna z definicji punktów przenikania i głębokości przenikania brzmi tak: odległość przenikania d_p jest najkrótszą odległością, która uniemożliwia dwóm obiektom przenikania, aby jeden z nich przekształcił jeden z obiektów o odległość d_p w pewnym kierunku. Punkty przenikania są punktami na każdym obiekcie, który dokładnie dotyka innego obiektu po translacji, która miała przed chwilą miejsce).

Spójrz ponownie na rys. 4. Tutaj pręt został przeniesiony po kroku Verleta pod wpływem uderzenia. Silnik kolizji określił dwa punkty przenikania, p i q. Na rys. 4a, p jest rzeczywiście identyczny z pozycją cząstki 1, czyli \textbf{x}_1. Na rys. 4b, p leży między \textbf{x}_1oraz \textbf{x}_2 w odległości ¼ długości pręta od \textbf{x}_1. W obu przypadkach punkt p leży na pręcie, a co za tym idzie może być przedstawiony jako kombinacja liniowa \textbf{x}_1 i \textbf{x}_2, \textbf{p}=c_1 \textbf{x}_1 + c_2 \textbf{x}_2 takie, że c_1+c_2=1. W pierwszym, przypadku {c}_1=1, {c}_2=0, natomiast w drugim \textbf{c}_2=0.75, \textbf{c}_1=0.25. Wartości te mówią nam, o ile powinniśmy przemieścić odpowiednie cząstki.

Aby poprawić nieprawidłową konfigurację pręta, powinien on zostać w jakiś sposób przeniesiony do góry.  Naszym celem jest uniknięcie przenikania dzięki przeniesieniu p na tę samą pozycję co q. Robimy to poprzez dostosowanie pozycji dwóch cząsteczek \textbf{x}_1 oraz \textbf{x}_2 w kierunku wektora między p i q, D = qp.

W pierwszym przypadku, po prostu przerzucamy jak wcześniej \textbf{x}_1 z błędnego obszaru (w kierunku q) i to wszystko (\textbf{x}_2 jest nietknięte). W drugim przypadku, p jest nadal najbliżej \textbf{x}_1 i jest to jeden z powodów, dla których \textbf{x}_1 powinno zostać przeniesione bardziej niż \textbf{x}_2. Ponieważ \textbf{p} = 0.75\textbf{x}_1 + 0.25\textbf{x}_2, wybierzemy do przeniesienia \textbf{x}_1 o 0,75 za każdym razem, kiedy przenosimy \textbf{x}_2 o 0.25. Innymi słowy, nowe miejsca cząstek \textbf{x'}_1 oraz \textbf{x'}_2 są dane wyrażeniami:

 {x_1}' = x_1+0.75\lambda \cdot \Delta
 {x_2}'= x_2+0.25\lambda \cdot \Delta

gdzie l jest pewną nieznaną wartością. Nową pozycją p po przeprowadzce obu cząstek jest
\textbf{p'}=c_1 \textbf{x'}_1 + c_2 \textbf{x'}_2.

Przypomnijmy, że chcemy, aby p’ = q, tzn. należy wybrać l dokładnie takie, żeby p’ zbiegło się z q. Ponieważ przenosimy cząstki tylko w kierunku D, również p przesuwa się w kierunku D i w związku z tym rozwiązanie równania p’ = q można znaleźć poprzez obliczenie

 p' \cdot \Delta = q \cdot \Delta

dla l. Rozwijając lewą stronę:

 \begin{tabular}{ r l } \( p' \cdot \Delta \) & \(= (0.75 \cdot {x_1}'+0.25 \cdot {x_2}') \cdot \Delta \) \\ & \(= (0.75 \cdot ( x_1 + 0.75\lambda \cdot \Delta) + 0.25 \cdot ( x_2+0.25\lambda \cdot \Delta)) \cdot \Delta \) \\ & \(= (0.75 \cdot x_1 + 0.25 \cdot x_2) \cdot \Delta + \lambda (0.75^2 +0.25^2) \cdot \Delta^2 \) \\ & \(= p \cdot \Delta + \lambda (0.75^2 + 0.25^2) \cdot \Delta^2 \) \end{tabular}

które z prawą stroną równania (**) daje:

 \lambda = \frac{(\textbf{q}-\textbf{p}) \cdot \Delta} { (0.75^2+0.25^2) \cdot \Delta^2}

Łącząc l z (*) otrzymujemy nowe pozycje cząstek, dla których p’ zbiegnie się z q.

Rysunek 5 obrazuje sytuację po ruszeniu cząsteczek. Nie mamy żadnego przenikającego obiektu, ale teraz długość ograniczającego pręta została naruszona. Aby rozwiązać ten problem, robimy kolejną iterację pętli (lub kilka).

Powyższa strategia działa również dla czworościanu w zupełnie analogiczny sposób. Najpierw znajdowane są punkty przenikające p i q (mogą to być również punkty leżące wewnątrz trójkąta), a **p** jest wyrażone jako liniowa kombinacja czterech cząstek \textbf{p}=c_1 \textbf{x}_1 + c_2 \textbf{x}_2 + c_3 \textbf{x}_3 + c_4 \textbf{x}_4 takich, że c_1 + c_2 + c_3 + c_4 = 1 (wymaga to rozwiązania niewielkiego układu równań liniowych). Po znalezieniu D = qp, obliczamy wartość

 \lambda = \frac{(\textbf{q}-\textbf{p}) \cdot \Delta} { (c_1^2+c_2^2+c_3^2+c_4^2) \cdot \Delta^2}

i nowe pozycje są następnie dane przez
 {x_1}' = {x_1} + c_1 \lambda \cdot \Delta
 {x_2}' = {x_2} + c_2 \lambda \cdot \Delta
 {x_3}' = {x_3}+c_3 \lambda \cdot \Delta
 {x_4}' = {x_4}+c_4 \lambda \cdot \Delta

Tutaj mamy kolizję ciała sztywnego z nieruchomym światem. Powyższa metoda jest ogólną do obsługi kolizji kilku sztywnych ciał. Kolizje są przetwarzane na jedną parę ciał naraz. Zamiast poruszać tylko p, w tym przypadku zarówno p i q są przenoszone do siebie.

Znowu, po skorygowaniu pozycji cząstki w taki sposób, że spełniają one ograniczenia nieprzenikania, należy uwzględnić sześć ograniczeń odległości, które tworzą ciała sztywne, itd. W tej metodzie, czworościan może być nawet zanurzony wewnątrz innego obiektu, który może być stosowany zamiast samego czworościanu do obsługi kolizji. Na rys. 6, czworościan jest osadzony wewnątrz kostki.

Po pierwsze, kostka musi być umocowana do czworościanu w jakiś sposób. Jednym z rozwiązań byłoby wybranie systemu masowej punkcie środkowym 0.25*(x_1 + x_2 + x_3 + x_4) jako pozycję kostki, a następnie dziedziczyć orientacyjną macierz (derive an orientation matrix) poprzez analizę obecnych pozycji cząsteczek. Gdy kolizja/przenikanie zostaną wychwycona, punkt kolizyjny p (który w tym przypadku zostanie położony na kostce) jest traktowana dokładnie tak samo, jak powyżej i pozycje cząsteczek są stosownie aktualizowane. Jako optymalizacja, możliwe jest wcześniejsze przeliczenie wartości c_1 - c_4 dla wszystkich wierzchołków z kostki. Jeśli punktem przenikania p jest wierzchołek, wartości c_1 - c_4 mogą być użyte bezpośrednio. W innym wypadku, p leży na wnętrzu powierzchni trójkąta lub jednego z jego krawędzi i wartości c_1 - c_4 mogą następnie być interpolowane z przeliczonych wcześniej wartości odpowiednich wierzchołków trójkąta.

Zazwyczaj 3 do 4 powtórzeń relaksacji jest wystarczające. Ciała nie będą się zachowywać tak, jakby były całkowicie sztywne, ponieważ iteracje relaksacyjne są zatrzymane przedwcześnie. Jest to przede wszystkim użyteczna funkcja, jako że nie istnieje coś takiego jak doskonale sztywne ciało – zwłaszcza ludzkie. To również sprawia, że system stał się bardziej stabilny.

Przez przemieszczenie cząsteczek, które tworzą czworościan, właściwości fizyczne również mogą być zmienione (matematycznie, bezwładność się zmienia, kiedy pozycje i masy cząstek są zmieniane).

Możliwe są inne ustawienia cząstek niż czworościan, np. umieszczenie cząsteczek w modelu układu współrzędnych, tzn. w (0,0,0), (1,0,0), (0,1,0), (0,0,1). Niech a, b, c będą wektorami od cząstki 1 do cząstek odpowiednio 2, 3 i 4. Ograniczenie pozycji cząstek przez przyjęcie, aby wektory a, b, c miały długość 1, a kąt między każdą z trzech par wektorów wynosił 90 stopni (odpowiadający iloczyn skalarny powinien wynosić zero). (Zauważ, że ten znów daje cztery cząstki i sześć ograniczeń).

PostHeaderIcon 1. Wprowadzenie

Początkowa próba tłumaczenia strony http://www.teknikus.dk/tj/gdc2001.htm. Prawdopodobnie wykorzystano przedstawione tam techniki w grze Soldat.

——

Advanced Character Physics
Zaawansowana fizyka postaci

Thomas Jakobsen
IO Interactive, Farvergade 2
DK-1463 Copenhagen K
Denmark
Email: tj@ioi.dk, www: www.ioi.dk/~tj

W skrócie

Niniejszy dokument opisuje podstawowe podejścia do modelowania fizycznego, które są dobrze dostosowane do interaktywnego wykorzystania. Zaprezentowane metody są proste, szybkie i dość stabilne, w podstawowej wersji nie wymagają zaawansowanej wiedzy matematycznej (choć są one oparte na solidnych fundamentach matematycznych). Pozwalają one na symulację zarówno miękkich jak i sztywnych ciał, połączonych przegubem lub ogranicznikami używając kinematyki normalnej, jak i odwrotnej.

Algorytmy zostały opracowane na potrzeby gry Hitman: Codename 47 firmy IO Interactive. Tam, między innymi, system fizyki był odpowiedzialny za przemieszczanie materiałów, roślin, sztywnych ciał oraz za upadanie w unikalny sposób martwych ludzkich ciał w zależności od tego, gdzie zostały one uderzone, w pełni interakcji z otoczeniem (wyniknął z tego powstały w prasie oksymoron „realistyczne animacje śmierci”).

Niniejszy artykuł zajmuje się również takimi kwestiami jak wnikliwy test optymalizacyjny i obsługa tarcia.

Wprowadzenie

Wykorzystanie modelowania fizycznego przy produkcji dobrze wyglądającej dla oka animacji rozważano już jakiś czas temu, a wiele istniejących dziś technik jest już dość zaawansowanych. W literaturze zostały zaproponowane różne podejścia [((bibcite Baraff))], [((bibcite Mirtich))], [((bibcite Witkin))] i inni) i został włożony duży wysiłek w budowę algorytmów, które są dokładne i niezawodne. Tak naprawdę, precyzyjne metody symulacji fizyki i dynamiki były znane już od pewnego czasu w inżynierii. Jednakże, do gier i użytku interaktywnego, dokładność nie jest najważniejszym celem (choć z pewnością wskazane byłoby ją mieć) – tutaj raczej ważne jest wierne odwzorowanie (programista może oszukiwać ile chce, jeśli gracz nadal jest wciągnięty w rozgrywkę) i szybkość wykonywania (tylko niewielki procent czasu będzie przeznaczony do obsługi silnika fizyki). W przypadku symulacji fizyki, słowo „wierność” oznacza również stabilność; metoda nie jest dobra, jeżeli obiekty wydają się przenikać przez przeszkody lub wibrują, kiedy powinny leżeć, albo jeśli cząsteczki materiału mają tendencję do „wybuchania”.

Metody zaprezentowane w niniejszym dokumencie zostały stworzone w celu osiągnięcia tych celów. Algorytmy zostały opracowane i zaimplementowane przez autora oraz wykorzystane w grze komputerowej Hitman: Codename 47 firmy IO Interactive i zostały zintegrowane w silniku Glacier. Metody okazały się dość proste do implementacji (w porównaniu do innych schematów) i mają na dodatek wysoką wydajność.

Algorytm jest iteracyjny, w związku z czym może być zatrzymany w dowolnej chwili. To zapewnia nam bardzo przydatny kompromis między czasem a dokładnością obliczeń: jeżeli zostaje przyjęte małe źródło nieścisłości, kod może zostać przystosowany do szybszego działania; ten margines błędu można nawet dostosowywać na bieżąco. W niektórych przypadkach metoda ta jest o rząd wielkości szybsza od innych istniejących metod. Obsługuje zarówno system kolizji i ‚resting contact’ w tym samym ‚frameworku’ i dobrze radzi sobie z ułożonymi w stertę pudełkami i innymi sytuacjami, które mocno obciążają silnik fizyki.

Powodzenie tej metody wynika z właściwej kombinacji kilku następujących technik, które korzystają od siebie nawzajem:
* całkowanie Verleta
* obsługa kolizji i przenikania przez rzutowanie
* proste spełnianie ograniczeń przy użyciu metody relaksacyjnej
* aproksymacja kwadratowa (dająca solidne przyspieszenie)
* modelowanie ciał sztywnych jako cząstek z ograniczeniami
* zoptymalizowany silnik kolizji ze zdolnością do obliczenia głębokości przenikania

Każdy z powyższych tematów zostanie pokrótce omówiony. W niniejszym dokumencie autor starał się uczynić go dostępnym dla jak najszerszej grupy odbiorców, bez utraty istotnych informacji niezbędnych do realizacji metody. Oznacza to, że techniczne, matematyczne pojęcia są ograniczane do minimum, jeśli nie mają kluczowego znaczenia dla zrozumienia tematu. Celem jest wykazanie możliwości implamentacji dość zaawansowanej i stabilnej symulacji fizycznej bez obciążeń związanych z matematycznymi tajnikami.

Zawartość tego dokumentu jest zorganizowana w następujący sposób. Po pierwsze, w sekcji 2 zostanie opisana niezależna od prędkości reprezentacja cząstek systemu. Ma wiele zalet, przede wszystkim stabilność i fakt, że ograniczenia są proste do implementacji. Sekcja 3 opisuje w jaki sposób odbywa się detekcja kolizji. Następnie, w sekcji 4 system cząsteczek jest rozszerzony o system ograniczeń pozwalający na modelowanie ciała sztywnego. Sekcja 5 wyjaśnia, w jaki sposób skonfigurować odpowiednio ograniczone cząstki systemu w celu emulowania ciała sztywnego. Następnie w sekcji 6 zademonstrowano dalsze rozszerzenie systemu pozwalające na połączenie części ciała stawami (czyli systemów wzajemnie połączonych części z kątami i innymi ograniczeniami). Sekcja 7 zawiera różne notatki i przekazuje pewne doświadczenia związane z implementacją tarcia, itd. Wreszcie, rozdział 8 zawiera krótkie podsumowanie.

W następnych rozdziałach, pogrubiona czcionka oznacza wektory. Składowe wektora są oznaczone indeksem dolnym, tj. \textbf{x} = (x_1, x_2, x_3)