BSP-bomen

Was is een BSP-boom?

Een BSP-boom (Binary Space Partitioning Tree) is een datastructuur die gebruikt wordt om objecten ruimtelijk te organiseren. In het domein van computer graphics wordt het gebruikt om niet-zichtbare vlakken te verwijderen (Hidden Surface Removal) en voor Ray Tracing. Een BSP-boom is een recursieve verdeling van een ruimte die ieder lijnsegment (of polygon, in 3D) als een snijvlak beschouwt. Dit vlak wordt dan gebruikt om alle resterende objecten te ordenen in die ruimte: ofwel ligt een object vóór dit snijvlak, ofwel erachter. Met andere woorden: als een lijnsegment wordt toegevoegd, wordt het eerst geordend ten opzichte van de wortel van de boom, en dan op een recursieve wijze ten opzichte van elk kind. Voor meer informatie over BSP-bomen, lees de BSP Tree FAQ.

Sorry, je browser ondersteunt geen Java applets.

Hoe gebruik ik dit applet

Je kan lijnsegmenten tekenen in het eerste paneel (het tekenen van de eerste lijn duurt veel langer dan de volgende lijnen omdat Java in het begin enkele initialisaties uitvoert). De lijnsegmenten zijn genummerd en de boom wordt opgebouwd door elk lijnsegment in numerische volgorde in te voegen. Als een lijnsegment gesplitst moet worden zal aan de naam van de voorkant en achterkant respectievelijk een “f” of een “b” worden toegevoegd. Bijvoorbeeld: als lijnsegment 1 door het snijvlak gaat van lijnsegment 0, dan zal het stuk van lijnsegment 1 dat zich vóór lijnsegment 0 bevindt “1f” heten, en het achterste stuk “1b”.

Je kan het magenta oogpunt (pijltje) verplaatsen door op het bolletje onderaan te klikken en het te verslepen. Als je op het pijlpuntje klikt en het versleept kan je de camera draaien die de pseudo-3D scène weergeeft.

Als bij het verplaatsen van lijnsegmenten het applet te traag reageert, schakel dan de optie “interactive” uit. In deze niet-interactieve modus wordt de BSP-boom alleen heropgebouwd nadat een lijnsegment verplaatst is en de muisknop werd losgelaten.

Als de tekening te groot wordt voor het paneel, klik en sleep dan in het paneel om de andere delen van de boom te kunnen zien.

Meer informatie over BSP-bomen

Waarschijnlijk de beste plek met informatie over BSP-bomen: BSP Tree FAQ.

Deze pagina werd vertaald naar het Nederlands door Alex Pfaffe, met correcties door Bart Greyson.