Grafické a fyzikální principy

Note	Příprava a vývoj scény, grayboxing, zástupné modely (placeholders). Optimalizace výkonu vykreslování (úrovně detailů, odstřelování objektů, MIP mapy). Využití shaderů pro efekty ve hrách. Sledování paprsků, objekty pro detekci kolizí, fyzika hadrové panenky. PA010, PA199, PA213, PV255

Příprava a vývoj scény

Note	Poznámky o grayboxingu, iterování, modulárním workflow, atd. jsou z přednášky Lukáše Medka v rámci PV255. [1]

Iterace

Práce v iteracích pomáhá:

udržet konzistenci,
mít přehled o objemu práce,
průběžně přídávat obsah a
šetřit čas.

Základní workflow

Modelování high-poly a low-poly modelů
Unwrap
Tvorba textur a materiálů
Vypečení map (normály, bump, atd.)
Aplikace shaderu v engine
Optimalizace

Grayboxing

Rychlý nástřel modelu / scény / prostředí.
Obrovská časová úspora při tvorbě assetů. Místo jejich finální podoby se používají placeholdery (obvykle šedé krabice).
Umožňuje implementovat mechaniky bez nutnosti čekat na assety.
Limituje odpad — nevyužité assety — při změnách nebo škrtech.

Modulární workflow

Využití malého množství assetů pro vytvoření rozsáhlého prostředí. Nutná promyšlená preprodukce. [2]

Modulární textury

Textury aplikovatelné na více modelů. Je potřeba na všechna využití myslet při vytváření textury.

Placeholders

Zjednodušené / low-poly / koupené / kradené modely nebo šedé / oranžové / libovolné krabice, které jsou v pohodě pro prototyping, ale neměly by být ve finální hře.

Optimizalizace výkonu vykreslování

Level-of-detail (LOD) / úrovně detailů

Čím větší vzdálenost, tím méně detailů. [15]

Pro každý model máme hierarchii modelů s různým počtem polygonů. V závislosti na vzdálenosti od pozorovatele vybíráme vhodný LOD.

Dají se vytvořit manuálně i automaticky (pomocí algoritmů pro mesh reduction / decimation).

Diskrétní LOD

Existuje fixní počet variant meshe, mezi kterými se přepíná diskrétně. Nevýhodou je "popping" efekt.

Continous LOD

Mezi variantami se nepřepíná "ráz naráz", ale postupně tak, že v jeden moment jsou vykresly dva LODy přes sebe a blendovány pomocí alpha kanálu.

Geomorphic LOD

Redukuje popping postupnou "proměnnou" jednoho LODu na druhý odebíráním a přidáváním hran. Generuje approximované mezistavy.

Obrázek 1. Geomorphing by Sirotk

Hierarchical LOD

Seskupuje objekty ve scéně do hierarchie a zjednodušuje celé skupiny objektů najednou. Vede k lepšímu výkonu.

Texture filtering

Popisuje, jakým způsobem se pixely textury (texely) mapují na pixely obrazovky / daného polygonu. [17]

Součástí problému je potřeba odhadnout, jak velkou plochu polygon zabere na obrazovce.

Mipmapy

multum in parvo — mnoho v malém prostoru

V zásadě LOD na texturách. Z velikosti $δ$ otexturovaného polygonu je LOD $D = lo g_{2} (max (δ, 1))$ . Výsledek je získán interpolací mezi LODy $⌊ D ⌋$ a $⌈ D ⌉$ .

Mimojiné je to tedy přístup k texture filteringu, kdy aproximujeme velikost polygonu pomocí čtverce daného úrovní mipmapy.

Obrázek 2. Separate color channels of a mipmapped texture by Phorgan1

Tip	Jak je patrné z obrázku výše, chytrým uložením je mipmapovaná textura jen o 33 % větší než původní textura. (Nová má velikost $\frac{4}{3}$ té staré.)

Shaderové / GPU optimalizace

Existuje řada nástrojů, které umožňují debugovat a optimalizovat GPU:

V Unity: Rendering Statistics, Frame Debugger
nVidia Nsight: obecné debuggování GPU
Intel Graphics Performance Analyzers: obecné debuggování GPU
RenderDoc: debuggování OpenGL, DirectX a Vulkan

Object culling / ostřelování objektů

Nalézání podmnožiny objektů ve scéně, která může být vynechána, aniž by viditelně ovlivnila výsledný obraz. Počítání přesné viditelnosti je příliš náročné, proto se používají aproximace známé jako potentially visible set (PVS). [16]

Back-face culling

Vykreslování pouze předních stran polygonů.

View frustum culling

Vykreslování pouze objektů, které jsou v zorném poli kamery.

Occlusion culling

Vykreslování pouze objektů, které nejsou zakryty jinými objekty.

