Compte Rendu Projet Image

Aujay Gregoire - Tournier Maxime

2005

    Le but de notre projet était d'écrire un programme permettant la voxelisation d'une scène polygonale d'après l'algorithme proposé par D. Haumont and N.Warzée en 2002 (site officiel par ici). Voxel signifie élément de volume (par analogie avec "pixel", picture element) et voxeliser un objet, trouver tous les voxels (des "petits cubes") se trouvant à l'intérieur de cet objet : on passe ainsi d'une représentation surfacique à une représentation volumique.

     Le point délicat d'une voxelisation est la détermination du statut des voxels : quelles sont les parties de l'espace qui se trouvent à l'intérieur des objets de ma scène et qu'elles sont celles qui sont l'extérieur ? Lorsque la surface est bruitée : avec des trous, des discontinuités, des normales mal orientées, des chevauchements...,  le travail est encore plus compliqué. L'algorithme que nous avons implémenté permet justement de voxeliser une scène en prenant en compte les trous et autres bruits de la surface.

-a-    L'espace va être est partitionné grâce à un Octree (arbre a 8 branches), véritable pierre d'angle de l'algorithme, il sera construit au fur et à mesure. La racine de cet Octree est le plus petit cube qui contienne toute la scène. On divise récursivement chaque cube (noeud de l'arbre) en 8 cubes jusqu'à obtenir un arbre de la profondeur souhaitée. A la fin, les feuilles de l'Octree qui correspondent à des voxels, contiendront toute l'information recherchée :

