Ik “zou graag in realtime een grote populatie kleine onafhankelijk bewegende objecten willen weergeven. Ze kunnen zwermachtig bewegen, maar hun relatieve posities zullen niet coherent zijn – hun positie kan willekeurig veranderen binnen een zwerm en zwermen kunnen op elk moment uiteenvallen en hervormen.
Welke benadering voor het opbouwen van een grensvolumehiërarchie past het beste bij deze situatie? een manier om een hiërarchie te behouden die suboptimaal is, maar goed genoeg, waarvoor slechts een gedeeltelijke update van elk frame nodig is? Of is er een manier om vanaf het begin een hiërarchie op te bouwen die snel genoeg is voor vloeiende animaties?
Het aantal objecten zal te groot zijn om zonder hiërarchie weer te geven, maar om dezelfde reden verwacht ik dat het opbouwen van de hiërarchie tijdrovend zal zijn.
Naar aanleiding van de opmerking van John Calsbeek, als mijn focus op grensvolumehiërarchieën is misplaatst, en er is een betere aanpak voor het verdelen van ruimte voor deze situatie, alstublieft dienovereenkomstig beantwoorden. Ik “ben op zoek naar iets dat kan omgaan met wat ik beschrijf, inclusief alles waar ik niet aan heb gedacht.
Opmerkingen
- Beperk je opzettelijk de vraag naar het begrenzen van volumehiërarchieën, of sta je open voor andere vormen van ruimtelijke partitionering?
- @JohnCalsbeek die ik ‘ heb bewerkt om te verduidelijken – bedankt voor het wijzen op mijn onbedoelde beperking.
- Overweeg om een ” zwerm ” als een enkele eenheid te behandelen, wanneer zwermen samenkomen; voeg ze samen tot een enkele zwerm, wanneer een eenling te ver afdwaalt, wordt het een ” zwerm ” van één. Dit werkt het beste als de zwermen vaak samenhangend zijn en de eenlingen eerder zeldzaam zijn. Er zijn veel leuke manieren om te spelen met de ” zwerm is een enkele eenheid ” zoals leden toestaan om alleen van zwerm te wisselen wanneer ze zijn in contact met elkaar, de lijst gaat maar door.
Answer
Overweeg om spatial hashing te gebruiken, vooral als uw objecten dezelfde grootte hebben.
Verdeel uw wereld in principe in rastercellen van uniforme grootte (2D en 3D zijn beide geldige mogelijkheden, afhankelijk van de hoeveelheid verticale beweging). Wijs bij elke update uw object toe aan elke bak die het overlapt. Als de cellen een behoorlijke grootte hebben ten opzichte van de objecten, moeten de meeste objecten in één bak terechtkomen.
Elke bak wordt in een hashtabel ingevoegd, met als sleutel de coördinaten van de bak. (Je kunt het ook zien als een hashtabel met meerdere waarden voor dezelfde sleutel, en een object één keer invoegen voor elke cel die het overlapt.)
Er is geen hiërarchie om opnieuw op te bouwen in dit schema, waardoor het zeer geschikt is voor dynamische scènes. U kunt de afmetingen van de cel nog steeds op een grof niveau testen tegen de afgeknotte kegel of tegen occluders en veel objecten tegelijk weggooien. Het is ook gemakkelijker om deze structuur incrementeel te beheren: u kunt de hashtabel van frame tot frame hetzelfde houden en alleen objecten van de ene bin naar de andere verplaatsen wanneer ze de grens van een cel overschrijden.
Answer
Je zou kunnen proberen om de begrenzingsvolumes simpelweg een beetje groter te maken dan nodig is, zodat de objecten hun grenzen niet bij elke beweging overschrijden, maar nogmaals, je zou de structuur toch af en toe moeten herbouwen.
Of er is Grensintervalhiërarchie die precies dit probeert aan te pakken scenario.
Of het artikel van Ingo Wald, Solomon Boulos en Peter Shirley met de titel Ray Tracing Vervormbare scènes met behulp van dynamische grensvolumehiërarchieën zou kunnen zijn van belang.
Antwoord
Ik “zou hier wat praktisch perspectief aan willen toevoegen.
Laten voorwoord dat ik hier met beperkte informatie werk:
- Ik weet niet hoe m alle objecten waarmee u te maken heeft.
- Ik weet niet waar uw versnellingsstructuur precies voor wordt gebruikt. Frustum ruimen? Ray tracing? Botsingsdetectie tussen objecten in de BVH?
In de toekomst ga ik ervan uit dat je het hebt over het afgeknot ruimen van een paar duizend objecten.
Het aantal objecten zal te groot zijn om zonder hiërarchie weer te geven, maar om dezelfde reden verwacht ik dat het opbouwen van de hiërarchie tijdrovend zal zijn.
Ik zou zeggen dat als je elk object elk frame moet bezoeken om een BVH te berekenen, het direct en zonder BVH verwijderen eigenlijk sneller is. Dit hangt natuurlijk af van de implementatie van uw afgeknotte ruiming. De begrenzende volumes van alle objecten moeten aaneengesloten in het geheugen worden opgeslagen. Dit resulteert in een efficiënter gebruik van de CPU-cache en maakt verdere optimalisatie mogelijk met behulp van SIMD-instructies. DICE heeft een hele presentatie over dit onderwerp: Culling the Battlefield: Data Oriented Design in Practice
De presentatie noemt ook het versnellen van ruimen nog meer, met behulp van een eenvoudig raster.
Aangezien ik aanneem dat de meeste 3D- / simulatie- / spelcodebases al een soort van BVH-klasse en ik weten niet hoe cruciaal het voor u is om de BESTE ruimingsprestaties te krijgen, ik wil graag enkele argumenten aandragen om vast te houden aan een BVH:
Afhankelijk van welke methode u gebruikt, een BVH kan snel en eenvoudig zijn.
Mijn huidige implementatie van een binaire BVH (elk knooppunt kan slechts nul of twee onderliggende items hebben en elk bladknooppunt slaat slechts één item op) dat is ontworpen voor snelle constructie duurt ongeveer 0,18 ms voor 1137 objecten op een enkele thread van een i7-5960X @ 3,89 GHz . Ik weet zeker dat het sneller kan. De constructie wordt uitgevoerd zonder het geheugen opnieuw toe te wijzen in het proces (dit verdubbelde de constructieprestaties).
Hoewel SAH de beste BVH kan genereren, duurt het lang. SAH is goed voor dingen die u vooraf kunt berekenen, zoals botsingsmazen. Tijdens runtime kunt u de botsingsmazen vervolgens in een BVH plaatsen die geschikter is voor realtime constructie.
Een snelle en eenvoudige BVH-constructiebenadering (degene die ik “Ik gebruik momenteel) is om alle objecten op een as te sorteren (bijvoorbeeld de langste as van de bovenliggende AABB) en de verzameling in het midden te splitsen.
Om de zaken nog sneller te laten verlopen, berekent u de knoop AABBs NA het construeren van de boom, door de twee onderliggende knooppunten AABBs van een bovenliggende knoop te combineren. Dit vermijdt iteratie door alle objecten (nog een 2x versnelling). Dit is echter alleen mogelijk als uw splitsingscriterium niet afhankelijk is van de AABB van de ouder.