Datové struktury Scene management Indoor Outdoor

Počítačové hry Grafika

Obsah přednášky

I

Datové struktury

I

Scene management

I

Indoor

I

Outdoor

Literatura a odkazy

I http://www.cognigraph.com/ROAM homepage/

I Dalmau. Core Techniques and Algorithms in Game Programming. 2003 I Zersst, Düvel. 3D game engine programming. 2004 I Eberly. 3D game engine architecture. 2005

Základní třídy

I

Základ dobré implementace I I I

I

co nejmenší co nejrychlejší naučte se svůj jazyk!

Co s přesností I

float I I

I

double I

I

větší rychlost problém s malými vs velkými čísly větší přesnost

většinou o přesnost nestojíme. . .

Znalost jazyka

I

Třídy vs. struktury I

I

Používání operátorů I I

I

v případě struktur – předávání parametrů! pouze pokud dělají stejnou věc přidat operátory += nevytváří novou proměnnou případně řešit metodou

Používání gettrů a settrů

Co budete potřebovat? I

ADT (PPA2) I I I I I I I I

pole dynamické pole spojový seznam (obousměrně zřetězený) fronty a zásobníky prioritní fronty tabulky hash tabulky stromy I I

I I I I

vyvážené jiné než binární

grafy ... a kombinace někdy i více různých implementací

Jak to implementovat?

I

Podle potřeby I I I

rychlé vyhledávání vs. rychlé vkládání/mazání měnící se velikost množiny dat vs. statická množina lokalizovaný přístup do paměti I

např. strom pomocí pole

Základní matematické třídy

I

Spousta matematiky – dobré třídy vám ji usnadní I I I I I I I I I I

indexy body a vektory matice paprsky a přímky roviny AABB, OBB a další obalová tělesa quaterniony polygony křivky a plochy ...

Vector3/4

I

Jedna z nejpoužívanějších struktur I I

I

body, vektory, barvy. . . neimplementovat jako pole

Základní operace I I I I I

sčítání, odčítání, přenásobení konstantou vektorový součin úhel který svírá s jiným vektorem velikost vektoru (i neodmocněná) násobení matice x vektor

Matice

I

Transformace – nejčastěji matice 4x4 I

I

neimplementovat jako pole

Základní operace I I I I I I

násobení maticí, vektorem jednotková matice – konstantní metoda transformace transformační matice – konstantní metoda transpozice inverze – i speciální případy

Přímky / paprsky

I

Často pro detekce kolizí a související věci I

I

má počátek a směr

Základní operace I I

inverzní transformace průsečíky I I I

trojúhelník rovina AABB, OBB

Roviny

I

Testy uvnitř/vně I I

I

I

např. clipping (viz dále) reprezentace pomocí počátku, normálového vektoru a vzdálenosti V ∗N +d =0 pro Vector4 se zjednoduší

Základní operace I I I I

vytvoření ze dvou vektorů, trojúhelníku. . . vzdálenost od roviny klasifikace bodu vůči rovině průsečíky

Bounding boxy

I

AABB – Axis Aligned Bounding Box I I

I

OBB – Oriented Bounding Box I

I

zarovnaný s osami rychlý, ne vždy optimální navíc daná orientace

Základní operace I I I

vytvoření průsečíky s . . . oříznutí rovinami

Quaterniony

I

Způsob určení orientace ve 3D I I I

I

Eulerovy úhly (roll, pitch, yaw) matice quaterniony

Vlastnosti matic I I I I

nativní pro transformace jednotný přístup k transformacím hodně paměti chyby v maticích I

I

ortonormalita

problémy s interpolací

Quaterniony

I

4 rozměrné číslo I

I

Geometrická reprezentace I I

I

quaternion je pár (θ, ~n) rotace o θ podle osy ~n

Řeší problém „gimbal lockÿ I

I

reálná část + 3 imaginární

ztráta stupně volnosti

Interpolace rotace I I

sférická interpolace nalezení nejkratší spojnice na povrchu koule

Quaterniony

I

Základní operace I I I I

převod z/na matice převod z/na Eulerovy úhly násobení SLERP