Portal culling

Užitečné, pokud máme statickou scénu, kde jsou některé části viditelné jen z některých jiných částí (např. místnosti v domě). Část dat potřebných pro odstřel tak může být předpočítána.

vph02 portal culling 1 vph02 portal culling 2

Obecné zásady

Nevykreslovat co není nutné (zahazovat na CPU, využívat předchozí snímky)
LODovat
Batching (Unity) — shlukovat geometrie a vykreslovat naráz
Instancing — vykreslovat vícero instancí stejného objektu naráz
Minimalizovat počet materiálů (např. spojováním textur).
Vypéct všechni nedynamické (statická světla, stíny, atd.)

Využití shaderů pro efekty ve hrách

Toon / cel shading

Toon shading používá jen několik ruzných "kroků" intezity barev. Cel shading prý přidává kontury, ale zdá se, že ty termíny jsou spíš synonyma. [3] [4]

Obrázek 3. Cel-shaded Utah Teapot by NicolasSourd

Color grading

Využívá se look-up table (LUT) pro jednotnou barevnou korekci. [5] [7]

Marschner Hair

Shader, co používá Pixar pro vlasy a chlupy postavený na výzkumu Steva Marschnera. Má tři složky: odraz (R), průchod skrz (TT), vnitřní odraz (TRT). [5] [6]

Hloubka obrazu / depth of field

Fyzikálně korektní bokeh. Simuluje fotoaparát včetně clony (F-stop), velikosti snímače (full-frame, APS-C, atd.), ohniskové vzdálenosti, počtu lamel, atd. [5]

Tip	Circle of Confusion (CoC) je kruh způsobený imperfektním zaostřením. Měřením CoC foťáky určují depth of field. [8]

Ray tracing / sledování paprsků

Ray tracing jsou techniky, které trasují paprsky světla napříč scénou.

Jsou pomalejší než empirické modely jako Blinn-Phong,
Jsou limitované na jeden úhel pohledu (pomineme-li hacky).
Ray tracing zvládá odrazy, refrakci a další chování světla věrohodněji.

Obrázek 4. The first bounce of the ray-tracing algorithm schematic by Henrik

Path tracing

Monte Carlo technika, kdy pro každý pixel je do scény vysláno množství paprsků. Když paprsek narazí na objekt, je buď absorbován, odražen nebo zlomen — což je zvoleno náhodně.

Rozdíl oproti klasickému ray tracingu je právě v oné náhodnosti. Klasický ray tracing počítá všechny odražené i zlomené paprsky, které trasuje ke každému ze světelných zdrojů. Path tracing poskytuje "jen" statistický vzorek z nich.

Využití

Animované filmy
Vizuální efekty
Architektonické vizualizace
Hry

Spatial data structure

Datové struktury popisujicí objekty v prostoru. Volba vhodné struktury je klíčová pro efektivitu ray tracingu, ale je fajn i pro všední průchod scénou. [12]

Bounding volume hierarchy (BVH)

Hierarchická reprezentace scény, díky které průchod scénou zredukován z $O (n)$ na $O (lo g n)$ ( $n$ je počet objektů ve scéně). Dá se stavět top-down nebo bottom-up. [12]

Chceme od ní dvě věci:

Rychlý průchod a dotazování na průnik mezi objemy.
Rychlou kostrukci a aktualizace.

Surface Area Heuristic (SAH)

Metrika udávající cenu průchodu BVH. Používá se v řadě různých BVH algoritmů a jejich evaluaci.

Mějme následující scénu:

Pravděpodobnost, že paprsek trefí $L$ je $p_{L} = \frac{S A ( L )}{S A ( N )}$ . Analogicky $p_{R} = \frac{S A ( R )}{S A ( N )}$ .

Cena průchodu uzlem BVH je pak:

C (N) = {c_{T} + p_{L} \cdot C (L) + p_{R} \cdot C (R) c_{I} \cdot t_{N} pro vnit \overset{r}{ˇ} n \overset{ı}{ˊ} uzel pro list

kde:

$c_{T}$ je cena průchodu vnitřním uzlem,
$c_{I}$ je cena kontroly průniku,
$t_{N}$ je počet trojúhelníků v listu,

Celková cena BVH je pak:

C (T) = \frac{1}{S A ( T )} \cdot c_{T} N \in inner nodes S A (N) \sum + c_{I} N \in leaves \sum S A (N) \cdot t_{N}

Modrý výraz je konstantní, tmavě červený se snažíme minimalizovat volbou BVH algoritmu.

Agglomerative Clustering

Bottom-up metoda, kdy se jednotlivé trojúhelníky postupně shlukují do clusterů. Strom trvá déle postavit, ale je efektivnější ho procházet.

Morton Codes

Pro efektivní hledání nejbližších bodů se využívá křivek vyplňujících prostor. Jednou takovou je Mortonova Z-křivka.

Obrázek 5. Four iterations of the Z-order curve by David Eppstein

Fyzikální simulace

Important

Renderování založenému na fyzikálních principech se věnuje část otázky Pokročilá počítačová grafika.

Rigid body

Aproximace reálného fyzikálního tělesa. Předpokládá uniformní hostotu a neřeší:

deformace objektu,
aerodynamičnost tvaru.

Nicméně řeší:

dynamiku (část mechaniky, která se zabývá příčinami pohybu),
kolize,
klouby.

Soft body

Deformovatelný objekt.

Fyzikální enginy

PhysX (Nvidia) — Unity, Unreal Engine.
Bullet — Blender, Paradox engine.
Havok
Box2D

Objekty pro detekci kolizí

V principu funguje detekce kolizí tak, že v každém kroku fyzikální simulace: [9]

dojde ke kontrole, zda se dva objekty dotýkají — či mají společný průnik,
pokud ano a kolize jsou pro dané objekty povoleny, dojde k výpočtu kolizních dat (normála, hloubka průniku, atd.),
ostatní systémy mohou reagovat na kolizi (např. způsobit explozi miny).

Fáze

Broad phase — hledání kandidátů na kolize
- Např. pokud se dotýkají AABB nebo jsou objekty v přibližně stejné oblasti.
- Využívají se struktury pro vyhledávání jako octree, k-D tree, BSP, atd, které je potřeba aktualizovat každé iteraci fyzikální simulace.
Narrow phase — kontrola zda se kandidáti fakt srazili.

Sweep and prune

Algoritmus pro broad phase.

Gilbert-Johnson-Keerthi (GJK)

Algoritmus pro narrow phase. Rozhoduje zda dva konvexní tvary mají společný průnik.

Primitivní collidery

Výpočty s nimi jsou rychlé.

krabice (AABB),
koule,
kapsle,
válec.

Obrázek 6. Primitivní collidery v Unity

Mesh collider

Neprimitivní collider objekt. Obvykle konvexní obal nějakého meshe. Vypočetně náročné.

Compound collider

Collider složený z vícero primitivních colliderů. Rychlejší než mesh collider. Použitelný i na nekonvexní objekty.

Quickhull

Algoritmus pro výpočet konvexního obalu.

Statické objekty

Terén, budovy, a podobné nehybné objekty. Nepůsobí na něj fyzikální síly, ale fungují jako collidery. Necollidují však vzájemně. Mívají komplexní tvar.

Dynamické objekty

Působí na ně fyzika. Měly by mít jednodušší collidery.

Discrete collision detection

Kolize se detekují v každém kroku fyzikální simulace. Výpočetně nenáročné, ale může docházet k "tunelování" objektů skrz jiné objekty.

Continous collision detection (CCD)

Kolize se detekují v "průběhu pohybu" objektů — pomocí supersamplingu, raycastingu, swept spheres, atd. Výpočetně náročné.

Fyzika hadrové panenky

Specifický pohyb postav bezvědomí. Kombinuje animace a fyziku. Je založená na:

skeletal systém (rig) — kostra postavy,
joint restriction — kloubech,
rozdělení postavy na skupiny rigid bodies,
springs and dampers — pružiny a tlumiče.

Obrázek 7. The first "ragdoll falling downstairs" (1997) [11]

Featherstone’s algorithm: Algoritmus pro výpočet dynamiky stromovité struktury propojených článků.

Zdroje

[1]: Lukáš Medek (CBE), Základní postupy při tvorbě assetů a herního vizuálu
[2]: http://wiki.polycount.com/wiki/Modular_environments
[3] Sochor: PA010 Intermediate Computer Graphics (podzim 2020)
[4] https://en.wikipedia.org/wiki/Cel_shading
[5] Jan Zelený, Grafické efekty
[6] https://www.fxguide.com/fxfeatured/pixars-renderman-marschner-hair/
[7] Using Look-up Tables for Color Grading
[8] https://en.wikipedia.org/wiki/Circle_of_confusion
[9] Chmelík, Trtík, PA199 Advanced Game Development
[10] Barber, Dopkin, Huhdanpaa: The Quickhull Algorithm for Convex Hulls
[11] http://www.animats.com/
[12] Bittner: Bounding Volume Hierarchies for Ray Tracing
[13] Path Tracing vs. Ray Tracing, Explained
[14] Pharr, Jakob, Humphreys; Physically Based Rendering: From Theory To Implementation; Chapter 4: Bounding Volume Hierarchies
[15] Chmelík, PV255 Game Development I
[16] Byška, Furmanová, Kozlíková, Trtík: PA010 Intermediate Computer Graphics (podzim 2021)
[17] Wikipedia: Texture mapping