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

O pożytkach i nieużytkach UML-a

Stare chińskie przysłowie mówi, że klient zazwyczaj nie wie dokładnie, czego tak naprawdę chce. (Inne przysłowie mówi też, że jeśli nie znamy pochodzenia danej sentencji, to najlepiej powiedzieć, że jest to stare chińskie przysłowie). Dlatego też często nie potrafi swoich potrzeb przełożyć na opis wymagań co do oprogramowania. Jest to jeden z problemów, przy rozwiązywaniu których ma pomagać Unified Modelling Language, czyli UML. W założeniu jest to notacja, umożliwiająca rozpisanie całego procesu tworzenia aplikacji na szereg różnego rodzaju diagramów, na których znaczenie poszczególnych symboli jest ściśle określone – na pewno ściślej niż języka naturalnego. Założenie jest szczytne i bardzo ambitne, a z praktyką jest jak zwykle nieco gorzej :)

Niewykluczone, że jedną z idei przyświecających twórcom UML-a było przynajmniej częściowe zasypanie tej przepaści między dwoma etapami tworzenia: kiedy wiemy, co mamy zrobić, ale jeszcze nie mamy wielkiego pojęcia o tym, jak to zrobić. Przeskoczenie dystansu pomiędzy tymi punktami jest bowiem często kwestią odpowiedniego pomysłu, który najlepiej realizuje całą koncepcję systemu. Jak zaś wiadomo, pomysły biorą się głównie z niezbadanych obszarów pewnego organu znajdującego się między uszami i ich jakość zależy głównie od tego, do kogo ów organ należy. UML stara się więc usystematyzować programistyczną kreatywność, aby zaprojektowanie dobrze działającego systemu nie było tylko wypadkową wymysłów kłębiących się pod czaszką analityka.
Trzeba przyznać, że wychodzi mu to dość średnio. Różne rodzaje diagramów, jakie mamy do dyspozycji, nie bardzo pomagają w płynnym przechodzeniu od wymagań funkcjonalnych do projektu, który te wymagania ma spełniać. Mam raczej wrażenie, że ich celem jest głównie spoglądanie na aplikację z coraz to nowych punktów widzenia. Patrzymy więc na projekt z perspektywy użytkownika zewnętrznego (diagram przypadków użycia), zmieniających się stanów obiektów (diagramy stanów), przepływu danych i obiektów między “miejscami” w programie (diagramy interakcji), i tak dalej. W sumie widzimy coraz więcej pojęć, związków, relacji i zależności, przez co projekt – zamiast upraszczać się, co z pewnością kieruje nas bliżej implementacji – komplikuje się jeszcze bardziej.

Większość z tych konstrukcji nie jest zresztą widoczna w wynikowym kodzie. Nic więc dziwnego, że spośród całego UML-a zdecydowanie najpopularniejsze i najczęściej stosowane są diagramy klas i diagramy sekwencji (przepływu zdarzeń). Odpowiadają one bowiem niemal bezpośrednio strukturze klas i ich składowych oraz przepływowi sterowania w metodach i funkcjach. W ich przypadku przyznaję, że schemat graficzny jest bardziej przejrzysty niż tekst w języku naturalnym czy kod. Co więcej, używana przy okazji notacja jest też najszerzej znana. Autorzy wielu książek dotyczących języków programowania bardzo często bowiem “przemycają” w nich zwłaszcza diagramy klas, z nieśmiertelną strzałką w górę jako symbolem dziedziczenia.
Jeśli zaś chodzi o resztę diagramów, to ich użyteczność wydaje mi się wątpliwa. Mówiąc wprost, uważam je póki co za zwyczajne zawracanie głowy :)

Prawie jak mapa kodu

Do pisania programów wystarczy dowolny edytor tekstu i linia poleceń, ale dzisiaj trudno przecenić wygodę, jaką dają zintegrowane środowiska programistyczne (IDE). I chociaż każda porządna aplikacja tego typu – niezależnie od języka, dla którego jest przeznaczona – posiada pewną określoną i oczywistą funkcjonalność (jak choćby rozbudowane zarządzanie projektami), to w wielu można znaleźć drobne i interesujące dodatki.
Taki NetBeans (IDE do Javy) posiada na przykład pasek boczny, widoczny po prawej stronie paska przewijania w polu z kodem. Reprezentuje on cały otwarty plik, zaś naniesione na niego kreski odpowiadają linijkom, w których “dzieje się” coś potencjalnie interesującego. Mogą to być wiersze zawierające błędy kompilacji albo wystąpienia identyfikatora (nazwy), w którym aktualnie znajduje się kursor. Najważniejsza cechą tych wskaźników jest to, że można w nie klikać i w ten sposób przenosić się do odpowiednich miejsc w kodzie.

Według mnie to całkiem zmyślne rozwiązanie, przydatne zwłaszcza przy poprawianiu błędów, gdyż oszczędza przechodzenia do okienka z outputem kompilatora, a potem z powrotem do kodu. Jego użyteczność może się aczkolwiek ujawnić najlepiej tylko w przypadku, gdy IDE przeprowadza kompilację w tle i na bieżąco podkreśla i zaznacza napotkane błędy.