Proč?

I

Typická herní scéna I I

I

tisíce objektů = miliony trojúhelníků řešíme i jiné věci než vykreslování

Rozumný přístup I

co nejrychleji zjistit co vidím I

I

I

platí i pro další části enginu (Fyzika, AI. . . )

paměťová omezení, možnost streamingu

Základní přístupy I I I I

Clipping Culling Occlusion testing Level of detail

Clipping

I

Ořezání geometrie, která je mimo zorný úhel I I

lépe - mimo ořezový objem (pyramidu) dělá se automaticky na GPU, ale čím dříve ořezáme my, tím více času ušetříme I I I I

I

Ne u každé hry důležité I

I

Tekken (5%?) vs. Far Cry (> 80%)

Ořezávání na úrovni trojúhelníků I

I

přenos geometrie do GPU přepínání textur a shaderů ... pozor na efekty, které na objektu závisí (stíny, odlesky. . . )

na CPU zbytečně náročné, na GPU zabírá sběrnici

Ořezávání na úrovni objektů I

testování zda je viditelný objekt

Object clipping

I

Herní svět je složen z objektů I

I

Precizní ořezávání objektů I

I

reprezentace: grafická, fyzikální. . . testování jednotlivých trojúhelníků - jsme tam kde předtím

Využití obalových těles I I I

jednoduchý test i za cenu, že objekt někdy testem projde aniž by měl typicky I I I

koule kvádr konvexní obálka

Obalová koule – příklad

I

Ořezávací rovina: Ax + By + Cz + D = 0 ~ a poloměr SR Koule: střed SC

I

Výsledný test: A · SCx + B · SCy + C · SCz + D < −SR

I

I I I

I

tři násobení čtyři sčítání jedno porovnání

Otestovat vůči všem rovinám bool IsVisible ( Object o ) { Sphere s = o . BoundingSphere ; for ( int i =0; i <6; i ++) { if ( clipPlane [ i ]. x * s . x + clipPlane [ i ]. y * s . y clipPlane [ i ]. z * s . z + clipPlane [ i ]. w <= -s . radius ) return false ; } return true ; }

Culling I

Ořezání geometrie v závislosti na její orientaci I

I

u objektů reprezentovaných hranicí můžeme rozlišit vnitřní a vnější stěnu v obvyklých případech vnitřní část stěny (odvrácenou) nevidíme I

I

I

v průměru 50% trojúhelníků

Ořezávání na úrovni trojúhelníků I

většinou na GPU I I

I

plochy které jsou k pozorovateli odvrácenou stranou lze odstranit

modely zadané pomocí VBO přeorganizování je nákladné

Ořezávání na úrovni objektů I I

má smysl pouze u velmi složitých objektů rozdělení na clustery podle směru normály I I I

vypočítat v preprocessingu seskupit trojúhelníky podle clusterů kreslení pouze přivrácených clusterů

Occlusion testing

I I

Ořezání geometrie na základě zakrytí Spousta možných technik I

I

viz dále

Na moderních kartách lze využít occlusion query I I I

na úrovni objektu kartě se pošle obalové těleso výsledek je zda I I

I

byl modifikován Z-buffer pokud ano, kolik pixelů

některé objekty se kreslí zbytečně I I

celková úspora i tak velká v závislosti na hře!!!

Level of detail

I

Redukce geometrie na základě vzdálenosti od kamery

I

Vzdálené objekty reprezentovány jednodušším modelem Dva možné přístupy

I

I I

konstantní předpočítané úrovně (diskrétní) spojitý LOD

Discrete Level of Detail

I I

Model je uložen v několika verzích s různou kvalitou Na základě vzdálenosti se volí správný model I I

I

používáno poměrně často pop-up efekty – vyskakující detaily

Lze řešit přechodem I I I I

model se nemění skokově, používá se alfa blending redukce pop-upů v přechodné fázi kreslení dvou objektů lze řešit např. indexací

Continuous Level of Detail

I

Model se zjednodušuje za běhu I

I

Mnoho způsobů jak to dělat I I I

I

