Speciální datové struktury pro pokročilé grafické techniky (vrhání paprsku)

Motivace: V metodě sledování paprsku potřebujeme najít průsečík mnoha paprsků (n ~ 10^6 - 10^9) se scénou, která obsahuje mnoho objektů (m ~ 10^5 - 10^7). Naivní metoda otestuje pro každý paprsek všechny objekty a vrátí nejbližší průsečík se složitostí O(n×m). To je v praxi nepoužitelné, proto chceme speciální struktury které výpočet urychlí na O(n×log m).
Struktury pro range a similarity search na bodových datech (otázka 10) nefungují přímo, musí se modifikovat
Běžně používané struktury:
- Grid
- Octree
- BVH
- kd-tree

Grid

Uniformní nerekurzivní dělení prostoru
Princip
1. Axis-aligned bounding box (AABB) scény se rozdělí na ~n přibližně krychlových buněk, kde n je počet objektů ve scéně
2. Udělá se jeden průchod nad objekty, každý se zařadí do všech buněk které protíná (buď se porovnávají jen bounding boxy, nebo se dělá přesnější test) - O(n)
3. Traverzace: každý paprsek se připraví (najde se první buňka kterou protíná, …), pak se pomocí DDA algoritmu traverzují postupně všechny buňky které zasahuje, testují se všechny objekty uvnitř těch buněk, po nalezení průsečíku uvnitř aktuální buňky algoritmus končí.
Stavba O(n) - vhodné na interaktivní aplikace, očekávaný čas traverzace O(n^1/3)
Problém s neuniformní distribucí objektů - teapot in stadium - většina objektů v jedné buňce - degeneruje na O(n)
Pokus vylepšit výkon ve scénách s neuniformní distribucí: neregulární mřížky, rekurzivní mřížky (buňkou mřížky může být další mřížka)

Octree

Jako point octree (strom arity 8, rekurzivní hierarchické dělení prostoru), skladuje nebodová data - duplikace objektů - každý objekt se skladuje ve všech listech které protíná
Obtížná implementace, neefektivní, nepoužívá se moc

kd-tree

Jako point kd-tree, opět musí duplikovat objekty
Stavba: SAH - surface area heuristic:
1. Udělá se AABB scény, setřídí se počáteční a koncové souřadnice objektů podél nejdelší osy
2. Na každé takové souřadnici se zkusí uzel rozdělit a vyhodnotí se SAH cenová funkce: pravděpodobnost že paprsek protne konvexní objekt úměrná jeho obsahu, ne objemu. Proto cena uzlu = obsah levého potomka*cena levého potomka + obsah pravého potomka*cena pravého potomka + cena iterace (implementační konstanta). Cena potomka se odhaduje jako počet objektů * cena průsečíku objektu (druhá implementační konstanta).
3. Vybere se nejlepší split (pozice splitu s nejnižší SAH cenou), případně se to zopakuje pro další 2 osy
4. Rekurzivně se pokračuje dokud nejsou listy dost malé, nebo SAH neřekne že už nemá cenu dělit (odhad pro list (počet objektů*cena průsečíku objektu) je menší než nejlepší cena splitu).
Traverzace: Použije se rekurze nebo explicitní stack kam se ukládají otevřené uzly. Po otevření vnitřního uzlu se zjistí jestli paprsek pokračuje jen do jednoho nebo obou potomků a ti se zařadí na stack, po otevření listu se protnou všechny skladované objekty. Algoritmus končí když najde průsečík uvnitř daného listu.
Stavba pomocí SAH je pomalá, urychlení: binning: nezkouší se tolik možných rozdělení, jen pár v pravidelných intervalech
Stavba: O(n log^2 n), O(n log n) s presortingem (optimalizace, zabraňuje vícenásobnému řazení) nebo binningem, traverzace: očekáváno log n.
Lépe reaguje na neuniformní rozdělení scény, SAH hodně pomáhá (~10-100krát lepší výsledky), celkově asi nejrychlejší struktura

BVH

Nedělí prostor, ale objekty. Každý uzel si pamatuje svůj AABB
AABB tvoří hierarchii, list drží sjednocení AABB všech skladovaných objektů, vnitřní uzel drží sjednocení AABB dvou potomků
Build: velmi podobný kd-tree, taky se sortuje podle jedné osy, ale nedělí se prostor, ale seřazený seznam uzlů (celkem n-1 možných rozdělení)
Optimalizace pomocí binning také možná
Asymptotická časová složitost stejná jako u kd-tree, možné stejné optimalizace
Traverzace: podobně jako u kd-tree, rozdíly:
1. u kd-tree se ve vnitřním uzlu vždy pokračuje do 1 nebo 2 potomků, u BVH do 0-2
2. po nalezení průsečíku je potřeba dál traverzovat, protože AABB se můžou částečně překrývat
Výkon: velmi dobrý, problém je průsečík paprsek-AABB - žere ~80% času - každý traverzační krok je o dost dražší než u kd-tree → kd-tree mírně lepší.