Magiczna interpolacja

Shaderami ostatni raz zajmowałem się (dość teoretycznie) parę lat temu, więc od tego czasu minęła już cała epoka – albo i kilka. W ramach przypomnienia oraz nauki HLSLa (bardzo prostego i przyjemnego języka swoją drogą) przeglądam więc implementację różnych technik graficznych, głównie oświetlenia i cieniowania.
Przy okazji natrafiłem tam na pewnego rodzaju shaderową sztuczkę. Bardziej zaawansowanym programistom grafiki pewnie nie będzie się ona wydawała niczym nadzwyczajnym. Dla mnie jednak jej pomysłowość i prostota była – że użyję modnego ostatnio słowa – porażająca :)

Otóż, jak powszechnie wiadomo, programowalny potok grafiki to przede wszystkim dwie części: vertex i pixel shader. W tym pierwszym transformujemy wierzchołki i wyliczamy inne ich dane, które potem trafiają do shadera pikseli. Ten zaś z racji częstości wykonywania musi być jak najlżejszy i dlatego jak najwięcej operacji trzeba wykonywać per vertex. Z drugiej strony, aby cokolwiek ładnie wyglądało (oświetlenie, nierówności, itd.) musi być liczone per pixel.
I tutaj pomaga część potoku włączająca się między shaderami, czyli interpolator. Jego głównym zadaniem jest interpolacja wartości koloru rozproszenia i współrzędnych tekstur na poszczególnych pikselach. To dzięki niemu piksel w środku trójkąta może mieć właściwy kolor rozproszenia i mieć przypisany odpowiedni teksel.

Trik polega na tym, że w interpolować możemy też inne dane. Typowy przykład to choćby pozycja w przestrzeni 3D – już przetransformowana, ale jeszcze nie zrzutowana na płaszczyznę projekcji. Podobnie może być z wektorami normalnymi. Już te dwie dane (plus kierunek światła) wystarczają, by otrzymać proste oświetlenie per pixel, które wygląda realistycznie, jeżeli tylko powierzchnia nie wymaga mapowania nierówności.
Żeby to wszystko było możliwe, wystarczy nieco oszukać sprzęt i oznaczyć określone pole wyjścia vertex shadera – zawierające np. wspomnianą normalną czy pozycję – jako… współrzędne tekstury. Wtedy zostaną poddane interpolacji i wyliczone w ten sposób wartości będą dostępne w pixel shaderze. A tam już wcale nie musimy ich traktować jako koordynaty tekstury i znów mogą być pozycją lub normalną.

W sumie wspomniane proste oświetlenie per pixel to kwestia użycia takich dwóch shaderów:

Różnica między oświetleniem wierzchołkowym a pikselowym
Źródło

Oczywiście nie ma tutaj wygaszania ani kontroli kształtu światła, ale to i tak długi przykład ;) Widać jednak, że to co kosztowne – przekształcenia macierzowe – są wykonywane dla wierzchołków, a nie pikseli. W pixel shaderze liczymy tylko oświetlenie, a to – jak wiemy i widzimy powyżej – tylko kwestia odpowiedniego iloczynu skalarnego. Możemy go obliczyć, bo w wyniku interpolacji mamy zarówno pozycję piksela w przestrzeni, jak i jego normalną.

A efekty wyglądają mniej więcej tak:

Świadomość wyboru

Każdy programista posługuje się zestawem narzędzi służącym mu do pracy: językiem programowania, środowiskiem developerskim, kompilatorem, debugerem, itd. Są to takie same atrybuty jak ołówek dla rysownika czy hebel dla stolarza. Jako podobne do takich właśnie przedmiotów produkty, mogą być one oceniane pod względem różnych kryteriów, w tym najważniejszego – użyteczności.

Narzędzia, jakimi się posługujemy jako koderzy, powinny więc być przede wszystkim adekwatne do sytuacji, w której się znajdujemy. Zawsze bowiem tworzymy coś przeznaczonego do działania w określonym kontekście – środowisku, platformie sprzętowej czy we współpracy z innymi programami. Jednocześnie nakładamy też pewne wymagania na produkt wynikowy czy też na sam proces jego tworzenia.
Możemy na przykład chcieć, by był on maksymalnie efektywny albo zajmował jak najmniej pamięci operacyjnej. Innym wymaganiem może być szybkość realizacji projektu – co zwykle oznacza, że pisząc nasz program, chcemy namęczyć się jak najmniej i skorzystać z jak największej ilości istniejącego już kodu. Wreszcie może nas interesować też elegancja wynikowego kodu źródłowego – chociaż na nią największy wpływ mamy sami.