podle vzdálenosti (a úhlu) (half-)edge collapse triangle collapse vertex removal

Často half-edge collapse I I

nevýznamná hrana se zhroutí do jednoho z vrcholů lze využít pouze přeindexování primitiv nad konstantní množinou vrcholů

Hierarchické struktury

I

Využívání hierarchie k urychlení vykreslování I I

neexistuje univerzální řešení závisí na typu hry I I I

I

indoor outdoor nodoor

často různá řešení pro statické a dynamické objekty

Scene management

I

Správa scény musí zajišťovat i další věci I I I I

nahrávání textur nahrávání shaderů nahrávání objektů a částí mapy správně zvolená strategie I

I

Správa stavů I I

I

minimalizace diskových operací

rozumné seskupování objektů podle vlastností minimalizace přepínání stavů GPU

Využívání koherencí I

objekty se většinou pohybují spojitě I

co platilo v předcházejícím snímku bude asi platit i v současném, pokud ne, změna bude jen malá

Dělení prostoru I

Nejjednodušší je použít hrubou sílu I I I I

I

testování všech objektů, . . . postačuje pro jednoduché aplikace používá se v raných fázích vývoje používá se pro části scény

Využití mřížky (2D, 3D) I I I I

uniformní dělení prostoru (nemusí být nutně čtvercová) seznam objektů uvnitř buňky často pro outdoor scény výhoda I I

I

průnik kamery s mřížkou v O(1) zbytek průnik AABB a kamery

nevýhody I I

dělení vs paměť neadaptivita

Quadtree a octree

I

Adaptivní dělení prostoru I I

I

strom – hierarchie rodičů a potomků každý uzel může mít 4 (8) potomků

Vytváření stromu I

není nutný kompletní strom, dělení lze ukončit, když I I

I

počet objektů menší než požadovaná mez velikost listu menší než daná mez (dosažená hloubka stromu)

Procházení stromu rekurzivně

Binary Space Partitioning

Indoor scény

I

Uzavřené prostory I I I

viditelnost jen pár metrů – chodby, dveře. . . nemá smysl řešit LOD má smysl clipping a occlusions

Algoritmy založené na překrývání I

Vychází z předpokladu, že blízké trojúhelníky pokrývají větší plochu I

rozdělení scény na I I

I

I

blízké objekty – ocluders vzdálené objekty – occluded

často lze navíc spočítat horní hranici viditelnosti

Základní postup occluders = set nearest large triangles for each triangle of the scene if closer than max distance test occlusion with any occluder if pass paint end if end if end for

Algoritmy založené na překrývání

I

Přímočará implementace I I I

v každém kroku potřebujeme množinu occluderů řazení podle vzdálenosti od kamery využívání prostoročasové koherence if camera change > threshold recompute occluders store new camera state end if

I

I

pořadí je „skoroÿ stejné – obdoba bubble sortu

Nevýhody I I

testování po trojúhelnících je náročné předpočítat co jde

Binary Space Partitioning I

Binární dělení prostoru I I I

I

rodič a dva potomci dělící roviny nejsou zarovnané s osami výsledkem je množina konvexních oblastí

Konstrukce I

rekurze function BuildBSP ( geometry , node ) triangle t = select best divider plane p = compute plane from t store t and p to node list f = geometry infront of p list b = geometry behind p if f not empty then BuildBSP (f , new node ) end if if b not empty then BuildBSP (b , new node ) end if end function

Binary Space Partitioning

8 5 7.2

7.1

4 3.1

10 6

2.1

7.1

1

6

3.2

7.2

9

8 1

10

5 4

9

2 2.1

2.2

3.1 3.2

BSP – k čemu to je?

I

2.2

Řazení podle pozorovatele TraverseBSP ( root ) function TraverseBSP ( node ) if viewpoint in front of node plane TraverseBSP ( back node ) paint node triangle TraverseBSP ( front node ) else TraverseBSP ( front node ) paint node triangle TraverseBSP ( back node ) end if end function

BSP – Řazení

8 5 7.2

7.1

4 3.1

10 6

2.1

7.1

2.2

1

6

3.2

