Uvod

Detekcija sudara je vrlo važna u simulaciji dinamičkih scena. Problem izračuna detekcije sudara između n pokretnih objekata je problem složenosti O(n^2), tj. točnije, uz n objekata, potrebno je evaluirati n*(n-1)/2 potencijalnih kolizijskih parova.

Klasičan pristup za ubrzanje tih kalkulacija je korištenje algoritma od dva koraka:

• U prvom koraku, poznatom kao široka faza, aproksimativni i brzi test pronalazi potencijalne kolizijske parove
• u drugom koraku, poznatom kao uska faza, ti parovi se točno provjeravaju za koliziju.

Kako široka faza algoritma mora biti vrlo brza, testovi se obično rade između jednostavnijih oblika – omeđujućih volumena, kao što su općeniti kvadri (eng. OBB - Oriented Bounding Box), kvadri paralelni sa osima (eng. AABB - Axis-Aligned Bounding Box) ili sfere.

Dodatna metoda koja se koristi kod ubrzanja široke faze detekcije sudara je korištenje prostornih struktura podataka, čime se smanjuje broj potencijalnih kolizijskih parova koje moramo provjeriti. Za takve strukture je poželjno da imaju mogućnost prilagodbe različitoj gustoći rasporeda objekata po sceni.

U ovom radu opisujem nekoliko struktura podataka i algoritama koji se koriste u širokoj fazi detekcije sudara za njeno ubrzanje. Algoritmi su implementirani u 3D prostoru pri čemu se testovi kolizije vrše između kugli, koje predstavljaju omeđujuće volumene složenijih objekata koji se mogu nalaziti u njima.

Implementiran je algoritam klasične detekcije sudara (složenosti O(n^2)), zatim prostorna struktura BSP stablo [2] (eng. Binary space partitioning tree), prostorna struktura Samo-podesivo BSP stablo [1] (eng. Self-adjusting BSP tree) koja se prilagođava različitoj gustoći rasporeda objekata na sceni te algoritam Brojenja parova i pojednostavljivanja [3] (eng. Sweep and prune). Performanse svih tih metoda su testirane kod međusobne kolizije od 50 objekata do 5.000 pokretnih objekata (tj. omeđujućih volumena – kugli) na sceni i to pri različitim rasporedima objekata. Također je ispitan utjecaj različitog broja poligona na sceni te sjenčanja na brzinu iscrtavanja te zauzeće resursa računala.

<< Početna stranica | Opis algoritama i struktura podataka >>