W teorii właśnie takimi przesłankami powinniśmy kierować się, gdy przychodzi nam wybrać narzędzie (na przykład język programowania) pomocne w tworzeniu. Oczywiście możemy do nich dodać własne – łącznie z tym dla niektórych najważniejszym: czy dane narzędzie znam wystarczająco dobrze i/lub czy chcę się go (pod/na)uczyć. Grunt żebyśmy byli świadomi powodów, dla których decydujemy na taki a nie inny wybór.
Dotyczy to nawet tych mniej racjonalnych powodów w rodzaju: “bo ‘wszyscy’ tego używają”, “bo dany język/biblioteka/itp. po prostu mi się podoba”, “bo przyjemnie mi się w tym pisało”, itp. Nie muszą one wcale być gorsze od tych solidnie ufundowanych i sprawdzonych argumentów. Jeżeli bowiem żadne zewnętrzne i niezależne od nas okoliczności nas nie ograniczają, powinniśmy dążyć do jak największej satysfakcji z tworzenia – zarówno z samego procesu, jak i z osiąganych rezultatów.

Układy odniesienia

Programując grafikę czy choćby cokolwiek, co ma się ostatecznie pokazać na ekranie, cały czas operuje się współrzędnymi w przestrzeni. Wówczas trzeba zawsze pamiętać, że ten zestaw liczb – zwykle X, Y i ewentualnie Z – nie istnieje sam dla siebie i zawsze jest podawany względem czegoś. Tak więc wszystkie współrzędne są względne, bo nawet nazywane “bezwzględnymi” różnią się tylko tym, że ich punkt odniesienia jest wyjątkowo dobrze zdefiniowany – na przykład jako lewy górny róg ekranu lub punkt (0,0,0) nieprzetransformowanego układu sceny 3D.

Kłopoty zaczynają się wtedy, gdy zaczynamy nieświadomie mieszać koordynaty korzystające z innych układów odniesienia. Nadal czasami mi się to zdarza w kodzie systemu GUI, mimo że starałem się bardzo dokładnie określić względem czego jest określona np. pozycja danej kontrolki i jakie przekształcenia (głównie odpowiednia translacja) są wykorzystywane przy rysowaniu każdego elementu.
To wszystko jest oczywiście w dwóch wymiarach. W 3D potencjalnych punktów odniesienia jest nawet więcej; wśród nich mamy chociażby ten związany z kamerą, z modelem, ze światłem, i tak dalej. A co gorsza, ocena czy taki lub inny błąd wynika właśnie z pomylenia różnych układów współrzędnych jest trudniejsza właśnie ze względu na obecność tego trzeciego wymiaru.

Wniosek stąd taki, że należy pamiętać o używanym aktualnie układzie odniesienia. Łatwo bowiem napisać:

i za jakiś (niedługi) czas zastanawiać się, względem czego te x, y czy z powinno tak naprawdę być liczone. A podejrzewam, że u większości programistów umiejętność rozwiązywania tego typu łamigłówek jest dość… względna :)

Bolączki C++ #4 – Właściwości

W teorii OOPu klasa może składać się wielu różnych rodzajów elementów. Mamy więc pola, metody, właściwości, operatory, typy, zdarzenia czy nawet sygnały (cokolwiek to oznacza). Z drugiej reprezentacja obiektu w pamięci operacyjnej działającego programu to niemal wyłącznie wartości jego pól (z drobną poprawką na ewentualną tablicę metod wirtualnych).
To są dwie skrajności, a między nimi mam wszystkie obiektowe języki programowania. Jedne oferują w tym zakresie więcej, inne mniej. Weźmy na przykład C++.

