Introduction aux octrees



I) Qu'est ce qu'un octree ?

La réponse est contenue dans le nom : un octree c'est un arbre qui a 8 fils. Mais plus précisement ?
C'est une méthode de subdivision de l'espace, plutôt simple a mettre en oeuvre (surtout si on la compare a d'autre structure, tel le BSP) et qui peut aider a pas mal de chose .

Imaginez une grosse boite qui englobe tout vos polys (une bounding box, donc) . Cette boite est alignée aux axes (dans le jargon on appelle ca une AABB, pour Aligned Axis Bounding Box) . Alignés aux axes veut dire que ses arretes sont parrallèles aux axes (explication un peu bidon, mais je pense que vous avez compris ce que je veux dire ..).
Bien, nous avons cette boite. Maintenant, comptons le nombre de poly qui se trouve dedans. Si ce nombre de poly excède une certaine valeur (mettons 50), alors on coupe notre boite en 8 petites boites. Ces 8 boites seront les fils de la grosse boite. On recommence le processus sur ces 8 boites, jusqu'a avoir un nombre de poly inférieur à 50.

Résulats des courses : un bel arbre, chaque noeud a soit 8 fils ou aucun (une feuille). Dans chacun de ses noeuds nous avons une liste des faces qu'il contient, ce qui nous permettra de faire de beau tests dessus plus tard

Pseudo code pour la création de l'octree :

pour i de 0 à nombreDeFace faire
   si face[i] est inclu dans la boite courante
      inclure i dans la liste des faces contenus dans le noeud
      incrémenté nombre de face contenu   
   fsi
fpour

si nombre de faces contenu > valeur
   créer 8 fils pour le noeud courant
   recommencer avec chacun des 8 fils
fsi



2) comment savoir si un triangle est contenu dans une bounding box?


Bonne question, puisque c'est la le nerf de la guerre dans la construction de notre octree.
La, 2 cas de figure :

Que faire si un triangle se trouve dans plusieurs boites ? Vous avez le choix : soit vous le splittez, de facon a ce qu'un triangle n'appartiennent qu'a une boite, soit vous l'incluez dans toutes les boites auquelles il appartient. (méthode que j'ai adoptée, n'ayant pas spécialement vu l'interet de couper du triangle ..)



3) petits trucs pour la construction de l'octree

4) Que faire avec l'octree ?

Excellente question Marie-Louise. La finalité de l'octree est de degager le max de poly en peu de temps. Ca peut etre utile :


5) Sauvegarde et lecture d'un octree


Au cas vous ne veriez pas trop comment faire, voila une méthode fort simple, dans un style C (m'enfin le pourcentage de chance que ca compile du premier coup me semble avoisinner le 0 absolu)

structure d'un noeud :

struct _octree
{
  int nbFaceContenu;	//nombre de face contenues dans le noeud
  int *indiceFace;      //indice des faces contenues dans le noeud
  _octree *fils[8];     //fils potentiels . Si fils[0] == NULL alors pas de fils
}octree;


sauvegarde d'un noeud et de ses sous noeud :


void sauveNoeud( octree *noeud,FILE *out)
{
   //sauvegarde des infos du noeud : nombre de face 
   //et liste des indices
   fwrite(&noeud->nbFaceContenu,sizeof(int),1,out);
   fwrite(noeud->indiceFace,sizeof(int),noeud->nbFaceContenu,out);
 
   //on regarde si il y a un fils
   unsigned char aFils = 0;
   if (noeud->fils[0] != NULL)
      aFils = 1;
   
   fwrite(&aFils,sizeof(unsigned char),1,out);

   if (aFils==1)
   {
      for (int i=0;i<8;i++)
         sauveNoeud(noeud->fils[i],out);
   }
}


void litNoeud( octree *noeud,FILE *in)
{

   //lecture du nombre de face / indice de face contenues dans le noeud
   fread(&noeud->nbFaceContenu,sizeof(int),1,in);
   noeud->indiceFace = new int[noeud->nbFaceContenu];
   fwrite(noeud->indiceFace,sizeof(int),noeud->nbFaceContenu,in);
 
   //on regarde si il y a un fils
   unsigned char aFils
   fread(&aFils,sizeof(unsigned char),1,in);

   if (aFils==1)
   {
      for (int i=0;i<8;i++)
      {
         noeud->fils = new octree;
         litNoeud(noeud->fils[i],in);
      }
   }  
}



Vala j'ai dis ce que j'avais a dire sur le sujet ... Questions, commentaires, améliorations : chrisbk@ifrance.com