Normalne w terenie

Parę dni temu przyszło mi w końcu napisać coś, co wielu programistów grafiki pewnie już nie jeden raz miało okazję kodować. Chodzi o generowanie siatki terenu na podstawie predefiniowanej mapy wysokości (heightmap), zapisanej w pliku jako obrazek w odcieniach szarości.

Cała procedura nie jest bardzo skomplikowana. W sumie sprowadza się ona do równomiernego próbkowania obrazka mapy i tworzenia wierzchołków leżących na ustalonej płaszczyźnie, z uwzględnieniem odczytanej wysokości.
Pozycje tych wierzchołków wyznaczyć jest prosto, chociaż zależy to trochę od przyjętej reprezentacji płaszczyzny (a właściwie prostokąta) “poziomu morza”. Trochę więcej zabawy jest natomiast z wektorami normalnymi, które niewątpliwie przydadzą się, jeśli nasz teren będziemy chcieli oświetlić. Właśnie o ich znajdowaniu chciałem napisać.

Jak wiadomo, wierzchołki dowolnej siatki możemy wyposażyć w normalne, posługując się niezwykle przydatną operacją iloczynu wektorowego. Przy jego pomocy można obliczyć normalne dla poszczególnych trójkątów; w przypadku wierzchołków należy po prostu uśrednić wyniki dla sąsiadujących z nimi face‘ów (oznaczonych niżej jako T(v)):

Konieczną normalizację niektórzy przeprowadzają tu na końcu, a inni dla poszczególnych trójkątów. Prawdę mówiąc nie wiem, które podejście jest właściwsze – jeśli którekolwiek.

W powyższy sposób można oczywiście wyliczać normalne również dla utworzonego terenu, bo przecież czym on jest, jak właśnie siatką :) Jednak w tym przypadku mamy dostęp do większej liczby informacji o nim. Mamy przecież źródłową mapę wysokości, z której na wierzchołki przerobiliśmy tylko niektóre piksele (plus ew. jakieś ich otoczenia). Czemu by nie wykorzystać jej w większym stopniu, generując być może lepsze przybliżenie normalnych?
Ano właśnie, dlaczego nie :) W tym celu można by wprowadzić nieco wyższej (dosłownie) matematyki i zauważyć, że nasza heightmapa jest zbiorem wartości pewnej funkcji i że wobec tego normalną w jakimś punkcie x₀, y₀ da się wyliczyć jako:

o ile tylko rzeczone pochodne istnieją. Można by – ale przecież nie będziemy tego robili ;-) Zamiast tego wystarczy zastanowić się, co by było, gdybyśmy wygenerowali skrajnie gęstą siatkę dla naszego terenu: tak gęstą, że każdemu pikselowi heightmapy odpowiadałby dokładnie jeden wierzchołek tej siatki. Wówczas opisana wyżej metoda liczenia normalnych korzystałaby ze wszystkich informacji zawartych w mapie.
Nie musimy jednak generować tych wszystkich wierzchołków. Do obliczenia wektora normalnego w punkcie wystarczą tylko dwa, odpowiadające – na przykład – pikselowi heightmapy położonemu bezpośrednio na prawo i u dołu tego, z którego “wzięliśmy” dany wierzchołek siatki. Z tych trzech punktów możemy następnie złożyć trójkąt, obliczyć wektor normalny i zapisać go w wierzchołku siatki:

Tutaj oznacza odpowiedni piksel mapy wysokości, a funkcja pos3d jest tą, która dla owego pikseli potrafi wyliczyć pozycję odpowiadającego mu wierzchołka w wynikowej siatce. (Taką funkcję mamy, bo przecież jakoś generujemy tę siatkę, prawda? :])

Z podanych sposobów obliczania normalnych terenu można oczywiście korzystać niezależnie od tego, z jaką biblioteką graficzną pracujemy. Jak to jednak często bywa, w DirectX sporo rzeczy mamy zaimplementowanych od ręki w postaci biblioteki D3DX i nie inaczej jest z liczeniem normalnych.
I tak funkcja D3DXComputeNormals potrafi wyliczyć wektory normalne dla dowolnej siatki – warunkiem jest to, żeby była ona zapisana w postaci obiektu ID3DXMesh, więc w razie potrzeby musielibyśmy takowy obiekt stworzyć. Z kolei D3DXComputeNormalMap potrafi stworzyć mapę normalnych na podstawie mapy wysokości; tę pierwszą możemy później indeksować w celu pobrania “wektorów normalnych pikseli”.

