Drzewa BSP

Co to jest Drzewo BSP?

Drzewo Binarnego Podziału Przestrzeni (BSP Tree) jest strukturą danych wykorzystywaną do organizacji obiektów w przestrzeni. W dziedzinie grafiki komputerowej stosuje się je do usuwania powierzchni niewidocznych oraz w metodzie śledzenia promieni. Drzewo BSP jest rekursywnym podziałem przestrzeni, który traktuje każdy odcinek (lub wielokąt w przestrzeni 3D) jako płaszczyznę tnącą służącą do segregacji wszystkich pozostałych obiektów przestrzeni jako będących “z przodu” lub “z tyłu” płaszczyzny. Innymi słowy, kiedy segment jest dodawany do drzewa najpierw klasyfikowany jest względem korzenia drzewa a następnie względem odpowiedniego potomka. Więcej informacji nt drzew BSP znajduje się pod adresem BSP Tree FAQ.


Niestety twoja przeglądarka nie obsługuje apletów Javy.

Jak używać tego apletu?

Możesz rysować odcinki w lewym górnym oknie (po narysowaniu pierwszego odcinka Java przeprowadza inicjalizację, więc jego narysowanie trwa dłużej niż kolejnych odcinków). Odcinki są kolejno numerowane a każdy odcinek dodawany jest do drzewa według tej kolejności. Jeśli segment musi zostać podzielony to do nazwy przedniej i tylnej jego części dodawana jest odpowiednio litera “f” oraz “b”. Na przykład jeśli segment 1 przecinany jest przez płaszczyznę utworzoną na podstawie segmentu 0, to część segmentu 1, która leży z przodu tej płaszczyzny będzie nazwana “1f” a część leżąca z tyłu “1b”.

Możesz zmieniać położenie obserwatora (zaznaczonego punktem w kolorze megenta) przy użyciu myszy (kliknij i przeciągnij punkt). Kliknięcie i przesunięcie grotu strzałki wektora wskazującego kierunek patrzenia spowoduje obrócenie kamery w okienku z widokiem pseudo-trójwymiarowym sceny. W trybie kierowcy (drive mode) wektor kierunku patrzenia wskazuje w kierunku, w którym przesuwasz obserwatora. Położenie obserwatora zaznaczone jest na grafie drzewa punktem w kolorze magenta.

Jeśli czas reakcji jest zbyt długi w trakcie przesuwania odcinków wyłącz tryb interaktywny apletu przełącznikiem “interactive”. W trybie nieinteraktywnym, gdy przesuwamy segment, drzewo BSP jest przebudowywane tylko po zwolnieniu przycisku myszy.

Jeśli drzewo staje się zbyt duże do narysowania w oknie kliknij i przeciągnij je aby zobaczyć jego pozostałe fragmenty.

BSP Tree FAQ (Najczęściej Zadawane Pytania).

Strona została przetłumaczona przez Krzysztofa Szydłowskiego, studenta informatyki Uniwersytetu Śląskiego.