-b-    La premiere phase de l'algorithme consiste à trouver toutes les feuilles DISCARDED. Pour cela on se sert de la structure de départ : un AABB Tree que l'on nomme INPUT TREE. Il s'agit d'un arbre binaire dont les noeuds sont des boites englobantes (AABB : aligned axis bounding box) qui englobent leurs deux fils, et dont les feuilles contiennent les triangles de la scène, englobés dans ces boites. Afin de gagner du temps les tests de collisions se font avec les AABB ( test très rapide ) et seulement si nécessaire avec les triangles (test couteux même en utilisant l'algorihtme optimisé de Tomas Akenine-Möller)

-c-    Il faut ensuite déterminer le statut des autres cellules. Le principe utilisé est le suivant, on choisit d'abord une feuille dont on détermine le statut : INSIDE ou OUTSIDE. Cette cellule est appelée racine (seed) car elle sert de point de départ à la deuxième phase qui est la propagation de ce statut aux feuilles qui sont dans la même potion d'espace que la racine.

    On répète ceci jusqu'à ce que le statut de toutes les feuilles soit déterminé.

    Il ne faut pas choisir la racine au hasard car elle doit pouvoir se propager le plus possible aux autres feuilles. La racine est donc choisie la plus grande possible afin de voir un maximum de feuilles et donc de leur propager son statut. Si plusieurs feuilles ont la taille maximum, alors on choisit celle qui est le moins entourée par des feuilles dont le statut est déjà connu, on a là aussi plus de chance de propager le statut. On introduit un poids, plus une feuille contient d'information plus son poids est grand, il suffit alors de choisir la feuille dont la somme des poids des noeuds rencontrés en remontant jusqu'à la racine de l' Octree est la plus petite.
    Nous avons utilisé un décor pour chaque noeud de l'arbre. Celui-ci nous permet de trouver à chaque fois la meilleure racine ( le poids, et la plus petite distance à une feuille).

En cyan les feuilles qui ont été élues racines extérieures et en orange, les racines intérieures

    On utilise openGL pour déterminer le statut de la racine. Pour cela, on place la caméra au centre de la racine et on prend des "photos" de la scène en regardant dans chaque direction (haut, bas, gauche, haut,...). Ces six photos (CubeMap) vont nous permettre de déterminer le statut de la cellule. En effet si on pouvait afficher en rouge les triangles dont les normales sont dans le sens de la camera et en bleu ceux dont les normales sont vers la caméra, le tout en tenant compte de la profondeur alors une cellule à l'intérieur verrait du rouge et une cellule à l'extérieur du bleu.
    Et comme si c'était fait pour, cela est possible en openGL, c'est du face culling. On peut donc à partir des six photos estimer le statut de la racine.

    On peut dire :
- dès que je vois du rouge je suis INSIDE, c'est la stratégie que nous appellons NOHOLE, car elle ne peut donner de bons résultats que lorsque la surface n'a pas de trou. En effet si la surface à un trou, je v voir le triangle intérieur par ce trou et donc du rouge.

à gauche  :   un exemple sans trou bien traité   et   à droite   :  un modèle bruité donnant une incohérence

à gauche :   le même que ci-dessus, bien traité par la stratégie HOLES
à droite :   il reste des incohérences dûes à de gros défaut (ici beaucoup de normales sont à l'envers)

    3.1 Optimisations

    Afin d'optimiser le programme qui s'est avéré être très lent et très couteux en place mémoire, nous avons utilisé l'outil gprof qui permet de connaitre quels sont les appels les plus frequents et le plus couteux. De plus, nous nous sommes servi des optimisations que le compilateur nous offre (déroulement des boucles : gain de temps pour le parcours de l'arbre, car les boucles sont de taille fixe = 8 et options d'optimisation de code). Au final, nous avons amélioré la rapidité de l'ensemble des opérations par un facteur voisin de 15.

    L'utilisation des Display Lists d'OpenGL qui permet d'améliorer grandement la vitesse de rendu de l'InputTree, et avec elle celle des parties de propagation et de résolution du status. Chaque feuille de l'InputTree est associée à une Display List qui est appellée lors du trace.

    L'utilisation intensive du Frustum Culling dans toutes les operations de rendu. Cette technique permet de restreindre le parcours de l'InputTree aux branches qui sont effectivement dans le champ de vision, et d'ainsi de n'effectuer que le rendu de ce qui est visible. Cette technique est également utilisée lors de la propagation : seules sont parcourues les branches de l'Octree visibles depuis la seed courante. Le gain de temps lors du rendu est tres important.

    Un point important qui n'est pas soulevé dans la description de l'algorithme concerne les feuilles qui n'ont pas pu devenir racine. Il se peut qu'à la fin leur statut ne soit pas encore déterminé. En effet, si elle est déclarée racine invalide, elle ne pourra jamais l'être et si elle n'est pas vue par assez de feuilles d'un même type, à cause du terme de confiance de propagation.

à gauche :    sans notre amélioration        à droite  :     avec notre amélioration on élimine les feuilles violettes parasites

Nous avons également pensé à une technique de propagation de proche en proche : une fois qu'une cellule a acquis son status, il peut etre intéressant de propager son status immédiatement aux cellules avoisinantes, sans se servir d'OpenGL. Cependant cette technique comporte de nombreux inconvénients :

La fenêtre principale où l'on affiche les modèles dans un QGLViewer. Elle permet de changer de mesh et de sauvegarder les Octrees calculés.



La fenêtre "param" qui permet de régler les paramètres donnés au programme et de lancer les calculs.
La fenêtre "display" qui permet de régler l'affichage des résultats qui se font dans la fenêtre principale.
La fenêtre rendu dans laquelle se trouve un QGLWidget et qui affiche les rendus lors du solveStatus et du propagateStatus.

Processeur Athlon 1,4GHz
~750Mo de memoire vive
Carte video NVidia GeForce3
Noyau Linux 2.4.27

                                

           

                  

	Prof. 6	Prof. 7	Prof. 8	Prof. 9	Prof. 10
Creation				38
Solving status				610
Propagation				546

Nous obtenons un temps bien meilleur que celui annoncé sur le papier, mais avec une machine un peu plus puissante.

    Cet algorithme c'est avéré être très robuste, nous avons eu d'excellents résultats même sur des formes très bruitées. Cependant dès que nous augmentons la profondeur de l'Octree, le coût en temps croît énormément, ce qui en fait un algorithme très lent. Il existe des algorithmes beaucoup plus rapide mais qui ne donne pas un aussi bon résultat dans autant de cas que celui-ci. Il faudra choisir l'algorithme qui correspond au du but visé, il n'existe surement pas d'algorithme miracle !

    Lors de ce projet, nous avons perdu un peu (beaucoup) de temps à régler des problèmes dûs à openGL mais cela nous a permis, en mettant les mains dans le camboui, de mieux comprendre le fonctionnement de ce précieux outil.