KONSTRUKTIVNA GEOMETRIJA
SA SLOBODNO OBLIKOVANIM OBJEKTIMA

Konstruiranje oktalnog stabla

 Oktalno stablo (engl. octree) je vrlo često korištena struktura u računalnoj grafici. Razlog popularnosti oktalnog stabla je u tome što na relativno jednostavan način omogućava znatna ubrzanja mnogih algoritama zahvaljujući svojstvu grupiranja objekata sličnih odabranih karakteristika. Oktalno stablo je struktura koja prostor od određenog interesa dijeli u manje dijelove. Obično se može zamisliti kao kocka koja se sastoji od osam manjih kocki-djece, koje se opet sastoje od manjih kocki i tako dalje sve do zadane dubine. Struktura je stablo, te svaki čvor ima pokazivač na oktalna stabla-djecu.

Gradnja počinje korijenom stabla koji je obujmica promatranog tijela i sadrži sve elemente površine tijela. Dalje se prostor dijeli na osam jednako velikih kocki-djece rekurzivno za svaki čvor sve dok sadrži elemente površine u prostoru koji obuhvaća ili je dostignuta zadana dubina rekurzije.  

Klasifikacija oktalnog stabla

Nakon što je izgrađeno oktalno stablo, potrebno je klasificirati njegove ćelije i to u tri moguće kategorije: vanjske, unutarnje i granične. Granične ćelije su sve one koje sadrže elemente površine. Ćelije koje su unutarnje i vanjske su uvijek prazne ćelije. Postavlja se pitanje kako odrediti što brže i što efikasnije koje su od tih ćelija unutarnje, a koje vanjske. Na određenoj razini, čvor u stablu ima osam ćelija od kojih svaka ima susjeda na svakoj od tri glavne osi. Kada želimo odrediti za praznu ćeliju je li unutar ili izvan tijela, gledati ćemo jednu od njoj susjednih ćelija. Moguća su tri različita slučaja:

• prazna ćelija ima jednu nepraznu susjednu ćeliju,

• prazna ćelija ima više nepraznih susjednih ćelija (najviše tri),

• prazna ćelija nema nepraznih susjednih ćelija.

Ako prazna ćelija ima jednu nepraznu susjednu ćeliju tada se klasifikacija vrši promatranjem elemenata površine te neprazne ćelije. Ako ima više nepraznih susjednih ćelija uzima se bilo koja od njih za promatranje kod klasifikacije (poput prvog slučaja).

 Ukoliko prazna ćelija nema nepraznih susjednih ćelija, potrebno je prvo klasificirati susjedne ćelije, a onda vrijednost dobivenu za njih pridijeliti i promatranoj praznoj ćeliji jer su dvije susjedne prazne ćelije uvijek ili unutar ili izvan tijela.Kada se želi klasificirati ćeliju na osnovu neprazne susjedne ćelije, promatraju se orijentacije (normale) elemenata površine u nepraznoj ćeliji. Orijentacija elementa površine koji je najbliži praznoj ćeliji određuje je li ta ćelija s unutarnje ili vanjske strane. 

Klasifikacija stabla počinje sa ćelijama na najvećoj dubini oktalnog stabla. Uz označene granične ćelije lako se klasificiraju sve susjedne prazne ćelije. Slijedi klasifikacija ćelija sljedeće više razine i tako sve do vrha stabla kako prikazuje slika.