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”.

Pule pamięci w DirectX

Jedną z rzeczy, która na początku programowania w DirectX może wydawać się dziwna, jest tajemniczy parametr Pool. Pojawia się on w każdej funkcji, która tworzy jakiś zasób graficzny: teksturę, bufor wierzchołków, siatkę modelu (ID3DXMesh), bufor głębokości, itp.
Rolą tego parametru jest określenie, w której puli pamięci znajdzie się tworzony zasób. DX wyróżnia bowiem ich kilka, co jest związane przede wszystkim z (przynajmniej) dwoma rodzajami pamięci, z jakimi możemy mieć do czynienia programując grafikę: zwykłym systemowym RAM-em oraz pamięcią karty graficznej.

W jakiej puli powinniśmy więc umieszczać swoje obiekty? To zależy od kilku czynników. Na początek na pewno warto przyjrzeć możliwościom:

• D3DPOOL_DEFAULT, jak wskazuje na to nazwa, oznacza pulę domyślną. Gdy użyjemy tej flagi, DirectX umieści nasz zasób w najlepszym – pod względem wydajności – miejscu, bazując przy tym na innym parametrze, Usage (określa on, mówiąc w skrócie, sposób wykorzystania danego zasobu). Tym najlepszym miejscem jest prawie zawsze pamięć karty graficznej.
  To sprawia jednak, że przy utracie urządzenia (o ile nie programujemy co najmniej w DX9Ex) taki zasób należy zwolnić, a potem utworzyć ponownie – musimy więc pamiętać sposób, w jaki go utworzyliśmy. Ponadto istnieją też pewne ograniczenia (bezwzględne lub wydajnościowe) w dostępie do obiektów z puli domyślnej: o ile nie zadeklarujemy ich jako dynamiczne (D3DUSAGE_DYNAMIC), ich blokowanie wiąże się ze stratą szybkości albo jest wręcz niemożliwe (w przypadku tekstur).
• D3DPOOL_MANAGED to pula zarządzana. Oznacza to, że pieczę nad nią sprawują sam DirectX i to on decyduje, w którym rodzaju pamięci zasoby z tej puli zostaną umieszczone. Zazwyczaj oznacza to, że w pamięci operacyjnej trzymana jest kopia obiektu, znajdującego się też w pamięci graficznej. Dzięki temu nie trzeba go tworzyć ponownie w przypadku straty urządzenia, a także można go blokować i modyfikować niezależnie od typu i flag Usage; w tym przypadku DX zadba o odpowiednią synchronizację.
• D3DPOOL_SYSTEMMEM oznacza pulę pamięci systemowej. Zasoby tu stworzone będą znajdowały się w zwykłym RAM-ie i nie będą mogły być bezpośrednio renderowane. Dane z nich mogą jednak być kopiowane do zasobów znajdujących się w puli domyślnej, jak chociażby poprzez funkcję UpdateTexture.
• D3DPOOL_SCRATCH jest również usytuowana w pamięci systemowej (RAM). W odróżnieniu od poprzedniej, zasoby z tej puli nie są jednak w żaden sposób (także pośredni) dostępne dla urządzenia i nie mogą być używane podczas renderowania. Oznacza to też, że nie podlegają one ograniczeniom związanym z kartą graficzną. Można więc, przykładowo, tworzyć w tej puli tekstury o rozmiarach niebędących potęgami dwójki także wtedy, gdy karta nie wspiera takich tekstur.

Spotkałem się z dwiema ogólnymi wytycznymi dotyczącymi tego, z których pul pamięci należy korzystać:

1. Pierwsza z nich mówi, że należy wszystko, co się da, umieszczać w D3DPOOL_DEFAULT, bo to zapewnia największą wydajność, jako że wtedy zasoby generalnie umieszczane są w pamięci karty graficznej.
2. Druga szkoła sugeruje z kolei, żeby wszystko, co się da, umieszczać w D3DPOOL_MANAGED, gdyż wtedy pozwalamy DirectX-owi zdecydować, w jakim rodzaju pamięci trzymać nasz zasób – a już on powinien o tym wiedzieć lepiej.

