Quand utiliser le partitionnement d'espace binaire, Quadtree, Octree?

Question

J'ai récemment découvert les arborescences de partitionnement d'espaces binaires et leur application aux graphiques 3D et à la détection de collision. J'ai aussi brièvement examiné des documents relatifs aux arbres quadrilatéraux et aux octrees. Quand utiliseriez-vous des quadtrees sur des arbres bsp ou vice versa? Sont-ils interchangeables? Je serais satisfait si j'avais assez d'informations pour remplir un tableau comme celui-ci:

            | BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

Que sont A, B et C?

Answer 1

Il n’ya pas de réponse claire à votre question. Cela dépend entièrement de l'organisation de vos données.

Quelque chose à garder à l'esprit:

Les arbres quadruples fonctionnent mieux pour des données essentiellement bidimensionnelles, telles que le rendu des cartes dans les systèmes de navigation. Dans ce cas, il est plus rapide que les octrees, car il s’adapte mieux à la géométrie et garde les structures de nœud petites.

Les octrees et les hiérarchies de volume limitant (BVH) sont avantageux si les données sont en trois dimensions. Cela fonctionne également très bien si vos entités géométriques sont regroupées dans un espace 3D. (voir Octree vs BVH .)

Oc- et Quadtrees présentent l’avantage de pouvoir cesser de générer des arbres à tout moment. Si vous souhaitez afficher des graphiques à l'aide d'un accélérateur graphique, il vous suffit de générer des arborescences au niveau de l'objet et d'envoyer chaque objet en un seul appel de dessin à l'API graphique. Cela fonctionne beaucoup mieux que d'envoyer des triangles individuels (ce que vous devez faire si vous utilisez pleinement BSP-Trees).

Les arbres BSP sont vraiment un cas particulier. Ils fonctionnent très bien en 2D et en 3D, mais générer de bons arbres BSP est une forme d'art en soi. Les arbres BSP ont l'inconvénient de devoir diviser votre géométrie en morceaux plus petits. Cela peut augmenter le nombre total de polygones de votre ensemble de données. Ils sont bien pour le rendu, mais ils sont beaucoup mieux pour la détection de collision et le lancer de rayons.

Une des propriétés intéressantes des arbres BSP est qu’ils décomposent une soupe de polygones en une structure qui peut être parfaitement restituée de haut en bas (et inversement) à partir de n’importe quelle position de la caméra sans effectuer de tri. L'ordre de chaque point de vue fait partie de la structure de données et est effectué lors de la compilation de l'arborescence BSP.

C’est d’ailleurs la raison pour laquelle ils étaient si populaires il ya 10 ans. Quake les utilisait parce que cela permettait au rastériseur logiciel / moteur graphique de ne pas utiliser un tampon z coûteux.

Tous les arbres mentionnés ne sont que des familles d’arbres. Il y a des octrees non fixés, des arbres hybrides kd-trees et bien d'autres structures connexes.

Answer 2

La principale différence pratique entre les arbres BSP et d'autres types d'arbres 3d réside dans le fait que les arbres BSP peuvent être plus optimaux, mais ne fonctionnent que sur des géométries statiques . Ceci est dû au fait que les arbres BSP sont généralement très lents à construire, prenant souvent des heures ou des jours pour un niveau de jeu urbain statique typique.

Les deux raisons principales pour lesquelles les arbres BSP ont besoin de plus de temps pour être construits sont (a) ils utilisent des plans de division non alignés, dont la recherche est plus longue, et (b) ils subdivisent la géométrie sur les limites des axes, garantissant ainsi qu'aucun objet ne se croise plans divisés.

D'autres types d'arbres 3d (octrees, quadruples, kd-tree, Bounding-Volume-Hierarchy) utilisent des volumes englobants alignés sur l'axe, et les volumes sont (facultativement) autorisés à se chevaucher; les objets contenus ne doivent donc pas nécessairement l'être couper sur les limites de volume. Cela rend les arbres moins optimaux que les arbres BSP, mais plus rapides à construire et plus faciles à modifier pour les objets dynamiques.

Extrapoler ces facteurs dans des situations ...

Les zones extérieures utilisent généralement des représentations du sol basées sur un champ de hauteur, soit de simples cartes de hauteur, soit des techniques plus complexes de mappage géographique telles que ROAM. Le sol lui-même ne participe pas au partitionnement de l'espace 3d, mais uniquement aux objets placés sur le sol.

Les mondes comportant de nombreuses occurrences de géométrie plus simple et similaire (maisons, arbres, astéroïdes, etc.) utiliseront souvent un arbre non BSP (tel qu'un BVH), car placer la géométrie dans un arbre BSP impliquerait une duplication. et scinder la géométrie de détail pour chaque instance.

Inversement, un grand maillage statique personnalisé sans instanciation, tel qu'une scène urbaine ou un environnement intérieur complexe, utilisera généralement un arbre BSP pour améliorer les performances d'exécution. Le fait que l'arborescence BSP divise la géométrie en limites de nœud est utile pour les performances de rendu, car les nœuds BSP peuvent être utilisés en tant que lots de rendu de triangle pré-organisés. L’arbre BSP peut également être optimisé pour l’occlusion, évitant ainsi de dessiner des parties de l’arbre BSP connues pour se trouver derrière une autre géométrie.

Voir aussi: Octree vs BVH , Didacticiel Limitation de la hiérarchie des volumes , Didacticiel BSP .

Answer 3

Un BSP convient parfaitement aux environnements urbains.

Un arbre à quatre est préférable lorsque vous utilisez une carte de hauteur pour un terrain, etc.

Un octree est préférable lorsque vous avez des amas de géométrie dans un espace 3D, tels qu'un système solaire.

Answer 4

Les BSP sont une bonne option pour accélérer la détection des collisions, selon le type de parfum que vous utilisez. Ils sont particulièrement rapides aux tests ponctuels et linéaires, un peu moins rapides et un peu plus compliqués pour les objets volumineux.

En ce qui concerne leur utilisation graphique, les BSP sont plutôt obsolètes. Les octrees fonctionnent bien pour des tâches telles que la sélection de visibilité brute, tout comme les arbres AABB.

Answer 5

Je n'ai pas beaucoup d'expérience avec les BSP, mais je peux dire que vous devriez utiliser des octrees sur des quadtrees lorsque la scène que vous rendez est grande. C'est-à-dire que la hauteur est supérieure à la moitié de la largeur et de la profondeur - une règle de base. Généralement, les octrees n'engendrent pas un coût énorme par rapport aux quadtrees et ils ont le potentiel d'accélérer les choses de manière décente. YMMV.

Answer 6

Habituellement, ces réponses ne sont pas claires. Je suggérerais que A, B et C sont le résultat d'une fonction de la taille de votre espace et de la quantité de choses que vous différenciez.

Answer 7

Un BSP est préférable pour un espace plus petit et plus simple dans lequel vous ne souhaitez effectuer qu'une occlusion. Si vous voulez toutes les intersections pour un rayon donné, vous devrez passer à un quadree / octree.

En ce qui concerne quadtree vs octree - combien de dimensions vous intéressent beaucoup? Deux dimensions signifient un quadtree, quatre un octree. Comme indiqué, quadtree peut fonctionner dans trois espaces, mais si vous voulez que chaque dimension soit traitée correctement, un octree est la voie à suivre.