Aller au contenu principal

Octree

Un octree est une structure de données arborescente utilisé pour diviser l'espace tridimensionnel en sous-region plus petites.

Concept de base​

Un octree divise l'espace en cubes plus petits. Chaque noeuds de l'octree représente un cube dans l'espace 3D, et chaque noeud peut avoir 8 enfants, chacun représentant un sous-cube de l'espace parent.

Division de l'espace​

L'espace global, généralement un cube englobant l'ensemble du monde, est divisé de manière récursive en 8 sous-cubes égaux :

  • Le cube parent est divisé en 8 cubes enfants
  • Chaque enfant peut à son tour être divisé en 8 cubes encore plus petits, et ainsi de suite.

Construction de l'octree​

Voici les étapes pour construire un octree :

  • Définir le cube englobant : Commencer avec un cube qui englobe le monde.
  • Diviser le cube : Diviser ce cube en 8 sous-cube égaux.
  • Répéter récursivement :
    • Pour chaque sous-cube, vérifier s'il doit être divisé davantage. Cela dépend généralement d'un critère de complexité, comme le nombre d'objets dans un sous-cube.
    • Si le critère de subdivision est rempli, diviser ce sous cube en 8 nouveaux sous-cubes et répéter le processus.
    • Si le critère n'est pas rempli, le sous-cube devient une feuille de l'arbre.

Utilisation des octrees​

Les octree sont utilisés pour :

  • Stocker des objets spatiaux : Chaque noeud peut stocker des références aux objets qui ce trouvent dans son espace.
  • Recherche rapide : L'organisation hierarchique permet des recherches rapides de voisins ou d'objets à proximité.
  • Frustrum culling: en rendu 3D, les octrees permettent de déterminer rapidement quelles parties du monde sont visibles et doivent être rendu.

Avantages et Inconvénients​

Avantages​

  • Efficacité spaciale : Réduit le nombre de test nécessaire pour les collision, les recherches et les rendus.
  • Adaptabilités : Les octrees s'adaptent bien aux mondes où la densité des objets varie.

Inconvénients​

  • Complexité de mise en oeuvre : La construction et la gestion d'un octree peuvent être complexes.
  • Coût de maintenance : Insérer, supprimer ou déplacer des objets dans l'octree peut être coûteux en terme de calcul.