Binarna podela prostora
| Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
U računarstvu, binarna podela prostora (BSP) je metod za rekurzivnu podelu prostora.
Ova podela dovodi do predstavljanja objekata unutar prostora putem strukture stabla podataka, poznate kao BSP stablo.
Binarna podela prostora je razvijena u kontekstu 3D kompjuterske grafike, gde BSP struktura stabla omogućava brzo pristupanje informacijama o objektima.
Pregled
уредиBinarna podela prostora je generički proces rekurzivne podele na dva dela dok deljenje zadovoljava jedan ili više uslova. Može se posmatrati kao generalizacija drugih prostornih struktura stabla. Specifičan izbor plana i kriterijuma zavisi od svrhe BSP stabla.
Na primer, u kompjuterskom grafickočkom prikazivanju, scena se deli dok svaki čvor u BSP stablu sadrži samo poligone koji se prikazuju u
proizvoljnom redosledu.
BSP stabla često koriste 3D video igre.
Generisanje
уредиOsnovna upotreba BSP stabla je za prikazivanje poligona (koji su dvostrani). Svaki poligon koji bi mogao biti proizvoljno izabran je odredjen prvom i drugom stranom.
Takvo drvo je konstruisano od nesortirane liste svih poligona.
Rekurzivni algoritam za izradu BSP stabla od te liste poligona je:
1. Izabrati poligon P sa liste.
2. Napraviti čvor N u BSP stablu i dodati P na listu poligona u tom čvoru.
1) Ako je taj poligon ceo ispred ravni koja sadrži P, pomerite taj poligon na listu čvorova ispred P.
2) Ako je taj poligon ceo iza ravni koja sadrži P, pomerite taj poligon na listu čvorova iza P.
3) Ako taj poligon preseca ravan koja sadrži P, podelite ga na dva poligona i pomerite ih na odgovarajućim listama poligona
ispred i iza P.
4)Ako taj poligon leži u ravni koja sadrži P, dodajte ga na listu poligona u čvor N.
4. Primenite ovaj algoritam na listu poligona ispred P.
5. Primenite ovaj algoritam na listu poligona iza P.
Sledeći dijagram ilustruje korišćenje ovog algoritma u konvertovanju liste linija ili poligona u BSP stablo.
| Počnite sa listom linija (ili u 3D, poligona) koje čine scenu. U dijagramima stabala, liste se označavaju zaobljenim pravougaonicima i čvorovi u BSP stablu krugovima. U prostornom dijagramu linija, pravac linije se označava strelicom. | 
| |
| i. | Prateći korake algoritma
|
|
| ii. | Primenjujemo algoritam na listu linija ispred A (B2, C2, D2). Izaberemo liniiju, B2, dodajemo je u čvor i delimo ostatak liste u one linije koje su ispred B2 (D2), i one koje su iza (C2, D3). | 
|
| iii. | Izaberite liniju, D2, sa liste linija ispred B2. To je jedina linija na listi, tako da nakon što je dodamo u čvor, ništa više ne treba da se uradi. | 
|
| iv. | Obradili smo linije ispred B2, pa prelazimo na linije iza (C2 i D3). Izaberemo jednu od njih (C2), dodamo je u čvor i stavimo drugu liniju (D3) u listu linija ispred C2. | 
|
| v. | Sada pogledamo listu linija ispred C2. Postoji samo jedna linija (D3), tako da je dodajemo u čvor i nastavljamo. | 
|
| vi. | Sada smo dodali sve linije ispred A na BSP stablo, počinjemo sa listom linija iza A. Biramo liniju (B1) sa ove liste, dodajemo B1 u čvor i delimo ostatak liste u linije ispred B1 (D1) i linije iza B1 (C1). | 
|
| vii. | Obradjujemo prvu listu linija ispred B1, D1 je jedina linija na ovoj listi, tako da je dodajemo u čvor i nastavljamo. | 
|
| viii. | Gledajući sledeće na listi linija iza B1, jedina linija na ovoj listi je C1, dodamo je u čvor i BSP stablo je završeno. | 
|
Konačan broj poligona ili linija u drvetu je često veći od originalnog spiska, jer poligoni ili linije moraju da se podele na dva dela. Poželjno je da se minimizira ovaj porast, ali i da se održi razuman bilans u krajnjem drvetu. Stoga je važan izbor poligona (u prvom koraku algoritma) za stvaranje efikasnog BSP stabla.
Reference
уреди