Game’s Anatomy 3: Komitet centralny

Pan władza

Witam w trzeciej części naszego przewodnika po anatomii gier. Zgodnie z tradycją jego przygotowanie trwało dłużej niż byśmy sobie tego wszyscy życzyli, ale mam nadzieję, że jeszcze pamiętacie co nieco z części drugiej. Jeśli jej nie czytaliście, to zachęcam do szybkiego nadrobienia zaległości, bo w przeciwnym razie może Wam być trudno zrozumieć treść tego i kolejnych tekstów. No, chyba że posiadacie już wiedzę z dziedziny algebry liniowej, werteksów i prymitywów — wtedy możecie spokojnie odpuścić sobie Game’s Anatomy 2, które właśnie o tym traktowało.

A o czym będzie tym razem? Dzisiaj zaczniemy bawić się w silnik 3D. Poważnie. W najbliższych tekstach będziemy przeprowadzać naszą trójwymiarową scenę z pamięci RAM na ekran, z premedytacją pomijając proces dostawania się do samej pamięci RAM. Dzisiaj zajmiemy się tym, co dzieje się jeszcze na CPU. Przede wszystkim więc, jak to niektórzy mówią, „kamerowaniem” naszej sceny i dobieraniem tych jej fragmentów, którymi w kolejnych tekstach nakarmimy kartę graficzną. Większość z Was zapewne kojarzy wyświetlanie gry niemal wyłącznie z GPU, tymczasem procesor centralny również ma tu niezmiernie ważną rolę do odegrania. Co więcej, zależnie od starań programistów silnika (i poniekąd też level designerów), CPU potrafi pomóc karcie graficznej rozwinąć skrzydła, albo ją kompletnie zmarnować. Dzisiaj dowiecie się jak.

Cały świat w pamięci, czyli scena 3D

Wszystko zaczyna się od zestawu modeli 3D, który to zestaw przez developerów zwykle nazywany jest sceną, a przez graczy światem. Dla zwiększenia zasobu zrozumiałych dla wszystkich określeń dodam, że modele najczęściej określa się mianem siatki lub mesha, gdyż de facto są właśnie przestrzenną siecią werteksów, połączonych w trójkąty wyznaczające wycinki płaszczyzn. Jak pamiętacie z GA2, każdy trójkąt wyznacza płaszczyznę, niezależnie od wzajemnego położenia jego wierzchołków (oczywiście pomijając sytuację, gdy są one współliniowe). Dlatego właśnie karta graficzna wykorzystuje trójkąty i dlatego gry wyścigowe musiały tak długo czekać na koła, które rzeczywiście wyglądają jak koła… przynajmniej z pewnego dystansu.

Dla przypomnienia, każdy mesh posiada swoją przestrzeń lokalną, w której wyznaczone są współrzędne jego werteksów. W tej przestrzeni te koordynaty są zawsze takie same, dzięki czemu nawet kiedy model się obraca, wiemy gdzie te wierzchołki powinny się znajdować (wystarczy zastosować do nich przekształcenie z jednej przestrzeni do innej). Silnik wyznacza mu również zestaw macierzy przekształceń, które umożliwiają poustawianie werteksów względem dowolnego układu współrzędnych tak, żeby model wyglądał jak widziany z określonego miejsca pod określonym kątem. To się przydaje chociażby kamerze — bez tych wszystkich przekształceń świat gry zawsze widzielibyśmy z jednego punktu (globalnego (0, 0, 0)), pod jednym kątem i bez perspektywy. Nuda by była, nie?

Same werteksy posiadają, poza współrzędnymi, zestaw arbitralnych parametrów takich jak kolor, współrzędne tekstur (zwane texcoord, co jest skrótem od „texture coordinates”, obviously) itp., dzięki którym shader wie co dokładnie ma zrobić z tym konkretnym werteksem. To, że można sobie do tych parametrów wstawić niemal dowolne wartości jest ważne, bo znacznie poszerza możliwość kreatywnego wykorzystania shaderów.

Co ja widzę?

To wszystko siedzi sobie w RAMie i czeka na wyrenderowanie. Jak jednak wspominałem we wstępie, zanim silnik wyśle cokolwiek do karty graficznej, musi zdecydować co jest sens wysyłać. W tym celu sprawdza, które obiekty znajdują się w polu widzenia kamery (wewnątrz tzw. view frustum). Dodatkowo może sprawdzić też czy nie są zasłonięte przez inne obiekty. To działanie ogółem określa się mianem „culling”, ponieważ jego celem jest wstępne odrzucanie modeli, których nie ma potrzeby renderować, ani nawet przesyłać do karty graficznej.

Kamera, czyli znajomy nieznajomy

