Portale Autor: Mirosław Kozioł

Portale 3D (ang. Portals) są wirtualnymi ścianami które łączą ze sobą zbiory wielokątów.

Aby wykorzystać portale musimy je najpierw wygenerować i zapisać w pliku danych. Mając wygenerowane portale wykorzystujemy je w procesie renderowania do ustalenia ścian widocznych. Możemy także rozdzielić proces renderowania od procesu ustalenia ścian widocznych tworząc dynamiczną listę PVS. Wykorzystując procedurę renderowania nie wyświetlamy ścian ale zapisujemy sektor do jakiego dana ściana należy czyli tworzymy listę sektorów widocznych PVS 3D. Właściwe renderowanie polega wtedy na wyświetleniu ścian zawartych w sektorach z tej listy.

W procesie renderowania nie stosujemy cięć (ang. clipping). Procedura renderowania kończy swoje działanie, gdy portal jest zbyt odległy, nie ma portali lub portal jest odwrócony tyłem do obserwatora.  Metoda ta została prawdopodobnie zastosowana w grze Soul Reaver.

Metoda bardzo szybka, odporna na zapętlenia spowodowane błędami w generacji portali, odporna na dużą ilość wygenerowanych portali (nie ma zwolnień), nie stosujemy cięcia portali.

Grafika wyświetlana jest do pewnej odległości od obserwatora.

Wykonujemy cięcia portali. Możemy ciąć portale w przestrzeni 2D lub 3D, dlatego opis odnosi się do obydwu technik. Prędkość procedury cięcia portali jest ściśle związana z ilością portali.

1. Renderowanie rozpoczynamy od wyświetlenia zbioru ścian z sektora, w którym jest gracz (sektor startowy).

2. Następnie sprawdzamy czy w rzucie tych ścian na ekran (2D) lub w widoku kamery (3D) nie jest widoczna ściana, która reprezentuje portal.

Jeżeli nie ma takiej ściany to kończymy renderowanie.

Jeżeli jest to przechodzimy do punktu 3.

3. Pobieramy krawędzie tnące (2D) lub tworzymy płaszczyzny tnące (3D) dla wszystkich krawędzi ściany reprezentującej portal wejściowy.

4. Pobieramy nowy zbiór ścian z sektora, z którym dany portal się łączy i renderujemy ten zbiór.

5. Jeżeli w tym zbiorze są ściany reprezentujące portale to korygujemy ich rozmiary tnąc krawędziami portala wejściowego (2D) lub płaszczyznami utworzonymi z portala wejściowego (3D).

6. Przechodzimy do punktu 2.

Możemy przycinać ściany w przestrzeni 2D lub 3D. Przez cały proces renderowania pozycja gracza nie zmienia się. Taki algorytm renderowania powoduje że wyświetlamy tylko to co widzimy. Dodatkowo możemy dowolnie modyfikować zbiory ścian włączając w to modyfikację portali. Algorytm nie jest zależny od wielkości ekranu przy zastosowaniu cięcia w przestrzeni 3D. Płaszczyzny przycinające tworzymy pomiędzy każdą krawędzią portala i punktem w którym znajduje się obserwator (gdy tniemy w przestrzeni 3D).  

Możemy także wykorzystać portale do generacji statycznej listy PVS dla drzewa BSP.

Należy wtedy sprawdzić, jakie sektory widzimy z każdego portala każdego testowanego sektora i dodać je do budowanej listy PVS dla testowanego sektora. Po przejściu wszystkich sektorów drzewa BSP 3D otrzymamy drzewo BSP 3D + Portale 3D + listy PVS 3D , czyli drzewo BSP 3D z portalami 3D, do których będziemy mieli dowiązane listy sektorów widocznych PVS 3D.

1. Znajdujemy sektor, w którym jest gracz (sektor gracza).

2. Pobieramy zbiór ścian z sektora gracza i go renderujemy.

3. Sprawdzamy czy w widoku kamery znajdują się jeszcze jakieś portale z sektora gracza.

Jeżeli nie ma to kończymy renderowanie.

Jeżeli są to przechodzimy do punktu 4.

