Łączenie efektów graficznych

Internet pełen jest opisów, tutoriali i przykładowych kodów pokazujących, jak implementować różne efekty graficzne. Zakodowanie ich pojedynczo zazwyczaj nie jest więc problemem, o ile mamy jako takie pojęcie o grafice czasu rzeczywistego, bibliotece DirectX/OpenGL i programowaniu w ogóle.
Znacznie większym problemem jest połączenie kilku(nastu/dziesięciu) efektów tak, by było one zaaplikowane w jednym momencie do tej samej sceny. Ze względu na to, że każdy pojedynczy efekt może wymagać kodu w bardzo różnych miejscach potoku graficznego (chociażby w samej aplikacji oraz w kodzie shaderów), zintegrowanie wszystkich tych fragmentów nie wydaje się sprawą prostą.

Ostatnio aczkolwiek zajmowałem się praktycznym rozwiązywaniem tych kwestii; było to łączenie różnych rodzajów oświetlenia z cieniami generowanymi techniką shadow depth mapping i efektami postprocessingu w rodzaju depth of field. Pozwolę więc sobie podzielić kilkoma uwagami na ten temat. To może jeszcze nie są rady, jak dobrze zaprojektować architekturę silnika 3D, ale mały framework pewnie można o nie oprzeć ;] A zatem:

• Należy wydzielić kod zajmujący się rysowaniem samych obiektów na scenie, gdyż będzie on wywoływany wielokrotnie. Niektórym może wydawać się to oczywiste, ale w ilu przykładowych kodach wywołania DrawPrimitive czy DrawSubset są w tej samej funkcji co Begin/EndScene? W rzeczywistym kodzie zapewne tak nie będzie, bo dana scena będzie na pewno renderowana wielokrotnie.
• Trzeba odpowiednio zająć się macierzami przekształceń. Ważne jest na przykład wydzielenie w shaderze macierzy lokalnego przekształcenia każdego obiektu. Nie można jej po prostu złączyć z macierzą WORLD (lub MODELVIEW w OpenGL), bo nasza scena będzie renderowana kilka razy w potencjalnie różnych widokach (kamery, światła, obiektu odbijającego otoczenie, itp.). Dodatkowo mogą być nam potrzebne punkty w różnych przestrzeniach, np. w układzie widoku obserwatora i widoku od konkretnego światła naraz. Wreszcie, nie należy zapominać o prawidłowym przekształcaniu wektorów normalnych. W sumie więc sekcja deklaracji pliku z shaderami może wyglądać np. tak:
  1. float4x4 ObjectTransform; // przekszt. lokalne obiektu
  2. float4x4 CameraWorld; // przekszt. globalne sceny
  3. float4x4 CameraWorldRotation; // jw. ale z samą rotacją
  4. float4x4 CameraView; // przekszt. do przestrzeni widoku
  5. float4x4 CameraProjection; // przekszt. do przestrzeni rzutowania
  6. float4x4 LightWorldViewProjection; // przekst. do przestrzeni światła
  7. // itd.

  Są tutaj jeszcze dwie sprawy warte zaznaczania. Po pierwsze, obiekty rysujące się na scenie muszą wiedzieć, gdzie ustawiać swoją macierz lokalnego przekształcenia. We wszystkich używanych shaderach nazwa odpowiedniej stałej (tutaj ObjectTransform) musi być taka sama; najlepiej też żeby mapowała się na te same rejestry stałych cn. Naturalnie kod renderujący obiekty musi też “wiedzieć”, żeby korzystać właśnie z niej zamiast z macierzy przekształceń z fixed pipeline – czyli np. wywoływać effect->SetMatrix("ObjectTransform", &mat); zamiast device->SetTransform (D3DTS_WORLD, &(currWorld * mat)); w przypadku DirectX).
  Po drugie, nie trzeba “dla efektywności” przekazywać do shadera iloczynów macierzy, jeśli używamy także ich poszczególnych czynników. Można bowiem zupełnie bezkarnie mnożyć je na początku kodu shadera:

  1. float4x4 CameraObjectWorld = mul(ObjectTransform, CameraWorld);
  2. float4x4 CameraWVP = mul(CameraObjectWorld, mul(CameraView, CameraProjection));
  3. // dalej reszta shadera
  4. Out.Position = mul(float4(In.Position, 1), CameraWVP);

  Kompilator wydzieli ten kod w postaci tzw. preshadera i zapewni, że będzie on wykonywany tylko raz (a nie dla każdego wierzchołka/piksela).

