Octree
Un octree est un arbre ou 8 branches partent de chaque noeuds.
On se limitera à une représentation ou les feuilles
ne peuvent ne prendre que 2 valeurs : 0 ou 1.
Dans un tel arbre on remplace systématiquement tous les noeuds contenant
8 feuilles avec une valeur identique par une feuille de cette valeur.
Une représentation graphique possible de l'octree est la suivante :
- Une feuille 0 ne s'affiche pas.
- Une feuille 1 affiche un cube unitaire (0,0,0) a (1,1,1)
- Un noeud affiche ses 8 branches en changeant le repère courant.
Si n est le numéro de la branche entre 0 et 7 inclus,
le repère subit une homothétie de 0.5 et est translaté en :
( n&1, (n&2)/2, (n&4)/4 ) / 2
(le symbole '&' est l'opérateur ET bit à bit du langage C).
Une représentation textuelle de l'octree peut être :
- '0' feuille 0 (vide)
- '1' feuille 1 (plein)
- '(' noeud
- ')' commentaire inutile
Représentation graphique de (100(01100000)(10000000)000)
Réalisez :
- L'affichage graphique de l'octree à
partir de sa définition
textuelle. On affichera les faces des cubes.
(Squelette : o_affiche_octree.c)
- L'intersection de deux octrees.
N'oubliez pas de remplacer les noeuds par des feuilles
si nécessaire.
(Squelette : o_inter_octree.c)
Pour ne pas perdre de temps en débuggage, faite des fonctions
résistante aux erreurs de codage : mauvais nombre
de feuilles pour un noeud, fin de chaîne de caractère
inopinée ou caractères inattendus.
Thierry EXCOFFIER
Last modified: Wed Nov 17 11:48:50 CET 1999