Oprócz niezbędnych pól i metod pozwala on definiować przeciążone operatory i typy wewnętrzne. Nie posiada za to niezwykle przyjemnego “cukierka składniowego”, czyli właściwości. Z punktu widzenia programisty właściwości to takie elementy interfejsu klasy, który wyglądają jak pola. Różnica polega na tym, że dostęp do właściwości nie musi oznaczać bezpośredniego odwołania do pamięci, lecz może mu towarzyszyć dodatkowy kod – na przykład sprawdzający poprawność ustawianej wartości.
Prawdopodobnie najbardziej elastyczny mechanizm właściwości wśród popularnych języków programowania ma C#. Tam kod wykonywany przy pobieraniu i ustawianiu właściwości pisze się bezpośrednio w jej deklaracji:

Nieco gorzej jest w Delphi czy Visual C++, gdzie istnieje deklaracja __declspec(property). Tam trzeba napisać odpowiednie metody służące pobieraniu/ustawianiu danej wartości (akcesory) i wskazać je w deklaracji właściwości.
Natomiast w czystym C++ rzeczone akcesory – metody Get/Set – stosowane bezpośrednio są jedynym wyjściem. Niezbyt ładnym rzecz jasna.

Bez właściwości można się obyć, a ich wprowadzenie do języka pewnie nie byłoby takie proste. Pomyślmy na przykład, jak miałyby się one do wskaźników i referencji: o ile pobranie adresu właściwości nie ma sensu, o tyle przekazywanie jej przez referencję byłoby z pewnością przydatne.
Dlatego chociaż akcesory wyglądają brzydko, pewnie jest przez długi czas będą jedyną opcją. Na pocieszenie dodam, że programiści Javy są pod tym względem w identycznej sytuacji :)

Ten straszny rendering

Mogę bronić się rękami i nogami, mogę starać się obchodzić temat ze wszystkich stron, ale w końcu przyjdzie taki czas, że po prostu trzeba będzie zająć się esencją silnikologii – czyli grafiką 3D :) Zwiększenie liczby wymiarów o 50% powoduje mniej więcej podobny przyrost potencjalnych powodów bólu głowy. Dlatego też nie należy się wybierać w tę wyprawę bez odpowiedniego przygotowania i planu.

Plan natomiast jest generalnie dość prosty, lecz jak wiemy diabeł tkwi w szczegółach. W grafice 3D mamy oczywiście do czynienia ze sceną, w której mogą się znaleźć przeróżne jej elementy – zwane też węzłami lub encjami. Takim elementem może być instancja modelu, teren oparty na mapie wysokości, emiter cząsteczek czy jeszcze coś innego. Ważne jest, że każdy taki element zajmuje się w przestrzeni określoną pozycję i miejsce; są one najprościej definiowane przez otaczający prostopadłościan równoległy do osi układu współrzędnych, czyli axis-aligned bounding box (AABB).

Źródło obrazka

Zadaniem obiektu sceny jest między innymi szybka odpowiedź na pytanie, czy dany węzeł znajduje się w polu widzenia kamery. Jako że pole widzenia jest najczęściej perspektywiczne i ma kształt ściętego ostrosłupa, czynność ta (eliminowanie niewidocznych obiektów) jest znana jako frustum culing. Można ją przeprowadzać, organizując odpowiednio przestrzeń sceny, dzieląc ją na sektory – na przykład przy pomocy drzewa ósemkowego.

Naturalnie wszystkiego wyeliminować się nie da i w końcu trzeba będzie coś narysować :) I tutaj znowu mamy kolejną dość skomplikowaną kwestię. Stosunkowo łatwo jest zaprogramować rysowanie każdego rodzaju obiektów tak, aby każdy odpowiadał tylko za siebie i nie zakładał nic chociażby o stanach renderowania przed i po tej operacji. Rzecz w tym, że o ile wygląda to bardzo ładnie z punktu widzenia zasad programowania obiektowego (jak okiem sięgnąć – hermetyzacja!), to w praktyce efektywność takiego rozwiązania byłaby co najmniej wątpliwa. Niestety dla karty graficznej przypisanie konkretnego wierzchołka do konkretnego obiektu w scenie nie ma żadnego znaczenia. Liczy się bowiem to, jakie stany renderowania, mieszania tekstur, itp. trzeba ustawić, aby ów wierzchołek narysować.

Źródło obrazka

