Binary space partitioning
Zasugerowano, aby zintegrować ten artykuł z artykułem Drzewo BSP (dyskusja). Nie opisano powodu propozycji integracji.
Binary Space Partitioning jest algorytmem obliczania widoczności na podstawie sortowania obiektów 3D w drzewo binarne. 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 okerś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 jest ma zawsze wartość 1.
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).
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