Normalne w terenie

2009-11-24 22:23

Siatka terenuParę 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)):

\displaystyle n(v) = \frac{1}{|T(v)|} \sum_{(a,b,c) \in T(v)}{(b-a) \times (c-a)}

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 z = f(x,y) i że wobec tego normalną w jakimś punkcie x0, y0 da się wyliczyć jako:

\displaystyle \frac{\partial z}{\partial x}(x_0, y_0) \times \frac{\partial z}{\partial y}(x_0, y_0)

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:

n(v) = (\mathit{pos3d}(p_{x+1,y}) - v) \times (\mathit{pos3d}(p_{x,y+1}) - v) \\ \text{gdzie} \quad v = \mathit{pos3d}(p_{x,y})

Tutaj p_{x,y} 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? :])

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

Tags: , , ,
Author: Xion, posted under Programming »


5 comments for post “Normalne w terenie”.
  1. .c41x:
    November 25th, 2009 o 16:46

    “…przydatną operacją iloczynu skalarnego…” chyba wektorowego?

  2. Xion:
    November 26th, 2009 o 1:49

    Bah! Oczywiście, że wektorowego. Dzięki za wskazanie pomyłki – już poprawione.

  3. Aithne:
    November 28th, 2009 o 18:16

    Powrót do formy? ;)

  4. Reg:
    November 29th, 2009 o 15:44

    Sam wymyśliłeś tą metodę? Jeśli tak to gratz, ale obawiam się, że książka Game Programming Gems podaje nieco lepszą, bo uwzględniającą sąsiednie wierzchołki ze wszystkich 4 stron (tom 6 rozdz. 5.5, tom 3 rozdz. 4.2).

    Mając dane wysokości punktów na północ, południe, wschód i zachód od bieżącego (n, s, e, w) oraz stałą odległości między sądniedniki wartościami wysokości w płaszczyźnie poziomej (d), wzór jest taki:

    N = float3( (w-e), 2*d, (s-n) );

  5. Xion:
    November 29th, 2009 o 18:31

    A czy ta metoda nie zakłada przypadkiem, że teren generujemy zawsze na płaszczyźnie XZ z wysokością równoległą do Y? Sposób wyznaczania N.x i N.y poniekąd to sugeruje :)

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.