4. Odczytujemy kolejne sektory z list PVS dla tego portala.

5. Dla kolejnych sektorów z listy PVS renderujemy zbiory ścian.

6. Przechodzimy do punktu 3.

Uwagi:

Ścian które są portalami nie wyświetlamy lecz tylko testujemy ich obecność. Algorytm sprawdza się dla gier których akcja rozgrywa się w pomieszczeniach lub ograniczonych ścianami obszarach i nie jest dobry do otwartych przestrzeni. Do generacji portali w najprostszym przypadku musimy napisać własny edytor do ręcznego wstawiania portali.

Programowa generacja portali sprawdza się dla prostej grafiki. Przy grafice zbudowanej z dużej ilości elementów lub przy skomplikowanych powierzchniach może prowadzić do wygenerowania bardzo dużej ilości małych portali. Pierwszym etapem programowej generacji portali jest zbudowanie standardowego drzewa BSP musimy jednak dodać do drzewa BSP następujące informacje:

• wskaźnik do węzła poprzedniego. Wskaźnik ten musimy dodać do wszystkich elementów drzewa tzn. do liści i do węzłów. Korzeń będzie posiadał wskaźnik równy NULL.
• informację z jaką stroną względem płaszczyzny rozdzielającej jest związany dany element drzewa. Informacja ta dla danego węzła lub liścia dotyczy zawsze płaszczyzny poprzedzającej utworzenie tego węzła lub liścia.

Przykładowa scena dla której znaleźliśmy płaszczyzny rozdzielające i zbudowaliśmy drzewo BSP:

Po wprowadzeniu opisanych powyżej zmian otrzymamy następujące nowe drzewo BSP:

Portale należy rozumieć tutaj jako brakujące ściany ograniczające obszar sektora. Portale tak generowane nadają się również do szybkiego generowania przy ich pomocy drzewa PVS. Właściwa procedura generowania portali składa się z dwóch podstawowych części:

• Procedury generującej portale 1:N. Procedura ta generuje portale które łączą N sektorów
• Procedury generującej portale 1:1. Procedura ta przetwarza portale 1:N i generuje nowe portale które łączą jeden sąsiedni sektor.

Krok 1

Wybieramy kolejne sektory dla których będziemy budować portale.

Krok 2

Na każdej płaszczyźnie rozdzielającej budujemy 'duży portal' (ang. Huge Portal). Budowa dużego portala polega na utworzeni ściany na płaszczyźnie rozdzielającej gdzie rozmiar ściany jest znacznie większy niż rozmiar lokacji. Orientacja ściany jest zgodna z kierunkiem wektora normalnego ściany. (algorytm tworzenia ściany na płaszczyźnie będzie opisany w części dla początkujących odnośnik Podstawy).

Krok 3

Tworzymy listę potencjalnych portali. Dla każdego dużego portala poruszając się od sektora do korzenia tniemy go płaszczyznami rozdzielającymi. Po cięciu bierzemy obie części dużego portala i dla każdej z nich powtarzamy cięcie kolejnymi płaszczyznami. Po dojściu do korzenia otrzymujemy listę potencjalnych portali.

Lista potencjalnych portali jest gorszą wersją algorytmu tworzącego portale. Dużo szybsze i prostsze jest utworzenie jednego potencjalnego portala i taki algorytm opiszę poniżej. 

Tworzymy jeden potencjalny portal. Do poprawnego utworzenia tego portala potrzebne będą opisane powyżej modyfikacje drzewa BSP. Dla każdego dużego portala poruszając się od sektora do korzenia tniemy go płaszczyznami rozdzielającymi. Po cięciu bierzemy tylko tą część dużego portala której położenie jest zgodne z informacją o kierunku zapisaną w węźle leżącym poniżej. Gdy portal leży na płaszczyźnie rozdzielającej to go przepisujemy bez zmian. Podobnie robimy gdy leży całkowicie po jednej ze stron płaszczyzny rozdzielającej. Dzięki tym trzem krokom możemy utworzyć podstawowe portale 1:N dla wszystkich sektorów. Następne kroki to obróbka otrzymanych podstawowych portali 1:N

