BSP stablo
BSP stablo (eng. Binary Space Partitioning tree) je struktura podataka koja predstavlja rekurzivnu, hijerarhijsku podjelu n-dimenzionalnog prostora u konveksne skupove (dijelove). Konveksni skup je skup poligona takav da je svaki poligon ispred svakog drugog poligona u tom skupu. Poligon je ispred nekog poligona ako su svi njegovi vrhovi sa pozitivne strane tog poligona. Na slici 6 su prikazani konveksni i nekonveksni skupovi.
Slika 6: Lijevo je prikazan konveksni skup, a desno nekonveksni skup
BSP stablo je binarno stablo koje se koristi za sortiranje i pretragu n-dimenzionalnog prostora. Ako BSP stablo gledamo kao cjelinu ono predstavlja cijeli prostor (scenu, domenu), a svaki čvor u stablu sadrži jednu "hiper-ravninu" koja dijeli prostor koji taj čvor predstavlja na dva dijela. Kod n-dimenzionalnog prostora "hiper-ravnina" je n - 1 dimenzionalni objekt koji se može koristiti za podjelu tog prostora na dva polu-prostora. U jednodimenzionalnom prostoru "hiper-ravnina" je točka i dijeli pravac na dva polu-pravca, u dvodimenzionalnom prostoru "hiper-ravnina" je pravac i dijeli ravninu na dvije polu-ravnine, a u trodimenzionalnom prostoru "hiper-ravnina" je ravnina i dijeli prostor na dva polu-prostora. Svaki čvor još dodatno sadrži i dva čvora-djece, prednji koji predstavlja prostor ispred "hiper-ravnine" i stražnji koji predstavlja prostor iza "hiper-ravnine". Dalje se ti dijelovi mogu rekurzivno dijeliti. Na slici 7 je prikazan primjer stvaranja BSP stabla u dvodimenzionalnom prostoru.
Slika 7: Primjer stvaranja BSP stabla u dvodimenzionalnom prostoru
Generiranje BSP stabla
Algoritam za generiranje BSP stabla se sastoji od 3 koraka:
- odaberi ravninu za podjelu prostora
- podijeli skup poligona odabranom ravninom
- rekurzivno prođi kroz algoritam za svaki od dva nova skupa
Odabir ravnine za podjelu prostora ovisi o tome kako će se BSP stablo upotrebljavati. Moguće je odabrati ravninu iz ulaznog skupa poligona ili odabrati ravninu koja je poravnata sa koordinatnim osima. Poželjno je da stablo bude balansirano, tj. da svaki list stabla sadrži približno jednak broj poligona. Ako poligon siječe ravninu podjele podijelit će se na dva ili više dijela. Loš odabir ravnine podjele rezultirat će povećanjem ukupnog broja poligona. Potrebno je naći ravnotežu između balansiranog stabla i velikog broja podjela.
Podjela skupa poligona ravninom radi se tako da se klasificira svaki poligon iz skupa u odnosu na ravninu podjele. Ako je poligon potpuno s jedne strane ravnine onda se on ne modificira i dodaje se u skup strane na kojoj se nalazi. Ako poligon siječe ravninu dijeli se na dva ili više dijela i svaki dio se dodaje u skup strane na kojoj se nalazi. Ako je poligon koincidentan s ravninom, tj. leži na ravnini on se dodaje u jedan od skupova. Poligon se nalazi potpuno na jednoj strani ravnine ako se svi njegovi vrhovi nalaze na jednoj strani ravnine. Ako se neki vrhovi nalaze na jednoj strani ravnine, a drugi na drugoj strani te ravnine, taj poligon siječe ravninu i dijeli se na dva ili više dijela. Ako se svi vrhovi nalaze na ravnini onda se i taj poligon nalazi na ravnini. To je ispred/iza provjera i provodi se za svaki vrh poligona uvrštavanjem koordinata (x, y i z) tog vrha u jednadžbu ravnine:
gdje su:
A, B i C - vektor normale te ravnine
D - pomak ravnine po normali od ishodišta koordinatnog sustava, tj. udaljenost najbliže točke na ravnini od ishodišta koordinatnog sustava
tj. potrebno je izračunati:
ako je s > 0 vrh se nalazi s pozitivne strane (ispred) ravnine, a ako je s < 0 vrh se nalazi s negativne strane (iza) ravnine, a ako je s = 0 vrh se nalazi na ravnini, tj. koincidentan je s ravninom.
Proces se može zaustaviti kada je broj poligona u pojedinom listu manji od nekog zadanog broja, druga mogućnost je zaustavljanje kada je dosegnuta maksimalna dubina stabla.
Primjene BSP stabla
Glavna prednost BSP stabla je to što može sortirati i pretraživati poligone po njihovoj udaljenosti od neke točke. Moguće je pretraživati poligone od nazad prema naprijed (eng. back to front) i od naprijed prema nazad (eng. front to back).
Slikarev algoritam (eng. Painter's algorithm) je način iscrtavanja scene kod kojeg se iscrtavaju objekti počevši od najudaljenijeg od očišta do najbližeg. Skriveni dijelovi objekata (poligoni) će biti precrtani sa onim objektima bliže očištu. Jedini uvjet je da postoje ravnine koje međusobno odvajaju te objekte, tako da je svaki objekt sam u svom dijelu prostora. Na slici 8 su prikazani koraci slikarevog algoritma.
Slika 8: Slikarev algoritam
Ako objekte nije moguće objekte međusobno odvojiti ravninama tako da je svaki objekt u svom dijelu prostora slikarev algoritam neće dati točne rezultate. Na slici 9 je prikazan slučaj cikličkog preklapanja za koji slikarev algoritam neće točno raditi.
Slika 9: Cikličko preklapanje
Da bi slikarev algoritam točno radio potrebno je podijeliti objekte na takav način da ih je moguće iscrtati od najudaljenijeg do najbližeg prema očištu. BSP stablo upravo omogućuje rekurzivan prolaz kroz stablo u smjeru od nazad prema naprijed. Da bi se iscrtao sadržaj BSP stabla slikarevim algoritmom potrebno je proći kroz stablo u smjeru od nazad prema naprijed. Počevši od korijena stabla odrediti gdje je očište u odnosu na ravninu podjele. Zatim iscrtati udaljeniji čvor od očišta, zatim iscrtati poligone u trenutnom čvoru, zatim iscrtati bliži čvor. Sljedeći pseudokod pokazuje prolaz kroz stablo od nazad prema naprijed (back to front).
void Draw_BSP_Tree (BSP_tree *tree, point eye)
{
real result = tree->partition.Classify_Point (eye);
if (result > 0)
{
Draw_BSP_Tree (tree->back, eye);
tree->polygons.Draw_Polygon_List ();
Draw_BSP_Tree (tree->front, eye);
}
else if (result < 0)
{
Draw_BSP_Tree (tree->front, eye);
tree->polygons.Draw_Polygon_List ();
Draw_BSP_Tree (tree->back, eye);
}
else // result is 0
{
// the eye point is on the partition plane...
Draw_BSP_Tree (tree->front, eye);
Draw_BSP_Tree (tree->back, eye);
}
}
Kod praćenja zrake BSP stablo se prolazi od očištu najbližeg do najdaljeg čvora u stablu. To se postiže tako da se u gornjem pseudokodu zamjeni redoslijed rekurzivnog pozivanja pretrage čvora. Tako se osigurava da se prvo provjeri da li je zraka pogodila bliže poligone, a zatim one udaljenije. Kod praćenja zrake nije potrebno dijeliti poligone da bi se dobili točni rezultati, što omogućuje da se ravnine podjele tj. "hiper-ravnine" biraju samo radi balansiranja stabla i smanjuje broj novostvorenih poligona. To omogućuje brže stvaranje BSP stabla i njegovu pretragu.