Streamování venkovní scény+optimalizace

[HonzikJ]

Dobrý den,
zkouším si udělat vlastní hru, kde bych chtěl vykreslovat ve většině případů poměrně rozsáhlé outdoor scény, ale mám par dotazů..

Dejme tomu, že mám obecný model vytvořený v grafickém nástroji (čili není to terén vygenerován nějakým algoritmem a tak i trojúhelníková síť je nepravidelná, zkrátka se jedná o nějaký outdoor level, možná by bylo lepší využít pravidelnou síť...).

Zatím používám streamování levelu a to takto: [] jsou jednotlivé buňky nebo-li velké části celkového modelu, 2-kde se právě nacházím 1-co vykresluji a 0-co nevykresluji :

[0][0][0][0][0]
[0][1][1][1][0]
[0][1][2][1][0]
[0][1][1][1][0]
[0][0][0][0][0]

Dá se říci, že pokud nejsem na kraji, tak vykresluji devět buňěk. Pro tuto reprezentaci jsem si vytvořil vlastní formát, zatím je podobný formátu obj a jeho struktura je taková:

//buňka 1
vertexy
face
uv,.....
.
.
// buňka n
vertexy
face
uv,...


Všechny jsou stejně velké, takže na základě aktuální pozice pozorovatele, vím pro jaké buňky šáhnout a co vykreslit.

A teď mé dotazy:

1)
chtěl bych nad tímto systémem dále aplikovat quadtree, ale nevím přesně jak.

Mám určité nápady

a) vždy při změně načtení buňěk přepočítat celý quadtree
b) pro každou buňku mít vlastní quadtree čili jich jakoby budu mít 9
c) vypočítat quadtree pro celou scénu jakoby byla celá vykreslená (a pak při procházení kontrolovat zda vůbec v daném uzlu je co vykreslit, aby se zbytečně neprocházeli ty uzly, které nemají co vykreslit v danou chvíli)

