Lemur zaprasza
Drzewo BSP (Binary Space Partitioning) Drzewo BSP to nic innego jak zwykłe drzewo binarne. Najciekawszy jest sposób jego generowania. Cała lokacja dzielona jest w taki sposób że w końcowym etapie tworzy zamknięte bryły. Do podziału lokacji wykorzystywane są płaszczyzny na których leżą poligony. Cała lokacja rozdzielana jest na zbiory poligonów leżących przed i za płaszczyzną podziału. Poligony które przecinają płaszczyznę podziału są dzielone tak aby jedna cześć leżała za a druga przed płaszczyzną. Poligony które leżą na płaszczyźnie podziału jeżeli mają taką samą orientację jak płaszczyzna podziału dodawane są do poligonów 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 poligony bryły zamkniętej czyli sektora. Przechodząc całe drzewo otrzymujemy kompletną lokację a dodatkowo kolejne sektory są posortowane względem odległości. Drzewo BSP ma wszystkie cechy algorytmu malarskiego a dodatkowo zapewnia połączenie przenikających się powierzchni. Struktura elementu drzewa BSP: Definicja sektora: Sektor to zbiór takich poligonów że dla każdego poligonu z tego zbioru są spełnione następujące dwa warunki: 1.Dla płaszczyzny zawierającej dany poligon nie znajdziemy żadnego poligonu ze zbioru poligonów sektora który byłby przez nią przecinany. 2.Pozostałe poligony sektora leżą zawsze po jednej stronie płaszczyzny zawierającej ten poligon. Przykłady sektorów i zbiorów które nie są sektorami: Definicje węzłów drzewa: 1. Sektor jest węzłem dla którego wskaźniki przód, tył, płaszczyzna podziału wynoszą NULL natomiast wskaźnik sektora jest różny od NULL. 2. 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 kryterium wyboru płaszczyzny rozdzielającej: W najprostszym przypadku jest to płaszczyzna zawierająca poligon dla której zachodzi warunek że liczba poligonów leżących przed i za tą płaszczyzną jest w przybliżeniu równa. Prosty przykład generowania drzewa BSP: Mamy prostą lokację składającą się z 12 ścian. Lokacja zawiera tylko ściany pionowe oznaczone numerami od 1do 12. 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: -przód to odpowiednik prawo w drzewie binarnym i wskazuje zbór ścian leżących po stronie zgodnej z kierunkiem wektora normalnego płaszczyzny rozdzielającej. -tył to odpowiednik lewo w drzewie binarnym i wskazuje zbiór ścian leżących po stronie przeciwnej do kierunku wektora normalnego płaszczyzny rozdzielającej. 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 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: 1 dla ściany z przodu potencjalnej płaszczyzny rozdzielającej -1 dla ściany z tyłu potencjalnej płaszczyzny rozdzielającej 0 dla ściany leżącej na potencjalnej płaszczyźnie rozdzielającej do sumowania 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 dla przykładowej lokacji. Uwagi końcowe: Procedura budująca drzewo BSP powinna być rekurencyjna Oto szkielet takiej procedury 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 powinna być rekurencyjna. Oto szkielet takiej procedury w pseudokodzie: 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 przód węzła początkowego) Renderuj drzewo BSP ( pozycja gracza, wskaźnik tył węzła początkowego) jeżeli jest z tyłu 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) } } Procedury zapisu i odczytu drzewa BSP powinny być również rekurencyjne. Oto 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, wszystkie ściany sektora i zakończ jeżeli nie jest to zapisz znacznik węzła 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. Oto 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) } } Dokładny opis algorytmów generowania i odczytu drzewa BSP należy szukać w Internecie. Polecam zapoznanie się z książką Wojciecha Jawora 'Principia silnika' gdzie można znaleźć gotowe programy do generacji drzewa BSP 3D oraz prosty silnik do gier 3D. Zalety: 1. Wyświetlana grafika jest od razu posortowana we właściwej kolejności np. od najdalszych poligonów do najbliższych. 2. Zapis grafiki do drzewa BSP powoduje że przenikające się powierzchnie są automatycznie łączone. Na przenikających się powierzchniach wykonywana jest operacja sumowania. Wady: 1. Chcąc wyświetlić lokację zapisaną w drzewie BSP musimy przejść całe drzewo zaczynając od korzenia. 2. Standardowe drzewo BSP uniemożliwia proste wykrywanie widoczności postaci. Uwagi: Wady drzewa BSP praktycznie uniemożliwiają jego zastosowanie w grach SPP i FPP z rozbudowanymi poziomami i dużą ilością postaci. Jedynym rozwiązaniem jest przełączanie się pomiędzy wieloma małymi drzewami BSP lub przejście na drzewa PVS i portale. Autor: Mirosław Kozioł |