Żeby zrozumieć jak działa najbardziej podstawowa metoda wstępnego odrzucania meshów musicie pojąć konstrukcję kamery w grze. Oczywiście nie składa się ona z kliszy i obiektywu. Jej części składowe (w rzucie z góry, ale rzut z boku wyglądałby identycznie) ilustruje poniższy obrazek:

Kamera z perspektywą

Środek to oczywiście środek kamery (i początek jej przestrzeni lokalnej), czyli punkt, który wyznacza jej położenie, wokół którego się ona obraca i względem którego oblicza się położenie wszystkich wierzchołków, które już trafią do shadera i mają zostać wyświetlone — ale o tym następnym razem. FOV, czyli „field of view”, to kąt widzenia — teoretycznie powinno się to nazywać „view angle”, ale „field of view” się przyjęło i trudno… Nazewnictwo w grafice komputerowej to większy bałagan niż ruch na trzypasmowym rondzie. W każdym razie te dwie rzeczy powinny być dość jasne, bo mówimy o nich również przy fizycznych kamerach, a nawet przy naszych oczach. Near i far to inna historia.

Near plane i far plane to dwie płaszczyzny wyznaczające graniczne odległości widzenia kamery, tak jak FOV wyznacza jej kąt widzenia. Razem z FOV, te dwie płaszczyzny wyznaczają bryłę określaną mianem „view frustum”. Każdy model, którego choć jeden werteks znajduje się w obrębie view frustum jest uznawany za widoczny — pozostałe są ignorowane. To jest właśnie frustum culling.

Oczywiście od razu widać, że podstawowym ograniczeniem tego procesu jest fakt, że nie bierze on pod uwagę zasłaniania obiektów przez inne obiekty — nawet jeśli cały widok zasłania nam stodoła, to i tak do karty graficznej wysłane zostaną wszystkie modele znajdujące się wewnątrz stodoły lub za nią, o ile tylko znajdują się one w obrębie view frustum. Niezależnie od prozaicznego faktu, że nigdy nie będą widoczne na ekranie. To straszne marnotrawstwo, bo procesor będzie musiał wysłać je do karty graficznej, która w tym czasie będzie siedzieć na dupie i nudzić się czekając na przesyłkę. Tym problemem zajmuje się occlusion culling, o którym za chwilę.

Choć frustum culling jest konieczny, to prowadzi on czasem do dziwnych sytuacji jeśli programiści nie upewnią się, że odległość od środka kamery do jakiegokolwiek trójkąta nigdy nie będzie mniejsza niż odległość do dowolnego punktu na near plane. Wtedy mamy do czynienia z „wnikaniem” kamery do wnętrza obiektu i możliwością patrzenia przez ściany, ludzi, drzewa czy co tam jeszcze. W przypadku far plane ten efekt również występuje, i to znacznie częściej, ale nie jest tak wyraźny, a to z dwóch powodów. Po pierwsze „przycięcie” obiektu nie rzuca się tak w oczy kiedy jest on bardzo daleko i kiedy owo przycięcie nie skutkuje gapieniem się w bebechy rzeczonego obiektu. Po drugie, zwykle far plane współdziała z mgłą, czyli mechanizmem, który „wywabia” kolor z obiektów w miarę zwiększania się ich odległości od kamery — dzięki temu w miejscu obcięcia obiekt jest już całkowicie przykryty mgłą, a więc niewidoczny.

Near plane -- odkrywa bogate wnętrze modeli 3D

Jest też trzeci powód, ale ma zupełnie inny charakter. Po prostu w dzisiejszych grach, z racji dostęptności mocy obliczeniowej i pamięci, mamy near i far rozpięte tak szeroko, że spokojnie obejmują całe lasy czy miasta — jak np. w GTA4. Inna sprawa, że rozstrzelenie ich w ten sposób powoduje innego rodzaju anomalie, ale o nich porozmawiamy przy okazji bufora głębi.

Powyższy opis elementów składowych dotyczy kamery z perspektywą, czyli tej najbardziej dla nas naturalnej, choć bardziej skomplikowanej matematycznie. Istnieje jednak jeszcze drugi rodzaj kamery — ortogonalna. Czym się różnią? Oczywiście tym, że kamera ortogonalna nie używa przekształcenia zwanego perspektywą, a więc nie występuje w niej efekt pozornego zmniejszania się obiektów ze wzrostem odległości. Nie ma również kąta widzenia, gdyż kamera tego rodzaju rzutuje obraz na płaszczyznę w najprostszy z możliwych sposobów, po prostu usuwając jedną współrzędną. To coś jak rysunek techniczny — bliższego porównania nie mogę znaleźć, może ktoś mi jakieś podpowie? View frustum takiej kamery wygląda jak zwyczajny prostopadłościan.

Ortogonalni na lewo, perspektywiczni na prawo

