Binary space partitioning
Binary space partitioning, BSP – algorytm polegający na rekurencyjnym dzieleniu danej przestrzeni na coraz mniejsze fragmenty. Powstaje wówczas struktura zwana drzewem BSP (ang. BSP tree).
Obliczanie widoczności
Obliczanie widoczności odbywa się na zasadzie sprawdzania, po której stronie płaszczyzny danego wierzchołka znajduje się kamera (obserwator). Na tej podstawie wybierany jest lewy lub prawy syn wierzchołka (bardziej odpowiednie jest określenie przedni lub tylny syn), który sam zawiera swoją płaszczyznę podziału i dwóch synów określających obiekty będące z przodu lub z tyłu tej płaszczyzny. Ostatnim synem jest liść, który zawiera właściwą geometrię do wyświetlenia. Dzięki temu szybko odrzucana jest znaczna część niewidocznych obiektów.
Po wybraniu liścia często następuje sprawdzanie jakie inne liście są z niego widoczne. Najczęściej dzieje się to przy użyciu portable visibility sets czyli pola bitowego, którego poszczególne bity określają po kolei widoczność każdego liścia. Bit określający widoczność samego siebie ma zawsze wartość 1.
Inne zastosowania
- opisywanie wielokątów, nawet wielokątów "z dziurami" - umożliwia szybsze stwierdzenie czy punkt leży wewnątrz/na zewnątrz figury, co jest wykorzystywane m.in. w zadaniach interakcji z użytkownikiem w programach graficznych;
- opisywanie brył zbudowanych z siatek wielokątów - jednym z zastosowań jest wykonywanie na bryłach geometrycznych operacji boolowskich: suma, część wspólna, różnica (patrz: CSG);
- opisywanie całych scen trójwymiarowych - łatwiejsza detekcja kolizji (istotne w grach komputerowych), łatwiejsze śledzenie promieni oraz usuwanie niewidocznych powierzchni.
Generacja drzewa
2. A jest dzielone na B i C
3. B jest dzielone na D i E
4. D jest dzielone na F i G, które są wypukłe, czyli stają się liśćmi
Na rysunku powyżej pokazano, w jaki sposób tworzone jest drzewo BSP opisujące wielokąt wklęsły. Widać, że dwie krawędzie musiały zostać podzielone (e-d, f-g). W tym przykładzie proste dzielące pokrywają się z krawędziami figury (tak jest najczęściej). Czarne kwadraciki oznaczają puste poddrzewo.
Zalety i wady BSP
BSP jest algorytmem bardzo szybkim i często stosowanym, szczególnie w grach komputerowych. Wadą BSP jest nieumiejętny podział otwartego świata 3D, dlatego jest zwykle wykorzystywany dla zamkniętych obszarów. Dla otwartych przestrzeni lepszym rozwiązaniem jest użycie drzewa ósemkowego (octree).
Drzewo BSP nie nadają się do opisu dynamicznych scen, gdzie obiekty przemieszają się, są dodawane lub usuwane. Często jednak są stosowane rozwiązania hybrydowe - jeśli statyczna część sceny jest duża, wówczas jest ona opisywana za pomocą drzewa BSP, natomiast części ruchome (np. drzwi budynków, ściany które mogą zostać usunięte) przechowywane są w jakiś inny sposób.
Zobacz też
Inne struktury podziału przestrzennego:
- drzewo kd – przestrzeń jest dzielona przez płaszczyzny równoległe do głównych płaszczyzn układu współrzędnych (XY, YZ, XZ)
- drzewo ósemkowe – przestrzeń jest dzielona na jednakowe sześciany (prostopadłościany)
- drzewo BVH – przestrzeń jest dzielona (lub współdzielona) na prostopadłościany różnej wielkości.