Vorrei essere in grado di visualizzare in tempo reale una vasta popolazione di piccoli oggetti in movimento indipendente. Possono muoversi in modo simile a uno sciame, ma le loro posizioni relative non saranno coerenti: la loro posizione potrebbe cambiare arbitrariamente allinterno di uno sciame e gli sciami potrebbero rompersi e riformarsi in qualsiasi momento.
Quale approccio alla costruzione di una gerarchia di volume limite si adatterebbe meglio a questa situazione? un modo per mantenere una gerarchia non ottimale ma abbastanza buona, che richiede solo un aggiornamento parziale di ogni fotogramma? O cè un modo per costruire una gerarchia da zero ogni fotogramma che sia abbastanza veloce per unanimazione fluida?
Il numero di oggetti sarà troppo grande per il rendering senza una gerarchia, ma per lo stesso motivo mi aspetto che la costruzione della gerarchia richieda molto tempo.
Dopo il commento di John Calsbeek, se il mio concentrarsi sul delimitare le gerarchie di volumi è fuorviante e per questa situazione esiste un approccio migliore per la suddivisione dello spazio, per favore rispondere di conseguenza. Sto cercando qualcosa che possa gestire ciò che descrivo, incluso qualsiasi cosa a cui non ho pensato.
Commenti
- Stai intenzionalmente limitando la domanda sul delimitare le gerarchie di volumi o sei aperto ad altre forme di partizionamento spaziale?
- @JohnCalsbeek I ‘ ho modificato per chiarire – grazie per aver sottolineato il mio restrizione involontaria.
- Considera lidea di trattare uno ” sciame ” come una singola unità, quando gli sciami si fondono; uniscili in un unico sciame, quando un solitario si allontana troppo lontano, diventa uno ” sciame ” di uno solo. Funziona meglio se gli sciami tendono ad essere coesi e i solitari tendono ad essere rari. Ci sono molti modi chiari per giocare con lo ” sciame è una singola unità ” come consentire ai membri di cambiare sciami solo quando lo sono in contatto luno con laltro, lelenco potrebbe continuare allinfinito.
Risposta
Prendi in considerazione lutilizzo di hashing spaziale, in particolare se i tuoi oggetti hanno dimensioni simili.
Fondamentalmente, dividi il tuo mondo in celle della griglia di dimensioni uniformi (2D e 3D sono entrambe possibilità valide a seconda della quantità di movimento verticale). Ad ogni aggiornamento, assegna il tuo oggetto a ogni contenitore che si sovrappone: se le celle sono di dimensioni adeguate rispetto agli oggetti, la maggior parte degli oggetti dovrebbe finire in un unico contenitore.
Ogni contenitore viene inserito in una tabella hash, con la chiave che sono le coordinate del cestino. (Puoi anche pensarla come una tabella hash con più valori per la stessa chiave e inserire un oggetto una volta per ogni cella che si sovrappone.)
Non cè nessuna gerarchia da ricostruire in questo schema, il che lo rende adatto per scene dinamiche.Puoi ancora testare le dimensioni della cella contro il tronco o contro gli occlusori a un livello grossolano e scartare molti oggetti contemporaneamente. Inoltre, è più facile gestire questa struttura in modo incrementale: puoi mantenere la stessa tabella hash da un fotogramma allaltro e spostare gli oggetti da un contenitore allaltro solo quando attraversano il confine di una cella.
Risposta
Potresti semplicemente provare a rendere i volumi di delimitazione un po più grandi del necessario in modo che gli oggetti non attraversino i loro confini ad ogni mossa, ma poi di nuovo, dovresti comunque ricostruire la struttura di tanto in tanto.
Oppure, esiste una gerarchia degli intervalli di delimitazione che cerca di affrontare esattamente questo scenario.
Oppure, larticolo di Ingo Wald, Solomon Boulos e Peter Shirley intitolato Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies potrebbe essere di interesse.
Risposta
Vorrei aggiungere una prospettiva pratica a questo.
Lascia premetto che sto operando su informazioni limitate qui:
- Non so come m qualsiasi oggetto con cui hai a che fare.
- Non so per cosa viene usata esattamente la tua struttura di accelerazione. Abbattimento del tronco? Ray tracing? Rilevamento di collisioni tra oggetti nel BVH?
Andando avanti, presumo che tu stia parlando di troncare che elimina alcune migliaia di oggetti.
Il numero di oggetti sarà troppo grande per il rendering senza una gerarchia, ma per lo stesso motivo mi aspetto che la creazione della gerarchia richieda molto tempo.
Direi che se devi visitare ogni oggetto ogni frame per calcolare un BVH, selezionarli direttamente e senza BVH è effettivamente più veloce. Questo ovviamente dipende dallimplementazione dellabbattimento del tronco. I volumi di delimitazione di tutti gli oggetti devono essere archiviati in modo contiguo in memoria. Ciò si traduce in un utilizzo più efficiente della cache della CPU e consente unulteriore ottimizzazione utilizzando le istruzioni SIMD. DICE ha unintera presentazione su questo argomento: Culling the Battlefield: Data Oriented Design in Practice
La presentazione menziona anche laccelerazione delleliminazione ancora di più, utilizzando una semplice griglia.
Dal momento che presumo che la maggior parte delle basi di codice di gioco / simulazione / 3D abbia già BVH class e non so quanto sia fondamentale per te ottenere le MIGLIORI prestazioni di abbattimento, mi piacerebbe presentare alcuni argomenti per attenersi a un BVH:
A seconda del metodo che usi, costruzione un BVH può essere veloce e semplice.
La mia attuale implementazione di un BVH binario (ogni nodo può avere solo zero o due figli e ogni nodo foglia memorizza solo un elemento) progettato per richiede circa 0,18 ms per 1137 oggetti su un singolo thread di un i7-5960X a 3,89 GHz . Sono sicuro che può essere più veloce. La costruzione viene eseguita senza riallocare la memoria nel processo (questo ha raddoppiato le prestazioni di costruzione).
Sebbene SAH possa generare il miglior BVH, ci vuole molto tempo. SAH è buono per cose che puoi precalcolare, come le mesh di collisione. In fase di esecuzione puoi quindi inserire le mesh di collisione in un BVH più adatto per la costruzione in tempo reale.
Un approccio di costruzione BVH semplice e veloce (quello I “sto usando attualmente) è ordinare tutti gli oggetti su un asse (ad esempio lasse più lungo del genitore AABB) e dividere la raccolta al centro.
Per velocizzare ulteriormente le cose, calcola gli AABB del nodo DOPO aver costruito lalbero, combinando i due nodi figlio AABB di un nodo genitore. Ciò evita di iterare attraverso tutti gli oggetti (un altro 2x speedup). Questo però è possibile solo se il tuo criterio di divisione non si basa sullAABB genitore.