D.Maciejewski.pdf

Wybrane techniki programowania

gier, cz¦±¢ druga - fizyka.

DariuszMaciejewski

dmaciej1@mion.elka.pw.edu.pl

Wydział Elektroniki i Technik Informacyjnych

Politechnika Warszawska

ul. Nowowiejska 15/19

00-665 Warszawa, Polska

30 maja 2008

Streszczenie

Opracowanie ma na celu przybli»enie zagadnienia pro-

gramowania fizyki w grach komputerowych. Dzi¦ki realisty-

cznej symulacji fizyki, gracz ma wi¦kszy wpływ na wydarzenia

i w efekcie lepiej wczuwa si¦ w klimat przedstawianego ±wiata.

Jednak»e reprodukcja zjawisk fizycznych jest procesem bardzo

kosztownym obliczeniowo, wi¦c aby była efektywna, na ka»dym

kroku trzeba szuka¢ miejsc do optymalizacji kodu. W es-

eju omówione s¡ podstawowe elementy silnika fizyki oraz

rozwi¡zania pozwalaj¡ce na wielokrotny wzrost ich wyda-

jno±ci.

Spistre±ci

1Detekcjakolizji

1.1 Wst¦p . . . . . . . . . . . . . . . . . . . . . .

1.2 Algorytm detekcji kolizji . . . . . . . . . . .

1.3 Hierarchie brył otaczaj¡cych . . . . . . . . .

1.4 Wybór obiektów mog¡cych kolidowa¢ . . . . . .

2Symulacjafizyki

2.1 Całkowanie Verlet’a . . . . . . . . . . . . . .

2.2 Nakładanie ogranicze« na punkty materialne .

2.3 Symulacja ciał odkształcalnych . . . . . . . .

2.4 Symulacja ciał sztywnych . . . . . . . . . . .

2.5 Fizyka szkieletu . . . . . . . . . . . . . . . .

1 DETEKCJA KOLIZJI

1Detekcjakolizji

1.1Wst¦p

Detekcja kolizji jest niezb¦dnym elementem ka»dego symula-

tora fizyki. Nie maj¡c informacji o zachodz¡cych zderzeni-

ach, symulator nie mógłby na nie zareagowa¢. Obiekty porusza-

łyby si¦ w ’±wiecie duchów’, przenikaj¡c si¦ nawzajem. Ruch

byłby jedynie skutkiem zaszytych w silniku sił, takich jak

np. siła ci¡»enia. Obserwowanie takiego ±wiata nie było by

ani pouczaj¡cym, ani zajmuj¡cym widowiskiem.

W wyniku detekcji kolizji silnik fizyczny otrzymuje in-

formacje które umo»liwiaj¡ symulacj¦ oddziaływa« mi¦dzy ciałami.

Dzi¦ki tej wiedzy mo»emy przenie±¢ si¦ ze ’±wiata duchów’ do

±wiata materialnego. Detektory najcz¦±ciej wykrywaj¡ kolizje

na jeden z dwóch sposobów: metod¡ apriori b¡d¹ aposteri-

ori [Wik].

W metodzie aposteriori silnik porusza symulacj¦ o pewien

mały krok do przodu, a nast¦pnie sprawdza, czy istniej¡ obiekty

które przecinaj¡ si¦. W ka»dym kroku symulacji tworzona jest

lista przecinaj¡cych si¦ obiektów. Na bazie tej listy popraw-

iane s¡ pozycje i trajektorie ruchu koliduj¡cych obiektów.

Nazwa metody bierze si¦ st¡d, i» najcz¦±ciej symulator przeskoczy

moment zaistnienia kolizji i dopiero po jej zaistnieniu pode-

jmuje akcj¦.

Odmiennym podej±ciem cechuje si¦ metoda apriori . W metodzie

tej algorytm detekcji kolizji musi potrafi¢ przewidzie¢ dokładne

trajektorie obiektów. Wykorzystuj¡c t¦ wiedz¦, mo»e precyzyjnie

okre±li¢ moment zderzenia, dzi¦ki czemu ciała nigdy si¦ nie

przetn¡. Momenty kolizji znane s¡ jeszcze przed przemieszcze-

niem ciał. Niestety kosztem tej wiedzy jest du»e skomplikowanie

numeryczne algorytmu.

Przewag¡ metody aposteriori jest mo»liwo±¢ logicznego rozdzie-

lenia algorytmu fizycznego od detektora kolizji. Detektor

nie musi mie¢ wiedzy o zmiennych fizycznych opisuj¡cych ruch

obiektów oraz o rodzajach materiałów z których s¡ wykonane.

Problemem tej metody jest jednak etap poprawiania niezgod-

nych z fizyk¡ pozycji obiektów, przez co metoda apriori cechuje

du»o wi¦ksz¡ dokładno±ci¡ i stabilno±ci¡ symulacji.

Specjalnym przypadkiem do rozpatrzenia jest stan spoczynku.

Je»eli odległo±¢ oraz ruch dwóch obiektów wzgl¦dem siebie jest

poni»ej pewnego progu, ciała powinny przej±¢ w stan spoczynku,