Do czego taka kamera może się przydać? W grach najczęściej jest używana do wyświetlania GUI i HUD, które są dwuwymiarowe i zwyczajnie nie potrzebują perspektywy. ich obraz jest później nakładany na obraz z kamery perspektywicznej renderującej świat gry. Kamera „ortho” może być też użyta do wyświetlania samego świata, zwłaszcza w grach typu 2.5D. Dodatkowo, rzut ortogonalny jest zawsze dostępny w edytorach 3D, jak Blender, oraz edytorach map do gier, jak Hammer czy Unreal Editor — znacznie ułatwia on bowiem edytowanie meshy oraz ustawianie ich w trójwymiarowych światach, a dodatkowo umożliwia korzystanie z rysunków poglądowych, które można zwyczajnie ustawić jako tło i dopasowywać do nich ustawienie obiektów czy werteksów.

Komórki i portale

Dodatkową metodą rozpoznawania co jest widoczne, a więc optymalizacji wyświetlania, jest statyczny podział sceny na kawałki i połączenie tych kawałków przejściami — a więc occlusion culling aka portal culling. Tak działa np. Umbra, czyli najpopularniejszy (o ile nie jedyny) middleware tego rodzaju.

Wspomniane kawałki noszą nazwę komórek i są to zwyczajnie prostopadłościenne wycinki świata gry, z których każdy obejmuje swoim zasięgiem jakieś obiekty. Zasada, które obiekty są przypisane do danej komórki jest taka sama jak w wypadku frustum cullingu — jeśli choćby najmniejszy fragment obiektu zahacza o dany sześcian, to ten obiekt jest „pod opieką” danego sześcianu. Pogłoski jakoby komórki occlusion cullingu pobierały haracz za wspomnianą opiekę są nieprawdziwe i krzywdzące. Nie zmienia to jednak faktu, że komórki mogą posiadać pod sobą cały harem obiektów. Nie mówiąc już o tym, że się nimi między sobą dzielą… No dobra, mówiąc bez dziwnych metafor, dany obiekt może znajdować się w obrębie wielu komórek i być do nich przypisany, co oznacza, że będzie uznany za widoczny jeśli choć jedna z nich będzie widoczna.

Komórki są połączone portalami, czyli „oknami” przez które z jednej komórki widać drugą, dlatego czasem tą konkretną metodę nazywa się portal culling. Zasada działania jest prosta jak życiorys Zenka. Najpierw znajdujemy komórkę, w której aktualnie przebywa środek kamery. Następnie odszukujemy wszystkie komórki, które całkowicie lub częściowo leżą w obrębie view frustum — to jest proces podobny do frustum cullingu, z tym że tutaj szukamy nie modeli, a komórek. Teraz z tych komórek wybieramy tylko te, do których możliwe jest poprowadzenie linii prostej przechodzącej od kamery przez portale.

Żeby sobie ułatwić sprawę i przyspieszyć cały proces, komórki mogą być pogrupowane w tzw. drzewo. To znaczy, że zamiast „płaskiej” struktury, w której wszystkie komórki są równie ważne, mamy hierarchię, w której mniejsze komórki zawierają się w większych. To trochę jak blok mieszkalny, który zawiera mieszkania, które zawierają pokoje, które zawierają szafy, które zawierają szuflady itd. Dzięki temu system może wykonywać obliczenia znacznie szybciej, bo do komórek mniejszych wchodzi tylko wtedy, kiedy ta w której się zawierają przejdzie test widoczności. Zrozumiałe jest, że dzięki temu można rach-ciach wykluczyć całe połacie terenu.

Wizualizacja occlusion cullingu. Lewa: renderowane wszystkie elementy w view frustum, Prawa: renderowane tylko niezasłonięte obiekty

Po zakończeniu tego procesu otrzymujemy listę obiektów do wyrenderowania, która nie zawiera absolutnie żadnego obiektu, który nie byłby chociaż częściowo widoczny. Oczywiście czasem może się zdarzyć, że zza ściany widać tylko dwa piksele drapacza chmur, który i tak w całości trafi do GPU, ale to i tak dużo lepsze niż sam frustum culling.

Polecam obejrzeć poniższy materiał opisujący działanie Umbra 3. Zapewne nie każdy z Was zrozumie o czym mówi sympatyczny pan nabijający się z George’a Michaela, ale samo wideo bardzo dobrze pokazuje opisywany mechanizm:

A dlaczego nie można tego wszystkiego zrobić wykorzystując samą geometrię, bez użycia dodatkowych struktur takich jak portale i komórki? Można, ale niewiele by to dało, gdyż sprawdzanie co widać a czego nie przy użyciu wyświetlanej geometrii byłoby bardzo powolne. Modele 3D mają wyglądać, a niekoniecznie nadawać się do tego typu voodoo. Dlatego właśnie buduje się możliwie proste struktury, których zadaniem jest przyspieszenie tego procesu. Wszystko po to, żeby gry chodziły możliwie jak najszybciej i żeby możliwie jak najmniej mocy obliczeniowej GPU się marnowało, bo dzięki temu można ją wykorzystać do poprawienia wyglądu sceny.