• Konieczne jest zadbanie o dobrą obsługę render targetów. Powinna być ona przezroczysta dla poszczególnych efektów – nie muszą one wiedzieć, czy renderują bezpośrednio na ekran, czy do tekstury. Jednocześnie każdy efekt powinien móc określić, do którego RT chce aktualnie renderować i mieć potem możliwość wykorzystania wyników jako tekstur w kolejnych przebiegach. Generalnie do tych celów wystarcza prosty menedżer oparty np. na słowniku identyfikującym poszczególne RT za pomocą nazw: "ShadowMap", "DepthMap, "Scene" itp.
• W bardziej skomplikowanych przypadkach trzeba pewnie będzie złączyć shadery. W chwili obecnej jest to pewnie jeden z najbardziej złożonych problemów przy tworzeniu silnika graficznego, ale istnieje szansa, że wprowadzane w DirectX 11 dynamiczne linkowanie shaderów będzie to w istotny sposób ułatwiało.
  Jeśli na razie nie chcemy się mierzyć z tym problemem, to można niekiedy go ominąć kosztem dodatkowych przebiegów renderowania. Przykładowo, cienie można nakładać na gotową scenę z już policzonym oświetleniem zamiast oświetlać i cieniować piksele w jednym passie.

Ogólnie trzeba przyznać, że implementowanie wielu efektów działających naraz w tej samej scenie to zagadnienie złożone i dość trudne. Chociaż więc starałem się podać kilka porad na ten temat, to w rzeczywistości niezbędne jest tutaj spore doświadczenie z różnymi rodzajami efektów, zarówno w teorii jak i praktyce.

W matematyce jest odwrotnie

W pewnych sprawach kiedyś występowała alternatywa dwóch równoważnych możliwości i trzeba było w końcu zdecydować się na wybór jednej z nich. Matematycy często ustalają w ten sposób coś “dla porządku” lub dla tzw. ustalenia uwagi. Jak na ironię zauważyłem jednak, że zwykle to właśnie w matematyce niektóre powszechnie obowiązujące umowy wcale nie wprowadzają porządku, gdyż są dokładnie odwrotne względem intuicji lub codziennego doświadczenia. Oto przykłady:

• Kąty w kartezjańskim układzie współrzędnych na płaszczyźnie – ze szczególnym uwzględnieniem współrzędnych biegunowych – są tak określone, że większe ich wartości oznaczają coraz większe przesunięcie w kierunku przeciwnym do ruchu wskazówek zegara.
• Tzw. główna przekątna macierzy przy jej zwykłej reprezentacji tablicowej obejmuje komórki od lewego górnego do prawego dolnego rogu. Linia, która jest pochylona w ten sposób, przypomina znak backslash :)
• 
  Ta funkcja jest wypukła :)

  Funkcje rzeczywiste nazywane wypukłymi narysowane w postaci wykresu przyjmują postać krzywej wygiętej do dołu, co sugeruje nazywać je raczej… wklęsłymi (obrazuje to rysunek po prawej).

• Tradycyjnie wektory w matematyce zapisuje się jako kolumnowe (czyli macierze ), a nie wierszowe (). To niby nic specjalnego, ale skutek “uboczny” jest taki, że macierze przekształceń (obrotu, translacji, itp.) w stosunku do takich wektorów należy aplikować w kolejności odwrotnej względem rzeczywistej kolejności transformacji, którą chcemy uzyskać (kiedyś już pisałem więcej na ten temat).

