|
Drzewo BSP Autor: Mirosław Kozioł |
|||||||||||||
|
Drzewo BSP 2D (ang. Binary Space Partitioning) Drzewo BSP 2D to nic innego jak zwykłe drzewo binarne służące do podziału przestrzeni 2D. Drzewo BSP 2D było drzewem odcinków które można traktować jako rzuty ścian na powierzchnię 2D. Cała płaska mapa sceny dzielona jest w taki sposób że w końcowym etapie tworzy zamknięte wielokąty czyli sektory. Przykład który przedstawiłem poniżej z uwagi na to że zawiera tylko ściany pionowe (narysowane jako płaskie rzuty) można łatwo zamienić na BSP 2D. Drzewa BSP 2D były prawdopodobnie stosowane w takich grach jak Duke Nukem 3D, Doom, Hexen, Heretic.
Drzewo BSP 3D (and. Binary Space Partitioning) Drzewo BSP 3D to nic innego jak zwykłe drzewo binarne służące do podziału przestrzeni 3D. Drzewa BSP 3D są również wykorzystywane do wykrywania kolizji oraz generacji portali i list PVS. Opis metody portali znajduje się w dziale Portale natomiast drzew PVS w dziale Drzewo PVS.
Przed przystąpieniem do generacji drzewa BSP 3D należy dokonać dekompozycji sceny w celu jej uproszczenia. Polega to na usunięciu elementów skomplikowanych. Podczas tworzenia drzewa BSP 3D cała lokacja dzielona jest na bryły wypukłe czyli sektory. Do podziału sceny wykorzystywane są płaszczyzny na których leżą ściany. Cała scena rozdzielana jest na zbiory ścian leżących przed i za płaszczyzną podziału. Ściany które przecinają płaszczyznę podziału są dzielone tak aby jedna cześć leżała za a druga przed płaszczyzną podziału. Ściany które leżą na płaszczyźnie podziału jeżeli mają taką samą orientację jak płaszczyzna podziału dodawane są do zbioru ścian leżących przed tą płaszczyzną jeżeli maja przeciwną orientację dodawane są do zbioru z tyłu płaszczyzny. Warunkiem kończącym dzielenie jest utworzenie przez ściany bryły wypukłej czyli sektora. Przechodząc całe drzewo otrzymujemy kompletną lokację a dodatkowo kolejne sektory są posortowane względem odległości. Ponieważ ściany w sektorach tworzą bryły wypukłe to łatwo można ustalić ich poprawną kolejność.
Struktura elementu drzewa BSP 3D: Elementem drzewa może być sektor (ang. Sector) czyli liść drzewa binarnego (ang. Leaf) lub węzeł (ang. Node). Sektor jest elementem dla którego wskaźniki przód, tył, płaszczyzna podziału wynoszą NULL natomiast wskaźnik sektora jest różny od NULL. Węzeł drzewa ma wskaźniki przód, tył, płaszczyzna podziału różne od NULL natomiast wskaźnik sektora jest równy NULL.
Definicja sektora: Sektor to zbiór takich ścian że dla każdej ściany z tego zbioru są spełnione następujące dwa warunki. Pierwszy jest taki że dla płaszczyzny zawierającej daną ścianę nie znajdziemy żadnej innej ściany ze zbioru ścian sektora który byłby przez nią przecinany. Drugi mówi o tym że pozostałe ściany sektora leżą zawsze po jednej stronie płaszczyzny zawierającej tą ścianę.
Definicja płaszczyzny podziału: Jest to płaszczyzna ściany wybranej ze zbioru ścian sceny która spełnia kryterium wyboru opisane poniżej.
Definicja kryterium wyboru płaszczyzny rozdzielającej: W najprostszym przypadku jest to płaszczyzna zawierająca ścianę dla której zachodzi warunek że liczba ścian leżących przed i za tą płaszczyzną jest w przybliżeniu równa.
Prosty przykład generowania drzewa BSP 3D: Mamy prostą lokację składającą się z 12 ścian. Scena zawiera tylko ściany pionowe oznaczone numerami od 1 do 12. W przykładzie scena składa się tylko ze ścian prostopadłych do podłogi dzięki czemu mogłem przedstawić je jako płaskie rysunki (rzuty na płaszczyznę 2D) co bardzo uprościło rysowanie kolejnych etapów tworzenia drzewa BSP 3D. Wektory normalne tych ścian oznaczyłem kolorem czerwonym. Wektor normalny ściany wyznacza jej orientację. Budując drzewo będziemy wykorzystywali dwa wskaźniki przód i tył gdzie:
Zwrot wektora normalnego płaszczyzny rozdzielającej jest taki sam jak zwrot wektora normalnego wybranej ściany leżącej na tej płaszczyźnie. Korzeń drzewa BSP 3D wynosi NULL.
Wybieramy ścianę numer 4 i względem płaszczyzny tej ściany rozdzielamy lokację na dwa zbiory. Dlaczego wybieramy ścianę numer 4 ? Wynika to przyjętego kryterium wyboru płaszczyzny rozdzielającej (patrz definicja tego kryterium) Jak wyznaczamy ściany według tego kryterium ? sumujemy wagi przypisane ścianom i sprawdzamy która waga jest najbliższa zeru. Wagi przypisujemy dla zbioru ścian który aktualnie przetwarzamy i wynoszą one:
Sumując wagi pomijamy ściany przecinane przez potencjalną płaszczyznę rozdzielającą. Zgodnie z tym kryterium ściany 4 i 10 mają najmniejszą (najbliższą 0) sumę wag wynoszącą 1. Do podziału wybrałem ścianę 4 (równie dobrze mogłem wybrać ścianę 10). Zgodnie z tym kryterium będę wybierał wszystkie następne płaszczyzny rozdzielające. Ściany numer 1 i 7 ulegają podziałowi. Sprawdzamy czy zbiory ścian po rozdzieleniu lokacji płaszczyzną P4 tworzą sektory.( brak sektora -> patrz definicja sektora). Korzeń wskazuje na węzeł zawierający płaszczyznę P4. Wskaźniki przód i tył dla węzła P4 wynoszą NULL tzn. nie wskazują na żaden sektor.
Wybieramy ścianę numer 3 i względem płaszczyzny tej ściany rozdzielamy zbiór leżący z tyłu płaszczyzny P4 na dwa zbiory. Ściany 3 i 5 mają najmniejszą (najbliższą 0) sumę wag która wynosi -1. Do podziału wybrałem ścianę 3 (równie dobrze mogłem wybrać 5). Sprawdzamy czy zbiory ścian po rozdzieleniu lokacji płaszczyzną P3 tworzą sektory.( oba nowe zbiory tworzą sektory -> patrz definicja sektora). Wskaźnik tył dla węzła zawierającego P4 wskazuje na węzeł zawierający płaszczyznę P3. Wskaźniki przód i tył węzła P3 wskazują odpowiednio na sektory S1 i S2.
Wybieramy ścianę numer 11 i względem płaszczyzny tej ściany rozdzielamy zbiór leżący z przodu płaszczyzny P4 na dwa zbiory. Ściany numer 11,9,10 mają taką samą najmniejszą sumę wag (najbliższą 0) wynoszącą -3. Do podziału wybrałem ścianę 11 (równie dobrze mogłem wybrać 9 lub 10). Sprawdzamy czy zbiory ścian po rozdzieleniu lokacji płaszczyzną P11 tworzą sektory.( zbiór z przodu P11 tworzy sektor -> patrz definicja sektora). Wskaźnik przód dla węzła zawierającego P4 wskazuje na węzeł zawierający P11. Wskaźnik przód dla węzła zawierającego P11 wskazuje na sektory S3. Wskaźnik tył dla tego węzła wynosi NULL.
Wybieramy ścianę numer 9 i względem płaszczyzny tej ściany rozdzielamy zbiór leżący z tyłu płaszczyzny P11 na dwa zbiory. Ściana 9 ma jako jedyna idealną sumę wag równą 0. Sprawdzamy czy zbiory ścian po rozdzieleniu lokacji płaszczyzną P9 tworzą sektory.( zbiory z przodu i z tyłu P9 tworzą sektory -> patrz definicja sektora). Wskaźnik tył dla węzła zawierającego P11 wskazuje na węzeł zawierający płaszczyznę P9. Wskaźnik tył dla węzła zawierającego P9 wskazuje na sektor S4. Wskaźnik przód dla tego węzła wskazuje na sektor S5. W ten sposób utworzyliśmy drzewo BSP 3D dla przykładowej lokacji.
Informacje dodatkowe: Procedura budująca drzewo BSP 3D: Szkielet procedury budującej drzewo BSP 3D w pseudokodzie:
Procedura generacji drzewa BSP ( zbiór ścian ,wskaźnik węzła początkowego) {
krok 1 Utwórz nowy węzeł i nakieruj na niego wskaźnik węzła początkowego Czy zbiór ścian jest sektorem ( zbiór ścian ) { Jeżeli jest to zapisz sektor i zakończ Jeżeli nie jest to idź do kroku 2 }
krok 2 Wybierz płaszczyznę dzielącą ( zbiór ścian) { wyznacz z kryterium wyboru płaszczyzny podziału płaszczyznę dzielącą oraz zapisz węzeł drzewa }
krok 3 Rozdziel zbiór zbór ścian ( zbór ścian , płaszczyzna dzieląca ) { podziel zbór ścian na dwa zbiory: zbiór ścian 1 i zbiór ścian 2 względem płaszczyzny dzielącej }
krok 4 Procedura generacji drzewa BSP ( zbiór ścian 1 ,wskaźnik przód nowego węzła) Procedura generacji drzewa BSP ( zbiór ścian 2 ,wskaźnik tył nowego węzła) }
Procedura renderująca poprzez drzewo BSP 3D: Szkielet procedury renderującej w pseudokodzie (wersja 1):
Renderuj drzewo BSP ( pozycja gracza, wskaźnik na węzeł początkowy) {
krok 1 Czy węzeł początkowy jest sektorem ( węzeł początkowy) { jeżeli jest to wyświetl wszystkie ściany sektora i zakończ jeżeli nie jest to idź do kroku 2 }
krok 2 Wyznacz z której strony płaszczyzny dzielącej węzła jest gracz ( pozycja gracza, płaszczyzna dzieląca węzła) { jeżeli jest z przodu to: Renderuj drzewo BSP ( pozycja gracza, wskaźnik tył węzła początkowego) Renderuj drzewo BSP ( pozycja gracza, wskaźnik przód węzła początkowego) jeżeli jest z tyłu to: Renderuj drzewo BSP ( pozycja gracza, wskaźnik przód węzła początkowego) Renderuj drzewo BSP ( pozycja gracza, wskaźnik tył węzła początkowego) } }
Szkielet procedury renderującej w pseudokodzie (wersja 2): Renderuj drzewo BSP ( pozycja gracza, kierunek patrzenia gracza, wskaźnik na węzeł początkowy) {
krok 1 Czy węzeł początkowy jest sektorem (węzeł początkowy) { jeżeli jest to sprawdź: { Czy otoczenie sektora jest w stożku widzenia gracza( pozycja gracza, kierunek patrzenia gracza) { jeżeli tak to: wyświetl wszystkie ściany sektora i zakończ jeżeli nie to: zakończ } } jeżeli nie jest to idź do kroku 2 }
krok 2 Wyznacz z której strony płaszczyzny dzielącej węzła jest gracz ( pozycja gracza, płaszczyzna dzieląca węzła) { jeżeli jest z przodu to: Renderuj drzewo BSP ( pozycja gracza, kierunek patrzenia gracza, wskaźnik tył węzła początkowego) Renderuj drzewo BSP ( pozycja gracza, kierunek patrzenia gracza, wskaźnik przód węzła początkowego) jeżeli jest z tyłu to: Renderuj drzewo BSP ( pozycja gracza, kierunek patrzenia gracza, wskaźnik przód węzła początkowego) Renderuj drzewo BSP ( pozycja gracza, kierunek patrzenia gracza, wskaźnik tył węzła początkowego) } }
Procedury zapisu i odczytu drzewa BSP 3D: Szkielet procedury zapisu w pseudokodzie:
Zapisz drzewo BSP ( wskaźnik na węzeł początkowy ) {
krok 1 Czy węzeł początkowy jest sektorem ( węzeł początkowy) { jeżeli jest to zapisz znacznik węzła (sektor), wszystkie ściany sektora i zakończ jeżeli nie jest to zapisz znacznik węzła (węzeł) i płaszczyznę węzła oraz idź do kroku 2 }
krok 2 Zapisz drzewo BSP ( wskaźnik przód węzła początkowego) Zapisz drzewo BSP ( wskaźnik tył węzła początkowego) }
Znacznik węzła pozwala na odróżnienie sektora od zwykłego węzła.
Szkielet procedury odczytu w pseudokodzie:
Odczytaj drzewo BSP ( wskaźnik na węzeł początkowy) {
krok 1 Utwórz nowy węzeł i nakieruj na niego wskaźnik na węzeł początkowy Czy odczytujemy sektor ( odczytany znacznik węzła) { jeżeli tak to odczytaj wszystkie ściany sektora i zakończ jeżeli nie to odczytaj płaszczyznę węzła i idź do kroku 2 }
krok 2 Odczytaj drzewo BSP ( wskaźnik przód nowego węzła) Odczytaj drzewo BSP ( wskaźnik tył nowego węzła) }
Procedura znajdująca sektor drzewa BSP 3D w którym jest gracz: Szkielet procedury znalezienia sektora w drzewie BSP w którym znajduje się gracz
Podaj sektor z drzewa BSP( pozycja gracza, wskaźnik na węzeł początkowy) {
krok 1 Czy węzeł początkowy jest sektorem ( węzeł początkowy) { jeżeli jest to zwróć wskaźnik do sektora i zakończ jeżeli nie jest to idź do kroku 2 }
krok 2 Wyznacz z której strony płaszczyzny dzielącej węzła jest gracz ( pozycja gracza, płaszczyzna dzieląca węzła) { jeżeli jest z przodu to: Podaj sektor z drzewa BSP( pozycja gracza, wskaźnik przód węzła początkowego) jeżeli jest z tyłu to: Podaj sektor z drzewa BSP( pozycja gracza, wskaźnik tył węzła początkowego) } }
Zalety i wady drzewa BSP 3D: Zalety: Przechodząc drzewo uzyskujemy sektory posortowane we właściwej kolejności np. od najdalszych sektorów do najbliższych lub odwrotnie. Zapis grafiki do drzewa BSP 3D powoduje że przenikające się powierzchnie są automatycznie łączone. Na przenikających się powierzchniach wykonywana jest operacja sumowania.
Wady: Chcąc wyświetlić lokację zapisaną w drzewie BSP 3D musimy przejść całe drzewo zaczynając od korzenia. Standardowe drzewo BSP 3D uniemożliwia proste wykrywanie widoczności postaci. Występują problemy z animacjami sceny.
|
