Drzewo BSP
Drzewo BSP 2D (ang. Binary Space Partitioning) jest drzewem binarnym służącym do podziału płaszczyzny. Drzewo BSP 2D jest drzewem odcinków, które można traktować jako rzuty ścian na płaszczyznę. Scena dzielona jest w taki sposób, że w końcowym etapie tworzy wielokąty wypukłe.
Drzewo BSP 3D (ang. Binary Space Partitioning) jest drzewem binarnym służącym do podziału przestrzeni 3D. Podczas tworzenia drzewa BSP 3D cała scena dzielona jest na bryły wypukłe, czyli sektory. Drzewo BSP 3D po wygenerowaniu dla każdego sektora portali i list PVS może być wykorzystane do szybkiego renderowania sceny. Opis generowania portali z drzewa BSP 3D znajduje się w artykule Portale. Opis tworzenia list PVS znajduje się w artykule Listy 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.
Struktura elementu drzewa BSP 3D:
Elementem drzewa może być sektor (ang. Sector), czyli liść drzewa binarnego (ang. Leaf) lub węzeł (ang. Node). Struktura elementu drzewa składa się z czterech wskaźników, którymi są wskaźnik do płaszczyzny rozdzielającej, wskaźnik do sektora, wskaźnik do kolejnego elementu leżącego przed i za płaszczyzną rozdzielającą. Sektor jest elementem, dla którego wskaźniki przód, tył, płaszczyzna rozdzielająca wynoszą NULL, natomiast wskaźnik sektora jest różny od NULL. Węzeł drzewa ma wskaźniki przód, tył, płaszczyzna rozdzielająca 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 dwa podstawowe warunki. Pierwszy warunek mówi o tym, że żadna płaszczyzna zawierająca daną ścianę sektora nie przecina pozostałych ściany sektora. Drugi mówi o tym, że dla każdej płaszczyzny zawierającej daną ścianę sektora pozostałe ściany sektora leżą zawsze po tej samej stronie. Metoda rozdzielania ścian sceny gwarantuje, że ściany sektora są zawsze zwrócone do jego wnętrza. Przykłady zbiorów ścian tworzących sektory:
Przykłady zbiorów ścian które nie są sektorami:
Metoda rozdzielania ścian sceny:
Do rozdzielania ścian 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ę rozdzielającą są dzielone tak, aby jedna cześć leżała za a druga przed tą płaszczyzną. Ściany, które leżą na płaszczyźnie rozdzielającej, 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. Kryterium wyboru płaszczyzny rozdzielającej opisane jest 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. Płaszczyznę rozdzielającą wybieramy poprzez sumowanie wag przypisanych ścianom a następnie poprzez sprawdzenie, która waga jest najbliższa zeru. Wagi przypisujemy dla zbioru ścian, który aktualnie przetwarzamy. Wagi mają następujące wartości:
- 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
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 można przedstawić je jako płaskie rysunki (rzuty na płaszczyznę ekranu), co bardzo upraszcza rysowanie kolejnych etapów tworzenia drzewa BSP 3D. Wektory normalne tych ścian są oznaczone kolorem czerwonym i wyznaczają orientację ściany. Budując drzewo będziemy wykorzystywać dwa wskaźniki przód i tył. 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 BSP 3D wynosi NULL.
Wybieramy ścianę numer 4 i względem płaszczyzny tej ściany rozdzielamy scenę na dwa zbiory. Wybór ściany numer 4 wynika z przyjętego kryterium wyboru płaszczyzny rozdzielającej. Zgodnie z tym kryterium ściany 4 i 10 mają najmniejszą (najbliższą 0) sumę wag wynoszącą 1. Do podziału została wybrana ściana 4 (równie dobrze mogła zostać wybrana ściana 10). Ściany numer 1 i 7 ulegają podziałowi. Sprawdzamy czy zbiory ścian po rozdzieleniu sceny 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 wybrana została ściana 3 (równie dobrze mogła zostać wybrana ściana 5). Sprawdzamy czy zbiory ścian po rozdzieleniu sceny 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 wybrana została ściana 11 (równie dobrze mogła zostać wybrana ściana 9 lub 10). Sprawdzamy czy zbiory ścian po rozdzieleniu sceny 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 sceny 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 sceny.
//Szkielet procedury budującej drzewo BSP 3D:
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ę rozdzielającą ( zbiór ścian)
{
Wyznacz z kryterium wyboru płaszczyzny rozdzielającej płaszczyznę podziału oraz zapisz węzeł drzewa
}
//krok 3
Rozdziel zbiór zbór ścian ( zbór ścian, płaszczyzna rozdzielająca )
{
podziel zbór ścian na dwa zbiory: zbiór ścian 1 i zbiór ścian 2 względem płaszczyzny rozdzielają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)
}
{
//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ę rozdzielającą ( zbiór ścian)
{
Wyznacz z kryterium wyboru płaszczyzny rozdzielającej płaszczyznę podziału oraz zapisz węzeł drzewa
}
//krok 3
Rozdziel zbiór zbór ścian ( zbór ścian, płaszczyzna rozdzielająca )
{
podziel zbór ścian na dwa zbiory: zbiór ścian 1 i zbiór ścian 2 względem płaszczyzny rozdzielają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)
}
//Szkielet procedury renderującej scenę zapisaną w drzewie BSP (wersja 1):
Renderuj drzewo BSP ( pozycja obserwatora, 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 rozdzielającej węzła jest obserwator ( pozycja obserwatora, płaszczyzna rozdzielająca)
{
Jeżeli jest z przodu to:
Renderuj drzewo BSP ( pozycja obserwatora, wskaźnik tył węzła początkowego)
Renderuj drzewo BSP ( pozycja obserwatora, wskaźnik przód węzła początkowego)
Jeżeli jest z tyłu to:
Renderuj drzewo BSP ( pozycja obserwatora, wskaźnik przód węzła początkowego)
Renderuj drzewo BSP ( pozycja obserwatora, wskaźnik tył węzła początkowego)
}
}
{
//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 rozdzielającej węzła jest obserwator ( pozycja obserwatora, płaszczyzna rozdzielająca)
{
Jeżeli jest z przodu to:
Renderuj drzewo BSP ( pozycja obserwatora, wskaźnik tył węzła początkowego)
Renderuj drzewo BSP ( pozycja obserwatora, wskaźnik przód węzła początkowego)
Jeżeli jest z tyłu to:
Renderuj drzewo BSP ( pozycja obserwatora, wskaźnik przód węzła początkowego)
Renderuj drzewo BSP ( pozycja obserwatora, wskaźnik tył węzła początkowego)
}
}
//Szkielet procedury renderującej scenę zapisaną w drzewie BSP (wersja 2):
//Procedura ta wykorzystuje otoczenia sektorów, którymi mogą być np. sześciany
//położone wzdłuż osi układu współrzędnych (ang. AABB Axis Aligned Bounding Box)
//Procedura ta wykorzystuje otoczenia sektorów, którymi mogą być np. sześciany
//położone wzdłuż osi układu współrzędnych (ang. AABB Axis Aligned Bounding Box)
Renderuj drzewo BSP ( pozycja obserwatora, kierunek patrzenia obserwatora, 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 obserwatora( pozycja obserwatora, kierunek patrzenia obserwatora)
{
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 rozdzielającej węzła jest obserwator ( pozycja obserwatora, płaszczyzna rozdzielająca)
{
Jeżeli jest z przodu to:
Renderuj drzewo BSP ( pozycja obserwatora, kierunek patrzenia obserwatora, wskaźnik tył węzła początkowego)
Renderuj drzewo BSP ( pozycja obserwatora, kierunek patrzenia obserwatora, wskaźnik przód węzła początkowego)
Jeżeli jest z tyłu to:
Renderuj drzewo BSP ( pozycja obserwatora, kierunek patrzenia obserwatora, wskaźnik przód węzła początkowego)
Renderuj drzewo BSP ( pozycja obserwatora, kierunek patrzenia obserwatora, wskaźnik tył węzła początkowego)
}
}
{
//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 obserwatora( pozycja obserwatora, kierunek patrzenia obserwatora)
{
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 rozdzielającej węzła jest obserwator ( pozycja obserwatora, płaszczyzna rozdzielająca)
{
Jeżeli jest z przodu to:
Renderuj drzewo BSP ( pozycja obserwatora, kierunek patrzenia obserwatora, wskaźnik tył węzła początkowego)
Renderuj drzewo BSP ( pozycja obserwatora, kierunek patrzenia obserwatora, wskaźnik przód węzła początkowego)
Jeżeli jest z tyłu to:
Renderuj drzewo BSP ( pozycja obserwatora, kierunek patrzenia obserwatora, wskaźnik przód węzła początkowego)
Renderuj drzewo BSP ( pozycja obserwatora, kierunek patrzenia obserwatora, wskaźnik tył węzła początkowego)
}
}
//Szkielet procedury zapisu drzewa BSP:
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 elementu drzewa (sektor) oraz wszystkie ściany sektora i zakończ
Jeżeli nie jest to zapisz znacznik elementu drzewa (węzeł) oraz płaszczyznę węzła i 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)
}
{
//krok 1
Czy węzeł początkowy jest sektorem ( węzeł początkowy)
{
Jeżeli jest to zapisz znacznik elementu drzewa (sektor) oraz wszystkie ściany sektora i zakończ
Jeżeli nie jest to zapisz znacznik elementu drzewa (węzeł) oraz płaszczyznę węzła i 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 elementu drzewa pozwala na odróżnienie sektora (liścia drzewa BSP) od węzła.
//Szkielet procedury odczytu drzewa BSP:
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 elementu drzewa)
{
Jeżeli tak to odczytaj wszystkie ściany sektora i zakończ
Jeżeli nie to odczytaj płaszczyznę rozdzielającą 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)
}
{
//krok 1
Utwórz nowy węzeł i nakieruj na niego wskaźnik na węzeł początkowy
Czy odczytujemy sektor ( odczytany znacznik elementu drzewa)
{
Jeżeli tak to odczytaj wszystkie ściany sektora i zakończ
Jeżeli nie to odczytaj płaszczyznę rozdzielającą 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)
}
//Szkielet funkcji zwracającej sektor drzewa BSP, w którym znajduje się obserwator:
Podaj sektor z drzewa BSP( pozycja obserwatora, 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 rozdzielającej węzła jest obserwator ( pozycja obserwatora, płaszczyzna rozdzielająca)
{
Jeżeli jest z przodu to:
Podaj sektor z drzewa BSP( pozycja obserwatora, wskaźnik przód węzła początkowego)
Jeżeli jest z tyłu to:
Podaj sektor z drzewa BSP( pozycja obserwatora, wskaźnik tył węzła początkowego)
}
}
{
//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 rozdzielającej węzła jest obserwator ( pozycja obserwatora, płaszczyzna rozdzielająca)
{
Jeżeli jest z przodu to:
Podaj sektor z drzewa BSP( pozycja obserwatora, wskaźnik przód węzła początkowego)
Jeżeli jest z tyłu to:
Podaj sektor z drzewa BSP( pozycja obserwatora, wskaźnik tył węzła początkowego)
}
}
Autor: Mirosław Kozioł, Komires Sp. z o.o.
Numer artykułu: 19
Wysłany: Sun, Feb 14, 2010 2:21 PM
Ostatnio zmieniony: Wed, Feb 17, 2010 4:20 AM
Adres URL: https://www.komires.net/article.php?id=19