Hiérarchie des volumes englobants
Une hiérarchie de volumes englobants ( BVH ) est une structure arborescente sur un ensemble d'objets géométriques. Tous les objets géométriques, qui forment les nœuds et les feuilles de l'arbre, sont enveloppés dans des volumes englobants. Ces nœuds sont ensuite regroupés en plus petits ensembles et sont enfermés dans des volumes plus grands, dit englobants. Ceux-ci, à leur tour, sont également regroupés et enfermés dans d’autres volumes plus grands, ce qui aboutit finalement à une structure arborescente avec un seul volume englobant au sommet de l'arbre. Les hiérarchies de volumes englobants sont utilisées pour prendre en charge efficacement plusieurs opérations sur des ensembles d'objets géométriques, comme dans la détection de collisions et le traçage de rayons.
De surcroît, cette méthode simplifie les tests de collisions et entraîne des améliorations significatives des performances. En effet, un même nombre de tests par paires entre les volumes englobants sont toujours effectués. En organisant donc les volumes dans une hiérarchie de volumes englobants, la complexité temporelle (le nombre de tests effectués) peut être réduite à un nombre logarithmique d'objets. Avec une telle hiérarchie en place, lors des tests de collision, les volumes enfants n'ont pas besoin d'être examinés si leurs volumes parents ne sont pas intersectés (par exemple, si les volumes englobants de deux autos tamponneuses ne se croisent pas, les volumes englobants des pare-chocs eux-mêmes ne peuvent pas l'être. Il n'est donc pas nécessaire de vérifier la collision à cet échelle).
Problèmes de modélisation modifier
Le choix du volume englobant est déterminé par un compromis entre deux objectifs. D’une part, nous aimerions utiliser des volumes englobants qui ont une forme très simple. Ainsi, nous n’avons besoin que de quelques octets pour les stocker, et les tests d’intersection et les calculs de distance sont plus simples et rapides. D’un autre côté, nous aimerions avoir des volumes englobants qui correspondent très étroitement aux objets de données correspondants. L'un des volumes englobants les plus couramment utilisés est un cadre de délimitation minimum aligné sur l'axe . Le cadre de délimitation minimum aligné sur l'axe pour un ensemble donné d'objets de données est facile à calculer et ne nécessite que quelques octets de stockage. Des tests d'intersection robustes sont donc faciles à mettre en œuvre et extrêmement rapides.
Il existe plusieurs propriétés souhaitées pour une hiérarchie des volumes englobants qui doivent être prises en compte lors de sa conception pour une application spécifique [1]:
- Les nœuds contenus dans un sous-arbre donné doivent être proches les uns des autres. Plus l’arbre est bas, plus les nœuds doivent être proches les uns des autres.
- Chaque nœud de la hiérarchie doit avoir un volume minimum.
- La somme de tous les volumes englobants doit être minimale.
- Une plus grande attention devrait être accordée aux nœuds proches de la racine de la hiérarchie. L'élagage d'un nœud près de la racine de l'arbre supprime davantage d'objets.
- Le volume de chevauchement des nœuds frères doit être minime.
- La hiérarchie doit être équilibrée en ce qui concerne à la fois sa structure de nœuds et son contenu. L'équilibrage permet d'élaguer autant de hiérarchie que possible chaque fois qu'une branche n'est pas traversée.
En termes de structure de la hiérarchie, il faut décider quel degré (le nombre d’enfants) et quelle hauteur utiliser dans l’arbre la représentant. Un arbre de faible degré sera de plus grande hauteur. Cela augmente le temps de parcours de la racine à la feuille. D'un autre côté, moins de travail doit être dépensé sur chaque nœud visité pour vérifier le chevauchement de ses enfants. L’inverse est vrai pour un arbre de haut degré : même si l’arbre est de plus petite hauteur, plus de travail est consacré à chaque nœud. En pratique, les arbres binaires (degré = 2) sont de loin les plus courants. L’une des principales raisons est que les arbres binaires sont plus faciles à construire[2].
Construction modifier
Il existe en tout trois catégories de méthodes de construction d'arbres : les méthodes descendantes, ascendantes et par insertion.
Les méthodes descendantes procèdent en partitionnant l'ensemble d'entrées en deux (ou plus) sous-ensembles, puis en les délimitant dans un volume englobant. Ce procédé est ensuite répété en conservant le partitionnement (et la délimitation) de manière récursive jusqu'à ce que chaque sous-ensemble ne soit constitué que d'une seule primitive (les nœuds feuilles sont atteints). Les méthodes descendantes sont faciles à mettre en œuvre, rapides à construire et de loin les plus populaires, mais ne donnent pas généralement les meilleurs arbres possibles.
Les méthodes ascendantes commencent par l'ensemble d'entrées sous forme de feuilles de l'arbre, puis en regroupent deux (ou plus) pour former un nouveau nœud (interne). Procédez de la même manière jusqu'à ce que tout ait été regroupé sous un seul nœud (la racine de l'arbre). Les méthodes ascendantes sont plus difficiles à mettre en œuvre, mais elles sont susceptibles de produire de meilleurs arbres en général. Certaines études récentes [3] indiquent que dans un espace de faible dimension, la vitesse de construction peut être largement améliorée (ce qui correspond ou surpasse les approches descendantes) en triant les objets à l'aide d'une courbe de remplissage d'espace et en appliquant un regroupement approximatif basé sur cet ordre séquentiel.
Les méthodes descendantes et ascendantes sont considérées comme des méthodes off-line car elles nécessitent toutes deux que toutes les primitives soient disponibles avant le début de la construction. Les méthodes d'insertion construisent l'arborescence en insérant un objet à la fois, en commençant à partir d'une arborescence vide. L'emplacement d'insertion doit être choisi de manière à ce que l'arbre pousse le moins possible selon une mesure de coût. Les méthodes d'insertion sont considérées comme des méthodes on-line car elles ne nécessitent pas que toutes les primitives soient disponibles avant le début de la construction et permettent ainsi d'effectuer des mises à jour au moment de l'exécution.
Usage modifier
Les hiérarchies de volumes englobants sont souvent utilisés dans le ray tracing pour éliminer les candidats potentiels à l'intersection dans une scène en omettant les objets géométriques situés dans les volumes englobants qui ne sont pas coupés par le rayon actuel[4]. De plus, comme optimisation courante des performances, lorsque seule l'intersection la plus proche du rayon est intéressante, comme l'algorithme de traversée du lancer de rayons est des nœuds descendants et que plusieurs nœuds enfants croisent le rayon, l'algorithme de traversée considérera d'abord le volume le plus proche, et s'il trouve intersection là-bas, qui est définitivement plus proche que toute intersection possible dans le deuxième (ou autre) volume (c'est-à-dire que les volumes ne se chevauchent pas), il peut ignorer en toute sécurité le deuxième volume. Des optimisations similaires lors du parcours de l'arbre peuvent être utilisées lors de la descente dans les volumes enfants du deuxième volume, pour restreindre davantage l'espace de recherche et ainsi réduire le temps de parcours.
De plus, de nombreuses méthodes spécialisées ont été développées pour ces hiérarchies, en particulier celles basées sur AABB (axis-alignedbounding box), telles que la construction parallèle, la traversée accélérée SIMD, une bonne heuristique de division (SAH - l'heuristique de surface est souvent utilisée dans le ray tracing), des arbres larges (les arbres 4-aire et 16-aire offrent certains avantages en termes de performances, à la fois en termes de performances de construction et de requête pour des scènes pratiques) et une mise à jour rapide de la structure (dans les applications en temps réel, les objets peuvent se déplacer ou se déformer spatialement relativement lentement ou être immobiles, et la même hiérarchie peut être mis à jour pour rester valide sans effectuer une reconstruction complète à partir de zéro).
Les hiérarchies des volumes englobants prennent également naturellement en charge l'insertion et la suppression d'objets sans reconstruction complète, mais cette hiérarchie résultante a généralement des performances de requête inférieures à celles d'une reconstruction complète. Pour résoudre ces problèmes (ainsi que la mise à jour rapide de la structure n'est pas optimale), la nouvelle hiérarchie pourrait être construite de manière asynchrone en parallèle ou de manière synchrone, après détection de changements suffisants (le chevauchement des feuilles est important, le nombre d'insertions et de suppressions a dépassé le seuil, et d'autres heuristiques plus raffinées).
Les hiérarchies des volumes englobants peuvent également être combinées avec des méthodes de graphe de scène et d'instanciation géométrique, pour réduire l'utilisation de la mémoire, améliorer la mise à jour de la structure et les performances de reconstruction complète, ainsi que pour guider un meilleur fractionnement d'objets ou de primitives.
Voir également modifier
- Partitionnement de l'espace binaire, octree, arbre k -d
- Arbre R, arbre R+, arbre R* et arbre X
- M-arbre
- Balayer et tailler
- Classification hiérarchique
- Optix
Notes et références modifier
- Christer Ericson, Real-Time collision detection, Morgan Kaufmann, coll. « Morgan Kaufmann Series in Interactive 3-D Technology », , 236–7 p. (ISBN 1-55860-732-3), « §6.1 Hierarchy Design Issues »
- Ericson 2005, p. 238
- Yan Gu, Yong He, Kayvon Fatahalian et Guy Blelloch, HPG '13: Proceedings of the 5th High-Performance Graphics Conference, ACM, , 81–88 p. (ISBN 9781450321358, DOI 10.1145/2492045.2492054, S2CID 2585433, CiteSeerx 10.1.1.991.3441), « Efficient BVH Construction via Approximate Agglomerative Clustering »
- J. Günther, S. Popov, H.-P. Seidel et P. Slusallek, 2007 IEEE Symposium on Interactive Ray Tracing, IEEE, , 113–8 p. (ISBN 978-1-4244-1629-5, DOI 10.1109/RT.2007.4342598, S2CID 2840180, CiteSeerx 10.1.1.137.6692), « Realtime Ray Tracing on GPU with BVH-based Packet Traversal »