Stąd potrzebne jest pojęcie materiału, znane z edytorów grafiki 3D. Tutaj jednak oznacza ono nie tyle wygląd powierzchni, co wszystkie właściwości wpływające na wygląd geometrii, które nie są zapisane w danych wierzchołków. Może to być więc zarówno tekstura, jak i właściwości świetlne czy nawet określenie, czy dana powierzchnia jest półprzezroczysta czy nie.
Aby efektywnie wyrenderować scenę, trzeba więc grupować fragmenty jej geometrii nie względem obiektu, ale materiału. Dodatkowo trzeba też pamiętać o tym, że pewne zmiany są bardziej kosztowane niż inne (taniej jest zmienić choćby teksturę niż shader) i uwzględniać to przy sortowaniu.

Na koniec pozostaje jeszcze ostatni etap, gdy dane o wierzchołkach trafiają już do karty graficznej i muszą być przetworzone przez shader, aby mogły zostać odpowiednio pokazane. Napisanie takie shadera, a potem sterowanie nim (np. włączanie lub wyłączanie pewnych jego fragmentów) to też nie jest lekki orzech do zgryzienia. Jest to solidny kawałek matematyki i geometrii połączonej z kombinowaniem, jak to wszystko zmieścić w limicie instrukcji, który jest nieubłagany :)

To oczywiście nie wszystko – nie wspomniałem na przykład w ogóle o oświetleniu czy cieniach, które wymagają renderowania potraktowanych nimi fragmentów więcej niż raz. Ale już z obecnego opisu widać, że jedna literką ‘D’ więcej to jednocześnie sporo dodatkowych literek ‘P’ – jak ‘problemy’ ;P

Ezoteryczne języki programowania

Pisać programy można na wiele sposobów, jako że obecnie mamy całe mnóstwo różnych języków programowania przeznaczonych dla różnych zastosowań i gustów. Wśród wyjątkowo pozycję zajmują jednak, które wcale nie dążą do tego, aby być wygodne, użyteczne, efektywne czy mieć inne podobne zalety. Otóż zwykle jest wręcz przeciwnie.
Chodzi mi o języki ezoteryczne. Ciężko za bardzo powiedzieć, do czego faktycznie one służą, ale jedno jest pewne: są one bardzo dziwne i przez to całkiem interesujące :)

Jednym z takich nietypowych języków jest twór o przeuroczej nazwie Brainfuck. Jego cechą szczególna jest mała liczba dostępnych instrukcji, których jest tylko osiem. Mimo to język jest zupełny w sensie Turinga, co z grubsza znaczy, iż można w nim zakodować dowolny algorytm.
Jak zatem wygląda w nim chociażby tradycyjny Hello World? Ano mniej więcej tak:

Dość nieoczywiste, prawda? :) Na pewno pomaga tu wyjaśnienie, że w tym języku wykonujemy wszystkie operacje przy pomocy wskaźnika skaczącego po wirtualnej pamięci. Wskaźnik ten można inkrementować i dekrementować (instrukcje > i <), przechodząc do kolejnych komórek; to samo można też robić z zawartością pamięci (+ i -). W końcu jest też możliwość realizacji jednego rodzaju pętli (a co za tym idzie także instrukcji warunkowych) oraz wejścia/wyjścia dla pojedynczych znaków. Innymi słowy mamy wszystko, co jest programiście potrzebne do szczęścia :)

Nazwa języka Brainfuck sugeruje aczkolwiek, że programowanie w nim nie jest zbyt proste i chyba powyższy kod dobrze o tym świadczy. Lecz tak naprawdę BF jest jednym z prostszych języków ezoterycznych! Dane są w nim oddzielone od kodu, pamięć jest jednowymiarową tablicą (taką jak w rzeczywistych komputerach), a wszystkie instrukcje są sprecyzowane jednoznacznie i zawsze takie same, Czy może być inaczej?
Odpowiedź jest naturalnie twierdząca, a świadczy o tym przykład języka Malbolge - uważanego powszechnie za najtrudniejszy istniejący obecnie język programowania. Jest on tak trudny, że program Hello World został w nim napisany nie bezpośrednio przez człowieka, lecz przy pomocy... specjalnie spreparowanego algorytmu genetycznego! To wszystko dlatego, że w kodzie napisanym w tym języku występuje nieprawdopodobna liczba zależności między instrukcjami. Wykonują one na przykład inne czynności w zależności od adresu pamięci, pod którym się znajdują (jako że dane i kod są umieszczone oczywiście w tym samym obszarze wirtualnej pamięci). Dodatkowo niemal wszystkie instrukcje po wykonaniu same się modyfikują, i to oczywiście zgodnie z trudną do ogarnięcia permutacją. Prawda, że programowanie w czymś takim to nie byłaby bułka z masłem? ;]
A jednak nawet w takim pokręconym języku ktoś wykonał drugie popularne zadanie programistyczne, czyli napisał program wypisujący słowa piosenki 99 Bottles of Beer. W większości normalnych języków sprawa zajęłaby najwyżej kilka minut, ale tutaj była to kwestia ośmiu... lat :)

