Binary space partitioning

Binary space partitioning, BSP – algorytm polegający na rekurencyjnym dzieleniu danej przestrzeni na zbiory wypukłe przy pomocy hiperpłaszczyzn. Powstaje wówczas struktura danych zwana drzewem BSP (ang. BSP tree).

Podstawowym zastosowaniem drzew BSP jest określanie porządku (od przodu w tył) obiektów znajdujących się na trójwymiarowej scenie, co jest fundamentalne przy jej renderowaniu realizowanym przez programy do tworzenia grafiki trójwymiarowej. Pozwalają one na znaczne uproszczenie procesu określania widoczności obiektów przez kamerę/obserwatora.

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 wybierane jest lewe lub prawe dziecko wierzchołka (bardziej odpowiednie jest określenie przednie lub tylne dziecko), które samo zawiera swoją płaszczyznę podziału i dwoje dzieci określających obiekty będące z przodu lub z tyłu tej płaszczyzny. Ostatnim dzieckiem 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 wykorzystuje się do tego portable visibility sets, czyli pola bitowe, których 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, czy 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.

Tworzenie drzewa

Proces budowania drzewa BSP do momentu powstania pierwszych liści przedstawia poniższy rysunek:

A jest korzeniem drzewa i całym złożonym obiektem;
A jest dzielone na B i C;
B jest dzielone na D i E;
D jest dzielone na F i G, które są figurami wypukłymi, czyli stają się liśćmi.

Kolejny rysunek pokazuje wielokąt wklęsły, w którym dwie krawędzie musiały zostać podzielone (e-d oraz f-g). W tym przykładzie (i tak jest najczęściej) proste dzielące wielokąt pokrywają się z krawędziami figury; czarne kwadraty natomiast oznaczają puste poddrzewo.

Zalety i wady BSP

BSP jest algorytmem bardzo wydajnym 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 (ang. octree).

Drzewa BSP nie nadają się do opisu dynamicznych scen, gdzie obiekty przemieszczają się, są dodawane lub usuwane. Często jednak stosowane są 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 innej strukturze danych.

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.