Krok 4

Tniemy duże portale płaszczyznami na których leżą ściany sektora dla którego znajdujemy portale. Jeżeli duży portal leży na jakiejś płaszczyźnie utworzonej na ścianie sektora to dodatkowo tniemy go płaszczyznami prostopadłymi do krawędzi tej ściany.

Krok 5

Znajdujemy duże portale przyległe do sektora dla którego liczymy portale. Portale które nie są portalami przyległymi usuwamy. Jest to bardziej skomplikowana część procedury obróbki portali 1:N i polega na wrzuceniu dużego portala do drzewa i sprawdzeniu czy trafi on do sektora dla którego liczymy portale.

Dodatkowo zapisujemy wszystkie pozostałe sektory (różne od sektora dla którego liczymy portale) do jakich trafi nasz portal. Sektory te są sektorami z którymi łączy się nasz portal. Procedura sprawdzania przyległości portala do sektora dla którego liczymy portale jest rekurencyjna. W procedurze tej mamy trzy przypadki:

• Gdy portal leży po jednej ze stron płaszczyzny danego węzła drzewa BSP to wywołujemy ją ze wskaźnikiem tej strony.
• Gdy portal przecina płaszczyznę danego węzła drzewa BSP to wywołujemy ją ze wskaźnikiem do obu stron.
• Gdy portal leży na płaszczyźnie danego węzła drzewa BSP to wywołujemy ją ze wskaźnikiem do obu stron.

Po dotarciu do danego sektora drzewa BSP zapisujemy go do tablicy. Po wykonaniu procedury sprawdzamy czy w tej tablicy znajduje się sektor dla którego liczymy portale. Jeżeli jest to portal jest portalem przyległym do sektora. Jeżeli nie ma go to portal nie jest portalem przyległym do sektora.

Krok 6

Usuwamy portale zawierające się w ścianach sektora dla którego liczymy portale. Usuwamy portale które nie zawierają się w przestrzeni lokacji

Krok 1

Wybieramy sektor S5. (Pełna procedura generująca portale powinna pobierać kolejno sektory od S1 do S5 i budować dla nich portale).

Krok 2

Budujemy duże portale na płaszczyznach P9,P11,P4. 

Dlaczego na tych ?

Płaszczyzny na których budujemy duże portale odczytujemy wykorzystując modyfikację którą wprowadziliśmy do drzewa BSP a mianowicie wskaźnik na węzeł poprzedzający (ang. parent). Do odczytania kolejnych płaszczyzn na których budujemy duże portale wykorzystujemy tylko wskaźnik na węzeł poprzedzający. Dla S5 kolejne pobierane płaszczyzny to P9,P11,P4 i na nich budujemy duże portale:

Krok 3

