Jeg vil gerne være i stand til at gengive en stor population af små uafhængige objekter i realtid. De kan bevæge sig på en sværmlignende måde, men deres relative positioner vil ikke være sammenhængende – deres position kan ændre sig vilkårligt inden for en sværm, og sværme kan bryde op og reformere på ethvert tidspunkt.
Hvilken tilgang til opbygning af et afgrænsende volumenhierarki passer bedst til denne situation? Er der en måde at opretholde et hierarki, der er suboptimalt, men godt nok, der kun kræver en delvis opdatering af hver ramme? Eller er der en måde at opbygge et hierarki fra bunden hver ramme, der er hurtig nok til jævn animation?
Antallet af objekter vil være for stort til at gengives uden et hierarki, men af samme grund forventer jeg at opbygge hierarkiet for at være tidskrævende.
Efter kommentar fra John Calsbeek, hvis min fokus på begrænsende volumenhierarkier er vildledt, og der er en bedre pladsopdelingsmetode til denne situation, tak svar i overensstemmelse hermed. Jeg leder efter noget, der kan håndtere det, jeg beskriver, inklusive alt, hvad jeg ikke har tænkt på.
Kommentarer
- Begrænser du med vilje spørgsmålet om at begrænse volumenhierarkier, eller er du åben for andre former for rumlig partitionering?
- @JohnCalsbeek I ‘ har redigeret for at afklare – tak for at påpege min utilsigtet begrænsning.
- Overvej at behandle en ” sværm ” som en enkelt enhed, når sværme smelter sammen; fusionere dem til en enkelt sværm, når en enspænder vandrer langt ud, bliver det en ” sværm ” af en. Dette fungerer bedst, hvis sværme har tendens til at være sammenhængende, og ensomere har tendens til at være sjældne. Der er mange pæne måder at lege med ” sværmen er en enkelt enhed ” som at lade medlemmerne kun skifte sværme, når de er i kontakt med hinanden fortsætter listen og fortsætter.
Svar
Overvej at bruge rumlig hashing, især hvis dine genstande har samme størrelse.
Grundlæggende skal du opdele din verden i gitterceller i ensartet størrelse (2D og 3D er begge gyldige muligheder afhængigt af mængden af lodret bevægelse). Hver opdatering tildeler dit objekt til hver bin, som det overlapper – hvis cellerne er anstændigt dimensioneret i forhold til objekterne, skal de fleste objekter ende i en enkelt bin.
Hver bin indsættes i en hash-tabel, med nøglen koordinaterne til skraldespanden. (Du kan også tænke på det som en hash-tabel med flere værdier for den samme nøgle og indsætte et objekt en gang for hver celle, som det overlapper.)
Der er intet hierarki at genopbygge i dette skema, hvilket gør den velegnet til dynamiske scener. Du kan stadig teste cellens dimensioner mod frustum eller mod okkluderer på et groft niveau og kassere mange objekter på én gang. Det er også nemmere at administrere denne struktur trinvist – du kan holde hash-tabellen den samme fra ramme til ramme og kun flytte objekter fra en bin til en anden, når de krydser grænsen for en celle.
Svar
Du kan prøve at gøre afgrænsningsvolumenne lidt større end nødvendigt, så objekterne ikke krydser deres grænser ved hvert træk, men derefter igen, du bliver alligevel nødt til at genopbygge strukturen nu og da.
Eller der er Afgrænsningsintervalhierarki , der forsøger at adressere netop dette scenarie.
Eller papiret af Ingo Wald, Solomon Boulos og Peter Shirley med titlen Strålesporing af deformerbare scener ved hjælp af dynamiske afgrænsningsvolumenhierarkier kan være af interesse.
Svar
Jeg vil gerne tilføje noget praktisk perspektiv til dette.
Lad mig forord, at jeg arbejder på begrænset information her:
- Jeg ved ikke, hvordan jeg alle objekter, du har at gøre med.
- Jeg ved ikke, hvad din accelerationsstruktur bruges til. Frustum slagtning? Strålesporing? Kollisionsdetektion mellem objekter i BVH?
Fremadrettet antager jeg, at du taler om frustum, der sletter et par tusinde objekter.
Antallet af objekter vil være for stort til at gengives uden et hierarki, men af samme grund forventer jeg at opbygge hierarkiet for at være tidskrævende.
Jeg hævder, at hvis du er nødt til at besøge hvert objekt for hver ramme for at beregne en BVH, er det faktisk hurtigere at slette dem direkte og uden en BVH. Dette afhænger selvfølgelig af din implementering af frustumudslettelse. Afgrænsningsvolumen for alle objekter skal opbevares sammenhængende i hukommelsen. Dette resulterer i mere effektiv udnyttelse af CPU-cache og giver mulighed for yderligere optimering ved hjælp af SIMD-instruktioner. DICE har en hel præsentation om dette emne: Culling the Battlefield: Data Oriented Design in Practice
Præsentationen nævner også hurtigere udrulning ved hjælp af et simpelt gitter.
Da jeg antager, at de fleste 3D / simulation / spilkodebaser allerede har en slags BVH-klasse, og jeg ved ikke, hvor kritisk det er for dig at få den BEDSTE slagtningsydelse, jeg vil gerne præsentere nogle argumenter for at holde fast i en BVH:
Afhængigt af hvilken metode du bruger, konstruerer en BVH kan være hurtig og enkel.
Min nuværende implementering af en binær BVH (hver node kan kun have nul eller to børn, og hver bladknude gemmer kun et element), der er designet til hurtig -konstruktion tager omkring 0,18 ms for 1137 objekter på en enkelt tråd i en i7-5960X @ 3,89 GHz . Jeg er sikker på, at det kan være hurtigere. Konstruktion udføres uden at omfordele hukommelse i processen (dette fordoblede konstruktionsydelsen).
Selvom SAH muligvis genererer den bedste BVH, tager det lang tid. SAH er god for ting, du kan beregne på forhånd, som kollisionsmasker. Ved kørsel kan du derefter sætte kollisionsmaskerne ind i en BVH, der er mere egnet til realtidskonstruktion.
En hurtig og enkel BVH-konstruktionstilgang (den jeg “m bruger i øjeblikket) er at sortere alle objekter på en akse (for eksempel den overordnede AABBs længste akse) og opdele samlingen i midten.
For at fremskynde tingene endnu mere, skal du beregne node-AABBerne. EFTER at træet er konstrueret ved at kombinere de to underordnede node-AABBer i en forældrenode. Dette undgår iterering gennem alle objekter (en anden 2x hastighed). Dette er dog kun muligt, hvis dit opdelingskriterium ikke stoler på forældrenes AABB.