Strukture podataka za detekciju sudara

Rezultati simulacije

Tijekom simulacija je ispitano kako različiti broj objekata te različiti rasporedi objekata na sceni utječu na brzinu iscrtavanja kod primjene opisanih algoritama i prostornih struktura podataka. Također je ispitan utjecaj različitog broja trokuta na sceni te sjenčanja na brzinu iscrtavanja te zauzeće resursa računala.

Dodatna ispitivanja su pokazala da brzina gibanja objekata ne utječe na brzinu iscrtavanja, dok povećanje veličine objekata utječe negativno na sve metode – uzrokuje povećanje broja kolizija, kod BSP stabala dodatno i povećanje redundancije, a kod algoritma brojenja parova i pojednostavljivanja uzrokuje veći broj preklapanja po osima.

Sva ispitivanja su provedena na sljedećem računalu:

Intel® Core(TM) 2 Duo E6550 2x2.33 GHz
ATI Radeon HD3870, 512MB GDDR3
2GB DDR2 RAM, 800 MHz

Korištene su dvije vrste rasporeda objekata na sceni. Kod slučajnog rasporeda (slika 8) kao izvor objekata se koristi kocka duljine stranice 2.0 unutar koje se generiraju objekti. Za objekte unutar kocke ne postoje druga ograničenja gibanja.

Slika 8. Slučajan raspored objekata.

Kod drugog, "FER" rasporeda objekta (slika 9), objekti su raspoređeni tako da nakon nekog vremena oblikuju slova "F" "E" i "R". To je postignuto pomoću četiri izvora objekta te nekoliko prepreka. Izvor koji sve omeđuje je ponovo kocka duljine stranice 2.0. Ostala 3 izvora čine dijelove slova "F" "E" i "R". Njihovim brisanjem iz liste, objekti mogu oblikovati slova "F" "E" i "R".

Slika 9. "FER" raspored objekata.

Slučajan raspored objekata

Slika 10. Graf zavisnosti brzine iscrtavanja i broja objekata (svi objekti).

Slika 11. Graf zavisnosti brzine iscrtavanja i broja objekata (1000 do 5000 objekata).

Iz slika 10 i 11 se može vidjeti da klasična metoda detekcije sudara pokazuje konstantno najlošije performanse, tj. najmanji broj iscrtanih slika u sekundi.

Kod slučajnog rasporeda objekata BSP stablo i samo-podesivo BSP stablo pokazuju vrlo slične performanse. Zbog slučajnog, prilično jednolikog rasporeda objekata, prilagodljivost samo-podesivog BSP stabla ne dolazi do izražaja i to stablo pokazuje (zanemarivo) lošije performanse od standardnog BSP stabla, zbog čestog evaluiranja balansiranosti čvorova.

Algoritam brojenja parova i pojednostavljivanja do 500 objekata pokazuje najbolje performanse, jer zbog male gustoće objekata na sceni te malo preklapanja projekcija objekata po osima, nije potrebno raditi puno stvarnih testova kolizije. Pri većem broju objekata raste broj preklapanja i broj testova kolizije te se performanse te metode pri većem broju objekata približavaju klasičnoj metodi.

Povećanje brzine iscrtavanja kod samo-podesivog i standardnog BSP stabla vidljivo kod 250, 500, 1000, 2000 i 4000 objekata (kao ravni ili blago rastući segment) je posljedica povećanja dubine stabla kod tog broja objekata. Povećanje dubine stabla se kod tih vrijednosti radi, kako bi broj objekata u svakom listu bio manji od 30 (kod idealnog rasporeda objekata na sceni).

"FER" raspored objekata

Slika 12. Graf zavisnosti brzine iscrtavanja i broja objekata (svi objekti).

Slika 13. Graf zavisnosti brzine iscrtavanja i broja objekata (300 do 1000 objekata).

Slika 14. Graf zavisnosti brzine iscrtavanja i broja objekata (1000 do 5000 objekata).

Sa slika 12-14. se može vidjeti da kod "FER" rasporeda objekata samo-podesivo BSP stablo pokazuje bolje performanse od standardnog BSP stabla i to od povećanja dubine stabla kod 250 objekata, pa sve do kraja simulacije. To je posljedica prilagodljivosti samo-podesivog BSP stabla različitom rasporedu objekata na sceni. Standardno BSP stablo ne mijenja svoj početni oblik pri novom rasporedu objekata, no samo-podesivo BSP stablo mijenja svoj oblik i pokušava svakim listom obuhvatiti jednak broj objekata. Zbog toga je negativan utjecaj neuniformnog rasporeda objekata na brzinu iscrtavanja mnogo veći kod standardnog BSP stablo, no što je kod samo-podesivog BSP stablo. Do 250 objekata dubina stabla nije dovoljna da samo-podesivo BSP stablo znatno bolje podijelilo objekte unutar scene od standardnog BSP stabla.

Algoritam brojenja parova i pojednostavljivanja pri "FER" rasporedu objekata ponovo pri manjem broju objekata (do 500) pokazuje najbolje performanse zbog male gustoće objekata na sceni. Kod 1000 objekata na sceni performanse algoritma padaju ispod performansi standardnog BSP stabla (slika 13), a do kraja simulacije se približavaju klasičnoj metodi (slika 14).

Utjecaj različitog broja trokuta i sjenčanja

Simulacije su pokazale da četverostruko povećanje broja trokuta na sceni rezultira smanjenjem brzine iscrtavanja za približno 66%, dok uključivanje sjenčanja smanjuje brzinu iscrtavanja za približno 40%. Rezultati i detaljniji opis tih ispitavanja se mogu naći u tekstu diplomskog rada.

Primjeri izgleda BSP stabala

U ovom dijelu se može vidjeti nekoliko scena te uz njih i prikaz standardnog te samo-podesivog BSP stabla. Za prikaz ravnina podjele koristi se crvena (y-z ravnina podjele), zelena (x-z ravnina) i plava boja (x-y ravnina) uz korištenje prozirnosti (eng. Alpha blending).