z którego zostan¡ wyrwane dopiero pod działaniem nowej siły.

1.2Algorytmdetekcjikolizji

Oczywistym podej±ciem do detekcji kolizji jest sprawdzenie

kolizji mi¦dzy wszystkim parami symulowanych obiektów. Poniewa»

modele 3d składaj¡ si¦ ze zbioru trójk¡tów, detekcja kolizji

sprowadza si¦ do sprawdzenia czy nie doszło do przeci¦cia trójk¡tów

1.3 Hierarchie brył otaczaj¡cych

1 DETEKCJA KOLIZJI

jednego z obiektów z trójk¡tami drugiego. Powstało wiele ró»nych

algorytmów badaj¡cych czy doszło do przeci¦cia dwóch trójk¡tów.

Jako baz¦ detektora wybrałem algorytm ’Fast Triangle-Triangle

Intersection Test’ autorstwa Oliviera Devillers oraz Philippe’a

Guigue z INRIA [DG02]. Algorytm ten w pierwszym kroku sprawdza

czy trójk¡ty przecinaj¡ wzajemnie płaszczyzny na których le»¡.

Jest to niezb¦dny warunek by mogło doj±¢ do kolizji. Je»eli

istnieje potencjalna kolizja, wystarczy przeprowadzi¢ cztery

kolejne testy by uzyska¢ ostateczne rozstrzygni¦cie.

Algorytmy wykrywania przecinaj¡cych si¦ trójk¡tów s¡ obec-

nie uproszczone do granic mo»liwo±ci. Modele obiektów składaj¡

si¦ najcz¦±ciej z co najmniej kilkuset trójk¡tów, a modele

postaci mog¡ by¢ zbudowane nawet z kilku milionów trójk¡tów.

Jak łatwo wyliczy¢, sprawdzenie kolizji zachodz¡cej mi¦dzy

dwoma modelami mo»e wymaga¢ przeprowadzenia od dziesi¡tek tysi¦cy

do milionów testów kolizji trójk¡tów. Grafika komputerowa

umo»liwia wykorzystanie sztuczek zwi¡zanych z mapowaniem mod-

elu, które umo»liwiaj¡ ograniczenie ilo±ci wierzchołków bez

wyra¹nej straty na jako±ci wizualnej. Kolejn¡ technik¡ ob-

ni»aj¡c¡ ilo±¢ wierzchołków jest przygotowanie dla detektora

kolizji modelu fizycznego, b¦d¡cego uproszczon¡ wersj¡ mod-

elu pokazywanego na ekranie. Pozwala to na opisanie modelu

postaci za pomoc¡ jedynie kilkudziesi¦ciu do kilkuset wierz-

chołków. Nadal daje to jednak kilka tysi¦cy testów dla tylko

jednej pary obiektów.

W celu ograniczenia ilo±ci wymaganych testów kolizji trójk¡tów,

stosuje si¦ kilka technik umo»liwiaj¡cych przycinanie zbioru

potencjalnych trójk¡tów mog¡cych wej±¢ w kolizj¦ z innym obiek-

tem, a tak»e przycinanie zbioru obiektów które mog¡ si¦ ze

sob¡ przeci¡¢.

1.3Hierarchiebryłotaczaj¡cych

Technika ta polega na podziale obiektu na hierarchiczne drzewo

mniejszych elementów. Ka»dy w¦zeł drzewa zawiera informa-

cj¦ o otaczaj¡cej go bryle. Brył¡ t¡ najcz¦±ciej s¡ sfery,

sze±ciany b¡d¹ walce.

Je»eli bryła otaczaj¡ca dany w¦zeł przecina si¦ z brył¡

otaczaj¡c¡ w¦zeł nale»¡cy do innego obiektu, to oznacza, »e

wyst¦puje potencjalna kolizja obiektów. Aby j¡ rozstrzygn¡¢,

nale»y sprawdzi¢ czy zachodz¡ kolizje mi¦dzy bryłami otacza-

j¡cymi w¦zły ni»szego rz¦du. Je±li algorytm dojdzie do na-

jni»szego rz¦du hierarchii brył otaczaj¡cych, b¦dzie musiał

dokona¢ testu kolizji mi¦dzy trójk¡tami nale»¡cymi do tych

najmniejszych w¦złów w hierarchii. Dzi¦ki zastosowaniu tej

techniki ju» pierwszy test mo»e wykluczy¢ kolizj¦ mi¦dzy obiek-

tami. Co wi¦cej, wszystkie testy przeprowadzane w w¦złach

drzewa operuj¡ na prostych bryłach geometrycznych, pozwala-

j¡cych na efektywne sprawdzenie czy zachodzi kolizja. Dopiero

test najni»szego rz¦du wymaga badania kolizji mi¦dzy trójk¡-

1.4 Wybór obiektów mog¡cych kolidowa¢ 1 DETEKCJA KOLIZJI

Rysunek 1: Hierarchiczny podział przestrzeni (na

przykładzie Drzewa Ósemkowego).

tami, jednak»e jest ich na tym poziomie tylko od kilku do kilku-

nastu dla ka»dego z w¦złów.

