Boîtes englobantes en octrees

J'ai vu que les octrees sont souvent utilisés pour des choses comme l'abattage du tronc et la détection de collision en 3D. Mais je ne sais pas du tout comment fonctionne l'algorithme. Certes, le principe entier de l'octree se casse lorsque vous essayez d'utiliser des boîtes englobantes, car toute boîte donnée peut être stockée dans un nœud mais chevauche en fait l'espace représenté par un autre nœud. De plus, je ne sais pas comment cela peut éventuellement fonctionner pour rechercher des boîtes englobantes plutôt que des points, car encore une fois, vous pourriez être bloqué en regardant pratiquement tous les nœuds, ce qui irait à l'encontre du but.

Alors, comment diable les octrois font-ils face aux boîtes englobantes?

Un Octree (3D) utilise les mêmes concepts qu'un Quadtree (2D). Si vous lisez et comprenez l'article de wikipedia sur Quadtrees, vous devriez pouvoir appliquer les mêmes concepts en 3D.

Ces deux arborescences vous permettent d'utiliser des recherches par zone qui peuvent réduire considérablement le nombre de comparaisons nécessaires pour déterminer quels objets se trouvent dans une certaine zone. Cela peut être utile pour l'abattage visuel, ou même pour les collisions, selon votre jeu.

Le concept de base est que l'espace-monde est divisé en "seaux": carrés pour 2D ou cubes pour 3D. Avec un monde vide, vous commencez avec un seul seau carré ou cube qui couvre le monde entier. Lorsque vous ajoutez des objets au monde, vous commencez au nœud racine et progressez dans l'arborescence en fonction de l'emplacement et de la taille de l'objet. Si le compartiment de destination atteint sa capacité, vous le subdivisez en divisant les carrés en 4 carrés plus petits (Quadtree) ou en divisant les cubes en 8 cubes plus petits (Octree). Chaque objet que vous ajoutez au monde est uniquement inséré aussi profondément dans l'arbre qu'il peut physiquement s'insérer complètement dans les limites du seau. Si un objet ne rentre pas dans les limites du compartiment actuel, vous devez déplacer l'objet vers le plus petit compartiment parent dans lequel il rentre complètement.

Notez que l'utilisation d'un Quadtree ou d'un Octree est exagérée si vous n'avez pas beaucoup d'objets dans votre monde. Il existe également des solutions open source pour les deux.

Les n-arbres sont le système de partitionnement spatial le plus connu mais pas le seul disponible. Il y en a beaucoup, beaucoup d'autres. Un peu plus d'informations sur les données dont vous disposez contribuerait grandement à trouver le meilleur choix. Vos boîtes changent-elles de taille ou se déplacent-elles? À quel point sont-ils gros? Combien y en a-t-il? Avez-vous beaucoup d'insertions / suppressions?