Portale


Portale (ang. Portals) są wirtualnymi ścianami, które łączą ze sobą zbiory wielokątów. Mając wygenerowane portale wykorzystujemy je np. do budowy list PVS lub dynamicznego ustalana widocznych wielokątów. Istnieją dwie podstawowe metody dynamicznego ustalania widocznych wielokątów i ich renderowania przy użyciu portali. Poniżej przedstawiony jest schematyczny opis pierwszej metody:
  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 nowy zbiór ścian z sektora, z którym dany portal się łączy i renderujemy ten zbiór.
  4. Przechodzimy do punktu 2.
Druga metoda polega na przycinaniu (ang. Clipping) kolejno przetwarzanych portali w przestrzeni 2D lub 3D. Poniżej przedstawiony jest jej schematyczny opis.
  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. Płaszczyzny tnące tworzymy pomiędzy każdą krawędzią portala i punktem, w którym znajduje się gracz.
  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.
Portale mogą zostać wykorzystane do utworzenia list PVS dla drzew BSP. Opis utworzenia list PVS dla portali drzewa BSP 3D znajduje się w artykule Listy PVS. Poniżej przedstawiona została zasada renderowania grafiki zapisanej w drzewie BSP 3D z portalami i dowiązanymi do nich listami sektorów widocznych PVS.
  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 listy PVS dla tego portala.
  5. Dla kolejnych sektorów z listy PVS renderujemy zbiory ścian.
  6. Przechodzimy do punktu 3.
Portale dla drzewa BSP 3D możemy wygenerować stosując algorytm opisany poniżej. Algorytm ten wykorzystuje gotowe drzewo BSP 3D. Przed przystąpieniem do generowania portali należy dodać następujące informacje do drzewa BSP 3D:
  1. 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.
  2. Opis, 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 jego utworzenie.
Po wprowadzeniu tych informacji otrzymujemy następujące drzewo BSP:


Portale wygenerowane dla wybranego sektora drzewa BSP 3D są brakującymi ścianami ograniczającymi jego obszar. Właściwa procedura generowania portali składa się z dwóch podstawowych części:
  1. Procedury generującej portale 1:N. Procedura ta generuje portale, które łączą N sektorów
  2. Procedury generującej portale 1:1. Procedura ta przetwarza portale 1:N i generuje nowe portale, które łączą ze sobą pojedyncze sektory.
Procedura generująca portale 1:N:
Krok 1
Wybieramy kolejne sektory, dla których będziemy budować portale.

Przykład:
Wybieramy sektor S5. Pełna procedura generująca portale powinna pobierać kolejno sektory od S1 do S5 i budować dla nich 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 takiej, że jej rozmiar jest znacznie większy niż rozmiar sceny. Orientacja ściany jest zgodna z kierunkiem wektora normalnego ściany. Algorytm tworzenia dużego portala opisany jest w artykule Podstawy grafiki 3D.

Przykład:
Budujemy duże portale na płaszczyznach P9,P11,P4. Płaszczyzny, na których budujemy duże portale odczytujemy wykorzystując pierwszą modyfikację, którą wprowadziliśmy do drzewa BSP a mianowicie wskaźnik na węzeł poprzedzający (ang. Parent). Dla S5 kolejne pobierane płaszczyzny to P9,P11,P4 i na nich budujemy duże portale:


Krok 3
Dla każdego dużego portala poruszając się od sektora do korzenia wykonujemy cięcia płaszczyznami rozdzielającymi biorąc 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 przepisujemy go 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.

Przykład:
Przycinamy kolejno duże portale P9, P11, P4. Do pobierania kolejnych płaszczyzn tnących wykorzystujemy wskaźnik na węzeł poprzedzający. Do pobierania odpowiedniej części portala po jego podzieleniu wykorzystujemy informację o stronie względem płaszczyzny rozdzielającej.

1. Przycięcie dużego portala P9 zbudowanego na płaszczyźnie P9:
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ą biorąc część leżącą z przodu tej płaszczyzny i przechodzimy dalej. 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:


2. Przycięcie dużego portala P11 zbudowanego na płaszczyźnie P11:
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ą biorąc 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:


3. Przycięcie dużego portala P4 zbudowanego na płaszczyźnie P4:
Sprawdzamy, jaka płaszczyzna leży powyżej sektora S5. Jest to płaszczyzna P9. Dzielimy duży portal tą płaszczyzną biorąc 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 przepisujemy go 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, dla którego znajdujemy portale. Jeżeli duży portal leży na płaszczyźnie ściany to dodatkowo tniemy go płaszczyznami prostopadłymi do krawędzi tej ściany.

Przykład:
Tniemy duże portale płaszczyznami, na których leżą ściany sektora S5. Jeżeli duży portal leży na płaszczyźnie ściany to dodatkowo tniemy go płaszczyznami prostopadłymi do krawędzi tej ściany. Otrzymujemy następujące duże portale:


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 w tablicy wszystkie sektory różne od sektora, dla którego liczymy portale, do których trafi nasz portal. Sektory te są sektorami, z którymi łączy się nasz portal. Procedura sprawdzania przyległości portala do sektora jest rekurencyjna. W procedurze tej mamy trzy przypadki:
  1. Jeżeli portal leży po jednej ze stron płaszczyzny danego węzła drzewa BSP to wywołujemy ją ze wskaźnikiem tej strony.
  2. Jeżeli portal przecina płaszczyznę danego węzła drzewa BSP to wywołujemy ją ze wskaźnikiem do obu stron.
  3. Jeżeli portal leży na płaszczyźnie danego węzła drzewa BSP to wywołujemy ją ze wskaźnikiem do obu stron.
Po wykonaniu procedury sprawdzamy czy w tablicy znajduje się sektor, dla którego liczymy portale. Jeżeli jest to portal jest portalem przyległym i należy go do zachować.

Przykład:
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. Otrzymujemy następujące duże portale:


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

Przykład:
Usuwamy portale zawierające się w ścianach sektora S5. Usuwamy portale, które nie zawierają się w przestrzeni sceny. Otrzymujemy następujące portale dla sektora S5:

Po wykonaniu kroku 6 otrzymujemy 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 przykładowej sceny są od razu portalami 1:1 i część druga procedury liczenia portali może zostać pominięta.

//Procedura generująca portale 1:1:
//krok 1
Każdy portal 1:N wybranego sektora dzielimy portalami sektorów przyległych. W wyniku tego otrzymujemy nowy zbiór portali dla wybranego sektora.

//krok 2
Dzielimy otrzymane portale płaszczyznami ścian należących do sektorów przyległych.

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

//krok 4
Usuwamy portale, które zawierają się w ścianach sektorów przyległych.

//krok 5
Sprawdzamy czy dla każdego portala wybranego sektora istnieje odpowiadający mu portal w sektorze przyległym. W wyniku tych operacji otrzymujemy portale 1:1.


Autor: Mirosław Kozioł, Komires Sp. z o.o.

Numer artykułu: 21
Wysłany: Sun, Feb 14, 2010 2:23 PM
Ostatnio zmieniony: Wed, Feb 17, 2010 4:22 AM

Adres URL: https://www.komires.net/article.php?id=21