Binary space partitioning

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Binary space partitioning, BSPalgorytm 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Tworzenie drzewa[edytuj | edytuj kod]

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

  1. A jest korzeniem drzewa i całym złożonym obiektem;
  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ą figurami wypukłymi, czyli stają się liśćmi.
Binary space partition.png

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.

BSP tree-example.svg

Zalety i wady BSP[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

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.

Linki zewnętrzne[edytuj | edytuj kod]