Oktalno stablo

Oktalno stablo (eng. Octree) je hijerarhijska struktura podataka kod koje svaki čvor ima do osmero djece. Oktalno stablo se najčešće koristi za podjelu 3D prostora gdje se prostor rekurzivno dijeli na osam oktanata tj. čvorova. Svaki čvor u stablu predstavlja dio prostora, čvorovi bez djece su listovi i oni sadrže podatke o tome što se nalazi u tome dijelu prostora (npr. vrhovi, poligoni, ...).

Slika 1: Prikaz oktalnog stabla u 3D prostoru i pripadajuće strukture

Oktalno stablo stvara se na temelju ulaznog modela, točnije njegovih vrhova, bridova i poligona. Domena koja obuhvaća geometriju modela je sadržana u korijenu oktalnog stabla. Taj korijenski čvor se zatim rekurzivno dijeli na osam djece-oktanata dok se ne dobije željena rezolucija oktalnog stabla. Tijekom dijeljenja tj. rafiniranja pojedinog oktanta on sadrži informacije o vrhovima, bridovima i poligonima koji su unutar njega. Ako neki poligon presijeca više oktanata informacija o tome će biti spremljena u svaki od tih oktanata. Svaki rafinirani oktant još sadrži informaciju o svom roditelju i djeci što omogućuje vertikalno kretanje po stablu u oba smjera. Na slici 1 prikazan je primjer oktalnog stabla. Svaki čvor u oktalnom stablu predstavlja jedan oktant u prostoru.

Korijen oktalnog stabla je poravnat sa koordinatnim osima, a time su i svi oktanti rezultirajućeg oktalnog stabla poravnati sa koordinatim osima. Time se pojednostavljuje određivanje koji element modela je u kojem oktantu i ubrzava se generiranje oktalnog stabla.

Listovi oktalnog stabla su oni oktanti koji se više ne dijele i oni sadrže informacije o elementima unutar njega. Na temelju listova se zatim stvara računska mreža, tako da rezolucija oktalnog stabla određuje konačnu distribuciju veličine ćelija.

Svaki list oktalnog stabla je klasificiran u jednu od ove tri kategorije:

• vanjski list - predstavlja oktant koji se nalazi izvan modela
• unutarnji list - predstavlja oktant koji se nalazi unutar modela
• podatkovni ili granični list - predstavlja oktant koji se nalazi na granici modela i sadrži podatke o elementima unutar tog oktanta

Potpuno oktalno stablo

Oktalno stablo koje se širi u svim smjerovima se naziva potpuno oktalno stablo, tj. to je stablo kod kojeg se svi oktanti rafiniraju do neke zadane razine. Za potpuno oktalno stablo moguće je izračunati broj čvorova na pojedinoj razini s time da je početna razina nula, tj. korijen stabla je na nultoj razini:

tj.

gdje su:
n - broj čvorova na pojedinoj razini,
k - razina za koju se računa broj čvorova

Moguće je i izračunati i ukupni broj čvorova u stablu:

gdje su:
N - ukupan broj čvorova u oktalnom stablu,
d - dubina oktalnog stabla

Prednost potpunog oktalnog stabla je to što se adresa svakog čvora može izračunati na temelju njene pozicije u stablu tj. može napraviti bez spremanja pokazivača, ali kod veće dubine stabla taj dobitak postaje nevažan. Nedostatak potpunog stabla je veliko zauzeće memorije, npr. za 10 razina broj čvorova je 153391689. Drugi nedostatak je taj što će većina tih čvorova, tj. pripadajućih oktanata će biti prazna.

Oktalno stablo koje se grana prema potrebi (Branch-on-need)

Oktalno stablo kod kojeg se pojedini čvorovi dijele prema potrebi, tj. ako je neki kriterij zadovoljen za razliku od potpunog stabla kod kojeg se dijele svi čvorovi do određene razine, npr. ako je broj elemenata unutar oktanta veći od nekog zadanog broja. Ovo će rezultirati neuniformnom raspodjelom oktanata, tj. neki oktanti će biti veći, a neki manji.

Budući da je većina prostora kojeg model zauzima prazan, tj. ne sadrži nikakve informacije, ovakva struktura je vrlo ekonomična u potrošnji memorije u usporedbi sa potpunim oktalnim stablom.

Balansiranje oktalnog stabla

Kako je već rečeno kod oktalnog stabla koje se grana prema potrebi oktanti će biti različitih veličina, a time će i razlika među veličinama susjednih oktanata biti velika. Radi toga će potraga za susjednim oktantima biti kompleksnija i vremenski zahtjevnija. Da bi se to izbjeglo na oktalnom stablu se obavlja balansiranje. Balansiranje je dodatno rafiniranje onih susjednih oktanata koji su udaljeni više od jedne razine u oktalnom stablu, tj. oni među kojima je razlika između razina rafiniranosti veća od jedan, to se još zove kriterij razlike od maksimalno jedne razine. Time se osigurava da je susjedni oktant maksimalno dvostruko veći ili dvostruko manji što rezultira sa ove dvije posljedice:

1. smanjuje se broj potencijalnih susjeda jer onda oktant po svakoj stranici može imati maksimalno četiri susjedna oktanta, a time se ubrzava potraga za susjednim oktanima
2. postiže se glađi prijelaz u rezoluciji tj. glađu promjenu veličine između susjednih oktanata

Na slici 2 prikazan je primjer balansiranja oktalnog stabla, prikazano je nekoliko koraka rafiniranja. Na prikazu:

1. imamo neko početno stablo koje je već jednom rafinirano
2. odabran je jedan oktant za daljnje rafiniranje, crveni oktanti su oni oktanti koji će se u sljedećem koraku rafinirati, na prikazu
3. rezultat rafiniranja odabranog oktanta
4. isto kao i pod b.
5. isto kao i pod c.
6. odabir oktanta za rafiniranje kojem je jedan susjeda dva puta veći
7. dolazi do balansiranja gdje se dodatno rafiniraju i oni oktanti koji nisu eksplicitno odabrani za daljnje rafiniranje.

Slika 2: Balansiranje oktalnog stabla

Na prikazu f) se vidi da je došlo do rafiniranja oktanta koji nije bio direktan susjed odabranom oktantu. To znači da kod balansiranja može doći do efekta širenja valova (eng. ripple effect) kod kojeg će se dodatno rafinirati svi oktanti u stablu koji ne zadovoljavaju kriterij razlike od maksimalno jedne razine.

Generiranje oktalnog stabla

Kao što je već rečeno oktalno stablo se gradi na temelju ulaznog modela ili scene. Sam model se sastoji od niza vrhova, poligona i bridova. Vrhovi predstavljaju pozicije u trodimenzionalnom prostoru, a bridovi i poligoni (trokuti, četverokuti, ...) govore kako su ti vrhovi spojeni. Zajedno čine mrežu koja predstavlja neko tijelo iz stvarnog svijeta u računalu. Sam model je iznutra šupalj, tj. ne sadrži ništa, dok bi u stvarnom svijetu mogao biti i popunjen, npr. model Zemlje. Na slici 3 je prikazan jedan model dijela ispušnog sustava automobila za koji će se generirati oktalno stablo. Taj model se sastoji od 8804 vrhova i 17604 poligona. Prije samog generiranja odabiru se ulazni parametri npr. minimalna i maksimalna dubina stabla, maksimalni broj elementa koji oktant smije sadržavati itd.

Slika 3: Primjer modela za koji se generira oktalno stablo

Na slici 4 su prikazani podatkovni (granični) listovi generiranog stabla tj. oni koji sadrže barem jedan element modela na temelju kojeg je oktalno stablo izgrađeno. Mogli bi se prikazati i svi oktanti, ali to ne bi bilo pregledno niti bi imalo smisla. Na slici se vidi da podatkovni oktanti prikazuju osnovni oblik početnog modela iako je dubina generiranog stabla mala, u ovom slučaju dubina stabla je 4 razine.

Slika 4: Listovi oktalnog stabla koji sadrže poligone

Na slici 5 je prikazana mreža bridova generiranog stabla na kojoj se bolje vidi model i generirano oktalno stablo. Kao što se vidi iz slike oktalno stablo aproksimira ulazni model. Ta aproksimacija je sve točnija što je dubina oktalnog stabla veća. U ovom primjeru oktant s najmanjim brojem objekata sadrži 1 poligon i 0 vrhova, oktant s najvećim brojem objekata sadrži 295 poligona i 125 vrhova, prosječan broj poligona po podatkovnom oktantu je 86.97, a vrhova 31.22, ako se uzmu u obzir svi listovi prosječan broj poligona po oktantu je 5.99, a vrhova 2.15.

Slika 5: Prikaz mreže bridova oktalnog stabla

Primjene oktalnog stabla

Oktalno stablo u računalnoj grafici ima više primjena. One se uglavnom odnose na podjelu prostora, a time i podjelu modela na manje dijelove. Time se smanjuje broj proračuna i ubrzava algoritam koji se koristi jer se ne treba ispitivati sve na sceni nego samo određeni dijelovi. Osim kod ubrzavanja izvođenja proračuna kod simulacije oktalno stablo primjenjivo je u postupku praćenja zrake, kod problema uklanjanja dijelova objekata obzirom na volumen pogleda, detekcije kolizije i u drugim područjima.