Jag skulle vilja kunna göra en stor population av små oberoende rörliga föremål i realtid. De kan röra sig på ett svärmliknande sätt, men deras relativa positioner kommer inte att vara sammanhängande – deras position kan förändras godtyckligt inom en svärm och svärmar kan bryta upp och reformera när som helst. ett sätt att upprätthålla en hierarki som är suboptimal men tillräckligt bra, som bara kräver en delvis uppdatering av varje ram? Eller finns det ett sätt att bygga en hierarki från grunden varje ram som är snabb nog för smidig animering?
Antalet objekt kommer att vara för stort för att återges utan en hierarki, men av samma anledning förväntar jag mig att det är tidskrävande att bygga hierarkin.
Efter kommentar från John Calsbeek, om min fokus på begränsande volymhierarkier är missriktat, och det finns en bättre rymdpartitioneringsmetod för denna situation, tack svara därefter. Jag letar efter något som kan hantera det jag beskriver, inklusive allt jag inte har tänkt på.
Kommentarer
- Begränsar du avsiktligt frågan till begränsande volymhierarkier, eller är du öppen för andra former av rumslig partitionering?
- @JohnCalsbeek I ’ har redigerats för att klargöra – tack för att du påpekade min oavsiktlig begränsning.
- Överväg att behandla en ” svärm ” som en enda enhet när svärmar slås samman; slå samman dem i en enda svärm, när en ensamstående vandrar bort till långt blir det en ” svärm ” av en. Detta fungerar bäst om svärmarna tenderar att vara sammanhängande och ensamstående tenderar att vara sällsynta. Det finns många snygga sätt att spela med ” svärmen är en enda enhet ” som att låta medlemmar bara byta svärmar när de är i kontakt med varandra fortsätter listan och fortsätter.
Svar
Överväg att använda rumslig hashing, särskilt om dina objekt har samma storlek.
I grund och botten delar du din värld i enhetligt stora rutnätceller (2D och 3D är båda giltiga möjligheter beroende på mängden vertikal rörelse). Varje uppdatering, tilldela ditt objekt till varje fack som det överlappar varandra – om cellerna är anständigt dimensionerade i förhållande till objekten, bör de flesta föremål hamna i ett enda fack.
Varje fack sätts in i en hashtabell med nyckeln som koordinaterna för papperskorgen. (Du kan också tänka på det som en hashtabell med flera värden för samma nyckel och infoga ett objekt en gång för varje cell som det överlappar.)
Det finns ingen hierarki att bygga om i detta schema, vilket gör den väl lämpad för dynamiska scener. Du kan fortfarande testa cellens dimensioner mot frustum eller mot höljen på en grov nivå och kasta många objekt samtidigt. Det är också lättare att hantera den här strukturen stegvis – du kan hålla hashtabellen densamma från ram till ram och bara flytta objekt från ett fack till ett annat när de passerar gränsen för en cell.
Svar
Du kan försöka helt enkelt göra avgränsningsvolymerna lite större än nödvändigt så att objekten inte kryssar sina gränser vid varje drag men sedan igen, du måste bygga upp strukturen då och då ändå.
Eller det finns Gränsintervallhierarki som försöker ta itu med just detta scenariot.
Eller papperet av Ingo Wald, Solomon Boulos och Peter Shirley med titeln Ray-spårning av deformerbara scener med dynamiska gränsvolymhierarkier kan vara av intresse.
Svar
Jag vill lägga till lite praktiskt perspektiv på detta.
Låt jag förordar att jag arbetar med begränsad information här:
- Jag vet inte hur m alla objekt du har att göra med.
- Jag vet inte exakt din accelerationsstruktur används för. Frustum avlivning? Strålspårning? Kollisionsdetektering mellan objekt i BVH?
Framöver kommer jag att anta att du pratar om frustum som avlägsnar några tusen objekt.
Antalet objekt blir för stort för att återges utan en hierarki, men av samma anledning förväntar jag mig att bygga hierarkin är tidskrävande.
Jag skulle argumentera för att om du måste besöka varje objekt för varje ram för att beräkna en BVH, är det faktiskt snabbare att rensa dem direkt och utan BVH. Detta beror naturligtvis på hur du avlägsnar frustum. Avgränsningsvolymerna för alla objekt ska lagras sammanhängande i minnet. Detta resulterar i effektivare CPU-cache-användning och möjliggör ytterligare optimering med SIMD-instruktioner. DICE har en hel presentation om detta ämne: Culling the Battlefield: Data Oriented Design in Practice
Presentationen nämner också att snabbare avskaffas ännu mer med ett enkelt rutnät.
Eftersom jag antar att de flesta 3D / simulering / spelkodbaser redan har någon form av BVH-klass och jag vet inte hur kritiskt det är för dig att få BÄSTA avlivningsprestanda, jag vill presentera några argument för att hålla fast vid en BVH:
Beroende på vilken metod du använder, konstruerar en BVH kan vara snabb och enkel.
Min nuvarande implementering av en binär BVH (varje nod kan bara ha noll eller två barn och varje bladnod lagrar bara ett objekt) som är utformad för snabb -konstruktion tar cirka 0,18 ms för 1137 objekt på en enda tråd i en i7-5960X @ 3.89GHz . Jag är säker på att det kan gå snabbare. Konstruktion utförs utan att minnet omfördelas i processen (detta fördubblade konstruktionens prestanda).
Även om SAH kan generera den bästa BVH, tar det lång tid. SAH är bra för saker du kan förberäkna, som kollisionsmaskor. Vid körning kan du sedan sätta kollisionsmaskorna i en BVH som är mer lämpad för realtidsbyggande.
En snabb och enkel BVH-konstruktion (den jag ”m använder för närvarande) är att sortera alla objekt på en axel (till exempel den överordnade AABB: s längsta axel) och dela upp samlingen i mitten.
För att påskynda sakerna ännu mer, beräkna noden AABBs EFTER att trädet konstruerats, genom att kombinera de två barn-nod-AABB: erna för en föräldernod. Detta undviker iterering genom alla objekt (ytterligare 2x hastighet). Detta är dock bara möjligt om ditt delningskriterium inte är beroende av föräldrars AABB. / p>