Ale to jest właśnie urok języków ezoterycznych oraz ich sens, którym jest całkowity brak sensownego zastosowania/ Albo raczej konieczność włożenia ogromnego wysiłku, jeśli komuś przyszłoby do głowy, by tego typu język rzeczywiście do czegoś sensownego zastosować. I o to tutaj chodzi.
Kontakt z takimi wynalazkami ma jeszcze jedną pozytywną cechę. Otóż widząc przykłady napisanego w nich kodu mamy wielką ochotę podziękować twórcom "normalnych" języków programowania, że napisanie w nich interpretera czy kompilatora języka ezoterycznego jest zwykle przynajmniej kilka razy łatwiejsze niż stworzenie programu Hello World w takim właśnie języku :)

Słowo kluczowe ‘base’

Z dobrodziejstwa metod wirtualnych po prostu nie można nie korzystać. Dzięki nim kod jest bardziej elegancki, krótki, często (wbrew powszechnej opinii) efektywniejszy i naturalnie bardziej obiektowy :) Wszystkie te zalety opierają się oczywiście na tym, że tak naprawdę nie musimy wiedzieć, jaką wersję metody wirtualnej – oryginalną czy nadpisaną w klasie pochodnej – wywołujemy w danym przypadku.
Sama metoda aczkolwiek ‘wie’ to doskonale. Czasami zdarza się jednak, że chcielibyśmy wywołać jej odziedziczoną wersję, pochodzącą z klasy bazowej. Podobnie jak większość języków, C++ nie czyni tego automatycznie (z wyjątkiem konstruktorów i destruktorów), jako że nie zawsze jest to potrzebne. Ale nierzadko się przydaje i jest wygodne.

W wielu językach, jak choćby Delphi czy C#, mamy pomocnicze słowa kluczowe, służące do takich właśnie wywołań. W przeciwieństwie do nich C++ oferuje jednak dziedziczenie wielokrotne, wobec tego czasami klasa bazowa nie jest określona jednoznacznie. Dlatego też chcąc wywołać odziedziczoną wersję metody, musimy jawnie użyć nazwy tej klasy., np.:

Wielodziedziczenia używamy jednak rzadko i w zdecydowanej większości sytuacji klasa bazowa będzie tylko jedna. Na takie okazje Visual C++ przewidział własne słowo kluczowe __super. Możemy też pokusić się o bardziej przenośne rozwiązanie, definiując taki oto szablon:

a wówczas zyskamy swoje własne “słowo kluczowe” base o możliwościach podobnych do tych z C#:

Na nieszczęście jest tu mnóstwo różnych “ale”. Największym problemem jest to, że właściwej klasy bazowej (tutaj CFoo) nie ma jak zainicjalizować w klasie pochodnej, wobec czego musi ona dysponować domyślnym konstruktorem, który na dodatek będzie używany zawsze. To poważny feler, którego nie ma za bardzo jak naprawić. Dlatego jeśli bardzo doskwiera nam brak słowa base, to chyba jedynym sposobem jest… ręczne dodawanie typedefa podobnego do tego w szablonie Inherits.
Dopiero C++0x wprowadzi możliwość dziedziczenia konstruktorów (na zasadzie przekierowywania ich parametrów do klasy bazowej), która pozwoli wyeliminować wspomniane ograniczenie. Wówczas taka wersja szablonu:

powinna zdać egzamin dla dowolnej klasy T.