Jednostronna umowa

Istnieje jeszcze jeden rodzaj cullingu, który następuje już na karcie graficznej, ale postanowiłem napisać o nim tutaj, żeby już mieć je wszystkie w jednym miejscu. Chodzi o tzw. backface culling.

Zasadniczo trójkąt wyznacza nam jedną płaszczyznę, którą można „oglądać” z dwóch stron — z dołu i z góry, niczym kartkę papieru. To oznacza, że każdy trójkąt powinien teoretycznie być renderowany dwukrotnie, co oczywiście nie ma sensu z uwagi na fakt, że najczęściej z tych trójkątów zbudowane są zamknięte bryły, których pustego wnętrza nikt nigdy oglądać nie będzie, bo nikogo ono nie interesuje. Z tego względu wprowadzono backface culling, czyli odrzucanie jednej ze stron naszego trójkąta. Skąd karta graficzna wie, która strona powinna być wyświetlona, a która nie? Dzięki współrzędnym werteksów i kolejności w jakiej były one dodawane do prymitywów — wyświetlana jest ta strona, z której werteksy były dodawane zgodnie z ruchem wskazówek zegara.

Przesyłka niezbyt ekspresowa

Teraz już wiadomo, co trzeba wyrenderować. Silnik wie już, które obiekty są widoczne dla naszej kamery i nie są przez nic zasłonięte. Nasze modele są już spakowane, zasiadły na miejscach i za chwilę pojadą po szynach do GPU. Ta podróż, niczym przechodzenie z pokoju do pokoju w Modzie na Sukces, zakończy się w kolejnym odcinku Game’s Anatomy. Zanim to jednak nastąpi, jeszcze kilka słów wyjaśnienia po co ta segregacja na tle widoczności.

Dzisiejsza karta graficzna może wyświetlić miliony, a nawet dziesiątki milionów trójkątów zawartych w pojedynczym obiekcie z prędkością 100 albo i więcej Hz. Framerate może się natomiast udławić tysiącem prostych sześcianów, po 12 trójkątów w każdym. Dlaczego? Ano dlatego, że karta graficzna pracuje pod dyktando komitetu centralnego CPU, który jest od niej znacznie wolniejszy. Zapewne domyślacie się, że to co Wam tutaj opisuję to tylko kawałek całej historii. Najważniejszym kawałkiem, który pomijam są tzw. render states. Pomijam to może źle powiedziane, ale nie padło jak dotąd to określenie. Otóż render states to po prostu ustawienia renderowania określonego obiektu — mówią karcie graficznej czy obiekt ma być renderowany dwustronnie (z pominięciem backface cullingu), czy ma mieć jakiś przypisany na sztywno kolor, czy ma być wyświetlany jako wireframe, czy ma obsługiwać przezroczystość itd.

Tych ustawień jest cała masa, a każdy kolejny obiekt oznacza przestawianie ich od nowa — niezależnie od tego, że poprzedni model mógł być identyczny pod każdym względem i korzystać z takich samych ustawień! To niestety chwilę zajmuje, a chwila to bardzo długo kiedy chcemy żeby wyrenderowanie całej klatki obrazu trwało mniej niż 1/30 albo 1/60 sekundy. Co gorsza, później trzeba jeszcze wysłać prymitywy do GPU. Zestawiając te dwa fakty mamy sytuację, w której kiedy wysyłamy dużo małych paczek (po kilka czy kilkanaście trójkątów), to czas wysyłania i przestawiania na CPU jest większy niż koszt renderowania na GPU. W rezultacie procesor graficzny opiera się o łopatę. To tak, jakby zamiast dowieść ciężarówkę cegieł, wozić je po trochu Tarpanem — poprzedni transport zostanie zużyty na długo zanim zdąży dojechać nowy, dlatego optymalnie jest wpakować do każdego transportu tak dużo werteksów ile się tylko zmieści.

Nie oznacza to jednak, że najlepiej byłoby ze wszystkich statycznych meshy zrobić jeden obiekt, bo nasz świat może być na tyle duży, że przekroczymy te kilka milionów werteksów, które możemy renderować bez wysiłku. To powinno Wam uświadomić wagę cullingów.

To be continued…

W następnej części Game’s Anatomy przeniesiemy się wreszcie na kartę graficzną i porozmawiamy o rasteryzacji, shaderach, kolorowaniu fragmentów i owijaniu tekstur wokół modeli. Będzie się działo.

Do zobaczenia i zachęcam do zadawania pytań w komentarzach, jeśli jakiekolwiek się Wam nasuwają.