Na pewno nie są to wszystkie przypadki podobnych “niefortunnych” rozstrzygnięć; z pewnością dałoby się znaleźć ich więcej. Na pewno też każdy z nich daje się w zadowalający sposób uzasadnić (jak chociażby przekątną macierzy – jest ona po prostu definiowana przez te komórki, których numer wiersza jest równy numerowi kolumny). I paradoksalnie to właśnie jest w nich najgorsze: nie da się z nimi nic zrobić, jak tylko zwyczajnie zapamiętać :)

Kilka nawiasów kwadratowych

Gdy w C++ tworzymy typ wymagający indeksowania więcej niż jednym indeksem – a więc coś w stylu wielowymiarowej tablicy, np. macierzy – zazwyczaj używa się do tego celu operatora nawiasów okrągłych. Nie jest to specjalnie spójne z tablicami wbudowanymi język, gdzie do indeksowania stosuje się nawiasy kwadratowe, w tym przypadku nawet więcej niż jedną parę.
O ile jednak da się przeciążyć operator [], o tyle “operatorów” [][], [][][], itd. już nie. Można jednak zastosować inną technikę, jeśli chcemy by nasze własne typy były składniowo maksymalnie podobne do wbudowanych.

Trzeba mianowicie przygotować je tak, by dało się do nich stosować operator [] niejako więcej niż raz. Wymaga to wprowadzenia jakiejś klasy pośredniej; dla macierzy może ona reprezentować pojedynczy wiersz:

Dla tego wiersza piszemy naturalnie zwykły operator indeksowania, pozwalający nam dostać się do jego elementów. Trik leży w postaci operatora, którą umieszczamy w samej klasie macierzy:

Zwraca ona nasz wiersz, a właściwie jego opakowanie, które to zdefiniowaliśmy. W ten sposób osiągamy dla Matrix<T>zachowanie niemal dokładnie analogiczne do tablic typu T**: pierwsza para nawiasów daje nam T* (u nas MatrixRow<T>), zaś druga konkretną wartość typu T:

W tym rozwiązaniu oczywiście parę szczegółów do uwzględnienia (np. warianty const naszego operatora). Widać jednak, że jeśli bardzo chcemy, to przy odrobinie pomysłowości da się wszędzie używać “właściwych” nawiasów :)

Kolejność przekształceń macierzowych

Kiedy uczyłem się biblioteki DirectX, miałem dość spore kłopoty z kwestią właściwej kolejności przekształceń opisanych przez macierze. Jak wiadomo, w grafice każdą transformację możemy opisać macierzą, a złożenie takich przekształceń możemy być reprezentowane przez odpowiedni iloczyn macierzy. Wówczas pomnożenie wektora (odpowiednio rozszerzonego o czwartą współrzędną) przez taką macierz skutkuje zastosowaniem do niego tych wszystkich przekształceń. Może być ich bardzo wiele, lecz wymagana jest tylko jedna macierz i jedno mnożenie przezeń wektora. Jest to więc efektywne, jeśli mamy dużą ilość geometrii do przetworzenia – czyli, co tu ukrywać, w zasadzie zawsze :)

Rzeczone macierze opisujące przekształcenia są kwadratowe; w przypadku grafiki 3D mają rozmiar 4×4. Dlatego też możliwe jest ich mnożenie w dowolnej kolejności. Wiemy jednak, że operacja mnożenia macierzy nie jest przemienna. Odpowiada to zresztą temu, iż przy przekształcaniu punktów w przestrzeni też liczy się kolejność: obrót, a potem przesunięcie to nie to samo, co przesunięcie, a potem obrót.
I tu się zaczyna problem, bowiem w bardzo wielu źródłach wprowadzone jest niezłe zamieszanie, jeśli chodzi o kolejność mnożenia macierzy opisujących geometryczne przekształcenia. Najczęściej pomieszane są konwencje tego, jaki porządek jest poprawny w danej bibliotece graficznej, a jaki “w matematyce”. Ostatecznie więc nie wiadomo, czy trzeba iloczyn macierzy zapisywać w kolejności, w jakiej chcemy aplikować przekształcenia, które reprezentują – czy może na odwrót. Dość prosto można oczywiście sprawdzić, jak to jest akurat w naszej bibliotece graficznej, lecz to nie mówi nic o istocie problemu…

