AABB

[Acer]

Zdravím.

Začátečnický dotaz. Trápím se teď pár dní s bounding boxy a asi už jsem v tom pokročil. Ve výchozím stavu bez rotace nebo rotaci v pravých úhlech AABB sedí, problém je, když je objekt zrotován pod jiným úhlem, než násobky 90. Prostě box je o něco větší a docela mi to vadí. Je to normální?

Zkoušel jsem několik postupů a vždy stejný výsledek. Začínám přemýšlet o jiném typu ohraničení objektu.

[VladR]

Je to normalne - je to proste nedostatok AABB (kedze tie hrany su dane natvrdo-axis-aligned), za cenu par rychlych porovnani v porovnani s vypoctami pri inych typoch ohranicenia.

Ak tych porovnani nerobis nejako vela, tak kludne chod do OBB.

Otazka ale je, preco ti to vlastne vadi. Mas konkretne cisla, ze kolko objektov si vykreslil navyse, aj ked ich nevidno a o kolko ti poklesol fps ?
Ak nie, tak sa len jedna o subjektivny pocit a je skoda mrhat energiou na ine riesenie.

Karty su dnes dost dobre v tom, ze ti to stopnu v najvyssich stadiach pipeline, takze sa ani omylom nedostanes k pixel shaderom - vacsinou to cullnu este pocas transform stadia.

[Acer]

Spíš je to subjektivní. Ale, když budu třeba dál konstruovat AABB tree nebude to nějaké rozhašené ty jednotlivé sub-boxy?

[VladR]

Co konkretne myslis ? Ked rozbijes velky objekt na mensie a tym padom mas viacej mensich aabb boxov ?

[Acer]

Ano. Jestli, když bude objekt zrotovaný, tak jestli ty "menší" boxy nebudou třeba se nějak moc překrývat nebo tak. Musím říct, že jak konstruovat AABB tree nemám nastudováno zatím ani teoreticky, tak možná plácám nesmysly.

[Vilem Otte]

Klidně pro začátek použij OBB (jestli je zvětšení AABB při rotaci problém) - převod OBB na AABB a zpět je jen pár skalárních součinů (pokud si je rozumně uložíš).

Pokud budeš konstruovat Bounding Volume Hierarchy (tak se nazývá AABB tree ), věci se trochu komplikují. V zásadě můžeš použít 3 metody postavení - shora (Top-Down), zdola (Bottom-Up) a vkládáním (Insertion) ... tady bych důrazně varoval před tím co tvrdí wiki, zpravidla se takřka vždy používají Top-Down buildy - které jsou rychlejší než insertion a mají spousty výhod (Insertion je silně špatný přístup).

Bottom-Up - je první způsob co tě napadne, vzít Bounding volumes (AABB v tvém případě) na nejnižší úrovni a vždy 2 spojit do jednoho většího (ideálně 2 nejbližší) ... uvažujeme binární strom, nikoliv jiné případy (na ty je to snadno rozšiřitelné). Tento způsob ale tvoří docela špatné stromy (a aplikovat dobrou heuristiku spojování buněk je velmi pomalé).

Insertion - je vcelku špatná heuristika, implementace není tak těžká, ale správně se rozhodnout kam vložit buňku stromu je složité (a taková heuristika je velmi pomalá) - pokud je heuristika špatná, strom stojí za nic ... navíc vložit buňku někam do stromu je složitější (časově) než u ostatních dvou případů.

Top-Down - nejlepší a nejpoužívanější možný způsob. Vezmeš AABB všech objektů a spočteš AABB celé scény. Nyní určíš rovinu, od které jestli bude střed bounding boxu vlevo, zařadíš jej doleva, jinak doprava. Rekurzivně pokračuješ, než dosáhneš kritérií (např. těsně nad listy stromů je vždy jeden, který spojuje 2 dohromady). Trik je v tom, určit dobře rovinu, zpravidla ti bude stačit medián (pokud nechceš dělat spousty operací ve stromě, pak budeš potřebovat dobrý SAH - Surface Area Heuristics na rozhodnutí kam dát rovinu). Výhod top-down je mnohem více než nevýhod - a jestli uvažuješ o Bounding Volume Hierarchies - rozhodně ji stavěj Top-Down (je to nejrychlejší a výsledný strom je kvalitnější oproti dalším dvěma možnostem).

Pozn. Překrývání AABB vůbec nikdy zpravidla nevadí
_________________
Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.

[Acer]

Děkuji za vyčerpávající odpověď. Podívám se na to. Případně bych se ještě ozval, kdyby mi něco nebylo jasné.