Dnešní lekce bude ryze teoretická. Začneme si povídat o optimalizační metodě quadtree, kterou v následující lekci použijeme na vykreslování komplexního terénu. Lekce tedy nebude tentokrát obsahovat příklad, to si ale vynahradíme příště, kdy vytvoříme novou aplikaci, využívající náš "engine" a hlavně dnes popsané principy.
Optimalizace v oblasti grafiky má nesmírný význam, protože i dnešní výkonné karty mají svá omezení a plýtvat jejich potenciálem (jak je dneska v módě a nemusí se jednat pouze o grafické karty) je krajně nevhodné! Engine, který se nezabývá optimalizacemi vykreslování dat a spoléhá jen na hrubou sílu grafického čipu, nikdy nemůže být úspěšný. Tohle pochopil John Carmack a vytvořil například geniální engine Quake3, na kterém běží mnoho her i dnes, 4 roky po uvedení hry Quake 3.
My se pochopitelně nebudeme zabývat takto složitými algoritmy, ale někde začít musíme. Jedna z častých úloh v Direct3D je vykreslování komplexní plochy a nemusí se jednat pouze o terén. Metod optimalizace vykreslování terénu je spousta, například Quadtree, který si rozebereme v dnešní lekci, OctTree se hodí pro složitější terény nebo třeba LOD (Level of Detail), kde pro změnu nahrazujeme víc podobně položených polygonů jedním a tím snížíme celkový počet polygonů.
Vůbec nejlepší optimalizace je nevykreslovat nic. Pak máme zaručeno, že náš engine bude nejrychlejší na světě. Problém bude pravděpodobně s využitím. Prvním úkolem je tedy vykreslovat pouze ta data, která jsou skutečně vidět. Vzpomeňte si na minulou lekci, když jsme probírali kameru. Měli jsme tam jakýsi čtyřstěn (frustrum), uvnitř kterého byla všechna data vidět, data umístěná vně tohoto objektu se nevykreslují. Direct3D se samo stará o to, aby se zbytečně nevykreslovala data, která jsou již mimo, jen tato vlastní optimalizace není nic extra a ani být nemůže, protože Direct3D již nevidí logické uspořádaní dat, o to se tedy musíme postarat my. Čím lépe a rychleji rozlišíme, které polygony vykreslit a které ne, tím bude náš engine lepší. Bohužel toto není zrovna lehká úloha a pan Carmack by zřejmě vždy našel další řešení, které by bylo ještě rychlejší než to naše! Chce to rovněž pořádnou dávku zkušeností s programováním a tím nemám teď na mysli pouze grafiku.
Druhým pohledem na optimalizaci může být snaha o snížení počtu polygonů, které se určitě musí vykreslit. V případě terénu je to právě technika LOD, kdy nahrazujeme více podobně umístěných polygonů jedním (snižujeme vlastně detail terénu). Pokud vykreslujeme složitější objekty načítané ze souborů .x, je dobré vytvářet rozumně složité modely. Docela dobré pravidlo je vytvářet modely s co nejmenším počtem polygonů tak, aby výsledný model měl reálné tvary. Můžete použít i více modelů a poté vybírat jednodušší model na pomalejších kartách a naopak. Další možnost je používat billboardy místo pravých 3D objektů. O billboardech jsme se povídali již v minulé lekci a nyní již není problém takový objekt vytvořit a správně nasměrovat pomocí billboard matice uložené v naší kameře.
Poslední optimalizační krok, kde můžeme také nahnat nějaké ty FPS navíc, se týká textur. Zde platí podobné pravidlo jako u objektů. Je potřeba vytvářet správně velké textury, aby byl výsledek vizuálně pěkný - rozblité textury nejsou na objektech zrovna moc hezké a když je textura zbytečně velká, dochází k jejímu smrštění a to taky není dobrý efekt, navíc pak dochází k zbytečnému plýtvání výkonu. Používejte mipmapping, kde to jen jde! Ten vám částečně zaručí, že textura bude v pořádku ať budete blízko či daleko od objektu. Toto je vykoupeno vyšší paměťovou náročností, protože mipmapové textury zabírají mnohem více místa v paměti.
Nyní si představte, že máte plochu složenou ze čtverečků podobně jako ve hře Transport Tycoon (Deluxe). V Direct3D má každé políčko minimálně 2 trojúhelníky (můžete dělat políčka i ze 4 trojúhelníků). V Tycoon je plocha složena asi z 120x120 políčky, počítejme tedy 120x120 = 14400 políček na celé ploše. Máme tedy 28800 trojúhelníků a to je pouze na terén, dalších 50 000 polygonů mohou zabírat stromy. Ve skutečnosti je ale povrch 120x120 hrozně malinkatý. Udělejme tedy 256x256 (proč takové rozměry, uvidíme za chvilku). To už máme 65536 políček a trojúhelníků tedy bude 2x tolik - 131072. To už je docela síla, nemyslíte? Kdybychom měli vykreslovat v každém cyklu takové množství polygonů, tak bychom FPS ukazatel moc vysoko nedostali - navíc by to z programátorského hlediska byla "prasárna na n-tou". A to se jedná pouze o povrch, který vlastně obsahuje minimum polygonů z celé scény (z dalších 500 000 polygonů můžou být další objekty atd.).
Náš problém je tedy jasně definovaný. Už ne tak jasné bude řešení. Můžete si zkusit vykreslovat vše nebo jen nějak primitivně zjišťovat, zda-li je dané políčko vidět či nikoliv (například testem na každé políčko), ale výsledek bude pomalý právě díky tomuto testu, protože i výkonným procesorům chvilku trvá než zpracují 131072 podmínek. Nakonec byste metodou pokus-omyl došli k závěru, že je lepší vykreslovat vše. Metoda quadtree slouží k velice efektivnímu rozpoznávání viditelných polygonů a o to nám jde! Čím efektivnější algoritmus použijete, tím lépe. Velice totiž usnadníte práci procesoru a posléze i grafické kartě.
Znáte-li binární stromy, bude pro Vás pochopení následující látky hračkou. Pokud jste se se stromy ještě vůbec nesetkali, mohu vám slíbit, že podrobně budou probírány v seriálu o Datových strukturách. Zde si ukážeme jen základní princip stromů. Začneme u binárního stromu. Binární strom vypadá nějak takto:
Každý kořen-rodič má dva své potomky-listy. Jak bychom očekávali, quadtree bude mít potomky čtyři:
Všechny modré kuličkou jsou listy. List je prvek, který nemá další potomky. Větev je část stromu, která obsahuje kořen a příslušné listy. Strom, který je vyvážený neobsahuje žádné kořeny, které by měly méně jak čtyři potomky. Na výše uvedeném obrázku vidíte vyvážený quadtree (ještě výše binární strom je upadlý doleva). Pokud chceme najít specifický list, najdeme ho velice rychle a jednoduše. Každého kořenu se zeptáme, zda-li požadovaný list obsahuje nebo ne. Pokud ne, dále se s větví stromu vůbec nezabýváme (většinou všem prvkům stromu přiřazujeme nějaké ohodnocení). U tohoto jednoduchého stromu najdeme prvek pokaždé stejně rychle, ale u složitější struktury začne rychlost rapidně narůstat.
Podíváme-li se na náš případ terénu, začíná být řešení poněkud jasnější. Nejprve rozdělíme naše políčka do skupin, které budou tvořit jednotlivé kořeny stromu, až v nejnižší vrstvě to budou listy. Od shora budeme projíždět kořeny a budeme zkoumat jestli tento kořen je vidět (třeba i částečně). Pokud ne, vůbec se s touto větví dále zabývat a přesuneme se dál. Celou plochu tedy rozdělíme na kořeny a listy následovně:
Pro jednoduchost jsem zvolil terén 32x32, ale v praxi to funguje na terén, u kterého můžete cyklicky dělit rozměr dvěma, kromě listu (tam již není potřeba dělit). Takže například pokud se rozhodnete udělat list 5x5, musí mít terén rozměry 10x10, 20x20, 40x40 atd. Nejmenší čtvereček na obrázku představuje skutečné políčko terénu složené například ze dvou trojúhelníků. Vnější šedý okraj představuje hlavní kořen stromu. V tomto kořenu se frustrum nachází vždy, takže tento prvek nemusíme ani testovat (v celkovém součtů testů se tento ztratí). Dále budeme testovat každý červeně ohraničený kořen. Otestujeme první a zjistíme, že frustrum se nachází v něm. Frustrum by ale mohlo být na rozhraní více kořenů, takže musíme otestovat i zbylé kořeny na stejné úrovni. V našem případě jsme ale vyloučili tímto testem tři kořeny, což je dohromady 768 políček z celkových 1024. To je slušné, že? Pokračujeme na další úrovni tentokrát modrých kořenů. Zde provedeme zcela analogicky totéž a vyloučíme dalších 192 políček (dohromady: 960 polí). Nakonec testujeme zelené listy a zjistíme, že frustrum se nachází ve všech těchto listech. Z toho plyne, že musíme vykreslit tyto čtyři listy. Takže jsme nakonec pouhými 9-ti testy zjistili, že 960 políček je mimo frustrum. Jak je vidět, testování čtyř potomků daného listu je vždy stejné, jen se pracuje pokaždé s jiným rodičem. Zde se tedy dá s výhodou využít rekurzivní volání funkce, které se spustí pokaždé na všechny potomky každého viditelného kořenu. Data viditelných listů se uloží do vykreslovací fronty (nebo přímo do dynamického vertex bufferu) a v následujícím kroku se vykreslují.
V praxi pak záleží jak velké máme listy a jak hluboký je strom - hloubka stromu = počet pater. Čím větší zvolíte listy, tím více se bude vykreslovat zbytečných polygonů mimo frustrum, ale zase bude rychlejší rozpoznávání, protože strom bude mít méně pater. Představte si extrém, kdy jako list zvolíme celou plochu. Rozpoznávání je pak zcela přeskočeno, ale dostali bychom se do případu z úvodu, kdy jsou vykreslována všechna políčka Pokud bychom zvolili druhý extrém a jako list bychom zvolili pouze jedno políčko, budeme mít jistotu, že se vykreslují jen ty políčka, které jsou skutečně vidět, ale rozpoznávání zde bude pomalejší. V praxi je proto dobré zvolit vhodný kompromis mezi oběma extrémy, často se můžete také rozhodnout podle výkonu procesoru nebo grafické karty. Výkonnou grafickou kartu pár políček navíc nezabije, ale pro pomalý procesor může být "hlubší" rozpoznávání tvrdý oříšek. Rozhodně není dobré spoléhat na to, že cílový uživatel má dostatečně výkonnou kartu, která zvládne vykreslit celý terén s 30FPS (což tedy stejně nic moc) a optimalizaci zcela přeskočit. Můžete se později rozhodnout, že políčko sestavíte z více trojúhelníků a výkon vám rapidně klesne!
Princip metody quadtree máme za sebou. Příště si ukážeme, jak vypadá konkrétní implementace.
Na závěr si jen ve zkratce popíšeme metody OctTree. Jak název napovídá, opět se bude jednat o nějaký strom. Tentokrát to bude strom, kde každý kořen bude mít 8 potomků. Proč zrovna 8? Nestačí 4? Možná jste si všimli, že v případě quadtree jsme dělili terén pouze v rovině, nyní budeme dělit v prostoru a právě proto je potřeba 8 listů. Již se nebude jednat o čtverce, ale o krychle. Určíme si tedy základní krychli, která obepíná celý terén (může se jednat obecně o kvádr) a tu pak rozdělíme na 8 menších krychliček. Každou tuto malou krychličku opět rozdělíme na 8 ještě menších krychliček, až se dostaneme na úroveň listů a dělení přerušíme.
Princip rozpoznávání viditelných polygonů je analogický metodě quadtree. Nejprve se podíváme, zda-li je frustrum v první největší krychli, tam bude asi určitě (pokud není kamera otočená na druhou stranu), dále testujeme všech 8 podkrychliček a vybereme jen ty, které jsou ve frustrum. S ostatními se vůbec nezabýváme.
Proč tedy dělit zbytečně prostor na více oddílů? Ano, rozpoznávání viditelných krychlí bude pravděpodobně pomalejší než v případě metody quadtree. Ale představme si město typu NY, kde je hodně mrakodrapů a když jsme s kamerou hodně blízko nad povrchem, nemusí být viditelné mrakodrapy vidět celé, jinými slovy uvidíme jen malou část a proč tedy zbytečně vykreslovat celý mrakodrap (tzn. i jeho nejvyšší patra), když jsme někde u jeho paty? Pomocí metody octree rozdělíme mrakodrapy i v horizontálním směru a tudíž se vykreslí přesně to, co je vidět (a možná patro navíc). V tom je hlavní výhoda této metody, vykoupená složitější implementací (ačkoliv to je dost relativní) a možná vyšší časovou složitostí vyhledávání viditelných krychlí.
Na závěr této části se podíváme na jednoduchý obrázek, který nám osvětlí princip metody octree. Vidíme, že hlavní krychle je rozdělena na 8 menších a ty dělí náš "vysoký" objekt. Pokud tedy kamera bude nasměrovaná ve směru šipky, bude se vykreslovat pouze krychle, která je vzadu a vlevo a z toho vyplývá, že o horní část objektu se nebudeme vůbec starat!
Již jsem zmínil, že v příští lekci se budeme věnovat implementaci algoritmů quadtree. Takže si vytvoříme jednoduchou plochu a na ní si budeme testovat různé postupy vykreslování jednotlivých políček.
Těším se příště nashledanou.
