BSP Trær

Hva er et BSP Tre?

Et "Binary Space Partitioning Tree" ( "Binært Rom Partisjonerings Tre", eller BSP Tre) er en datastruktur som blir brukt til å organisere objekter innenfor et 3-dimensjonellt rom. Innenfor datagrafikk-feltet er det anvendelig for å fjerne overlappende overflater og ray tracing. Et BSP tre er en rekursiv under-indeling av rommet som behandler hvert linjesegment (eller polygon, i 3D) som et skjærende plan som brukes til å kategorisere alle gjenværende objekter til å enten være "foran" eller "bak" dette planet. Med andre ord, når en partisjon settes inn i treet, blir det først kategorisert i forhold til rot noden, og deretter rekursivt i forhold til hver gjeldene barn node. For mer informasjon om BSP trær, se BSP Tre FAQ’en.


Sorry, your browser does not support Java applets.

Hvordan du bruker appleten

Du kan tegne linjesegmenter i den første ruten (når du tegner den føste linjen tar den litt lengre tid enn de påfølgende, siden Java må foreta en del initialisering.). Segmenter er nummererte, og treet bygges ved å sette inn segmentene sekvensiellt. Hvis en partisjon må deles, får forrerste og bakerste partisjon en "f" og en "b" bak sine respektive navn. For eksempel, hvis partisjon 1 krysser planet definert av partisjon 0, så blir den delen av partisjon 1 som er foran partisjon 0 benevnt "1f", og den delen som er bak blir benevnt "1b".

Du kan flytte det magenta-fargede øyepunktet ved å klikke og dra det, og hvis du klikker og drar i nærheten av pilspissen på øyepunktets syns-vektor, kan du rotere kameraet som ser på pseudo-3D scenen. I "drive" modus peker syns-vektoren i den retningen du beveger øyepunktet. BSP tre klassifiseringen av øyepunktet vises som en magenta-farget prikk i BSP tre grafen.

Hvis respons tiden er for lang når du flytter linjesegmenter, skru av "interactive" checkboksen for å kjøre i ikke-interaktiv modus. I ikke-interaktiv modus blir ikke BSP treet gjennoppbygd før et linjesegment har blitt flyttet til et nytt sted og museknappen slippes opp.

Hvis tegningen av treet blir for stor for ruten, klikk og dra for å panorere over treet.

Klikk her for BSP tree FAQ’en.

Denne siden blev oversatt til norsk av Erik Berglund.