Opis algoritama i struktura podataka

Klasična metoda

Kod klasične metode detekcije sudara, potrebno je provjeriti za svaki od n objekata u sceni da li je u koliziji sa ostalih n-1 objekata. Dakle, ukupno je za koliziju potrebno provjeriti: n*(n-1)/2 parova. Čak i kad je test kolizije trivijalan, kao što je slučaj kod kugli, to postaje problem pri velikom broju objekata. Npr. Kod 10.000 pokretnih objekata na sceni potrebno je za koliziju ispitati gotovo 50 milijuna parova, i tako u svakom koraku simulacije.

BSP stablo

BSP stablo je struktura podataka koje se može koristi kod pretrage i sortiranja objekata u n-dimenzionalnom prostoru. Stablo kao cjelina predstavlja cijeli prostor, a svaki čvor predstavlja konveksni dio tog prostora. Svaki čvor (osim krajnjih čvorova – listova) ima hiper-ravninu koja dijeli prostor koji predstavlja na dvije polovine. Svaki čvor također sadrži i reference na ta dva nova čvora. BSP stablo se najčešće koristi u 2D ili 3D prostoru. U tim slučajevima hiper-ravnine su zapravo pravci i ravnine.

BSP stablo se u širokoj fazi detekcije sudara koristi u svrhu smanjenja potencijalnih kolizijskih parova koje treba evaluirati. Koliko to smanjenje iznosi, ovisi o dubini samog stabla i uspješnosti odabira što boljih ravnina podjele. Poželjno je da ravnina podjele dijeli prostor na pola, tj. da je sa obje njene strane jednak broj objekata. Također je poželjno da je redundancija pri tome što manja, tj. da je što manji broj objekata koji se nalaze sa obje strane ravnine podjele (zbog toga što ih ravnina siječe).

Slika 1. Podjela prostora BSP stablom i samo stablo.

Na slici 1 je pomoću BSP stabla dubine 2 broj potencijalnih kolizijskih parova smanjen sa 55 na 11. Kod većeg broja objekata, dobitak je još veći. Tako, npr. dok kod 10.000 objekata klasičnom metodom imamo oko 5 milijuna parova, uz idealnu podjelu objekata unutar BSP stabla dubine 9, broj parova je približno 50 puta manji.

Glavni nedostatak BSP stabla u primjeni kod široke faze detekcije sudara u dinamičnim scenama je taj što se raspored objekata u sceni tijekom vremena mijenja, te početno BSP stablo, koje je statična struktura, ne daje jednaki faktor ubrzanja kao što je davalo na početku. Zbog toga su potrebna proširenja BSP stabla, koja ga prilagođavaju promjenjivom rasporedu objekata na sceni.

Samo-podesivo BSP stablo

Sve što je rečeno za BSP stablo u prošlom dijelu vrijedi i za samo-podesivo BSP stablo. Jedini dodatak je taj što se nad BSP stablom periodički, nakon vremena T, izvodi funkcija podešavanja BSP stabla. Ona prilagođava oblik stabla novom rasporedu objekata u sceni, kako bi se dobio što bolji raspored objekata po listovima stabla.

Potrebno je vršiti balans između želje za odabirom što boljih ravnina podjele i cijene funkcije kojom se takve ravnine biraju, zbog toga što će se ta funkcija vrlo često pozivati tijekom izvođenja simulacije. Zbog toga, i dodatnih pojednostavljenja koja takva odluka donosi, moguće ravnine podjele sam limitirao na x-y, y-z te x-z ravnine.
Stablo kod kojeg su ravnine podjele limitirane na taj način se zove kd-stablo (eng. kd-tree, k-dimensional-tree) i ono je specijalni slučaj BSP stabla, no u nastavku ću koristiti isključivo naziv BSP stablo.

Kod samo-podesivog BSP stabla svakih T = 0,2s se vrši podešavanje stabla. Ono se sastoji od balansiranja čvorova koji su nebalansirani, tj. odabira novih ravnina podjele za takve čvorove. Čvor se smatra nebalansiranim ako je omjer objekata sa jedne i druge strane njegove ravnine podjele manji od 0,5 (ili recipročno,veći od 2,0).

Slika 2. Lijevo – nebalansirani čvor; Desno – nova os balansira čvor.

Kod podešavanja stabla, u sve čvorove stabla koji nisu listovi se spremaju objekti, i kada se usporedbom broja objekata utvrdi da neki čvor nije balansiran, za njega i njegovu djecu se odabiru nove osi podjele. Na slici 2 se može vidjeti kako radi funkcija balansiranja čvora u 2D. Kako navedeni čvor ima samo 2 lista, balansiranje je završeno. Detalji o implementaciji samog stabla i balansiranja se mogu pogledati u diplomskom radu koji se može preuzeti sa ove stranice.

Algoritam brojenja parova i pojednostavljivanja

Koristi se u širokoj fazi detekcije sudara, kao i BSP stablo, u svrhu smanjenja potencijalnih kolizijskih parova koje treba evaluirati. Algoritam se sastoji od dvije faze - prva je prikazana na slici 3.

Slika 3. Prva faza algoritma brojenja parova i pojednostavljivanja.

Prva faza (faza brojenja parova) počinje projekcijom minimuma i maksimuma omeđujućih volumena (tj. ploha u slučaju 2D) na sve osi (X, Y, Z u slučaju 3D ili samo X, Y u slučaju 2D). Kako se u ovom radu kao omeđujući volumeni koriste kugle, koje sve imaju isti radijus, dovoljno je projicirati na svaku os samo središte kružnice. Zatim se po svim osima projekcije središta sortiraju, te se linearnim algoritmom broje parovi objekata koji se preklapaju. Tako bi za scenu navedenu na prošloj stranici, te zadanu os dobili sljedeće parove objekata: (1,4), (2,4), (3,5). Postupak je potrebno ponoviti i za sve ostale osi. Dobiveni parovi pojedine osi se spremaju u zasebnu listu parova koju ima svaka os.

U drugoj fazi algoritma (fazi pojednostavljivanja) se vrši pojednostavljivanje, tj. dodatna eliminacija parova. Za to se koristi kvadratna matrica dimenzije jednake broju objekata. Svi elementi te matrice se na početku postave na nulu, a zatim, kad se po pojedinoj osi detektiraju parovi, u matrici se inkrementira element čiji redak i stupac je jednak indeksima dvaju objekata koji se po toj osi preklapaju. Pri tome se treba pobrinuti da je indeks prvog elementa manji od indeksa drugog – tako se zapravo koristi samo gornja trokutasta matrica. Za scenu navedenu na slici 3, te zadanu os dobili bi matricu prikazanu na slici 4.

Slika 4. Matrica kolizijskih parova.

Postupak treba napraviti za sve osi. Stvarna provjera kolizije se vrši nakon toga, i to za sve elemente matrice u kojima piše da postoji poklapanje po svim osima (2 za 2D, tj. 3 za 3D). Pri tome se ne čita cijela matrica već samo parovi one osi koja ima najmanji broj preklapanja (elemenata u listi parova te osi). Prije sljedećeg koraka simulacije potrebno je sve elemente matrice koji su različiti od nula postaviti na nulu.

<< Uvod | Opis implementacije >>