Na pierwszej linii

Przez kilka ostatnich dni zaglądałem na forum Warsztatu dość nieregularnie i kiedy w końcu przyjrzałem się mu dokładniej, byłem odrobinę zdziwiony. Mógłbym wręcz powiedzieć, że beze mnie forum jest zostawione niemal na pastwę losu, ale na szczęście nie cierpię na aż taki brak skromności :P Prawdą jest raczej to, że jako moderator nie jestem obecnie odosobniony w potyczkach zaliczeniowo-sesyjnych, na czym jakość sprawowania pieczy nad forum oczywiście nieco cierpi.

Zostało to zresztą zauważone i wywiązała się przy okazji ciekawa dyskusja. Według mnie najciekawszym spostrzeżeniem, jakie w niej padło, jest hipoteza dotycząca przyczyn, dla których na Warsztacie pojawiają się często osoby mające nikłe pojęcie o programowaniu w ogóle – mimo że o wiele lepszym dla nich miejscem są fora ogólnokoderskie, jakich sporo można znaleźć w sieci. Otóż wskazuje ona, że wiele osób zaczyna się interesować programowaniem głównie dlatego, że chce pisać właśnie gry. Wszelkie problemy, na jakie nieuchronnie natrafiają, uważają więc za związane z programowaniem gier. Nie zdają sobie sprawy, że osoba rozpoczynająca przygodę z kodowaniem z zupełnie innego powodu również z dużym prawdopodobieństwem może natrafić na podobne kłopoty. Cel (tworzenie gier) wydaje się im bowiem o wiele ważniejszy niż środek (nauka programowania), szukają więc pomocy w środowisku związanym z tym pierwszym.
I tak Warsztat staje się naturalnym miejscem, do którego początkujący programiści (z aspiracjami bycia programistami gier) kierują swoje kroki. Dla bardziej doświadczonych bywalców wydaje się to niezmiernie dziwne. Przecież “wiadomo”, że aby zająć się gamedevem, należy wpierw być dobrym programistą w sensie ogólnym. No cóż, rzecz w tym, że właśnie nie wiadomo – a przynajmniej nie wiedzą tego ci, którzy powinni.

Jeżeli tezę tę uznamy za prawdziwą, to wiemy już, skąd się bierze ten strumień newbies, przepływających codziennie przez forum. Aby go powstrzymać, można oczywiście budować kolejne (coraz silniejsze) tamy regulaminów i moderacji, ale chyba bardziej zależałoby nam na skierowaniu go na inne – właściwe – tory. A do tego droga jest tylko jedna: uświadamiać, że programistą gier nie zostaje się w chwili, gdy rozpoczyna się naukę jakiegoś języka i że jest to dopiero początek bardzo długiej drogi. Ładnie obrazuje ją na przykład stworzone przez Rega drzewko umiejętności programisty gier.

Trójkątyzacja

Wyświetlanie pojedynczych trójkątów – nawet najpiękniej pokolorowanych – to oczywiście dopiero początek. Niezależnie od tego, czy uczymy się obsługi jakiejś biblioteki 3D czy też piszemy własną, chcemy zająć się przede wszystkim wyświetlaniem brył. Rodzajów możliwych brył jest oczywiście sporo, ale te często używane i “regularne” ich rodzaje charakteryzują się przede wszystkim tym, że dają się opisać równaniami matematycznymi i zależnościami geometrycznymi. Wiemy na przykład, że sfera jest taką figurą, która składa się ze wszystkich punktów znajdujących się dokładnie w określonej odległości od danego – środka.
Problem w tym, że takich punktów jest “dość” dużo, bo nieprzeliczalnie wiele. Zarówno tą, jak i każdą inną bryłę w tradycyjnym renderingu zwykło się więc przybliżać automatycznie generowanymi trójkątami (jest to różnica np. w stosunku do raytracingu, czyli śledzenia promieni). Nazywa się to triangulacją i wymaga kilku operacji, takich jak:

1. Wyznaczenie odpowiedniej liczby punktów należących do powierzchni. Ich ilość powinna być regulowana – tak, aby w razie potrzeby otrzymywać siatki o różnych gęstościach punktów, a więc wpływać na jakość obrazu wynikowego (i, oczywiście, szybkość rysowania).
2. Połączenie wygenerowanych wierzchołków w trójkąty. W przypadku stosowania backface cullingu, czyli eliminowania powierzchni zwróconych przeciwnie do obserwatora, należy zadbać o właściwą kolejność wierzchołków w tych trójkątach.
3. Obliczenie wektorów normalnych dla wierzchołków. Wiadomo, że w gotowych siatkach możliwe jest przybliżone wyznaczenie tych wektorów w oparciu o sam rozkład trójkątów i kilka iloczynów wektorowych, lecz sposób ten jest niedokładny. Nie powinniśmy też z niego korzystać, gdy mamy dodatkową informację o powierzchni, którą nasze trójkąty przybliżają. W sferze na przykład dokładnie wiadomo, że normalne muszą być równoległe do wektorów biegnących od środka do punktu na powierzchni sfery.

