Wstęp do nowoczesnego rysowania terenu z wykorzystaniem GPU
Wstęp
Zdecydowana większość współczesnych gier trójwymiarowych posługuje się terenem. Często wyznacza on płaszczyznę rozgrywki, w której znajduje się nasz awatar lub wrogie jednostki. Abstrahując od jego rozmiarów – czasem widzimy tylko małą jego część (Company of Heroes, Titan Quest, Command & Conquer 3 - Tiberium Wars), zaś czasem możemy go całego ogarnąć z lotu ptaka (Supreme Commander, TA Spring, RollerCoaster Tycoon 3). Wiele gier posiada teren, który zazwyczaj obserwujemy z punktu widzenia postaci znajdującej się na nim, przeważnie patrząc na horyzont (Far Cry, S.T.A.L.K.E.R. - Shadow of Chernobyl, The Elder Scrolls 4 - Oblivion). Od dawna stosowane są również planety, czyli niejako tereny kuliste (Populous 3, Elite Frontier). W wielu produkcjach gracze mieli ponadto sposobność wpływania na samo jego ukształtowanie. W dodatku bardziej wyszukane gry pokrywały teren trawą lub lasem (Black & White 2, Operation Flashpoint).
Cała ta różnorodność każe nam myśleć o terenie jako rozwiązaniu ściśle dedykowanym. Nie można stworzyć uniwersalnej implementacji w tej dziedzinie. Nawet tak wyszukany i skalowany system, jakim z pewnością jest Google Earth, nie nadaje się do zastosowania w grach. Nie zawsze wykorzystanie zaawansowanych metod renderowania terenu do prostych aplikacji jest korzystne – złożoność kosztuje, nigdzie bardziej, niż w grafice komputerowej.
Współczesne silniki graficzne dosyć mocno osadzone są na programowalnych jednostkach przetwarzania, czyli bazują na programowaniu z wykorzystaniem GPU (ang. Graphics Processing Unit). Każdy rysowany trójkąt jest renderowany przy użyciu konkretnej techniki. Rysujemy różne elementy sceny trójwymiarowej wielokrotnie przy wykorzystaniu różnych technik, aby uzyskać realistyczne oświetlenie, wyrafinowane cienie, falującą wodę czy estetyczne wgłębienia pomiędzy cegiełkami posadzki.
Nasz teren, podobnie jak każdy widoczny element sceny, musi umieć narysować się w różnych kontekstach; czasami zechcemy wypełnić tylko Z-buffer, czasem narysować mały fragment terenu oświetlany światłem latarki. To szalenie komplikuje stworzenie w miarę elastycznego rozwiązania, stąd prawie zawsze będziemy chcieli iść w tej dziedzinie na solidny kompromis; przykładowo, ograniczymy się do uwzględnienia tylko jednego światła kierunkowego – najczęściej powiązanego z tzw. daylight system, czyli całokształtem efektów (głównie świetlnych) związanych z dobowym cyklem ruchu słońca po sferze niebieskiej. Stworzenie kompletnego systemu do wspomagania rysowania terenu jest bardzo kosztowne. Polecam podejrzenie istniejących rozwiązań w jakimś silniku dla gier, np. OGRE 3D (http://www.ogre3d.org/).
Podstawowe wiadomości
Chcąc narysować teren musimy narysować jego wierzchnią (widoczną) powierzchnię. Renderowanie podziemnych warstw skalnych raczej nie przyniesie nam żadnych korzyści, jako że są one ukryte przez wzrokiem obserwatora. Nie oznacza to, że nie można posiłkować się dodatkowymi powierzchniami (flora, woda), jednak zasadniczo problematyka terenu koncentruje się na metodach budowania i rysowania siatki trójkątów odzwierciedlających jego wierzchnią warstwę.
Zarządzanie terenem można podzielić na dwa zasadnicze podproblemy: zarządzenie kształtem terenu oraz zarządzaniem wyglądem jego pokrycia. Pierwszy aspekt wiąże się ściśle z wysokością wierzchołków siatki terenu, zaś drugi – z doborem odpowiednich kolorów renderowanych pikseli. Te problemy są w dużej mierze rozłączne, jednak tylko poprawna implementacja ich obydwu przyniesie zamierzone rezultaty.
Każdy teren wymaga kilku źródeł danych. Aby odzwierciedlić kształt terenu, potrzebna jest mapa wysokości (ang. height map), czyli tekstura, która dostarcza informacji o względnej wysokości wierzchołków siatki trójkątów. Ponadto będziemy chcieli pokryć nasz teren jedną lub więcej teksturami, aby stworzyć złudzenie trawy, piasku, czy kamiennej posadzki. Różne rozwiązania korzystają z dodatkowych źródeł danych. Niektóre implementacje korzystają z obrazów, które w całości nie mieszczą się w pamięci RAM, nie wspominając o pamięci karty graficznej. Nierzadko w grach komputerowych możemy zaobserwować dodatkową, szczegółową teksturę ziemi, w promieniu kilkunastu metrów od naszej postaci. W grze The Elder Scrolls 4 – Oblivion bardzo wyraźnie widać podział na teren bliski i daleki – każde z nich wymaga swoich specyficznych źródeł danych.
Istnieje wiele sposobów na zarządzanie siatkami terenu. Wiele z nich się zdezaktualizowało przez dominację metodyki odciążenia CPU (ang. Central Processing Unit) na rzecz GPU i, w ostatecznym rozrachunku, optymalizację w nich zastosowane, z obecnego punktu widzenia, wprowadzają niepotrzebny chaos i niezdarnie hamują wydajność całej aplikacji. Metody zawarte w tym opracowaniu bazują na możliwości odczytu z tekstur (ang. texture fetch) z poziomu vertex shadera dostępnego w standardzie Shader Model 3.0. To właśnie ta operacja pozwala na kształtowanie terenu nie wcześniej jak w samym vertex shaderze. Ma to kolosalny wpływ na finalną wydajność renderingu, jako że pozbywamy się dynamicznych siatek trójkątów, więc i czasochłonnych transferów dużej ilości danych wierzchołków pomiędzy pamięcią RAM a pamięcią karty graficznej. Kod pixel shadera nadaje ostateczny kolor powierzchni terenu.
Rozwiązanie podstawowe
Wyobraźmy sobie mapę wysokości o rozmiarach 512 x 512 pikseli. Gdybyśmy chcieli utworzyć możliwie najdokładniejszą siatkę trójkątów o takich rozmiarach, na ten cel potrzebowalibyśmy ponad 500 000 trójkątów. To o dwa rzędy wielkości zbyt wielka liczba. Raczej nie powinniśmy operować siatkami większymi niż 64 x 64 (7938 trójkątów), co wcale nie oznacza, że nasz teren nie może składać się z kilkunastu tysięcy (lub kilkudziesięciu tysięcy) trójkątów. Choć ostatecznie i tak średnia liczba renderowanych trójkątów jest zdeterminowana przez ustawienia szczegółowości grafiki, podejście minimalistyczne jest tutaj jak najbardziej pożądane.
Nie możemy na raz przekazać tak dużego zbioru danych do wyświetlenia. Nawet gdybyśmy mogli, szybko zauważymy, że jest to swojego rodzaju marnotrawstwo. Teren, podobnie jak każdy widzialny obiekt sceny, renderowany jest z pewnego widoku (potocznie: kamery), który można opisać macierzami widoku i projekcji, oraz związaną z nimi piramidę widzenia (ang. frustum). Okazuje się, że gdyby fragmenty terenu, które są odległe od obserwatora, były kilkukrotnie mniej dokładne (pokrycie siatką trójkątów było rzadsze), otrzymany obraz zasadniczo nie różniłby się od tego wyrenderowanego dużym nakładem szczegółowości geometrii – różnice byłyby pomijalnie małe; zarówno w kontekście wysokich kosztów techniki jak i ograniczonej percepcji oka ludzkiego. Jakby nie patrzeć, grafika trójwymiarowa jest sztuką iluzji; umiejętnością zanurzania ludzkich zmysłów w wielkim, teatralnym, wirtualnym oszustwie.
Nic jednak nie stoi na przeszkodzie, aby można było wykorzystać pokaźną teksturę jako mapę wysokości, o rozmiarach sięgających nawet 2048 x 2048, zajmującą 4 MB (w formie nieskompresowanej). Takie wymiary tekstur to w zasadzie praktyczne maksimum. Możemy posługiwać się obrazami o rozmiarach nawet 16384 x 16384, zajmujących 256 MB, jednak do shadera należy przekazywać tylko tekstury o rozsądnie małych rozmiarach, czyli do kilkunastu megabajtów – mogą to być wycinki większej całości, lub obrazy odpowiednio pomniejszone.
Jak już wcześniej stwierdziliśmy, rysowanie doskonale szczegółowego terenu jest tak samo niewykonalne, jak i nierozsądne. Podstawowym rozwiązaniem jest zbudowanie sztywnej siatki płatu terenu, powiedzmy 64 x 64 wierzchołki (7938 trójkątów), oraz odpowiednie wodzenie jej za widokiem kamery, automatycznie nadając wysokość jej wierzchołkom w vertex shaderze. Zamiast pojedynczego płata można rysować całą grupę płatów. Płynne wodzenie za widokiem siatek terenu może powodować lekkie falowanie jego powierzchni, stąd płat można przemieszczać skokowo. Jeśli używamy całej grupy płatów, nie trzeba ich w ogóle przesuwać – w miarę przemieszczania się kamery, dodajemy i usuwamy płaty do i z grupy płatów tak, aby uzyskać efekt jednolitego terenu.
Rysunek 1 - Pojedynczy płat terenu pokrywa całe pole widzenia. Obserwator nie jest świadom krawędzi płata, jako że wykracza on poza widok.
Rysunek 2 - Płaty są dynamicznie dostawiane, aby pokryć zmieniające się pole widzenia. Lepiej, żeby pole widzenia nie objęło horyzont.
W przypadku gier RTS, ze sztywno określoną maksymalną wysokością kamery oraz widokiem skierowanym w dół lub pod niewielkim kątem, metoda ta przynosi najlepsze rezultaty. Zdecydowanie gorzej sprawuje, gdy kamera nie jest skierowana w dół (bez względu na jej wysokość), czyli również w przypadku gier FPP. Obszar blisko obserwatora jest zbyt mało dokładny, a odległe wzniesienia są zbyt kanciaste. Posługując się dynamicznie dostawianym zestawem płatów, problematyczne jest pokrycie dużych obszarów terenu, jako że wymaga to dużej liczby płatów.
Przedstawiona technika jest zdecydowanie najprostszą i najszybszą ze wszystkich zaprezentowanych w tym opracowaniu - powinna być użyta wszędzie tam, gdzie spełnia wymogi związane ze spodziewanym widokiem i pracą kamery.
Zmienny poziom szczegółowości
Rozwiązanie, przedstawione w poprzednim dziale, jest niedoścignione w swojej prostocie, jednak w rzeczywistości tylko mała część gier może pozwolić sobie na taki teren. Większość gier, szczególnie FPP, potrzebuje terenu adaptującego się do bieżącego widoku tak, aby minimalizować niepotrzebne detale oraz sam narzut spowodowany zarządzeniem zmienną szczegółowością (ang. level of detail lub w skrócie LOD).
Zamiast posługiwać się jedną siatką trójkątów, można przygotować sobie kilka geometrii płatów terenu o różnych stopniach szczegółowości. Dzięki temu można ulepszyć poprzednio opisane rozwiązanie korzystające z zestawu płatów. O ile poprzednio poszczególne komórki zestawu płatów terenu rysowane były jako identyczne płaty, teraz można zdecydować z jaką dokładnością dany płat ma zostać narysowany.
Podczas inicjalizacji terenu należy przygotować kilka zestawów siatek płatów terenu o różnych rozmiarach; dobrym wyborem są siatki 1 x 1, 2 x 2, 4 x 4, 8 x 8, 16 x 16, 32 x 32, 64 x 64. Każda zmiana widoku wymusza aktualizację informacji płatów-komórek. O ile poprzednio należało tylko zdecydować, czy dany płat jest widoczny, teraz trzeba określić poziom jego szczegółowości, czyli przykładowo liczbę z przedziału od 0 do 6. W tym celu należy posłużyć się heurystyką oceniającą, jak redukcja poziomu detali płata wpływa na jego wygląd.
Najprościej policzyć odwrotność odległości obserwatora do płata. Metoda ta jednak powoduje powstawanie tzw. poppingu – ruch obserwatora przy powierzchni terenu powoduje okresowe zmiany poziomu szczegółowości odległych wzniesień, co niestety nie wygląda rewelacyjnie. Jednak jak to możliwe, że w grze Far Cry nie zwracamy uwagi na popping (lub nawet nie jesteśmy jego świadomi)? Teren pokryty jest bujną roślinnością – jest ona praktycznie nieodzowna dla gier FPP; w przypadku gier RTS nie ma to tak wielkiego znaczenia. Bardziej zaawansowanym podejściem jest rozbudowanie heurystyki poziomu szczegółowości płata o dodatkowe uwzględnienie zmiany wysokości terenu w obszarze płata z perspektywy obserwatora. Sposób ten wymaga wstępnych obliczeń przeprowadzonych na mapie wysokości.
Przedstawiony mechanizm z powodzeniem może być zastosowany przy rysowaniu planet, o ile obserwator nie wzniesie się zbyt wysoko.
Drzewa czwórkowe
Do tej pory rozpatrywaliśmy płaty, jako siatki rysowane w tych samych rozmiarach. Ułatwiało to układanie z nich kwadratowej mozaiki. Co by było jednak, gdybyśmy dopuścili rozmiary płata będące wykładniczą wielokrotnością bazowej wielkości? Z pewnością to nie ułatwiłoby nam zarządzania terenem, jednak umożliwiłoby budowanie dowolnie złożonych fragmentów terenu oraz jego upraszczanie - teoretycznie nawet do pojedynczego, dużego płata, jeśli obserwator byłby wystarczająco daleko.
Jako że płaty są kwadratowe, najlepiej posłużyć się drzewami czwórkowymi do przechowywania informacji o bieżącej strukturze terenu w odniesieniu do bieżącego widoku kamery. Jeśli używanych jest kilka kamer obserwujących świat z możliwie diametralnie różnych punktów widzenia, przechowywanie kilku drzew czwórkowych (w kontekście poszczególnych widoków) jest rozsądnym rozwiązaniem. Niekiedy nie jest to konieczne, jednak wszystko zależy od woli projektanta silnika 3D.
Budowę drzewa czwórkowego terenu zaczynamy od korzenia – węzeł reprezentuje całościowy model struktury terenu. Jeśli stwierdzimy, że dany węzeł wymaga większego poziomu szczegółowości, dzielimy jego płat na cztery (dwukrotnie mniejsze) części budując cztery węzły-dzieci. Proces powtarzamy rekurencyjnie. Jeśli stwierdzimy, że dany płat na pewno nie przetnie się z piramidą widzenia, możemy oznaczy go jako płat niewidoczny i tym samym przerwać budowę tej gałęzi drzewa. Również węzły niebędące liśćmi nie są rysowane – tylko węzły liście mogą reprezentować widzialne płaty.
__Rysunek 3 - Konstrukcja struktury terenu opartej o drzewa czwórkowe przebiega w sposób rekursywny.
Na biało oznaczone są nieprzeanalizowane gałęzie drzewa. Kolorem czerwonym oznaczone są niewidoczne płaty terenu, zaś zielonym - płaty widzialne.__
Można połączyć zalety terenu opartego o drzewo czwórkowe oraz terenu-mozaiki ze zmiennym poziomem szczegółowości, poprzez umożliwienie płatom drzewa czwórkowego przybierania różnych poziomów szczegółowości, przykładowo jeden spośród siedmiu możliwych. Podczas budowy takiego drzewa, rozpatrując każdy węzeł stwierdzamy, czy jest on widoczny. Jeśli tak – decydujemy, czy dzielić go dalej, czy też wybrać jeden z kilku poziomów szczegółowości.
Nie trzeba za każdym razem budować drzewa czwórkowego na nowo. Po pierwsze: wystarczy to robić, gdy widok zmieni się bardziej niż założony próg tolerancji. Po drugie: drzewo nie musi być na nowo budowane – algorytm powinien umieć zarówno budować nowe drzewo jak i aktualizować istniejące.
Drzewa czwórkowe sprawiają, że teren jest bardzo adaptowalny do pozycji kamery. Umożliwia to rysowanie terenów zręcznie oddających detale mapy wysokości, którą zaopatrzyliśmy nasz mechanizm. Sprawdzają się zarówno w grach FPP jak i RTS. Z jednak drugiej strony są bardziej złożone i wprowadzają pewien narzut związany z obsługą drzewa czwórkowego.
Dziury
Zarówno teren-mozaika o zmiennym poziomie szczegółowości, jak i teren wzbogacony o drzewo czwórkowe, mają niedopuszczalną wadę: po narysowaniu terenu widać dziury. Niestety, jest to surowa cena za zróżnicowanie odległości pomiędzy wierzchołkami rysowanych siatek trójkątów. Płaty bardziej dokładne niezdarnie ujawniają prześwity na krawędziach sąsiadujących z płatami mniej dokładnymi (stąd problem ten nie dotyczy terenu opartego o siatkę równomierną). Jest to efekt tzw. T-cracków.
__Rysunek 4 - T-crack - efekt niedopasowania krawędzi płata dokładniejszego do krawędzi płata mniej dokładnego.
Na czerwono zaznaczono prześwit, który drastycznie obniża wizualną jakość terenu.__
Generalnie są dwa sposoby eliminacji dziur w terenach renderowanych z silnym wsparciem GPU:
- Obudowanie siatek płatów podstawką.
- Sklejenie problematycznych wierzchołków z krawędziami sąsiednich płatów.
Najprostsze rozwiązanie pozwala nam szybko zapomnieć o problemie T-cracków. Jest sprytne, proste w implementacji, wprowadza bardzo niewielki impakt na kod vertex shadera. Z drugiej strony tworzy niepozorne artefakty wizualne – tam, gdzie byłaby dziura, znajduje się pionowa ścianka. Jednak takie rozwiązanie satysfakcjonuje prawie każdy teren.
Rysunek 5 - Ukształtowana siatka płatu terenu obudowanego ścianami bocznymi.
Planety
Techniki związane z zarządzeniem i rysowaniem planet zasadniczo nie odbiegają od tych stosowanych przy terenach. Planetę można rysować jako mozaikę płatów o stałych rozmiarach, jak i w oparciu o drzewo czwórkowe. Drugie rozwiązanie, poprawnie zaimplementowane, jest na tyle skalowalnym rozwiązaniem, że pozwala traktować planetę zarówno jako odległy obiekt w przestrzeni kosmicznej, jak i klasyczny, lekko zakrzywiony, teren, dla obserwatora znajdującego się przy powierzchni ziemi. Niestety, zastosowanie pojedynczej mapy wysokości praktycznie ogranicza wielkość globu do niewielkich rozmiarów asteroid - spore planety wyglądają dobrze tylko z dużych odległości.
Budując mozaikę płatów trzeba pamiętać, że lewymi sąsiadami pierwszej kolumny płatów są płaty z ostatniej kolumny. Dotyczy wszystkich płatów mozaiki na wszystkich czterech jej krawędziach. W przypadku rozwiązania opartego na drzewach czwórkowych, wygodnie jest dokonywać pierwszego podziału drzewa nie na cztery, a na osiem węzłów tak, aby rozmiar pionowy był równy rozmiarowi poziomemu.
Aby nakładane na kulę płaty były odpowiednio zakrzywione, należy posłużyć się współrzędnymi biegunowymi przy ich pozycjonowaniu.
Program w vertex shaderze musi wykonać zaledwie dwa mnożenia i dwukrotnie wywołać funkcję sincos(), aby zamienić współrzędną biegunową na wektor normalny.
Z drugiej strony posługiwanie się współrzędnymi biegunowymi skupia większą liczbę wierzchołków wokół biegunów.
Wady tej nie posiada mechanizm, który zamiast płatów kwadratowych wykorzystuje płaty trójkątne, jednak to opracowanie nie opisuje tej grupy rozwiązań.
__Rysunek 6 - Przykładowa aplikacja renderująca planetę w oparciu o drzewa czwórkowe.
(A) Bez eliminacji T-cracków. (B) Z eliminacją T-cracków. (C) Planeta z bliska. (D) Anomalie na biegunach planety, związane ze sposobem teksturowania i pozycjonowania płatów.__
Podsumowanie
Zawarte w tym dokumencie informacje to jedynie niezgrabne przedstawienie kilku podstawowych rozwiązań. Prawdziwe implementacje, stworzone na użytek gier komercyjnych, są o wiele bardziej złożone i każde z nich jest na swój sposób unikatowe. Ponadto zagadnienie formowania siatki terenu z jednakowych płatów to tylko część problemu. Równie trudne jest ustalanie koloru renderowanych pikseli.
Jeśli dotrwałeś do końca tego opracowania, drogi Czytelniku, to liczę, że nie uważasz tej lektury za stratę czasu. Z pewnością dokument ten jest daleki od doskonałości, jednak od samego początku w intencjach autora miał być tylko pobieżnym spojrzeniem pod skorupę współczesnej metodologii zarządzania i rysowania terenu.
Źródła:
- Harald Vistnes (2006), Game Programming Gems 6, Sec. 5.5, GPU Terrain Rendering, Charles Rivers Media.
- Własne - mniej lub bardziej udane - eksperymenty.
Aby dodawać komentarze musisz być zalogowany!