2)
Nyní scénu vykresluji úplně jednoduše, to znamená trojúhelník za trojúhelníkem.
Chtěl bych vytvořit Index Buffery (ale nevím přesně jak, říkal jsem si, že nejlépe pro každý list quadtree, ale když se mi ten strom pořád mění, tak budu muset také předělávat index buffery, popřípadě je všechny mít vytvořené pro celkovou scénu, ježe když mám scénu velkou, tak mi to zabere spoustu paměti...

Přemýšlel jsem nějakým způsobem ještě uravit můj formát modelu, aby ještě v rámci buňky došlo k rozdělení na listy quadtree, čili takto:

// buňka 1
// list 1.1
vertexy, face, uv,...
// list n
vertexy, face, uv,...
.
.
// buňka n
// list 1.1
vertexy, face, uv,....

Omlouvám se za, tak dlouhý dotaz, ale kraší jsem to nedokázal napsat a chtěl jsem, aby byl můj problém pocchopitelný. Snad se mi to povedlo. Samozřejmě předem děkuji za každou radu.

[pcmaster]

Chapem to spravne, ze pohlad na scenu mas "zhora", a tak vzdy vies garantovat, ze v jednom momente neuvidis viac nez 9 (ci 4) buniek?
V tom pripade by som sa na hierarchicku akceleracnu strukturu vykaslal A dal by som to do uniformnej mriezky (uniform grid).

No, ale ak aj chces quad-tree, tak asi takto. Tvoj teren je staticky, ak to dobre chapem, takze quad-tree postavis raz a budes pouzivat naveky. V podstate je uplne jedno, ci je to quadtree, octree, kD-tree. U vsetkych (aj u uniform grid!!!) ti dojde k tomu, ze niektore polygony budu pretate rozdelovacimi rovinami a dostanu sa do viacerych listov. Tomu sa neda zabranit, pretoze tieto space-partitioning metody tak funguju.
Pouzivat ho budes tak, ze si vyrobis quad, ktory reprezentuje tvoj pohlad na scenu (okno) a budes testovat jednotlive nody (tj quady) v strome na prienik s tymto tvojim okno. V pripade, ze je cely quad nodu v tvojom okne, vykreslis vsetkych jeho potomkov bez dalsieho testovania. V pripade, ze je cast quadu nodu v tvojom okne, postupis na dalsiu uroven stromu. No a v pripade, ze nie je vobec vidno, tak uz dalej nepostupujes. Takto vykreslis vsetky casti, ktore su (aspon trochu) vidno.

Ja osobne mozem este odporucit BVH (Bounding Volume Hierarchy), ktora je tiez velmi jednoducha na postavenie, pouziva sa presne tak isto ako tie ostatne, akurat v nej NIKDY nedochadza k rozseknutiu primitiv, pretoze primitivum (trojuholnik?) padne vzdy na prave jednu stranu deliacej roviny, za cenu prekryvajucich sa buniek. Nieco za nieco

V pripade, ze mas scenu dynamicku (tj pohybuju sa ti tam veci v case), tak rozhodne odporucam BVH. Tam existuju aj postupy pre dynamicke sceny, ktore neprepocivavaju cely strom, ale len cast, za cenu malickych vykonovych pokut. Ale to je asi uz prilis, co?

Potom je este dalsia moznost, nad statickou scenou postavit jednu strukturu, ktora bude staticka a vecna a nad dynamickou stavat dalsiu (BVH) a hlavne rychlo, kazdy frame. Tu sa ale dostavame k tomu, ze postavit takuto stromovu strukturu obecne trva NlogN, kdezto testovat kazdy objekt na prienik s oknom trva len N, vsakze

No a co sa tyka (index) bufferov. Ja by som to videl tak, ale vela o tom neviem, ze ten mesh proste rozsekas na "najmensie meshe" (co urcite nebudu trojuholniky), ktore budu zastupovat vzdy jeden list. Tj samostatne buffery a tie potom budes vykreslovat (nacitat, whatever). Kazdy list akceleracnej struktury bude mat odkaz na index buffer, ktory reprezentuje. Nezabudaj na to, ze ak to spravis jednoducho, tak niektore trojuholniky budes musiet naduplikovat. Samozrejme, ak mas takto pravidelnu scenu, tak mozno ani nie, ale za cenu, ze vzdy budes musiet kreslit aj kusok dalej za viditelne okno, aby sa ti tam vzdy vliezli cele kusy a nevznikali (akekolvek = neprijatelne) chyby.
No a ak planujes zase tak strasne velky teren (bavime sa o mnozstvach dat, ktore sa uz rozumne nevlezu do VRAM?) tak to budes musiet premysliet este asi inak

Je to aspon trochu opoved na tvoju otazku?
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[johnnash]

Asi bych nevynalezal znovu kolo.
Mrkni se na geometrical clipmaps nebo pripadne geomipmapping(chunked lod).

[HonzikJ]

Díky za reakci,
na scénu se nedívám zhora, ale přímo zevnitř, prostě klasicky jak v FPS a z toho tedy vím, že musím vykreslovat část terénu, ve které se právě nacházím + ještě načítám dalších osm kolem, kvůli přechodu, když přejdu vlastně třeba vlevo tak se mi 3 smažou z paměti a tři nové načtou. situace zde (pohled zezhora:

[0][0][0][0][0]
[0][1][1][1][0]
[0][1][2][1][0]
[0][1][1][1][0]
[0][0][0][0][0]

přesunu-li se do nové buňky

[0][0][0][0][0]
[1][1][1][0][0]
[1][2][1][0][0]
[1][1][1][0][0]
[0][0][0][0][0]

Nevím jestli jsem se správně vyjádřil co mám na mysli buňkou, tak ještě takto: v těchto buňkách mám vždy část terénu (jedna buňka nyní obsahuje část výškové mapy o rozměrech 128*128 celkově má tedy terén rozměry (128*5)*(128*5). (na internetu jsem našel něco jako terrain streaming).
Čili když vykresluju, tak max devět map (128*3)*(128*3). A nad tímto bych chtěl právě budovat quadtree.
Ale nevím zda-li ho vytvářet při každém přechodu nový (to znamená pro těch devět buněk) což se mi moc nezdá, anebo hodně zajímavé by mohlo být vytvořit jej nad celou scénou(tedy pro všech 25 buněk). Mám na mysli nějakým předzpracováním, že bych si pak někde uložil ještě nějakou strukturu stromu, kterou bych si načetl spolu s levelem a nemusel už jej budovat.

Ještě jeden dotaz mimo toto; když buduju quadtree pro statickou scénu, třeba terén, zahrnuje se do výpočtů také statické modely jako domy,... já bych to třeba řešil tak, že když znám pozice těch statických modelů, tak bych si rozdělil jen terén a pak každý list stromu měl nějaký seznam, jaké statické modely obsahuje (zřejmě by byl problém u objektů zasahujících do více listů, ale to by mohlo být řešitelné).

[pcmaster]

Dufam, ze chapes, ze ucelom tychto akceleracnych struktur je VYRADIT co najviac veci z vykreslovania. Nechapem preto, co ma prechod kamery do inej, statickej bunky spolocne s prebuildovanim akejkolvek struktury.

Tiez nechapem, ako je mozne, ze mas volnu kameru a vidis maximalne do vzdialenosti 1-2 buniek. To tam mas steny a v oknach a dverach portaly, alebo co? Nechcel by si to upresnit?

Ja som cely cas hovoril o frustum cullingu, pretoze to je to, na co sa tieto struktury, napriklad, daju pouzit. Samozrejme, ak mas v tie meshe tak zlozite (co ja viem 10 MB geometrie na jednu "bunku"), tak mozes riesit aj streaming, no ale v opacnom pripade si to vsetko nahraj do VRAM a uz len nevykreslovat zarucene neviditelne casti. No a este k tej kamere. Ak sa kamera diva napriklad smerom "hore" (v tom 2D), tak je zbytocne kreslit cele casti geometrie, ktore su uplne za nou, nie? Zato veci pred kamerou kreslit chceme, ci?

Btw, na zaciatku si pisal, ze tvoja trojuholnikova siet je nepravidelna a zrazu mas vyskovu mapu (co je pravidelna vec).
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[HonzikJ]

No k te výškové mapě. Od prvního postu jsem změnil vstupní data a nenačítám obecný model, ale právě terén z výškové mapy.
A do vzdálenosti dvou buněk jsem zvolil proto, aby když mám načtenou pouze jednu, tak to je špatný kvůli nahrávání oblasti, do které jsem právě vstoupil(navíc když dojdu na kraj oblasti, tak jakobych došel na konec světa).
Právě proto jsem zvolil, že budu vykreslovat tu v které se nacházím + oblasti, které se nachází kolem mě (což znamená tedy nanejvýš devět výškových map). Velikost jsem zvolil zatím 128, plánuju to případně navýšit, ale zatím je to dostačující a opravdu mi stačí abych viděl právě jednu buňku kolem mě.

Jinak je jasný, jak píšeš frustum culling, který bych použil na quadtree,..., ale frustum culling nemá nic společného s načítáním buněk (s vykreslováním ano, pokud jsem samozřejmě natočený tak, že nevidím celou buňku, tak ji nemá cenu vykresovat, ale přesto v paměti bude). To, jaké buňky mám v paměti závisí pouze na pozici pozorovatele.

Je to těžký popsat:-) Navíc programování je jen moje hobby a nejsem úplně zběhlý v terminologii, takže možná proto ty nesrozumitelnosti z mé strany.

Ale teď když mám vlastně scénu tvořenou pomocí terénu, tak to budu řešit asi tak, že si udělám ten strom tak jak jsem psal posledně nad celým terénem, jakoby byl načten celý, ne jen část.

[pcmaster]

Podla mna sa da ten quad-tree pouzit aj na vypocet / predikciu, ktore bunky nacitat do pamati. Ale asi to nie je to prave V podstate, zda sa, ze budes potrebovat nejaku vlastnu cache, tj spravu chunkov dat v pamati (tie chunky mozu byt napriklad listy toho stromu). No a nacitat dopredu dostatocne mnozstvo dat v zavislosti na tom, kam asi tak kamera moze ist a kam sa natocit. Taky nejaky lazy, on-demand loader, alebo ako by som to nazval.

VladR, co v popelnici teraz urputne diskutuje, by nam mohol povedat, co si mysli, ze by bolo vhodne pouzit na tvoj konkretny problem. Pretoze viem, ze pisal streamovany teren, co mu beha 3000 FPS na GeForce2

Tak snad bude taky dobry a podeli sa (znovu!) o nejake napady

VladR, si tu?
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[tomasslavicek]

pcmaster: Díky, takovéhle příspěvky jsou super

Co je ale pravda, člověk si pak ty struktury stejně trochu přizpůsobí. Např. quadtree jde rozdělit vždy tak, aby dělící rovina vycházela přesně mezi polygony (šířka 16 se rozdělí na 8 a 9). Pro mé obskurní účely mi quadtree funguje i u pootočeného terénu (bounding boxy jednotlivých nodů se trochu překrývají), také jsem ho např. v případě dlouhého úzkého terénu rozděloval jen na dvě části místo čtyřech.

Terén nenačítám dynamicky ze souboru, ale každý list si už od začátku drží svůj naplněný vertex a index buffer. Který se má potom vykreslit se posuzuje při renderování, stejně jak psal pcmaster (ověřuje se průnik view frustum a bounding boxů quadtree). Vykresluji je pomocí TriangleStripů.

[HonzikJ]

pcmaster:
Ano máš pravdu, vidím to přesně tak, jak jsi napsal. Budu mít jednu strukturu nad správou "velkých" buněk v paměti a "pod" ní nějaký třeba quadtree, který bude řešit vykreslování "malých" buněk (listů toho quadtree)

tomasslavicek:
No v okamžiku, kdy máš terén "rozumný", tedy ne nějaký obrovský, tak není třeba řešit nějaké streamování a opravdu pro každý list stromu vytvořit IB a podle rtoho, které listy vidím, tak volat jednotlivé IB.
Což také tak plánuji.

Jinak zde také řešili stremování terénu a zhruba uprostřed diskuze tam outRider popisuje podobný princip streamování, o který se snažím já. Takže snad se ubírám trochu správným směrem.
http://www.gamedev.net/community/forums/topic.asp?topic_id=250855

[VladR]

[HonzikJ]

Aha moc díky tak nějak jsem to myslel +-. Jen pro upřesnění:
centrální chunk je tam kde se nachází pozorovatel, a teď kolem něj načtu nejdetailnější heightmapy (3x3) kolem tohoto kruhu bude další s méně detailní mapou(5x5),.... A ve velké vzdálenosti, je třeba ještě načítat něco?, nebo prostě chunky, které budou moc daleko už prostě nenačítat (až v momentě kyd se k ním začnu přibližovat?), nebo myslíš že je dobré udělat ty kruhy, aby pokryly pro celý terén?

[Dlaha]

HonzikJ: Podle mýho selskýho rozumu (nikdy jsem to ještě neimplementoval) tohle bude záležet na dohlednosti a typu terénu. To znamená, že jestli tam dáš mlhu, tak je zbytečný načítat chunky, který by nebyly vidět.
Stejně tak, jestli budeš takhle řešit třeba město s vysokýma barákama a budeš vědět, že se hráč nikdy nedostane nad jejich úroveň, tak proč by jsi vykresloval něco, co neuvidí.

Na druhou stranu, jestli budeš dělat obrovskou krajinu s neuvěřitelným rozhledem, tak by se možná vyplatilo tam něco hodit, ať nevidí hráč doskakující části mapy.
_________________
Other Inside
Greenlitnuto!

[franz]

A co teprve tohle Imho nejlepší studijní materiál na kreslení pekelně rozsáhlých a detailních exteriérů s poctivým dohledem

[pcmaster]

Mas na mysli nejake konkretne clanky/pejpre?
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[Vilem Otte]

#franz - nechci být rýpal a říkat že to nemá pěkný dohled (nebo že to není pěkná hra), ale podívej se někdy v noci ven (nejlépe někde u menšího města - které vše nepřesvětlí, tedy ne Brno, Praha, Ostrava, apod.), ale ta vzdálenost dohledu je šíleně přehnaná (na noc).

já bych doporučil podívat se na Elevated - http://pouet.net/prod.php?which=52938 - kdy do 4k natlačili také terén s dohledností (a řekl bych že celkem chytře řešenou, za hranicí kde rozptyl světla zastíní model jej nekreslí).

Tedy do dálky určitě započítej rayleighův, či mieho rozptyl (google či na gamedev.net - rayleigh scattering a mie scattering), a vyjádři si z něj i vzdálenost za kterou kreslit nemusíš (e.g. za kterou ti rozptyl zabarví model do barvy pozadí).

A poslední věc, pokud kreslíš něco do dálky, proleť si tento článek:
http://www.gamasutra.com/blogs/BranoKemen/20090812/2725/Logarithmic_Depth_Buffer.php
a případně ještě Ysaneyovi poznámky k němu:
http://www.gamedev.net/community/forums/mod/journal/journal.asp?jn=263350&reply_id=3513134
_________________
Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.