W sumie więc wygląda na to, że nic nie wiadomo :) Oczywiście są przypadki, gdy wyboru nie mamy, jak to się dzieje choćby dla tekstur typu render target, które muszą być stworzone w D3DPOOL_DEFAULT. Zawsze jednak będziemy mieli takie zasoby, które “równie dobrze” dałoby się umieścić w puli domyślnej, jak i zarządzanej. Co wtedy?
Otóż wydaje mi się, że to zależy od wielkości naszej aplikacji (w sensie rozmiaru używanych zasobów) oraz… stopnia zaawansowania w programowaniu w DirectX. Na początek bowiem D3DPOOL_MANAGED jest pulą bezpieczniejszą: nie musimy się w niej martwić o stratę urządzenia i możemy każdy zasób blokować i zmieniać. Ceną za to jest wzrost zużycia pamięci przez aplikację, spowodowany trzymaniem przez DX kopii obiektów w pamięci systemowej.
Jeśli jednak nasza gra (nie bójmy się użyć tego słowa ;)) używa dużej ilości zasobów, to takie marnotrawstwo jest zwykle nie do przyjęcia. Wtedy przynajmniej część z nich należy przenieść do D3DPOOL_DEFAULT. Istnieje szansa, że na tym etapie będziemy już wiedzieć lepiej, którą część ;-)

Na koniec pozwolę sobie też wspomnieć o – często pomijanej – puli D3DPOOL_SCRATCH. Jej przeznaczeniem są wszelkiego rodzaju zasoby pomocnicze, których nie renderujemy, ale mimo to wykorzystujemy do jakiegoś celu – na przykład tworzenia innych zasobów. Typowym przykładem są wszelkiego rodzaju pomocnicze, narzędziowe tekstury – jak choćby mapy wysokości (heightmap), na podstawie których generujemy ukształtowanie terenu.
Najlepszą pulą dla takich obiektów jest właśnie D3DPOOL_SCRATCH. Użycie jakiejkolwiek innej spowodowałoby uszczerbek na wydajności lub wręcz błędy, jak np. niezamierzone przeskalowanie tekstury do rozmiaru 2ⁿ.

Powtórka z DirectX

Za sprawą przedmiotu o nazwie Grafika Komputerowa 3D musiałem ostatnio przypomnieć sobie, jak tak naprawdę i w praktyce koduje się w DirectX. Pewnie brzmi to dziwnie, ale w rzeczywistości przez ładnych kilka miesięcy nie pisałem większych ilości kodu, który by z tej biblioteki korzystał.

Piękna scena ;-)

Projekt, który musiałem teraz napisać, nie był ani trochę ambitny, bo polegał li tylko na wyświetleniu zupełnie statycznej sceny z kilkoma modelami, oświetleniu jej i zapewnieniu możliwości poruszania się w stylu strzelanek FPP. Oczywiście nie było też mowy o żadnych shaderach.

Niby banalne, ale jednak rzecz zajęła mi w sumie jakieś cztery znormalizowane wieczory (czyli od 3 do 4 godzin każdy). Częściowo było tak pewnie dlatego, że pokusiłem się jeszcze o teksturowanie, możliwość regulacji paru opcji renderowania czy bardzo, bardzo prosty menedżer sceny – czytaj: drzewko obiektów + stos macierzy ;)
Wydaje mi się jednak, że ważniejszą przyczyną był nieszczęsny fixed pipeline, którego byłem zmuszony używać. Jeszcze kilka lat temu nigdy bym nie przypuszczał, że to powiem, ale… shadery są po prostu łatwiejsze w użyciu. Porównując chociażby trywialne mieszanie koloru diffuse wierzchołka z teksturą przy użyciu pixel shadera:

oraz stanów urządzenia:

nietrudno jest ocenić, w której znacznie lepiej widać, co faktycznie dzieje się z kolorem piksela. No, chyba że dla kogoś multum stałych w rodzaju D3DABC_SOMESTRANGEOPTION jest czytelniejsze niż po prostu mnożenie ;P

Inną sprawą jest też to, że w DirectX napisanie aplikacji od podstaw jest stosunkowo pracochłonne. Brak “złych” funkcji typu glVertex* ma rzecz jasna swoje zalety, lecz jest też jednym z powodów, dla których tak opłaca się posiadanie własnego frameworka, a może nawet i – tfu tfu – silnika ;-)

Skąd wziąć matematyczne stałe

Jeśli tylko liczymy coś bardziej skomplikowanego niż rozmieszczenie kontrolek w oknie, to niechybnie zaczniemy potrzebować którejś ze stałych matematycznych – na przykład π. Co wtedy robimy? Ano całkiem często skutkuje to włączeniem do programu deklaracji typu:

Nie jest to oczywiście wielkie zło (a już na pewno mniejsze niż bezpośrednie korzystanie z definicji typu π = 4atan(1)), ale w większości przypadków jest to też wyważanie otwartych drzwi. Potrzebne stałe mamy bowiem często już gdzieś zdefiniowane – trzeba tylko wiedzieć, gdzie ich poszukać:

• W C/C++ mamy M_PI, M_E, a nawet M_LN10 czy M_SQRT2 zdefiniowane w math.h lub cmath. Definicje te nie są jednak częścią standardu, więc dbające o zgodność kompilatory (czyli większość kompilatorów w ogóle) wymagają pewnych #define‘ów przed dołączeniem ww. nagłówków. I tak dla Visual C++ jest to _USE_MATH_DEFINES, a dla GCC bodajże prawie dowolne z makr _SOURCE (jak _GNU_SOURCE czy _ALL_SOURCE).
• W DirectX mamy tylko DX3DX_PI i D3DX1BYPI (1/π) – co nie dziwi, bo przecież w grafice więcej do szczęścia nie potrzeba ;) Obie te stałe są zdefiniowane w d3dx#math.h (gdzie # to numer wersji DirectX), który to nagłówek jest dołączany automatycznie jeśli korzystamy z D3DX.
• W .NET mamy stałe PI i E zdefiniowane jako statyczne pola klasy System.Math. W Javie klasa java.lang.Math zawiera dwa identycznie zdefiniowane pola.

Jak zatem łatwo zauważyć, wynajdywanie koła w postaci definicji π czy e jest w wielu przypadkach nieuzasadnione :]

Nie tylko alpha blending

Uaktywnienie łączenia alfa w DirectX na pierwszy rzut oka wydaje się dość skomplikowana. Niby występuje tam oczywiste ustawienie stanu renderowania D3DRS_ALPHABLENDENABLE na true, jednak to nie wszystko. Potem zwykle od razu występują przynajmniej dwa inne stany: D3DRS_SRCBLEND i D3DRS_DESTBLEND, ustawiane na równie tajemnicze wartości. Wyjaśnimy sobie dzisiaj, co one oznaczają i jak można je wykorzystać.

Należy zacząć od tego, że ten zagadkowy alpha blending to nic innego, jak zwykła suma ważona:

SourceBlend * SourceColor + DestBlend * DestColor

(z dokładnością do tego, że dodawanie można zastąpić innym działaniem przy pomocy D3DRS_BLENDOP, ale tę możliwość zostawimy w spokoju ;]). To, co jest tutaj sumowane, to dwa kolory: źródłowy – pochodzący od właśnie mającego się narysować piksela, oraz docelowy – będący już w danym miejscu bufora ramki (ekranu). Normalnie ten pierwszy zwyczajnie zastąpiłby ten drugi, ale dzięki łączeniu alfa można zamiast tego uzyskać jakąś kombinację ich obu – czyli na przykład symulację półprzezroczystości. Wagami dla sumy są SourceBlend i DestBlend, i to właśnie je ustawiamy przy pomocy stanów renderowania.

Możliwych wartości jest kilka i obejmują one zarówno tak proste jak zero czy jeden aż po same kolory: źródłowe i docelowe (podobnie jak one, współczynniki te są 4-elementowymi wektorami), wartości ich kanału alfa, specjalny globalny współczynnik blend factor – jak również negacje tych wszystkich wartości. Sporo tego, prawda? :) Zobaczmy więc kilka typowych kombinacji:

• SourceBlend = SourceAlpha; DestBlend = InvSourceAlpha

  To najbardziej typowy sposób osiągania przezroczystości. Używamy tutaj źródłowej wartości alfa, by określić, jak bardzo kolor źródłowy ma wpływać na wynikowy oraz jak bardzo ma być pominięty wpływ koloru docelowego – że tak spróbuje się “intuicyjnie” wyrazić :) Ostatecznie mamy wtedy równanie typu:

  SourceAlpha * SourceColor + (1 – SourceAlpha) * DestColor

  czyli tzw. kombinację liniową obu kolorów, która w wyniku daje wrażenie półprzezroczystości.

• SourceBlend = One; DestBlend = One

  Ustawienie obu wag na 1 sprawia, że nasza suma ważona stają się zwykłą sumą, więc kolory są po prostu dodawane. Taka konfiguracja jest stosowana na przykład do łączenia ze sobą efektów oświetlania sceny kilkoma różnymi światłami i nazywa się blendingiem addytywnym.

• SourceBlend = DestColor; DestBlend = Zero

  Takie dziwne ustawienie wag sprawia z kolei, że zamiast dodawania otrzymujemy w istocie mnożenie przez siebie kolorów – czyli blending multiplikatywny. Istnieje oczywiście jeszcze jedna konfiguracja współczynników dająca ten sam efekt, która jest symetryczna do powyższej.

Powyższe warianty nie są naturalnie wszystkimi możliwymi ani nawet wszystkimi praktycznie wykorzystywanymi. Widać z nich jednak, że tak zwany alpha blending nie służy tylko do przezroczystości i nierzadko wykorzystujemy go również wtedy, gdy wszystkie obiekty naszej sceny nie są ani trochę prześwitujące.

Triki z PowerShellem #4 – DirectX

