Szeretném, ha valós időben nagy számú, egymástól függetlenül mozgó objektumot hoznék létre. Lehet, hogy rajszerűen mozognak, de relatív pozícióik nem lesznek koherensek – helyzetük önkényesen megváltozhat egy rajon belül, és a rajok bármikor széteshetnek és megreformálódhatnak.
A korlátozó kötet-hierarchia kialakításának milyen megközelítése felelne meg a legjobban ezt a helyzetet? az optimálisnál alacsonyabb, de elég jó hierarchia fenntartásának módja, amely csak az egyes képkockák részleges frissítését igényli? Vagy van-e olyan módszer, amellyel a semmiből fel lehet építeni egy hierarchiát, amely elég gyors a sima animációhoz?
Az objektumok száma túl nagy ahhoz, hogy hierarchia nélkül jelenjen meg, de ugyanezen okból azt gondolom, hogy a hierarchia kiépítése időigényes.
John Calsbeek megjegyzése nyomán, ha a kötethierarchiák korlátozására való összpontosítás téves, és ennél a helyzetnél van egy jobb térfelosztási megközelítés, kérem ennek megfelelően válaszoljon. Keresek valamit, ami képes foglalkozni azzal, amit leírok, beleértve bármit, amire még nem gondoltam.
Megjegyzések
- Szándékosan korlátozol a kötet-hierarchiák korlátozásának kérdése, vagy nyitott vagy a térbeli particionálás egyéb formáira?
- @JohnCalsbeek I ‘ szerkesztettem a pontosítás érdekében – köszönöm, hogy rámutattál véletlen korlátozás.
- Fontolja meg egy ” raj ” kezelését egyetlen egységként, amikor a rajok egyesülnek; egyesítsd őket egyetlen rajba, amikor egy magányos ember messzire vándorol, egy ” raj ” lesz belőle. Ez akkor működik a legjobban, ha a rajok összetartóak, a magányosak pedig ritkák. A ” rajdal nagyon ügyesen lehet játszani, ez egyetlen egység “, például lehetővé teszi a tagok számára, hogy csak akkor váltsanak rajokat, amikor egymással érintkezve a lista folytatódik.
Válasz
Fontolja meg a térbeli hash használatát, különösen ha az objektumai hasonló méretűek.
Alapvetően ossza fel világát egyenletes méretű rácscellákra (a 2D és a 3D egyaránt érvényes lehetőség a függőleges mozgás mértékétől függően). Minden frissítéshez rendelje hozzá az objektumot az egyes átfedő tálcákhoz – ha a cellák megfelelő méretűek az objektumokhoz képest, akkor a legtöbb objektumnak egyetlen tárolóba kell kerülnie.
Minden tárolót hash-táblába illesztenek, a kulcs a kuka koordinátái. (Úgy is gondolhat rá, hogy hash-tábla több értékkel rendelkezik ugyanahhoz a kulcshoz, és minden objektumba egyszer beilleszt egy objektumot, amelyet átfed.)
Ebben a sémában nincs újjáépíthető hierarchia, ami kiválóan alkalmas dinamikus jelenetekhez. Még mindig tesztelheti a cella méreteit a porckoronggal vagy az elzáródókkal durva szinten, és sok objektumot egyszerre dobhat el. Emellett egyszerűbb kezelni ezt a struktúrát fokozatosan – megtarthatja a hash táblát kockáról kockára, és az objektumokat csak akkor helyezheti át egyik binből, amikor átlépik a cella határait.
Válasz
Megpróbálhatja egyszerűen a szükségesnél kissé nagyobbra tenni a kötőköteteket, hogy az objektumok ne lépjék át határaikat minden mozdulatnál, de aztán újra, amúgy is újra kellene építenie a struktúrát.
Vagy létezik Korlátozó intervallum hierarchia , amely megpróbálja pontosan ezt kezelni forgatókönyv.
Vagy Ingo Wald, Solomon Boulos és Peter Shirley írása Deformálható jelenetek sugárzásának nyomon követése dinamikus korlátozó kötethierarchiák segítségével érdekes lehet.
Válasz
Szeretnék ehhez gyakorlati perspektívát adni.
Engedje meg, hogy nekem előszó, hogy itt nem korlátozott információval dolgozom:
- nem tudom, hogy m bármely tárgy, amellyel foglalkozik.
- Nem tudom, hogy pontosan mire használják a gyorsulási szerkezetét. Frustum selejtezése? Sugárkövetés? Ütközés észlelése a BVH-ban lévő objektumok között?
A továbbiakban azt feltételezem, hogy néhány ezer objektum megsemmisítéséről beszélünk.
Az objektumok száma túl nagy lesz ahhoz, hogy hierarchia nélkül jelenjen meg, de ugyanezen okból azt gondolom, hogy a hierarchia kiépítése időigényes.
Azt állítom, hogy ha minden objektumot meg kell látogatnia minden képkockán a BVH kiszámításához, akkor a közvetlen és BVH nélküli selejtezés valóban gyorsabb. Ez természetesen a frustum selejtezésének végrehajtásától függ. Az összes objektum kötöttségeit egymás mellett kell tárolni a memóriában. Ez hatékonyabb CPU-gyorsítótár-felhasználást eredményez, és további optimalizálást tesz lehetővé a SIMD utasításai segítségével.A A DICE teljes előadással rendelkezik erről a témáról: A csatatér megsemmisítése: Adatorientált tervezés a gyakorlatban
Az előadás emellett megemlíti a gyorsabb felszámolást is, egyszerű rács segítségével.
Mivel feltételezem, hogy a legtöbb 3D / szimulációs / játékkód már rendelkezik valamilyen A BVH osztály és nem tudom, mennyire kritikus az Ön számára a LEGJOBB selejtezési teljesítmény elérése, szeretnék néhány érvet felhozni a BVH-hoz való ragaszkodás mellett:
Attól függően, hogy milyen módszert használ, a konstrukciót egy BVH lehet gyors és egyszerű.
A bináris BVH jelenlegi megvalósítása (minden csomópontnak csak nulla vagy két gyermeke lehet, és minden levélcsomópont csak egy elemet tárol), amelyet gyors építése 11,18 objektumhoz körülbelül 0,18 ms-ot tesz ki egy i7-5960X @ 3,89GHz egyetlen szálán. Biztos vagyok benne, hogy gyorsabb lehet. Az építkezést a memória átcsoportosítása nélkül hajtják végre (ez megduplázta az építési teljesítményt).
Bár az SAH a legjobb BVH-t képes előállítani, hosszú időbe telik. A SAH jó olyan dolgokhoz, amelyeket előre kiszámíthat, például ütközési hálókat. Futás közben az ütközési hálókat belehelyezheti egy valós idejű építésre alkalmasabb BVH-ba.
Gyors és egyszerű BVH-konstrukció (az I “m használatával jelenleg” az összes objektum rendezése egy tengelyen (például az AABB szülő leghosszabb tengelye), és a gyűjtemény felosztása középen.
A dolgok még gyorsabbá tételéhez számítsa ki az AABB csomópontokat. A fa felépítése UTÁN, a szülőcsomópont két gyermekcsomópont AABB-jének kombinálásával. Ez elkerüli az összes objektumon keresztüli iterációt (további 2x gyorsítás). Ez azonban csak akkor lehetséges, ha a felosztási feltétel nem támaszkodik a szülő AABB-re. / p>