Projektuj¡c detektor, warto si¦ równie» zastanowi¢, jak

wielk¡ precyzj¦ wykrywania kolizji wymaga nasza symulacja.

Prawdopodobnie mo»emy całkowicie zrezygnowa¢ z testowania kolizji

mi¦dzy trójk¡tami, gdy» wystarczy nam przybli»enie zapewnione

przez hierarchi¦ brył otaczaj¡cych.

1.4Wybórobiektówmog¡cychkolidowa¢

Zło»ona scena 3d mo»e składa¢ si¦ z bardzo du»ej ilo±ci obiek-

tów. Obiekt poruszaj¡cy si¦ np. na scenie rozgrywaj¡cej si¦

w mieszkaniu mo»e wej±¢ w kolizj¦ z du»¡ ilo±ci¡ obiektów.

Mog¡ to by¢ zarówno drobne modele przedstawiaj¡ce np. ksi¡»ki,

ale te» obiekty znaczniejszych rozmiarów przedstawiaj¡ce meble

i ±ciany. Sprawdzanie czy poruszaj¡cy si¦ obiekt wchodzi w

kolizj¦ z wszystkim modelami w scenie niepotrzebnie mno»y ilo±¢

przeprowadzanych testów, wpływaj¡c na znaczne obni»enie szy-

bko±ci detekcji kolizji. Je±li posta¢ znajduje si¦ w kuchni,

to niema najmniejszego sensu sprawdzanie, czy przypadkiem nie

zderzyła si¦ z wann¡ mieszcz¡c¡ si¦ na drugim ko«cu mieszka-

nia. W celu wyeliminowania takich zb¦dnych testów stosuje

si¦ techniki podziału przestrzeni.

Najbardziej uniwersalnym sposobem podziału przestrzeni jest

zastosowanie drzewa BSP (Binary Space Partitioning - Bina-

rny Podział Przestrzeni). Ka»dy w¦zeł takiego drzewa dzieli

opisywan¡ przez siebie przestrze« na dwie podprzestrzenie le»¡ce

po przeciwnych stronach pewnej hiperpłaszczyzny. Drzewo takie

mo»na zastosowa¢ do podziału przestrzeni o dowolnej wymiarowo±ci.

Pozwala ono na bardzo szybkie odrzucenie obiektów znajduj¡-

cych si¦ poza rozpatrywan¡ podprzestrzeni¡.

Drzewo BSP dobrze nadaje si¦ do opisu zamkni¦tych pomieszcze«,

2 SYMULACJA FIZYKI

Rysunek 2: Drzewo Binernego Podziału Przestrzeni.

jednak»e otwarte przestrzenie lepiej opisuj¡ drzewa ósemkowe

(lub czwórkowe dla przestrzeni dwuwymiarowych). Drzewa takie

polegaj¡ na otoczeniu sceny sze±cianem, który jest nast¦p-

nie dzielony na osiem mniejszych sze±cianów. Podział taki

zagł¦bia si¦ rekurencyjnie, a» do osi¡gni¦cia ustalonego kry-

terium - zadanej gł¦boko±ci lub minimalnej ilo±ci obiektów

w minimalnym sze±cianie. Obiekt przypisywany jest do min-

imalnego sze±cianu w którym mo»e si¦ pomie±ci¢ oraz wewn¡trz

którego znajduje si¦ jego ±rodek ci¦»ko±ci. Wybieraj¡c obiekty

które mog¡ wej±¢ w kolizj¦ z danych modelem, nale»y sprawdzi¢

wszystkie obiekty znajduj¡ce si¦ w jego sze±cianie (a wi¦c

i w jego sze±cianach ni»szych rz¦dów) oraz s¡siednie sze±-

ciany. W praktyce sprawdzaj¡c sze±ciany s¡siaduj¡ce, wystar-

czy przejrze¢ te le»¡ce po stronie rosn¡cych współrz¦dnych

- kolizje z pozostałymi s¡siadami zostały sprawdzone podczas

badania kandydatów dla obiektów nale»¡cych do tamtych pod-

przestrzeni.

2Symulacjafizyki

Posiadaj¡c wiedz¦ o siłach oddziałuj¡cych na obiekty oraz koliz-

jach do których doszło, mo»na przej±¢ do symulacji ruchu. Przykład-

owym podej±ciem mo»e by¢ otwarcie podr¦cznika do fizyki i za-

stosowanie przedstawionych w nim wzorów opisuj¡cych ruch.

Stosuj¡c opis dynamiczny na poziomie modelu jako cało±ci,

nale»ałoby uwzgl¦dni¢ w algorytmie takie wielko±ci jak pozy-

cja, pr¦dko±¢, masa obiektu, a tak»e działaj¡ce na« siły. Model

taki jest w najprostszym przypadku ciałem sztywnym, nie mo»na

wi¦c równie» zapomnie¢ o opisuj¡cych ruch obrotowy momencie

bezwładno±ci oraz momencie siły. Gdy zechcemy symulowa¢ ciała

odkształcalne, takie jak materiały, powierzchnie elastyczne,

b¡d¹ ro±liny, nasz algorytm rozro±nie si¦ jeszcze bardziej.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: