Compte Rendu Projet Image

Voxelisation d'une Scene Polygonale


sg



Aujay Gregoire - Tournier Maxime

2005


   

Sommaire
  1. Introduction
  2. Description de l'algorithme et résultats
  3. Ameliorations et modifications
  4. A propos du programme
  5. Performances
  6. Bilan critique - Conclusion


1. Introduction



    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.

Les interêts d'une telle représentation sont :

     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.

Tuteur de Projet : Franck Hetroy

Outils utilisés :



[retour sommaire]



2. Description de l'algorithme et résultats


-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 :
Les sous arbres dont toutes les feuilles ont le même statut seront supprimés et remplacés par leur racine qui deviendra une feuille (correspondant donc à une portion d'espace plus grand) portant le statut correspondant. L'Octree n'est pas complet on gagne ainsi en place mémoire et en temps d'exécution pour la suite.



-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)

    Ces cellules sont rejetées (discarded) car elles ne peuvent pas être prises en compte par la suite de l'algorithme elles sont vraissemblablement à la fois à l'intérieur et à l'extérieur d'un objet.

inputtreefemur6femur8
De gauche à droite : un fémur dans son INPUT TREE (profondeur 5) puis les feuilles DISCARDED (profondeur 6 et 8)




-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é.




    2.1 Choix de la racine : seedChoice

    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).
   
racine dinotorus

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






    2.2 Trouver le statut de la racine : solveStatus

    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.
    snake seed            dino seed
à gauche  :   un exemple sans trou bien traité   et   à droite   :  un modèle bruité donnant une incohérence





- ou dès que je vois un certain nombre de pixels rouges sur l'ensemble des 6 "photos" alors je suis INSIDE. On peut ainsi quand même avoir le bon résultat pour des surfaces qui ne sont pas parfaites. Pour des modèles peu bruités, on fixera ce paramètre à environ 80 % du nombre total de pixels et pour ceux qui sont très abîmés, 25 % donne des résultats souvent corrects. Il s'agit de la stratégie que nous nommons HOLES.
dino seedgratte
à 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)






- on ne propage que si la feuille à un statut défini de façon assez sûre. On évite ainsi de propager une information dont on est pas certain. On introduit alors un terme de confiance qui est égal au nombre de faces sur lesquelles ont voit un nombre donné de pixels rouges. On décide alors qu'une cellule ne peut être INSIDE qui si son terme de confiance est supérieur ou égal à 4 et elle ne peut être OUTSIDE que si il est nul. 

    chevalcheval
Un modèle très bruité bien traité par l'algorithme (profondeur 7)





    2.2 Propager le statut de la racine : propagateStatus

    openGL va là encore nous être utile. En effet, comme pour le solveStatus, on va prendre des "photos" sur chacune des faces de la racine qui a été retenue mais on s'interesse cette fois au buffer de profondeur (depth buffer). Connaissant celui-ci on peut propager le statut aux cellules qui sont dans le champ de vision de la racine et qui ne sont pas cachées par les objets de la scène.

proapage1propage2
En fil de fer bleu, les cellules qui ont reçu le statut OUSTIDE de la racine après propagation dans une direction (vers les z>0).



    Afin d'éviter de marquer des feuilles d'après une racine dont le statut est incorrect, on introduit un terme de confiance de propagation. Ainsi une feuille ne reçoit pas son statut qu'après avoir été vu par plusieurs racines du même statut.
   
   Ci-dessous une racine n'a pas propagé son statut erroné, grâce au terme de confiance de propagation : les feuilles voisines ont été vues qu'une seule fois par la racine orange et plusieurs fois par les bleues.
dino seed
Le terme de confiance permet de rattrapper les erreurs du seedSolve.


    L'algorithme s'arrête lorsque l'on connait le statut de toutes les feuilles.



[retour sommaire]



3. Ameliorations et modifications


    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.


     En ce qui concerne les améliorations que nous avons apporté, il y a :
    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.

    La combinaison de ces deux optimisations nous ont permis de réduire significativement les durées de rendus (de plusieurs minutes à quelques secondes, dans certains cas).

    Le décor de l'arbre se fait au fur et à mesure que l'on trouve le statut des feuilles, on évite ainsi de parcourir tout l'Octree avant chaque choix de racine ce qui serait couteux ( O(8^n+1) où n est la profondeur).


    3.2 Eclairages de points obscurs

    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.
    Nous avons donc décidé d'essayer d'éliminer ce manque d'information.
On procède ainsi : on regarde si la feuille a été vue par plus de INSIDE que de OUTSIDE, si oui elle acquiert le statut correspondant.
(non codé :)  Et si jamais elle a été vue par autant de feuilles de chaque sorte alors on regarde le statut des fils de son père.
Et si après cela le statut est indéfini : pas de chance !

zeaxch
à 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 :
En résumé, et contrairement à ce que nous pensions au premier abord, cette technique ne presente pas de reel intérêt dans le cadre de ce problème. Peut-être en mettant en place un terme d'atténuation : une feuille proche de la racine recevrait plus d'information qu'une feuille éloignée....

Il nous parait possible de paralleliser cet algorithme en subdivisant la scène puis en recoupant les informations, ou en répartissant les directions de propagation, etc.


[retour sommaire]

4. A propos du programme

Le programme se compose de 4 fenêtres :
shs

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.

vdwdwgqrgh

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.

Il reste quelques problèmes d'interface, des boutons qui ne s'enfoncent pas quand il faut, etc.



[retour sommaire]



5. Performances


Les tests ci-dessous ont ete effectues sur une machine dont les caracteristiques sont les suivantes:

Processeur Athlon 1,4GHz
~750Mo de memoire vive
Carte video NVidia GeForce3
Noyau Linux 2.4.27
  
Les durees sont exprimees en secondes.



Mesh dino.txt, 47 904 triangles:

dino1.png                   dino1_vox.png              

Prof. 6
Prof. 7
Prof. 8
Prof. 9
Prof. 10
Creation 0
2
5
19
69
Solving status 2
3
4
8
16
Propagation
2
3
10
40
183




Mesh bones.txt, 4 204 triangles:

bones1.png            bones1_vox.png

Prof. 6
Prof. 7
Prof. 8
Prof. 9
Prof. 10
Creation 0
0
1
6
23
Solving status 0
2
8
5
93
Propagation
1
4
18
79
471

La propagation demande un temps important car la géométrie de la forme ne permet pas une propagation efficace : beaucoup de parties cachées les unes par rapport aux autres.

Mesh buddha-original.txt, 1 087 716 triangles:


buddha1.png                    buddha1_vox.png



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.


[retour sommaire]


6. Bilan critique - Conclusion

    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.

[retour sommaire]


Dernière version: Vendredi 17 Juin 2005