Płaska wizualizacja funkcji 3D

Źródło

Funkcje, których dziedziną jest podzbiór R² (czyli płaszczyzna) ciężko jest przedstawić na płaskim ekranie w sposób poglądowy, a jednocześnie pozwalający na odczytanie jakichś wartości. O ile bowiem izometryczny rzut 3D wygląda efektownie, to poza ogólnym kształtem powierzchni nie przedstawia wielkiej ilości informacji. Sprawa wygląda trochę lepiej, jeśli taką figurę możemy jeszcze obracać… co aczkolwiek może być z kolei trudne do zrealizowania np. na wydruku :]

Źródło

Jednym z wyjść może być tutaj zastosowanie sposobu używanego do map wysokości w grach. Nietrudno zauważyć, że są one niczym innym jak właśnie funkcjami typu R²->R, a reprezentowane są najczęściej jako bitmapy w odcieniach szarości: jasność piksela x,y odpowiada w nich wysokości odpowiedniego punktu terenu.
Takie heightmapy wprawdzie łatwo się rysuje, ale niespecjalnie nadają się do pokazania jako ilustracja czegokolwiek – odcienie szarości są przecież z definicji szare i nieciekawe :) Dlatego bardzo spodobał mi się prosty pomysł na uczynienie tej reprezentacji znacznie ładniejszą, o którym to usłyszałem niedawno.

Idea jest prosta: po co używać samych szarości, skoro mamy do dyspozycji całą paletę kolorów?… Każdy kolor w reprezentacji RGB jest przecież tożsamy z liczbą, co widać najbardziej, jeśli weźmiemy jego typową reprezentację 32-bitową:

W niej “największym” kolorem jest kolor biały (0x00FFFFFF, czyli 2²⁴ – 1), zaś “najmniejszym” czarny (0x0), a pomiędzy nimi włącznie występuje każdy z 256³ możliwych kolorów. Jeśli teraz przeskalujemy wartości naszej funkcji do tak określonego przedziału (lub nieco mniejszego), a następnie przekonwertujemy każdą z tych 32-(a właściwie 24-)bitowych liczb na odpowiadający jej kolor RGB, to otrzymamy w ten sposób heightmapę o znacznie bogatszej palecie barw niż poprzednio.
Jeśli ponadto używamy dokładnie takiej reprezentacji liczbowej kolorów, jak powyżej (najmłodsze bity na kolor niebieskie, a najstarsze używane na czerwony), to zauważymy, że rozkład barw w wyniku jest całkiem znajomy. I tak obszary niebieskie odpowiadają wartościom najmniejszym, zielone średnim, żółte – wysokim, a czerwone – najwyższym. Łącznie przypomina mapę hipsometryczną – czyli, jakby nie patrzył, mapę wysokości właśnie :)

Do czego może przydać się takie cudo, oprócz wspomnianej już wizualizacji funkcji R²->R na płaszczyźnie? Pewnie do niewielu rzeczy :) Ja wpadłem jednak na jeszcze jedno potencjalne zastosowanie.
Ponieważ wynikowy obrazek używa tak “geograficznych” barw, może on całkiem dobrze wyglądać jako… tło minimapy pokazywanej w grze, która rozgrywa się na terenie opisanym mapą wysokości. Oczywiście rzecz wymagałaby dopracowania: przede wszystkim bardziej starannego dobrania kolorów brzegowych (niekoniecznie białego i czarnego) oraz być może kolorów pośrednich (np. kolor poziomu morza), a i pewnie zastosowania jakichś filtrów na wynikowym obrazku (np. wygładzania). Efekty mogłyby być jednak interesujące, co widać obok.

Tekstury do wszystkiego

W potocznym rozumieniu tekstura to taki obrazek, który nakłada się obiekt trójwymiarowy, aby w ten sposób imitować wygląd jego powierzchni. Rzeczywiście, dawno temu była to ich jedyna funkcja. Tego rodzaju tekstury (nazywane teksturami rozproszenia) są oczywiście nadal niezbędne. Obok nich powstało jednak całe mnóstwo innych rodzajów tekstur, które są wykorzystywane podczas renderowania scen 3D.

Wśród nich są na przykład takie, które zawierają pewne niezbędne informacje na temat obiektów na scenie – nie tylko zresztą geometrii. Są to chociażby:

• 
  Przykład mapy wysokości

  Mapy wysokości (height maps). To czarno-białe tekstury, używane do modelowania terenu. Jasność konkretnego piksela odpowiada wysokości terenu w danym punkcie. Taka tekstura musi być naturalnie przetworzona na odpowiednie trójkąty (co specjalnie trudne nie jest), ale jej używanie zamiast innych reprezentacji ma dwie wyraźne zalety. Po pierwsze, umożliwia regulowanie stopnia szczegółowości (Level of Detail, LoD) wyświetlanego terenu. Po drugie, mapy wysokości są bardzo łatwe do wykonania za pomocą dowolnego programu graficznego nawet przez średnio uzdolnionego w tym kierunku kodera :)

• 
  Odpowiadająca jej
  mapa normalnych

  Mapy normalnych (normal maps) obrazują z kolei wektory normalne punktów powierzchni. Pomysł jest bardzo prosty: kolor każdego piksela w formacie RGB odpowiada normalnej o współrzędnych XYZ. Ponieważ współrzędne te są ograniczone (długość normalnej to zawsze 1), mogą być zapisane jako kolor. Mapa normalnych jest potem wykorzystywana przy obliczeniu oświetlenia per-pixel.

• Mapy światła (light maps) reprezentują natomiast rozkład oświetlenia na scenie lub wokół źródła światła. W tym pierwszym przypadku chodzi o użycie wygenerowanego wcześniej jakąś kosztowną metodą (np. śledzenia fotonów) “wzorca” oświetlenia sceny. Ma to rzecz jasna sens tylko wtedy, gdy oświetlenie jest statyczne. Z kolei lightmapa dla źródła światła obrazuje kształt promieni świetlnych, które rzekomo z niego wychodzą. W obu przypadkach jasność pikseli odpowiada intensywności oświetlenia, chociaż mapy światła nie muszą być monochromatyczne.

Tego rodzaju tekstury są przygotowywane wcześniej i obok modeli, tekstur rozproszenia i innych danych stanowią informacje umożliwiają renderowanie sceny. Oprócz nich w trakcie samego rysowania wykorzystywane są też inne tekstury, tworzone na bieżąco i zwykle niezachowywane na później. Wśród tych efemerycznych tekstur mamy na przykład:

• Mapy cieni (shadow maps). Są one używane przy jednej z technik liczenia cieni. Pojedyncza mapa to po prostu zapis bufora głębokości dla sceny widzianej z punktu widzenia źródła światła. Dzięki temu możliwe jest następnie określenie, który piksel jest widoczny dla tegoż źródła, a który jest w cieniu. To dość prosty sposób obliczenia cieniowania, w podstawowej wersji wymaga jednak dodatkowego przebiegu dla każdego źródła światła.
• 
  Imbryczek z cubemapą

  Mapy odbić środowiskowych (environmental maps) służą do symulowania przedmiotów o powierzchniach lustrzanych. Podobnie jak wyżej, wymagają osobnego przebiegu renderowania, i to często nawet niejednego (jak w przypadku map sześciennych). Tak powstałe obrazy odbić są potem nakładane na przedmiot, który dzięki temu sprawia wrażenie, jakby odbijał w sobie resztę sceny.

• Bufory geometrii (G-buffers) to w zasadzie nie jedna, a zestaw tekstur, z których każda zawiera informacje o pewnym parametrze materiału dla danego piksela z gotowego obrazu sceny. Po wypełnieniu ich informacjami, “bufor” ten jest wykorzystywany np. dla obliczeń związanych z oświetleniem i cieniowaniem we wszystkich technikach opatrzonych modnym przydomkiem ‘deferred‘. Dzięki temu oszczędza się każdorazowego przekształcania całej geometrii dla każdego przebiegu renderowania przez wszystkie macierze.

Potencjalnych i aktualnych zastosowań tekstur jest o wiele więcej. Ale już na tych przykładach widać, że tekstury tak naprawdę nie są obrazkami, a jedynie zbiorami jakichś informacji, które tylko z konieczności są zapisywane w postaci kolorów pikseli. Być może niedługo staną się one pełnoprawną “pamięcią operacyjną” kart graficznych, którą można będzie np. alokować i zwalniać w kodzie shaderów. Jak dotąd możliwy jest ich odczyt oraz w pewnym stopniu zapis (zależnie od modelu shaderów), ale kto wie – może wkrótce doczekamy się czegoś więcej?…