Octtree, view frustum

[Filkon]

Zdravim. Scháním nějaký informace o octtree a view frustum culling - vykresluju krajinu a potřeboval bych to aplikovat... můžete mi poradit, kde seženu nějaký informace? Byl bych rád za jakejkoliv tutoriál nebo ukázku kódu pokud možno pro DirectX a C#. (zkoušel sem googlit, ale moc nevládnu angličtinou a OpenGL v kombinaci s C++ pro mě taky není moc názorný...) Díky za každej link nebo radu...

[juroo]

zdarec. imho googlis slabo V tomto pripade sa nesmies limitovat tym, ze to musi byt pre DX a C#. Vyhovorka

[Peto]

No presne toto je jedna z tych veci co by si nemal len bezducho zkoprirovat ale trochu ju aj pochopit, jednak len tak to zkopirovat asi nepojde a tiez sa ti to urcite zijde tomu chapat .

Najprv sa zameraj na frustum culling, pochop ho skus po hopuzivat, vytvor si orezove roviny, a nejaku funckiu ktora ti zisti ze ci kocka popr gula je v dohlade kamery.

Potom si najdi nieco o rekurzivnych funkciach (su to funkcie ktore volaju samy seba, cize vo vnutri funkcie Skuska(), bude prikaz Skuska();, tiez ich pochop nauc sa pouzivat a potom mozes prejst na samotne octree, princip je pomerne jednoduchy, takze by to nemal byt problem

juroo > ja jeho vyhovorku chapem, ale to naznamena ze nema googlovat s nsnazit sa to pochopit aj s OGL ... Filkon pastnem ti tu neskor kod pre frustum culling v C++ a DX, je dost si myslim prehladne napisany, urcite pochopis .. ale ten octree tak to je viac ako na dve funkcie
_________________
Code or die!

[Filkon]

Já to tam zapomněl napsat - čet sem o tom nějaký info, chápu co je frustum culling, vím jak to funguje, zrovna tak teoreticky vim, jak funguje octree. Ale ta praxe prostě chybí... nedovedu si představit, jak se octree vytváří apod... Je mi jasný, že nemůžu vzít kus kódu a jenom ho připlácnout do toho svýho...

[Quiark]

Pokud máš terén, který se skládá ze čtverců, pak je tvorba quadtree docela jednoduchá. Všechny uzly stromu kromě listů nemusí obsahovat žádnou geometrii, jen její ohraničující čtverec pro frustrum culling. Kořen stromu ohraničuje celý terén. Jeho 4 potomci ohraničují každý jednu ze čtvrtek terénu. A tak to jde dál, až v určité úrovni zastavíš, čímž vzniknou listy a ty už obsahují příslušné trojúhelníky.

Zkus se zeptat konkrétně co nechápeš.
_________________
Mám strach

[krkovicka]

a co kdyz budu chtit obdelnikovou mapu, a mit cvercove elementy, takze jejich pocet na sirku a vysku bude rozdilnej a nebude delitelnej ctyrma, napr. 3x6 bude pak muset bejt koren 8x8 bez kompletniho potomstva? nebo se to resi jinak

[frca]

Já myslím, že tak.

Ale mám jiný dotaz k této problematice. Je lepší rozříznout polygon, který leží na rozhraní dvou krychlí stromu? (Mám na mysli nějaký obecnější model, ne čtvercovou síť.) Anebo je lepší ho vykreslit 2x (nebo i víckrát, když leží hodně nešikovně na rozhraní více čtverců nebo je opravdu velký) přes sebe (přičemž je depth func GL_LESS, takže se vlastně vykreslí jenom poprvé?)? Zatím to mám řešené druhým způsobem, tak by mě zajímalo, co je lepší? A nebo je ještě jiný lepší způsob kromě těchto dvou?
Díky,
frca

[Ladis]

Zvol si nejake pravidlo pro rozhodovani, kam patri, kdyz je na hranici mezi vicema. Napr. vzdy do krychle s mensi souradnici X/Y/Z (blize pocatku). Pak je nemusis rezat ani kreslit vicekrat, ale zas potrebujes vykreslit i krychle, ktere uz nejsou videt, ale muzou byt v nich polygony zobrazene i na krychly, ktera videt ma byt. V pripade polygonu nepresahujici 2 krychle tteda vykreslujes o 1 radu krychli navic.

[rezna]

My jsme toto resili urcitym parametrem overlap (presah). Pokud krychle jeste spadla do overlapu nemusela se rezat. Pokud byla pres tak se rezala.

[kerekes]

Najprv podelit s tym, ze triangle na rozhrani dat tam, kde je jeho vacsia cast. Potom po podeleni urobit druhy prechod zospodu stromu a pozvecsovat boundingboxy (resp zistit nove boundingboxy).

[Filkon]

Quiark: Mám terén, kterej je tvořenej trojúhelníkovou sítí. Je to jeden mesh, kterej tvoří tu krajinu. Nerozumim tomu, co mam do toho stromu vlastně vkládat a co potom vykreslovat - frustum culling mi zjistí, jestli tu část mam ve výhledu nebo ne. Ale jak to provedu technicky, když tam mam jenom jeden mesh? Mam ho nějak rozdělit, nebo co s nim vlastně provedu?

[Quiark]

Aha, takže problém je v tomhle. Bohužel já neznám odpověd Snad se najde někdo jiný
_________________
Mám strach

[Augi]

Mesh není prakticky nic jiného než sjednocení vertex bufferu a index bufferu. Takže to můžeš udělat třeba tak, že budeš mít všechny vertexy ve vertex bufferu a pro každý list octree budeš mít index buffer do toho velkýho vertex bufferu. A jak index buffery naplníš? Jednoduše Projdeš všechny trojúhelníky v původním meshi (buď přes index buffer nebo pokud ho mesh nemá, tak přes vertex buffer) a zjistíš, do kterýho listu ten trojúhelník bude patřit a do odpovídajícího index bufferu zapíšeš jeho indexy. Takže ve výsledku budeš mít jeden vertex buffer a hromadu index bufferů. Samozřejmě to není jediný řešení. Např. můžeš ve finále index buffery sloučit do jednoho velkýho index bufferu a u každýho listu si pak pamatovat první a poslední index z index bufferu. Jsem nějakej unavenej, tak snad jsem to napsal nějak srozumitelně a dobře

[pcmaster]

Ja robim podobnu semestralku do skoly, tu mas nejake papery
Po prazdninach budem mat vlastny kratucky "paper" (LOL) a cez skuskove aj kod, tak to sem asi hodim (ako tu slubovanu bakalarku, muhehe )

* http://www.gamedev.net/reference/articles/article1212.asp
* http://www.cescg.org/CESCG-2002/DSykoraJJelinek/index.html
* http://www.flipcode.com/articles/article_frustumculling.shtml
* http://jgt.akpeters.com/papers/AssarssonMoller00/

(Jo, btw, je to AABB VFC, ale to je jedno, lebo octree defacto AABB je )
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[krkovicka]

zdravim,
napsal jsem si tridu, reprezentujici uzel stromu a realizoval frustum culling. Problem je nasleduji, kdyz pouzivam velky teren, radove milion uzlu, tak je inicializace neunosne dlouha. Problem je v tom, ze nemam uzel jako strukturu, ale jako tridu a inicializace objektu je mnohonasobne delsi, nez ini struktury. Jenze struktura nemuzu ukazovat na sebe sama a musi se proto zavest pointry, bohuzel dal, nez k tomuto zjisteni jsem se nedostal. nemohl by mi sem nekdo poslat ukazku struktury, ktera ma tohle osetreny? Staci uzel spojaku se settrama a gettrama na potomka.
predem diky