I to w zasadzie wszystko. Warto oczywiście natychmiast sprawdzić rezultat przy pomocy renderowania w trybie wireframe, czyli rysowania tylko konturów figur. Jeśli wszystko dobrze pójdzie, to można się już pochwalić czymś więcej niż tylko jednym trójkątem, co też niniejszym czynię :)

Syndrom pustego ekranu

Zawsze jest coś do zakodzenia. Nawet jeśli żadne potężne siły zewnętrzne niczego nam nie narzucają, to mimo to (czy raczej: właśnie dlatego) pod czaszką ciągle kołaczą się pomysły. Te co lepsze przejdą w końcu do stadium projektów, by wreszcie – w nielicznym gronie – dojść do tego momentu, w którym należy otworzyć swoje ulubione środowisko programistyczne i zacząć pisać.

Uważa się powszechnie, co poparto (zbyt) wieloma przykładami, że projekty ciężko jest kończyć. Jednak związana z tym aktywna czynność – czyli porzucenie – przychodzi oczywiście bardzo, bardzo łatwo. Tak naprawdę o wiele trudniej jest zacząć i choć wiele osób mówi, że wystarczy to zrobić “tak po prostu”, w istocie sprawa jest chyba znacznie bardziej skomplikowana.
Niezależnie bowiem od tego, czy wypływamy na szerokie wody kodu, mając w głowie jedynie pomysł, czy też posiadamy dokładny plan; i niezależnie od tego, czy już zabieramy się za programowanie, czy jeszcze zajmujemy się samym projektowaniem – w każdym przypadku musi nadać swojemu dziełu zupełnie nową formę. Opieramy się wprawdzie na notatkach, szkicach, w ostateczności tym co zostało na jeszcze w głowie – lecz musimy to wszystko przerobić na całkowicie inną postać.
Można więc powiedzieć, że zaczynamy from scratch – od zera. Ta pustka ma najczęściej bardzo konkretny wymiar: dużego, ascetycznego okienka z uporczywie migającym kursorem, żądającym, abyśmy te wolne miejsce czym prędzej zapełnili. Dla mnie jej widok jest zawsze rozpraszający i nawet jeśli akurat dokładnie wiem, co chcę napisać, zbija mnie to z tropu.

W takiej sytuacji przydatne jest posiadanie jakiegoś stałego, “magicznego” szablonu, nagłówka lub jakiekolwiek innego kawałka kodu – niekoniecznie komentarza – od którego możemy zacząć. Choćby nazwa pliku, doskonale nam znane imię autora, data, nazwa projektu, krótki opis pliku, niezbędne dyrektywy dla kompilatora… Coś, co na pewno nie sprawi, że nasz kod będzie lepszy, łatwiejszy do zrozumienia czy efektywniejszy. Ale przynajmniej pozwoli zacząć go pisać.

Sam zrobiłem ten trójkąt!

Gdyby zorganizować konkurs na jak największą ilość kodu napisaną celem osiągnięcia jak najprostszego efektu, to pewnie obrazek po lewej (i kod, który za nim stoi) mógłby zająć w nim całkiem dobrą lokatę. Na pierwszy rzut oka to tylko niebieski trójkąt na żółtym tle; na drugi, trzeci i każdy następny zresztą też :) Na tym arcyprostym obrazku nie widać całego, dość skomplikowanego mechanizmu, dzięki któremu możemy go oglądać.

Rzeczony trójkąt jest bowiem efektem pracy programowego renderera, którego to od jakiegoś czasu - z konieczności, acz nie bez pewnej przyjemności - staram się popełnić. Taki kawałek oprogramowania ma za zadanie robić mniej więcej to, co potrafią zaawansowane biblioteki graficzne w rodzaju DirectX i OpenGL. Są oczywiście istotne różnice, wśród których największą jest brak wykorzystania typowych możliwości współczesnych kart graficznych - czyli właśnie przetwarzania trójkątów. Wręcz przeciwnie: wszystkie obliczenia pracowicie wykonuje główny procesor, zajmując się po kolei nie tylko każdym wielokątem, ale także każdym pikselem. Ma więc wyjątkowo dużo roboty, z którą jednak potrafi sobie poradzić.
O czym świadczy więc pokazany tutaj trójkąt? Ano o tym, że podstawowy potok renderowana ma się całkiem dobrze. W jego skład wchodzi transformowanie trójkątów przekształceniami macierzowymi, oświetlenie per-vertex, sprawdzanie widoczności pikseli przy pomocy bufora Z oraz rzutowanie perspektywiczne i rasteryzacja wynikowej płaskiej geometrii. Zgadza się, to zupełne podstawy podstaw, nieobejmujące chociażby teksturowania, lecz i tak realizujący je kod nie wiadomo kiedy rozrósł się do ponad dwóch tysięcy linijek. Faktycznie więc to był dosyć pracochłonny trójkąt :)

Zabłysnę jeszcze przykładowym kodem wykorzystującym renderer, który to wyglądać może mniej więcej tak:

Inspiracje pewną popularną biblioteką w zakresie interfejsu są, jak sądzę, doskonale widoczne :)