Jakiś czas temu pokazałem, że w PowerShellu można zrobić rzeczy, które są – jak na konsolkę tekstową – co najmniej niespotykane. Przedstawiłem na przykład sposób na wyświetlenie zwykłego windowsowego okienka. Nie było ono aczkolwiek zbyt interesujące, jako że w środku było zupełnie puste – chociaż, oczywiście, Aero robił co mógł, by wyglądało ono na atrakcyjniejsze niż było w rzeczywistości ;)
Jako że zajmowania się rzeczami zupełnie nieprzydatnymi nigdy dość, postanowiłem więc pewnego razu spróbować wnieść w stworzoną formę nieco więcej życia. Efekty okazały się raczej ciekawe, przedstawiając się następująco:

Tak, to jest trójkąt. Tak, on się obraca. Tak, na pasku tytułowym okna jest napisane Direct3D… Wszystkie te trzy fakty nie są żadnym zbiegiem okoliczności :) Za wszystko odpowiedzialny jest ten ono skrypt:

Przyznam, że byłem mocno zaskoczony, iż taki trik jest w ogóle możliwy przy pomocy czegoś, co w założeniu jest tylko powłoką tekstową dla poleceń administracyjnych. A tu proszę: DirectX w całej (aczkolwiek zarządzanej) okazałości!
Nietrudno rzecz jasna zauważyć, że powyższy skrypt jest w dużym stopniu tłumaczeniem na język PowerShella odpowiedniego kodu, który mógłby zostać napisany w dowolnym języku programowania z platformy .NET. Trzeba było jedynie poradzić sobie z pewnymi niedogodnościami, jak na przykład koniecznością ręcznego załadowania assemblies czy jakimś obejściem braku sensownej możliwości reakcji na zdarzenia – tutaj “program” po prostu kończy się po 5 sekundach.

Właśnie ta niemożność sprawia, że tandem PowerShell + DirectX zapewne nie ma przed sobą świetlanej przyszłości w grach :) Przez chwilę zastanawiałem się, czy wobec tego nie da się go użyć do tworzenia dem… Niestety, już powyższy skrypt zajmuje ponad 2 kilobajty, nie potrafiąc przy tym zbyt wiele, więc ta możliwość też prawdopodobnie odpada.
Pozostaje zatem pokazywanie podobnych trików linuksowcom i wytykanie im, że ich bash czegoś takiego nie potrafi ;D

Fragmenty a piksele

W terminologii DirectX programowalny potok graficzny ma dwie ważne części: vertex shader i pixel shader. Nazwa tej drugiej jest zasadniczo trochę myląca. Sugeruje ona, że shader jest wykonywany dla każdego piksela na ekranie, co tak naprawdę jest dalekie od prawdy.
Tak naprawdę bowiem “piksele” te są dopiero kandydatami do zapisania w buforze tylnym. Po drodze mają bowiem wiele okazji na to, aby być całkowicie wyeliminowane z renderingu. Może to się stać z któregoś z poniższych powodów, które jednak nie wyczerpują wszystkich możliwości:

• Test alfa. W przypadku włączenia tego rodzaju testu, możliwe jest odrzucenie “pikseli”, których wartość kanału alfa nie jest dostatecznie duża. Zwykle jako wartość porównawczą wykorzystuje się 127, 128 albo domyślnie 0. Nie zawsze można sobie oczywiście pozwolić na takie skwantowanie informacji o przezroczystości, ale ma ono niebagatelną przewagę wydajnością nad alpha-blendingiem.
• Test głębi. To najbardziej oczywisty test, a związany jest z przesłanianiem obiektów. W wielu przypadkach możliwe jest wykonanie go przed pixel shaderem, lecz w określonych sytuacjach może być konieczne testowanie już przetworzonych “pikseli”. W zależności od powodzenia testu wartość głębi zapisana w buforze może być oczywiście uaktualniona, co wpływa na dalsze testy.
• Test stencila. Test wykorzystujący stencil buffer jest sprzężony z testem głębi, wobec czego podlega podobnym ograniczeniom. W szczególności możliwe jest na przykład zapisanie innej wartości do wspomnianego bufora w zależności od tego, czy “piksel” wyłoży się na teście głębi czy stencila.

A zatem wyjście pixel shadera niekoniecznie musi bezpośrednio trafić na ekran. Nie powinniśmy więc brać liczby pikseli w buforze ekranu za średnią liczbę wywołań tego shadera, a już na pewno nie jako górną granicę.
Dlatego też trzeba przyznać, że używana w OpenGL nazwa ‘fragment program‘ jest o wiele lepsza niż ‘pixel shader’. Fragment (wyjście shadera) nie jest bowiem jeszcze pikselem, a jedynie kandydatem na niego, który może odpaść przy wielu okazjach.