Właściwie to dopiero niedawno dowiedziałem się, gdzie jest tu pies pogrzebany. Otóż matematycy z pewnych przyczyn lubią traktować wektory jako kolumnowe, tj. jako macierze Nx1 (N wierszy, 1 kolumna). Przy takiej interpretacji tylko iloczyn w postaci:

macierz1 * wektor_kolumnowy

daje w wyniku wektor (także kolumnowy, rzecz jasna). W tym przypadku będzie on przekształcony przez macierz1. Jeżeli teraz zechcemy dodać drugie przekształcenie, to mnożenie przez odpowiednią macierz również musimy zapisać z przodu:

macierz2 * (macierz1 * wektor_kolumnowy)

Ale mnożenie jest oczywiście łączne, więc:

(macierz2 * macierz1) * wektor_kolumnowy = macierz * wektor_kolumnowy

a wynikowa macierz = macierz2 * macierz1 opisuje złożenie naszych przekształceń. Jak widać wyżej, najpierw jest stosowane to opisane przez macierz1, a dopiero potem to z macierzy2 – mimo że są one mnożone w porządku odwrotnym. Tak bowiem wygląda sprawa kolejności przekształceń dla wektorów kolumnowych.

Twórcy DirectX uznali prawdopodobnie, że jest to nieintuicyjne dla nie-matematyków i dokonali pewnego “triku”. Opiera się on na tym, że gdy w dwóch macierzach zamienimy ze sobą wiersze i kolumny – czyli dokonamy transpozycji – pomnożymy je przez siebie, a następnie transponujemy wynik, to rezultat będzie taki, jakbyśmy mnożyli wyjściowe macierze w odwrotnej kolejności. Wyjątkowo trzeba tutaj przyznać, że wzór mówi więcej niż jego opis, więc spójrzmy na ten wzór :)

(A * B)^T = B^T * A^T

W DirectX dokonano więc transpozycji wszystkich macierzy opisujących przekształcenia. Przykładowo, funkcja D3DXMatrixTranslation zwraca macierz z wartościami przesunięć wpisanych w ostatnim wierszu, podczas gdy w wersji “matematycznej” powinny być one w ostatniej kolumnie. Podobnie jest ze wszystkimi innymi macierzami… ale także z wektorami!
Chociaż wektory z programistycznego punktu widzenia to cztery składowe i nic więcej, to w DirectX należy je traktować jako wektory wierszowe, czyli macierze 1xN. Dla nich zaś sensownym sposobem mnożenia przez macierz jest tylko następujący:

wektor_wierszowy * macierz1

Dodając kolejne przekształcenie, mamy:

(wektor_wierszowy * macierz1) * macierz2

i znów opierając się na łączności mnożenia otrzymujemy ostatecznie:

wektor_wierszowy * (macierz1 * macierz2) = wektor_wierszowy * macierz

Tutaj z kolei widać wyraźnie, że przekształcenia są stosowane w takiej samej kolejności, w jakiej odpowiadające im macierze występują w iloczynie.

Ponieważ, jak wspomniałem wyżej, cała sprawa jest kwestią czysto arbitralną (wystarczy transpozycja, aby odwrócić porządek), powinniśmy tym bardziej zwrócić na nią uwagę. A jeśli programujemy w DirectX, nie należy dopuścić do tego, by matematycy wmawiali nam ‘właściwą’ kolejność :P

Odwracanie macierzy 4×4

