BSP-Puut

Mikä on BSP-puu?

Binäärinen avaruudenlohkomispuu (tai BSP-puu) on tietorakenne, jota käytetään objektien järjestelyyn avaruudessa. Tietokonegrafiikan alueella sillä on sovelluksia mm. näkymättömien pintojen poistossa ja raytracingissa. BSP-puu on rekursiivinen tilan alajaostus, joka kohtelee jokaista janaa (tai polygonia 3D:ssä) leikkaustasona, jota käytetään lajittelemaan kaikki jäljelle jäävät objektit avaruudessa tason edessä oleviin ja takana oleviin. Toisin sanoen, kun jana on lisätty puuhun, se on ensin järjestelty juuri solmun arvon mukaan ja sitten rekursiivisesti jokaisen asianmukaisen haaran arvon mukaan. Jos haluat lisää tietoa BSP-puista, lue BSP Tree FAQ.


Selaimesi ei tue Java appletteja.

Kuinka käytän tätä applettia?

Voit piirtää janoja ensimmäiseen ruutuun (kun ensimmäinen jana piirretään, Java suorittaa joitain alustuksia, joten piirtämiseen menee enemmän aikaa). Janat ovat numeroitu järjestyksessä, ja puu on rakennettu lisäämällä kukin jana numeroidussa järjestyksessä. Jos jana täytyy halkaista, lohkonnan etu-ja takaosat saavat nimeensä liitteet “f” ja “b”. Esimerkiksi, jos jana 1 ylittää leikkaavan tason jonka jana 0 on muodostanut, silloin se osa jana 1:stä joka on jana 0:n edessä nimetään “1f”:ksi, ja takana sijaitseva osa nimetään “1b”:ksi.

Voit liikuttaa nuolta vetämällä sitä. Jos vedät nuolenpäätä lähellä katselukohdan vektorin loppua, voit pyörittää kameraa, mikä luo näennäis-3D-kentän.

Jos vasteaika on liian pieni kun liikutat janoja, vaihda “interactive”-valitsin pois päältä, jotta saat appletin vuorovaikutteisuuden pois. Ei-vuorovaikutteisessa tilassa BSP-puu uudelleenrakennetaan vain, kun jana on liikutettu uuteen paikkaan ja hiirennäppäin on vapautettu.

Jos puu kasvaa liian suureksi mahtuakseen ruutuun, klikkaa ja vedä puuta liikuttaaksesi sitä ympäriinsä ruudussaan.

Mistä voin löytää lisää tietoja BSP-puista?

Luultavasti paras paikka, josta voisi etsiä lisätietoja BSP-puusta on BSP Tree FAQ.

Tämän sivun suomensi Henrik Erkkila.
Suomennoksen korjasi oikeakieliseksi Juuso Takalainen.