Przycinamy kolejno duże portale P9, P11, P4. (Wykorzystujemy tutaj wskaźnik na węzeł poprzedzający podobnie jak dla kroku 2 (do pobierania kolejnych płaszczyzn) oraz dodatkowo informację o stronie względem płaszczyzny rozdzielającej (do pobrania odpowiedniej części portala gdy go dzielimy).

Sprawdzamy jaka płaszczyzna leży powyżej sektora S5. Jest to płaszczyzna P9. Ponieważ jest ona taka sama jak płaszczyzna dużego portala to przechodzimy dalej. Sprawdzamy jaka płaszczyzna leży powyżej węzła P9. Jest to płaszczyzna P11. Ponieważ duży portal jest równoległy do płaszczyzny rozdzielającej P11 to go przepisujemy bez zmian i przechodzimy dalej. Sprawdzamy jaka płaszczyzna leży powyżej węzła P11.

Jest to płaszczyzna P4. Dzielimy duży portal tą płaszczyzną i bierzemy część leżącą z przodu tej płaszczyzny i przechodzimy dalej.

Dlaczego bierzemy część leżącą z przodu ?

Wynika to z informacji o stronie względem płaszczyzny rozdzielającej. Dla wskaźnika wskazującego na węzeł zawierający płaszczyznę P4 informacja ta to przód. Sprawdzamy jaka płaszczyzna leży powyżej węzła P4. Jest to NULL tzn. możemy zakończyć przycinanie dla dużego portala P9:

Sprawdzamy jaka płaszczyzna leży powyżej sektora S5. Jest to płaszczyzna P9. Ponieważ duży portal jest równoległy do płaszczyzny rozdzielającej P11 to go przepisujemy bez zmian i przechodzimy dalej. Sprawdzamy jaka płaszczyzna leży powyżej węzła P9. Jest to płaszczyzna P11. Ponieważ jest ona taka sama jak płaszczyzna dużego portala to przechodzimy dalej. Sprawdzamy jaka płaszczyzna leży powyżej węzła P11. Jest to płaszczyzna P4. Dzielimy duży portal tą płaszczyzną i bierzemy część leżącą z przodu tej płaszczyzny. Sprawdzamy jaka płaszczyzna leży powyżej węzła P4. Jest to NULL tzn. możemy zakończyć przycinanie dla dużego portala P11:

Sprawdzamy jaka płaszczyzna leży powyżej sektora S5. Jest to płaszczyzna P9. Dzielimy duży portal tą płaszczyzną i bierzemy część leżącą z przodu tej płaszczyzny i przechodzimy dalej. Sprawdzamy jaka płaszczyzna leży powyżej węzła P9. Jest to płaszczyzna P11. Ponieważ duży portal leży całkowicie po jednej stronie płaszczyzny rozdzielającej to go przepisujemy i przechodzimy dalej. Sprawdzamy jaka płaszczyzna leży powyżej węzła P11. Jest to płaszczyzna P4. Ponieważ jest ona taka sama jak płaszczyzna dużego portala to przechodzimy dalej. Sprawdzamy jaka płaszczyzna leży powyżej węzła P4. Jest to NULL tzn. możemy zakończyć przycinanie dla dużego portala P4:

Otrzymaliśmy podstawowe portale 1:N ograniczające sektor S5:

Krok 4

Tniemy duże portale płaszczyznami na których leżą ściany sektora S5. Jeżeli duży portal leży na jakiejś płaszczyźnie utworzonej na ścianie sektora to dodatkowo tniemy go płaszczyznami prostopadłymi do krawędzi tej ściany. W wyniku tego otrzymujemy następujące duże portale:

Krok 5

(Jest to jedna z ważniejszych części procedury generującej portale 1:N oraz 1:1 )

Znajdujemy duże portale przyległe do sektora S5. Portale które nie są portalami przyległymi usuwamy

Wszystkie portale otrzymane z podziału dużego portala P9 trafiają do sektora S5 i S4 a wszystkie portale otrzymane z podziału dużego portal P4 trafiają do S5 i S2. Portale otrzymane z podziału dużego portala P11 trafiają do sektorów S3 i S4. Ponieważ nie trafiają do S5 to znaczy że nie są przyległe do S5 i są usuwane.

W wyniku tego otrzymujemy następujące duże portale:

Krok 6

Usuwamy portale zawierające się w ścianach sektora S5. Usuwamy portale które nie zawierają się w przestrzeni lokacji. Otrzymujemy następujące portale dla sektora S5:

Otrzymaliśmy kompletne portale 1:N dla sektora S5. Podobnie jak dla sektora S5 liczymy portale dla pozostałych sektorów. (Można zauważyć że portale dla tej przykładowej lokacji są od razu portalami 1:1 i część druga procedury liczenia portali może być pominięta).

Krok 1

Każdy portal 1:N wybranego sektora dzielimy portalami z sektorów z którymi ten portal się łączy. W wyniku tego otrzymujemy nowy zbiór portali dla wybranego sektora.

Krok 2

Dzielimy otrzymane portale płaszczyznami leżącymi na ścianach należących do sektorów z którymi łączy się portal 1:N.

Krok 3

Powtarzamy krok 5 z procedury generującej portale 1:N.

Krok 4

Usuwamy portale które zawierają się w ścianach należących do sektora z którym dany portal się łączy.

Krok 5

Sprawdzamy czy dla każdego portala wybranego sektora istnieje odpowiadający mu portal w sektorze z którym ten portal się łączy. W wyniku tego powinniśmy otrzymać portale 1:1

Uwagi:

Sektory czyli ściany wygenerowane z drzewa BSP po dodaniu do nich portali mogą nie tworzyć już sektora !!!. Nie można dodać do procedury generującej portale warunków które przynależność portala do sektora będą opierały na warunku tworzenia sektora (ściany( = sektor) + portale mogą nie tworzyć sektora i jest to prawidłowe). Przykład:

Nie jest tutaj spełniony warunek przecinania i warunek leżenia ścian po jednej stronie a jest to poprawny zbiór (sektor + portale) !!!. 

Każdy kto zapoznał się z metodą programowej generacji portali zauważy że w wyniku działania procedury otrzyma zbiór sektorów z portalami (w naszym przykładzie będzie to zbiór sektorów S1-S5) oraz drzewo BSP z którego tworzyliśmy portale. Jeżeli zastanowić się nad tym głębiej to można dojść do wniosku że drzewo BSP nie jest już nam do niczego potrzebne. Wystarczy przyjąć jeden z sektorów jako sektor startowy gracza i możemy chodzić po lokacji bez drzewa BSP. Widoczność wszystkich ścian lokacji zapewniają nam portale i przez nie przechodzimy do kolejnych sektorów. Jeżeli czytelnik ma wiedzę o starszej metodzie nie opartej na wielokątach czyli metodzie rzucania promieni to może stwierdzić że metoda portali zachowuje się jak metoda rzucania promieni tzn. wybierane są tylko te ściany które są widoczne na danym kierunku czyli znajdują się w stożku widzenia gracza.

Zalety:

Możemy wygenerować portale dla dowolnie dużej lokacji (musi być poprawnie zbudowana) zapisanej w drzewie BSP 3D. Dobrze napisany program generujący portale 3D jest tak szybki jak program generacji drzewa BSP 3D. Możemy pozbyć się drzewa BSP 3D po wygenerowaniu portali. Możemy dynamicznie przetwarzać i modyfikować scenę. Metoda portali zapewnia poprawne widzenie postaci (cecha drzew PVS 3D ). Prędkość renderowania może być większa niż w drzewach PVS 3D (dla bardzo prostych lokacji). Algorytm nadaje się również do otwartych przestrzeni.

Wady:

Złożoność i skomplikowanie program generacji i renderowania. Grafika musi być poprawnie zbudowana. Bardzo ważny jest program generacji drzewa BSP 3D (zły lub nieoptymalny program generacji to złe lub nieoptymalne portale 3D).

Mając dla każdego sektora wygenerowane portale możemy bardzo szybko zbudować statyczne listy PVS.

Przykład generacji statycznych list PVS:

Nasza przykładowa scena po wygenerowaniu portali:

Dla sektora S5 portal p2 to P9 (z przykładu liczenia portali dla sektora S5) natomiast portal p1 to P4 (z przykładu liczenia portali dla sektora S5).

Patrząc na zewnątrz sektora z wierzchołków wszystkich portali należących do sektora określamy widoczne sektory tworzące listy PVS dowiązane do portali:

Dla sektora S1 są to sektory (S3, S4, S5 dla portala p1).

Dla sektora S2 są to sektory (S3, S4, S5 dla portala p1).

Dla sektora S3 są to sektory (S1 dla portala p1), (S2, S4, S5 dla portala p2).

Dla sektora S4 są to sektory (S1, S3 dla portala p1), (S2, S5 dla portala p2).

Dla sektora S5 są to sektory (S1, S3, S4 dla portala p2), (S2 dla portala p1).

Po dodaniu do sektorów drzewa BSP portali z listami PVS otrzymujemy nowe drzewo BSP + Portale + PVS. Takie drzewo zapewnia bardzo szybkie wyświetlanie grafiki z każdego punktu sceny i jest wykorzystywane w grach 3D. Cechą tego drzewa jest zawężanie list PVS na kierunkach poprzez portale. Jeżeli portal nie jest widoczny w stożku widzenia gracza to nie jest przetwarzana jego lista PVS.