Do napisania czegokolwiek z dziedziny programowania gier lub grafiki potrzebna jest zawsze chociaż skromna biblioteka, zawierają podstawowe obiekty matematyczne. Jej częścią na pewno muszą być wektory, a nie od rzeczy są także macierze, kwaterniony, obiekty reprezentujące linie i płaszczyzny, i tak dalej. Taką bibliotekę zwykle albo pisze się raz, albo wykorzystuje jedną z już istniejących. Jakikolwiek byłby nasz wybór, mogłoby się wydawać, że sprawę z nią można załatwić raz na zawsze.
Cóż, nic bardziej błędnego :) Możemy być oczywiście bardzo przywiązani do narzędzi, którymi się posługujemy – języka programowania, platformy, itd. – ale kiedyś na pewno przyjdzie nam zmierzyć się z zupełnie innym językiem i innym środowiskiem. A wtedy trzeba jakoś ten problem matematycznej biblioteki rozwiązać choćby na szybko.

Ostatnio przytrafiło mi się właśnie coś takiego. Nie jest to naturalnie nic pasjonującego, bowiem implementowania dodawania, odejmowania czy mnożenia wektorów jest zajęciem raczej nużącym. Jednak okazało się, że istnieje przynajmniej jedna potrzebna, a niezbyt oczywista matematyczna operacja, którą należy koniecznie uwzględnić. To odwracanie macierzy.
Chcąc tego dokonać programowo, możemy wykorzystać na przykład któryś z tych trzech sposobów:

• Metoda bezpośrednia. Jest to prostu zaimplementowanie ręcznego sposobu odwracania macierzy, wykorzystywanego zazwyczaj w połączeniu z kartką i długopisem :) Dla tych, co przysypiali na wykładach z algebry (lub nie mieli jeszcze szczęścia na nie uczęszczać ;)) przypominam, że polega to na wykonaniu określonych operacji (mnożenia przez liczbę oraz dodawania) na wierszach naszej macierzy oraz jednocześnie na wierszach macierzy jednostkowej. W ich wyniku nasza macierz sama ma zmienić się w jednostkową, zaś ta druga będzie wtedy szukaną odwrotnością. Wiadomo skądinąd, że złożoność tego algorytmu to O(n³), gdzie n to wymiar macierzy.

  

• Rozwiązanie układów równań. Ta metoda wymaga posiadania procedury rozwiązującej układy równań, jak na przykład eliminacji Gaussa lub znajdowania rozkładu LU. Posługując się nią, możemy obliczyć kolejne wiersze macierzy odwrotnej i też zajmie nam to czas O(n³). Oczywiście trzeba jeszcze mieć (tj. napisać) rzeczoną procedurę, co już takie proste nie jest :)
• Dopełnienie algebraiczne. Ten sposób charakteryzuje się głównie tym, że wymaga obliczenia sporej liczby wyznaczników – nie tylko tej macierzy, którą odwracamy, ale i każdej z jej podmacierzy. Wiadomo zaś, ze wyliczanie wyznaczników nie należy do operacji tanich. W istocie złożoność tej metody odwracania leży gdzieś w okolicach wykładniczej.

Trzeba jednak zauważyć pewną rzecz. Otóż do celów graficznych potrzebujemy jedynie macierzy o stałym rozmiarze, i to niewielkim – zwykle 4×4. Przy tak małym rozmiarze danych złożoność algorytmu (która niejawnie zakłada, że rozmiar ten jest bardzo duży) nie jest miarodajna. Liczy się bowiem dokładna ilość faktycznie wykonywanych operacji. A przy takim podejściu spotyka nas niespodzianka, jako że najwyraźniej najlepsza okazuje się metoda ostatnia. Jest ona używana na przykład w funkcji D3DXMatrixInverse, zatem posiada całkiem dobrą rekomendację :)
I ma chyba tylko jedną wadę. Po rozpisaniu występującej w niej pętli (co jest możliwe, jeśli znamy z góry rozmiar macierzy) zamienia się ona w dość odstraszającą szpaltę kodu z kilkunastoma długimi, niemal identycznie wyglądającymi wierszami, które różnią się tylko permutacją cyferek oraz plusów i minusów. Ale przecież tak wygląda kod w zasadzie każdego działania na macierzach i właśnie dlatego tak lubimy je implementować ;-)