Jaimerais être en mesure de rendre en temps réel une grande population de petits objets se déplaçant indépendamment. Ils peuvent se déplacer comme un essaim, mais leurs positions relatives ne seront pas cohérentes – leur position peut changer arbitrairement au sein dun essaim et les essaims peuvent se désagréger et se reformer à tout moment.
Quelle approche pour construire une hiérarchie de volumes englobants conviendrait le mieux à cette situation? un moyen de maintenir une hiérarchie qui est sous-optimale mais suffisamment bonne, qui ne nécessite quune mise à jour partielle de chaque image? Ou y a-t-il un moyen de construire une hiérarchie à partir de zéro chaque image qui est assez rapide pour une animation fluide?
Le nombre dobjets sera trop grand pour être rendu sans hiérarchie, mais pour la même raison, je pense que la construction de la hiérarchie prendra du temps.
Suite au commentaire de John Calsbeek, si mon se concentrer sur la délimitation des hiérarchies de volumes est erroné, et il existe une meilleure approche de partitionnement de lespace pour cette situation, veuillez répondez en conséquence. Je « cherche quelque chose qui puisse traiter ce que je décris, y compris tout ce à quoi je nai pas pensé.
Commentaires
- Êtes-vous intentionnellement restrictif la question aux hiérarchies de volumes de délimitation, ou êtes-vous ouvert à dautres formes de partitionnement spatial?
- @JohnCalsbeek Jai ‘ modifié pour clarifier – merci davoir signalé mon restriction par inadvertance.
- Envisagez de traiter un » essaim » comme une seule unité, lorsque les essaims fusionnent; fusionnez-les en un seul essaim, quand un solitaire ségare trop loin, il devient un » essaim » dun. Cela fonctionne mieux si les essaims ont tendance à être cohérents et les solitaires ont tendance à être rares. Il existe de nombreuses façons intéressantes de jouer avec » une seule unité « , comme permettre aux membres de changer d’essaim uniquement quand ils le sont en contact les uns avec les autres, la liste sallonge encore et encore.
Réponse
Pensez à utiliser le hachage spatial, en particulier si vos objets sont de taille similaire.
En gros, divisez votre monde en cellules de grille de taille uniforme (2D et 3D sont toutes deux des possibilités valables en fonction de la quantité de mouvement vertical). À chaque mise à jour, attribuez votre objet à chaque chutier quil chevauche – si les cellules sont de taille décente par rapport aux objets, la plupart des objets doivent se retrouver dans un seul chutier.
Chaque chutier est inséré dans une table de hachage avec la clé étant les coordonnées du bac. (Vous pouvez également le considérer comme une table de hachage avec plusieurs valeurs pour la même clé et insérer un objet une fois pour chaque cellule quil chevauche.)
Il ny a pas de hiérarchie à reconstruire dans ce schéma, ce qui le rend bien adapté pour les scènes dynamiques. Vous pouvez toujours tester les dimensions de la cellule contre le tronc ou contre des occluseurs à un niveau grossier et jeter de nombreux objets à la fois. En outre, il est plus facile de gérer cette structure de manière incrémentielle: vous pouvez conserver la même table de hachage d’une image à l’autre et ne déplacer les objets d’un bac à l’autre que lorsquils franchissent la limite d’une cellule.
Réponse
Vous pouvez simplement essayer de rendre les volumes de délimitation un peu plus grands que nécessaire pour que les objets ne franchissent pas leurs limites à chaque mouvement, mais encore une fois, vous devrez de toute façon reconstruire la structure de temps en temps.
Ou, il y a Hiérarchie dintervalles de délimitation qui essaie de résoudre précisément cela
Ou, larticle dIngo Wald, Solomon Boulos et Peter Shirley intitulé Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies pourrait être dintérêt.
Réponse
Je « voudrais ajouter une perspective pratique à cela.
Laissez me préface que jopère sur des informations limitées ici:
- Je ne sais pas comment m tous les objets avec lesquels vous avez affaire.
- Je ne sais pas à quoi sert exactement votre structure d’accélération. Abattage de Frustum? Tracé laser? Détection de collision entre des objets dans le BVH?
À lavenir, je vais supposer que vous parlez de labattage de quelques milliers dobjets.
Le nombre dobjets sera trop grand pour être rendu sans hiérarchie, mais pour la même raison, je pense que la construction de la hiérarchie prendra du temps.
Je dirais que si vous devez visiter chaque objet chaque image pour calculer un BVH, les éliminer directement et sans BVH est en fait plus rapide. Cela dépend bien sûr de votre implémentation dabattage frustum. Les volumes englobants de tous les objets doivent être stockés de manière contiguë dans la mémoire. Cela se traduit par une utilisation plus efficace du cache CPU et permet une optimisation supplémentaire à laide des instructions SIMD. DICE propose une présentation complète sur ce sujet: Culling the Battlefield: Data Oriented Design in Practice
La présentation mentionne également laccélération de labattage encore plus, en utilisant une simple grille.
Puisque je suppose que la plupart des bases de code 3D / simulation / jeu ont déjà une sorte de BVH et je ne sais pas à quel point il est essentiel pour vous d’obtenir les MEILLEURES performances d’abattage, je voudrais présenter quelques arguments pour vous en tenir à un BVH:
En fonction de la méthode que vous utilisez, la construction un BVH peut être rapide et simple.
Mon implémentation actuelle dun BVH binaire (chaque nœud ne peut avoir que zéro ou deux enfants et chaque nœud feuille ne stocke quun seul élément) qui est conçu pour prend environ 0,18 ms pour 1137 objets sur un seul thread dun i7-5960X à 3,89 GHz . Je suis sûr que cela peut être plus rapide. La construction est effectuée sans réallouer de la mémoire dans le processus (cela a doublé les performances de construction).
Bien que SAH puisse générer le meilleur BVH, cela prend beaucoup de temps. SAH est bien pour des choses que vous pouvez précalculer, comme les maillages de collision. Au moment de lexécution, vous pouvez ensuite placer les maillages de collision dans un BVH plus adapté à la construction en temps réel.
Une approche de construction BVH rapide et simple (celle que je « m utilisé actuellement) consiste à trier tous les objets sur un axe (par exemple laxe le plus long de lAABB parent) et à diviser la collection au milieu.
Pour accélérer encore plus les choses, calculez le nœud AABBs APRÈS avoir construit larborescence, en combinant les deux AABB des nœuds enfants dun nœud parent. Cela évite de parcourir tous les objets (une autre accélération 2x). Ceci nest toutefois possible que si votre critère de fractionnement ne repose pas sur lAABB du parent.