7.2

9

1, 7.2, 2.1, 10, 2.2, 3.2, 9, 8, 7.1, 6, 5, 4, 3.1 8 1

10

5 4

9

2 2.1

2.2

3.1 3.2

BSP – a co dál?

I

Hierarchický clipping I I

I

při vytváření počítat bounding box uzlu není-li vidět BB uzlu, nejsou vidět ani potomci

Occlusion detection I

leafy-BSP I I I I I

I

propagace trojúhelníků do uzlů stromů vytvoření konvexních buněk nalezení otvorů mezi buňkami detekce viditelnosti mezi buňkami uložení viditelnosti do PVS

PVS – potentially visible set I

počítá se v preprocesu a ukládá se do matice viditelnosti

BSP – leafy BSP a PVS

8 5 7.2

7.1

4 3.1 6

8

5

10 6

2.1

7.1

1

4 3.1 8

2.2 3.2

7.2

6 7.1

9 2.2 3.2 9

10 2.1 1 7.2 8 1

10

5 4

9

2 2.1

2.2

3.1 3.2

Portály

I

Základní myšlenka I I I

I

rozdělení scény na konvexní oblasti graf sousedících oblastí oblasti spojeny speciálním průhledným polygonem — portálem

Vykreslování I I I

I

začínáme oblastí kde stojíme nakreslíme vše a zjistíme zda je vidět nějaký portál pokud ano, omezíme ořezávací pyramidu a kreslíme oblast za portálem rekurzivně postupujeme, dokud vidíme nějaké portály

Portály

Portály – a co to ještě umí?

I

Snadné řešení některých optických efektů I I I

průhlednost portálu – není nutné řadit zrcadla – speciální portál do stejné místnosti portály do jiných světů

Kombinace

I

Portal + Octree I I I I

I

Quadtree + BSP I I I

I

vhodné do velkých detailních místností portál určuje viditelnost mezi místnostmi octree v každé místnosti obsahuje vybavení lze využít i referencování objektů (šetří paměť) velké oblasti + přesná detekce kolizí quadtree pomůže najít lokaci BSP v uzlech quadtree umožňuje rychlé řešení kolizí

...

Outdoor scény

I

Rozsáhlé souvislé oblasti I I

viditelnost mnoho kilometrů nemá smysl řešit occlusions I

I I

nebo alespoň ne primárně

má smysl řešit clipping je nutné řešit LOD

Často používané struktury I I

Ve hrách často omezováno na 2.5D Výškové pole I I I I

I

nejjednodušší reprezentace pravidelná síť s výškou v jednotlivých uzlech samotné není příliš vhodné – nemožnost LOD dobré v začátku vývoje

Quadtree I

adaptivní metoda I I

I

pro ukládání – při malých rozdílech se dál nedělí pro vykreslování – úroveň se volí podle kamery

Binary Triangle Tree I I I

binární strom trojúhelník se dělí na dva potomky zajišťuje spojitost mezi levely

ROAM I I

Real-time optimally adapting meshes Založeno na BTT I

dvouprůchodové I I

1. zjisti chybu 2. vytvoř geometrii

1. Zjištění chyby I

založeno na kombinovaném kritériu – členitost + vzdálenost

2. Vytvoření geometrie I I I

staví se BTT expanze uzlu je řízená vypočítanými hodnotami pravidla I I I

pokud je součást diamantu – rozděl uzel a bratra pokud je na okraji – rozděl dle libosti pokud není součástí diamantu – vynuť dělení souseda

ROAM v praxi I

Dynamické přestavování stromu je časově náročné I I

rozdělení terénu na menší části využití koherence!!!

Mark Duchaineau

Graf scény

I

Outdoorové hry obsahují velké množství objektů I I I

I I

stovky domů tisíce stromů ...

Práce s takovým množstvím není možná Graf scény umožňující referencování I I I

objekt existuje v paměti jednou ve scéně jsou reference na tento objekt objekt navíc může být parametrický I

I

typicky parametry vertex programu

graf v podobě mřížky či stromu I

rychlá eliminace objektů na základě ořezové pyramidy