Chtěl bych být schopen vykreslit velkou skupinu malých nezávisle se pohybujících objektů v reálném čase. Mohou se pohybovat rojem, ale jejich relativní pozice nebudou koherentní – jejich pozice se může v roji libovolně měnit a roje se mohou kdykoli rozpadnout a reformovat.
Jaký přístup k vytvoření hraniční objemové hierarchie by této situaci nejlépe vyhovoval? Existuje způsob, jak udržovat hierarchii, která je neoptimální, ale dostatečně dobrá, vyžaduje pouze částečnou aktualizaci každého snímku? Nebo existuje způsob, jak vytvořit hierarchii od začátku, která je dostatečně rychlá pro plynulou animaci?
Počet objektů bude příliš velký na to, aby se vykreslil bez hierarchie, ale ze stejného důvodu očekávám, že budování hierarchie bude časově náročné.
V návaznosti na komentář od Johna Calsbeeka, pokud můj zaměření na hierarchie ohraničení svazků je zavádějící a pro tuto situaci existuje lepší přístup k dělení prostoru odpovídat odpovídajícím způsobem. Hledám něco, co by se dokázalo vypořádat s tím, co popisuji, včetně všeho, na co mě nenapadlo.
Komentáře
- Záměrně omezujete otázka ohraničujících hierarchií svazků, nebo jste otevřeni jiným formám prostorového rozdělení?
- @JohnCalsbeek jsem ‚ upravil, abych objasnil – děkuji za poukázání na můj neúmyslné omezení.
- Zvažte možnost zacházet s “ rojem “ jako s jednou jednotkou, když se roje spojí; sloučit je do jediného roje, když samotář odejde daleko, stane se “ rojem “ jednoho. To funguje nejlépe, pokud roje bývají soudržné a samotáři bývají vzácní. Existuje spousta elegantních způsobů hraní s “ rojem je jedna jednotka „, jako je umožnění členům přepínat roje, jen když jsou ve vzájemném kontaktu seznam pokračuje dál a dál.
Odpovědět
Zvažte použití prostorového hashování, zejména pokud mají vaše objekty podobnou velikost.
V zásadě rozdělte svůj svět na buňky mřížky o stejné velikosti (2D a 3D jsou obě platné možnosti v závislosti na rozsahu vertikálního pohybu). Při každé aktualizaci přiřaďte svůj objekt ke každému zásobníku, který překrývá – pokud mají buňky slušnou velikost vzhledem k objektům, většina objektů by měla skončit v jednom zásobníku.
Každý zásobník je vložen do hash tabulky, klíčem jsou souřadnice koše. (Můžete si to také představit jako hashovací tabulku s více hodnotami pro stejný klíč a vložení objektu jednou pro každou buňku, kterou překrývá.)
V tomto schématu není žádná hierarchie, kterou by bylo možné znovu sestavit, díky čemuž se dobře hodí pro dynamické scény. Stále můžete testovat rozměry buňky proti frustum nebo proti okluzorům na hrubé úrovni a odhodit mnoho objektů najednou. Je také snazší spravovat tuto strukturu inkrementálně – můžete udržovat stejnou hashovací tabulku od rámečku k rámečku a objekty přesouvat z jednoho koše do druhého pouze tehdy, když překročí hranici buňky.
Odpověď
Můžete zkusit jednoduše omezit objem ohraničení o něco větší, než je nutné, aby objekty nepřekročily hranice při každém pohybu, ale pak znovu, budete muset strukturu znovu a znovu vytvořit tak jako tak.
Nebo existuje hierarchie mezních intervalů , která se to snaží přesně řešit scénář.
Nebo může být příspěvek Ingo Wald, Solomona Boulose a Petera Shirleye s názvem Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies zájmu.
Odpověď
Chtěl bych k tomu přidat nějaký praktický pohled.
Nechť předmluvu, že zde pracuji s omezenými informacemi:
- nevím, jak m jakékoli objekty, se kterými máte co do činění.
- Nevím, na co přesně se vaše struktura zrychlení používá. Frustum utracení? Sledování paprsku? Detekce kolizí mezi objekty v BVH?
Do budoucna budu předpokládat, že mluvíte o frustum utracení několika tisíc objektů.
Počet objektů bude příliš velký na to, aby se vykreslil bez hierarchie, ale ze stejného důvodu předpokládám, že budování hierarchie bude časově náročné.
Tvrdím, že pokud musíte navštívit každý objekt, každý snímek, abyste mohli vypočítat BVH, je jejich vyřazení přímo a bez BVH ve skutečnosti rychlejší. To samozřejmě závisí na vaší implementaci utracení frustum. Hraniční svazky všech objektů by měly být souvisle uloženy v paměti. To má za následek efektivnější využití mezipaměti CPU a umožňuje další optimalizaci pomocí pokynů SIMD. DICE má na toto téma celou prezentaci: Culling the Battlefield: Data Oriented Design in Practice
Prezentace také zmiňuje zrychlení utracení ještě více pomocí jednoduché mřížky.
Protože předpokládám, že většina základen 3D / simulačních / herních kódů již má nějaký druh Třída BVH a já nevím, jak důležité je pro vás získat NEJLEPŠÍ utracení, rád bych představil několik argumentů pro dodržování BVH:
Podle toho, jakou metodu použijete, konstrukci a BVH může být rychlý a jednoduchý.
Moje aktuální implementace binárního BVH (každý uzel může mít pouze nulu nebo dvě podřízené a každý listový uzel ukládá pouze jednu položku), který je určen pro rychlé konstrukce trvá přibližně 0,18 ms pro 1137 objektů v jediném vlákně i7-5960X @ 3.89GHz . Jsem si jistý, že to může být rychlejší. Stavba se provádí bez přerozdělení paměti v procesu (to zdvojnásobilo výkon konstrukce).
I když může SAH generovat nejlepší BVH, trvá to dlouho. SAH je dobrý pro věci, které můžete předpočítat, například kolizní sítě. Za běhu pak můžete kolizní sítě vložit do BVH, který je vhodnější pro stavbu v reálném čase.
Rychlý a jednoduchý stavební postup BVH (ten, který „Aktuálně používám) je třídit všechny objekty na ose (například nejdelší osu nadřazené AABB) a rozdělit kolekci do středu.
Chcete-li věci ještě více zrychlit, spočítejte AABB uzlu PO sestavení stromu kombinací dvou podřízených uzlů AABB nadřazeného uzlu. Tím se zabrání iteraci všemi objekty (další zrychlení 2x). To je však možné pouze v případě, že se vaše kritérium rozdělení nespoléhá na nadřazené AABB.