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. Example of BSP tree construction - step 1.svg
i. Prateći korake algoritma
  1. Biramo liniju, A, sa liste...
  2. ...i dodajemo je u čvor
  3. Podelimo preostale linije u listi u one ispred A ( B2, C2, D2), i one iza (B1, C1, D1).
  4. Prvo obradimo linije ispred A (koracima ii-v)
  5. ... zatim one iza (koracima vi–vii).
Example of BSP tree construction - step 2.svg
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). Example of BSP tree construction - step 3.svg
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. Example of BSP tree construction - step 4.svg
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. Example of BSP tree construction - step 5.svg
v. Sada pogledamo listu linija ispred C2. Postoji samo jedna linija (D3), tako da je dodajemo u čvor i nastavljamo. Example of BSP tree construction - step 6.svg
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). Example of BSP tree construction - step 7.svg
vii. Obradjujemo prvu listu linija ispred B1, D1 je jedina linija na ovoj listi, tako da je dodajemo u čvor i nastavljamo. Example of BSP tree construction - step 8.svg
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. Example of BSP tree construction - step 9.svg

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[уреди]


Spoljašnje veze[уреди]