require("../global.php");
entete();
?>
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 :
- un des points du triangle est contenu dans la boite : le triangle est donc
dedans
- aucun des points composant le triangle est dans la boite : cela ne veut pas
dire que le triangle ne se trouve pas dedans (imaginez une petite boite et
un gros triangle ....) . On peut deja tester si le centre du triangle se
trouve dans la bounding box, auquel cas le triangle coupe bien la boite.
Si jamais ce n'est pas le cas, dernier recours : on va tester si une arrete
de l'AABB coupe le triangle ( pour un bout de code sur le test ray / triangle,
voir glvelocity.gamedev.net)
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
- Si vous avez bien compris comment marche un octree, vous en êtes arrivé a
une fine conclusion : lors de la construction des noeuds fils d'une boite,
pas la peine de retester toutes les faces : ne faire que celle contenue
dans le noeud père .
- Histoire de ne pas avoir de suprise, vous pouvez aussi spécifier une taille
minimale de boite : on ne subdivisera une boite que si sa taille est
supérieur a la taille minimale autorisée et que si son nombre de poly est
supérieur a une valeur (50 pour nous);
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 :
- test de visibilité
- Si une boite n'est pas visible, ses fils ne le seront pas, et les poly
contenus dedans non plus
- si une boite est completement visible, tous ses fils le seront : pas la
peine de tester plus, on affiche tous les polys contenus dans le noeud
- si une boite est partiellement visible, alors on fait le test sur chacun
de ses fils et on recommence le processus
- ray tracing / detectection de collision (on teste quels sont les boites
que le rayon coupe, et on ne teste que les poly contenus dans ces boites.
Pour le test Ray / AABB je vous conseille d'allez voir sur
www.realtimerendering.com
et de ramasser leur article sur le sujet)
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
PiedDePage(); ?>