Drzewo PVS Autor: Mirosław Kozioł

Drzewo PVS 3D jest to drzewo BSP 3D z listami sektorów widocznych PVS 3D. Mówiąc o drzewie PVS 3D mam na myśli drzewo BSP 3D + PVS 3D. Chcąc uzyskać drzewo PVS 3D należy wprowadzić następujące modyfikacje drzewa BSP 3D:

1. Ponieważ do wyświetlenia lokacji musimy przejść całe drzewo to przy większych drzewach jest to operacja wolna a przy dużych bardzo wolna. Aby przyspieszyć obsługę drzewa należy wygenerować listy sektorów widocznych z każdego sektora drzewa.

2. Chodzenie po drzewie z listami sektorów widocznych nie może polegać na każdorazowym wrzucaniu obserwatora i testowaniu w jakim sektorze się znajdzie. Przy dużym drzewie i wielu postaciach operacja ta staje się bardzo czasochłonna. Aby wyeliminować ten efekt należy zrzucić postać raz a następnie analizować tylko wycinek drzewa. (innym rozwiązaniem jest ograniczenie wielkości drzewa i ilości postaci)

3. Standardowy algorytm drzewa BSP 3D dzieli ściany co prowadzi do generowania dużej ilości nowych ścian. Prowadzi to, już przy niewielkiej scenie, do znacznego spowolnienia działania programu renderującego. Aby wyeliminować ten efekt nie należy zapisywać w sektorach podzielonych ścian. (Gdy chcemy mieć zapisane w drzewie podzielone ściany możemy pominąć tą modyfikację).

Z dowolnego punktu przestrzeni 3D renderujemy tylko to co widzimy - (modyfikacja 1). Kolizje sprawdzamy tylko na ściany które widzimy - (modyfikacja 1). Prędkość dostępu do ścian jest na poziomie dostępu do izolowanych zbiorów wielokątów opisujących to co widać z punktu w którym znajduje się obserwator - (modyfikacja 1,2). Po zapisie lokacji w drzewie BSP 3D mamy tyle samo ścian co przed zapisem - (modyfikacja 3). Wzajemne widzenie postaci zapewnia lista sektorów widocznych co nie byłoby możliwe gdyby do danego sektora drzewa była doczepiona lista ścian widocznych. Gdy postać znajduje się w sektorze który należy do listy sektorów widocznych doczepionych do sektora postaci głównej lub sektora dowolnej innej postaci w grze to automatycznie można to wykryć analizując tylko listę sektorów widocznych. - (modyfikacja 1).

Uwagi:

Modyfikacja 1 jest najważniejsza i nie może być pominięta. Modyfikacja 2 może być pominięta (przyspiesza tylko dostęp do sektora). Modyfikacja 3 nie może być wprowadzona jeżeli korzystamy z modułu świateł bibliotek DirectX, OpenGL. Modyfikację 3 możemy wprowadzić jeżeli generujemy światła statyczne i dynamiczne w oparciu o mapy świateł (ang. lightmaps) nie korzystając z wektorów normalnych.

Po generacji drzewa BSP 3D możemy wygenerować listy PVS 3D. Poniżej przedstawiam parę sposobów na generację list PVS 3D:

1. Matematyczna

Określamy przestrzeń w której zawiera się lokacja i próbkujemy ją z pewnym minimalnym krokiem w celu uzyskania zbioru punktów zawartych w tej przestrzeni. Dla każdego punktu znajdujemy sektor w drzewie BSP 3D do którego będziemy dodawać sektory widoczne a następnie z każdego punktu prowadzimy promienie we wszystkich kierunkach w celu znalezienia najbliższej przecinanej przez niego ściany. Sprawdzamy do jakiego sektora w drzewie BSP 3D należy znaleziona ściana i dodajemy go do sektora który zawiera punkt z którego rzuciliśmy promień.

2. Graficzna

Określamy przestrzeń w której zawiera się lokacja i próbkujemy ją z pewnym minimalnym krokiem w celu uzyskania zbioru punktów zawartych w tej przestrzeni. Dla każdego punktu znajdujemy sektor w drzewie BSP 3D do którego będziemy dodawać sektory widoczne a następnie z każdego punktu renderujemy obraz w podstawowych kierunkach. Do bufora ekranu zapisujemy numery sektorów do jakich należą renderowane  ściany. Dla każdego obrazu wyrenderowanego w każdym z podstawowych kierunków skanujemy bufor ekranu i dodajemy odczytane z niego numery sektorów do sektora który zawiera punkt z którego renderowalismy.

3. Generator portali 3D

Przykładowy program generujący portale 3D omówiłem w rozdziale Portale. Wygenerowane portale 3D można wykorzystać do zbudowania list PVS 3D. Listy PVS 3D budujemy patrząc na zewnątrz sektora z wierzchołków wszystkich portali należących do tego sektora i określając widoczne sektory.

4. Edytor CSG (ang. Constructive Solid Geometry)

Metoda ta polega na wstawieniu portali poprzez proste operacje dodawania i odejmowania brył. Po usunięciu fragmentu bryły możemy w to miejsce wstawić portale. Mając portale generujemy listy PVS 3D jak w metodzie Generator portali 3D.

• Problem pozostawiania sektorów które nie mają listy sektorów widocznych. Problem ten dotyczy bardzo małych sektorów których 'nie łapiemy' ponieważ mamy za duży krok próbkowania objętości lokacji. Podczas chodzenia po lokacji może to prowadzić i zwykle prowadzi do nagłego znikania całej grafiki gdy gracz 'wpadnie' do takiego sektora.
• Problem prędkości generacji list sektorów widocznych oraz dokładności z jaką tworzymy taką listę. Problem dokładności w metodzie graficznego wyznaczania list sektorów widocznych jest związany z wielkością ekranu na który renderujemy. Problem dokładności w metodzie matematycznego wyznaczania list sektorów widocznych jest związany z liczbą rzucanych promieni. Prowadzi to zwykle do pomijania części sektorów czego konsekwencją jest to że podczas chodzenia po lokacji nagle 'znikają' nam fragmenty grafiki.