Hvad er et BSP Træ?

Et ‘Binary Space Partitioning’ træ (eller BSP træ) er en datastruktur, som er brugt til at organisere objekter i et rum. Indenfor computergrafik-verdenen bruges det i ‘hidden surface removal’ og ray tracing. Et BSP træ er en rekursiv underinddeling af et rum, som ser hvert liniesegment (eller polygon i 3D) som en skære-flade, som bruges til at kategorisere de resterende objekter i rummet som enten at være “for” eller “bag” fladen. Med andre ord, når en partition indsættes i træet, bliver det først kategoriseret i henhold til roden af træet, og derefter rekursivt i henhold til hvert barn. For mere information omkring BSP træer, se BSP Træ FAQ’en.

Undskyld, men din browser lader ikke til at understøtte java applets.

Hvordan bruger jeg denne applet?

Du kan tegne liniesegmenter i det første vindue (den første linie tager noget længere tid end de efterfølgende, da java laver en del initialisering). Segmenterne numereres i rækkefølge og træet er bygget ved at indsætte hvert segment i numerisk rækkefølge. Hvis en partition skal splittes, lægges “f” og “b” til navnene for for- og bagdelen af partitionen respektivt. For eksempel, hvis partition 1 krydser skære-fladen lavet af partition 0, så vil den part af partition 1 som er foran partition 0 få navnet “1f” og den del der ligger bag vil få navnet “1b”.

Du kan flytte den magentarøde pil ved at klikke og trække den, og hvis du gør det samme med hovedet af pilen, kan du rotere kamera vinklen.

Hvis tegningen af træet bliver for stort for vinduet, klik og træk indenfor vinduet for at flytte rundt på træet.

Mere information om BSP Træer

Det bedste sted at finde information omkring BSP træer er sandsynligvis i BSP Træ FAQ’en.

Denne side blev oversat til dansk af Henrik Gram.