Jeg vil gjerne gjengi en stor populasjon av små uavhengige objekter i sanntid. De kan bevege seg på en svermlignende måte, men deres relative posisjoner vil ikke være sammenhengende – deres posisjon kan endre seg vilkårlig i en sverm og svermer kan bryte opp og reformere når som helst.
Hvilken tilnærming til å bygge et begrensende volumhierarki vil best passe denne situasjonen? en måte å opprettholde et hierarki som er suboptimalt, men godt nok, som bare krever en delvis oppdatering av hver ramme? Eller er det en måte å bygge et hierarki fra grunnen av hver ramme som er rask nok til jevn animasjon?
Antall objekter vil være for stort til å gjengis uten hierarki, men av samme grunn forventer jeg at det er tidkrevende å bygge hierarkiet.
Etter kommentar fra John Calsbeek, hvis min fokus på begrensende volumhierarkier er misvisende, og det er en bedre tildeling av rompartisjonering for denne situasjonen, vær så snill svar deretter. Jeg ser etter noe som kan håndtere det jeg beskriver, inkludert alt jeg ikke har tenkt på.
Kommentarer
- Er du bevisst begrensende spørsmålet om å begrense volumhierarkier, eller er du åpen for andre former for romlig partisjonering?
- @JohnCalsbeek Jeg ‘ har redigert for å avklare – takk for at du påpekte min utilsiktet begrensning.
- Vurder å behandle en » sverm » som en enkelt enhet når svermer smelter sammen; slå dem sammen til en enkelt sverm, når en ensom vandrer langt, blir det en » sverm » av en. Dette fungerer best hvis svermene har en tendens til å være sammenhengende og ensomhetene har en tendens til å være sjeldne. Det er mange fine måter å spille med » svermen er en enkelt enhet » som å la medlemmene bare bytte svermer når de er i kontakt med hverandre fortsetter listen og fortsetter.
Svar
Vurder å bruke romlig hashing, spesielt Hvis objektene dine er av samme størrelse.
Del i utgangspunktet verdenen din i jevn størrelse rutenettceller (2D og 3D er begge gyldige muligheter, avhengig av hvor mye vertikal bevegelse). Hver oppdatering, tilordne objektet til hver søppel som den overlapper – hvis cellene er ordentlig størrelse i forhold til objektene, bør de fleste objekter havne i en enkelt søppel.
Hver kasse blir satt inn i en hash-tabell med nøkkelen som koordinatene til søpla. (Du kan også tenke på det som en hash-tabell med flere verdier for samme nøkkel, og å sette inn et objekt en gang for hver celle som det overlapper.)
Det er ikke noe hierarki å gjenoppbygge i dette skjemaet, som gjør den godt egnet for dynamiske scener. Du kan fremdeles teste cellens dimensjoner mot frustum eller mot lukkere på et grovt nivå og kaste mange gjenstander på en gang. Det er også lettere å administrere denne strukturen trinnvis – du kan holde hash-tabellen den samme fra ramme til ramme og bare flytte objekter fra en søppel til en annen når de krysser grensen til en celle.
Svar
Du kan bare prøve å gjøre avgrensningsvolumene litt større enn nødvendig, slik at objektene ikke krysser grensene ved hvert trekk, men så igjen, du må gjenoppbygge strukturen nå og da uansett.
Eller det er Avgrensningsintervallhierarki som prøver å adressere nettopp dette scenario.
Eller papiret av Ingo Wald, Solomon Boulos og Peter Shirley med tittelen Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies kan være av interesse.
Svar
Jeg vil gjerne legge til noe praktisk perspektiv på dette.
La meg forord at jeg bruker begrenset informasjon her:
- Jeg vet ikke hvordan jeg noen objekter du har å gjøre med.
- Jeg vet ikke hva akselerasjonsstrukturen din brukes til. Slakting av Frustum? Strålesporing? Kollisjonsdeteksjon mellom objekter i BVH?
Fremover vil jeg anta at du snakker om frustum som slakter noen få tusen objekter.
Antallet objekter vil være for stort til å gjengis uten et hierarki, men av samme grunn forventer jeg at det tar tid å bygge hierarkiet.
Jeg vil hevde at hvis du må besøke hvert objekt hver ramme for å beregne en BVH, er det faktisk raskere å slå dem direkte og uten en BVH. Dette avhenger selvfølgelig av implementeringen av frustum. Grensevolumene til alle objekter skal lagres sammenhengende i minnet. Dette resulterer i mer effektiv bruk av CPU-cache og muliggjør ytterligere optimalisering ved hjelp av SIMD-instruksjoner. DICE har en hel presentasjon om dette emnet: Culling the Battlefield: Data Oriented Design in Practice
Presentasjonen nevner også å øke hastigheten på å avlive enda mer, ved hjelp av et enkelt rutenett.
Siden jeg antar at de fleste 3D / simulering / spillkodebaser allerede har en slags BVH-klasse, og jeg vet ikke hvor viktig det er for deg å oppnå BEST utslippsytelse. Jeg vil gjerne presentere noen argumenter for å holde fast ved en BVH:
Avhengig av hvilken metode du bruker, konstruerer en BVH kan være rask og enkel.
Min nåværende implementering av en binær BVH (hver node kan bare ha null eller to barn, og hver bladnode lagrer bare ett element) som er designet for rask konstruksjon tar rundt 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 gå raskere. Konstruksjon utføres uten å omfordele minne i prosessen (dette doblet konstruksjonsytelsen).
Selv om SAH kan generere den beste BVH, tar det lang tid. SAH er bra for ting du kan beregne på forhånd, som kollisjonsmasker. Ved kjøretid kan du deretter sette kollisjonsmasken i en BVH som er mer egnet for sanntidskonstruksjon.
En rask og enkel BVH-konstruksjonstilnærming (den jeg «m bruker for øyeblikket) er å sortere alle objekter på en akse (for eksempel den overordnede AABBs lengste akse) og dele samlingen i midten.
For å øke hastigheten på ting enda mer, beregne noden AABBs ETTER å konstruere treet, ved å kombinere de to barn-node-AABB-ene til en foreldrenode. Dette unngår å iterere gjennom alle objekter (ytterligere 2x hastighet). Dette er imidlertid bare mulig hvis delingskriteriet ikke stoler på foreldrenes AABB.