Aș dori să pot reda o populație mare de obiecte mici în mișcare independentă în timp real. Acestea se pot mișca într-un mod asemănător roiului, dar pozițiile lor relative nu vor fi coerente – poziția lor se poate schimba în mod arbitrar în cadrul unui roi, iar roiurile se pot despărți și se pot reforma în orice moment.
Ce abordare pentru construirea unei ierarhii de volum limitativ s-ar potrivi cel mai bine acestei situații? Există o modalitate de a menține o ierarhie sub-optimă, dar suficient de bună, care necesită doar o actualizare parțială a fiecărui cadru? Sau există o modalitate de a construi o ierarhie de la zero fiecare cadru care este suficient de rapid pentru o animație lină?
Numărul de obiecte va fi prea mare pentru a fi redat fără o ierarhie, dar din același motiv mă aștept ca construirea ierarhiei să consume mult timp.
În urma comentariului lui John Calsbeek, dacă concentrarea pe limitarea ierarhiilor de volum este greșită și există o abordare mai bună de partiționare a spațiului pentru această situație, vă rog răspunde în consecință. „Caut ceva care să poată face față a ceea ce descriu, inclusiv tot ceea ce nu m-am gândit.
Comentarii
- Restrângeți intenționat întrebarea cu privire la limitarea ierarhiilor de volum sau sunteți deschis către alte forme de partiționare spațială?
- @JohnCalsbeek Am ‘ modificat pentru a clarifica – mulțumesc că ați indicat restricție accidentală.
- Luați în considerare tratarea unui ” roi ” ca o singură unitate, atunci când roiurile se îmbină; îmbinați-le într-un singur roi, atunci când un singuratic rătăcește departe, acesta devine un ” roi ” al unuia. Acest lucru funcționează cel mai bine dacă roiurile tind să fie coezive și cei singuri tind să fie rare. Există o mulțime de moduri îngrijite de a juca cu ” roiul este o singură unitate ” cum ar fi permiterea membrilor să schimbe roiurile numai atunci când sunt în contact unul cu celălalt, lista continuă.
Răspuns
Luați în considerare utilizarea hash spațial, în special dacă obiectele dvs. au dimensiuni similare.
Practic, împărțiți-vă lumea în celule de grilă de dimensiuni uniforme (2D și 3D sunt ambele posibilități valabile în funcție de cantitatea de mișcare verticală). Fiecare actualizare, atribuiți obiectul fiecărui coș pe care îl suprapune – dacă celulele sunt dimensionate decent față de obiecte, majoritatea obiectelor ar trebui să ajungă într-un singur coș.
Fiecare coș este introdus într-un tabel hash, cu cheia fiind coordonatele coșului. (De asemenea, vă puteți gândi la acesta ca la un tabel hash cu mai multe valori pentru aceeași cheie și inserarea unui obiect o dată pentru fiecare celulă pe care o suprapune.)
Nu există nicio ierarhie de reconstituit în această schemă, ceea ce îl face foarte potrivit pentru scenele dinamice. Puteți testa dimensiunile celulei împotriva frustului sau împotriva ocluzoarelor la un nivel gros și aruncați multe obiecte simultan. De asemenea, este mai ușor să gestionați această structură în mod incremental – puteți menține tabelul hash la fel de la un cadru la altul și puteți muta obiecte dintr-un coș în altul doar când trec granița unei celule.
Răspuns
Puteți încerca să faceți pur și simplu volumele de delimitare puțin mai mari decât este necesar, astfel încât obiectele să nu-și depășească limitele la fiecare mișcare, dar din nou, ar trebui să reconstruiți structura acum și apoi oricum.
Sau există Ierarhia intervalului de limitare care încearcă să abordeze exact acest lucru scenariu.
Sau, lucrarea de Ingo Wald, Solomon Boulos și Peter Shirley intitulată Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Ierarhii ar putea fi de interes.
Răspuns
Aș dori să adaug o perspectivă practică la acest lucru.
Să prefața mea că „operez pe informații limitate aici:
- Nu știu cum m orice obiecte cu care aveți de-a face.
- Nu știu pentru ce este utilizată exact structura dvs. de accelerație. Frustum sacrificare? Trasarea razelor? Detectarea coliziunilor între obiecte din BVH?
Înainte, voi presupune că vorbiți despre frustum care elimină câteva mii de obiecte.
Numărul de obiecte va fi prea mare pentru a fi redat fără o ierarhie, dar din același motiv mă aștept ca construirea ierarhiei să consume mult timp.
Aș susține că dacă trebuie să vizitați fiecare obiect fiecare cadru pentru a calcula un BVH, eliminarea lor directă și fără un BVH este de fapt mai rapidă. Bineînțeles, acest lucru depinde de implementarea tăierii de frustum. Volumele de delimitare ale tuturor obiectelor trebuie stocate în memorie contigu. Acest lucru are ca rezultat o utilizare mai eficientă a cache-ului procesorului și permite o optimizare suplimentară folosind instrucțiunile SIMD. DICE are o prezentare completă pe acest subiect: Culling the Battlefield: Data Oriented Design in Practice
Prezentarea menționează, de asemenea, accelerarea reducerii și mai mult, utilizând o grilă simplă.
Deoarece presupun că majoritatea bazelor de coduri 3D / de simulare / joc au deja un fel de Clasa BVH și nu știu cât de critic este pentru dvs. să obțineți cea mai bună performanță de eliminare, aș dori să vă prezint câteva argumente pentru a rămâne cu un BVH:
În funcție de ce metodă utilizați, construirea un BVH poate fi rapid și simplu.
Implementarea mea actuală a unui BVH binar (fiecare nod poate avea doar zero sau doi copii și fiecare nod frunză stochează doar un articol) care este conceput pentru durează aproximativ 0,18 ms pentru 1137 de obiecte pe un singur fir al unui i7-5960X @ 3,89 GHz . Sunt sigur că poate fi mai rapidă. Construcția se realizează fără realocarea memoriei în proces (acest lucru a dublat performanța construcției).
În timp ce SAH ar putea genera cel mai bun BVH, durează mult. SAH este bun pentru lucruri pe care le puteți precomputa, cum ar fi ochiurile de coliziune. În timpul rulării, puteți pune ochiurile de coliziune într-un BVH mai potrivit pentru construcții în timp real.
O abordare simplă și rapidă a construcției BVH (cea I „M folosesc în prezent) este de a sorta toate obiectele pe o axă (de exemplu cea mai lungă axă a părintelui AABB) și de a împărți colecția în mijloc.
Pentru a accelera lucrurile și mai mult, calculați AABB-urile nodului DUPĂ construirea arborelui, prin combinarea celor două AABB-uri de nod copil ale unui nod părinte. Acest lucru evită iterarea prin toate obiectele (o altă accelerație de 2 ori). Acest lucru este posibil însă numai dacă criteriul de împărțire nu se bazează pe AABB-ul părintelui.