PROJET : Interpolation de formes 3D (Octobre-Novembre 2002)

EA Géométrie et Synthèse d'Images - Francois Sillion

Description du projet:

Le but du projet consistait en la réalisation d'un algorithme fusionnant deux topologies 3D (par topologie on entend les connections entre un ensemble de points, de côtés, et de faces) en une seule. Cette dernière topologie unique pouvait être utilisée ensuite pour obtenir des résultats visuels, par exemple il devenait très simple de produire un "morphing" entre les deux objets originaux. La base du projet consiste à projeter les deux topologies originelles sur une sphère, ce qui permet de calculer et d'introduire des intersections entre les deux modèles. Une fois les intersections calculées, il faut alors recréer la nouvelle topologie en exploitant au maximum les informations contenues dans les anciennes topologies.

Techniques et Algorithmes utilisés:

L'algorithme général utilisé se base sur les papier de recherche "Establishing Correspondences by Topological Merging: A new approach to 3-D shape transformation", publié dans Graphics Interface '91, et surtout sur "Shape Transformation for Polyhedral Objects" paru dans Computer Graphics. Dans ce papier, l'algorithme principal se subdivise en 6 étapes, qui sont toutes très détaillées, à l'exception de la dernière, pourtant la plus compliquée. Implémenter les étapes 1 à 5 de l'algorithme ne relevait donc que de la programmation simple, mais l'étape 6 demandait une certaine réflexion et des choix stratégiques. Le problème est simple: il faut, alors que l'on a pour chaque ancien côté des deux modèles originaux, une liste d'intersections qui pointe vers des points( qui eux mêmes repointent sur des côtés), reproduire la topologie des faces et des côtés du nouveau modèle. Le cas des côtés est vite résolu: pour chaque ancien côté on aura n+1 nouveaux côtés où n est le nombre d'intersections de ce côté.

Par contre le cas des faces est beaucoup plus complexe. J'ai finalement opté pour une approche "par faces": on boucle sur les faces du modèle A en essayant de repérer certaines nouvelles faces, puis on fait de même sur les faces de B. Par exemple, on part du point numéro 1 d'une face de A: si on trouve sur un côté partant de 1, une intersection qui a un lien avec une intersection sur l'autre côté de la face partant de 1, alors on obtient une nouvelle face à 3 côtés. La difficulté consistait donc à répertorier tous les cas possibles pour l'obtention de nouvelles faces: cela peut en effet être des faces à 3, 4, 5, ou 6 côtés. Le déboguage était donc assez pénible car il fallait trouver des modèles exploitant "tous les cas de figure possibles" pour traquer tous les bugs. L'avantage est par contre que cette méthode est rapide (en temps machine), et est bien compréhensible visuellement. En procédant de cette manière, j'étais sûr d'aboutir à des résultats concrets et rapides.

La technique de projection sur la sphère utilisée était simplissime, puisqu'on se borne au cas des objets étoilés. Dans ces cas là on peut à partir d'un point bien défini normer tous simplement tous les points sur la sphère unité. La recherche d'algorithmes pour traiter de cas non triviaux serait une recherche passionnante en elle-même: se reporter au dernier paragraphe pour une ouverture sur le sujet.

Du point de vue technique, j'ai programmé en C (avec les outils standard GNU). Ce projet, outre de m'initier au C, m'a appris beaucoup de nouvelles techniques de programmation et surtout de déboguage et d'organisation, vu sa taille. Ainsi j'ai appris succesivement à utiliser une Makefile, et à utiliser des directives de compilation. Le résultat est qu'on peut compiler le code source avec deux options: la version normale et la version "pour déboguage" qui affiche de nombreuses lignes utiles pour localiser les bugs. Je pense que je ne serai pas venu à bout de la phase déboguage si je n'avais pas restructuré mon code en vu du déboguage.

Pour la visualisation finale des morphings, j'ai utilisé Geomview en compilant mon algorithme comme module externe. Rien à dire de particulier là-dessus: cela donne de très jolis résultats, qu'on peut voir dans le paragraphe suivant.

Résultats obtenus:

Les résultats obtenus sont assez impressionants visuellement, et j'aurai pu encore rajouter des effets esthétiques comme de la couleur (ce qui ne présente aucune difficulté technique). Vous pouvez télécharger le code source du programme ici:

Morph version 0.9.1 (archive tar)

Comment obtenir des résultats?

Tout d'abord compiler le programme en tapant "make" dans le répertoire du projet;
Puis renommer geomview_module en .geomview;
Puis lancer Geomview dans le répertoire courant;
Alors dans la fenêtre Geomview, dans les modules externes, on voit apparaitre "Morphing": il suffit de cliquer dessus.

Et voilà...

Ci-dessous la transformation d'une bouteille en étoile:

Comment paramétrer l'algorithme ?

Tout se fait au moyen du fichier config.morph. La syntaxe est un peu compliqué à décrire. Succinctement, on met le modèle A et le modèle B (noms des fichiers) comme premiers arguments de config.morph. Le reste des paramètres servent essentiellement à gérer la mémoire: normalement en laissant avec les valeurs de défaut, ca marche bien...

Dans le répertoire examples, il y a beaucoup de modèles d'objets étoilés: on peut s'amuser à morpher l'un sur l'autre, normalement ils marchent tous (enfin je n'ai pas testé toutes les combinaisons possibles). Au programme: tétraèdre, octaèdre, cube, dodécaèdre, isocaèdre, bouteille, étoile, et même ballon!

Alors? Reste t-il des bugs? Pourquoi une version 0.9.1 et pas 1.0 ?

Bonne question. A force de chasser les bugs, je pense qu'il n'en reste que très peu, mais sait-on jamais... Potentiellement les bugs sont de trois types: erreurs dans l'alogrithme correspondant à l'étape de reconstruction de la topologie, erreurs liées à l'utilisation de la mémoire, et ... erreurs numériques !!

A vrai dire, les bugs liés à la mémoire sont complètement inconnus car ceux-ci se produiraient en cas de nombre de points de l'ordre de 10, 000. Aucun de mes modèles ne fait autant de points. De plus ces problèmes ne sont pas très intéressants.

Les bugs liés à la "terrible étape 6" ont presque tous été éliminés. Presque; j'en ai laissé un, à la fois pour donner une idée au lecteur de ce qu'un bug à ce niveau de l'agorithme produit comme résultat visuel, et parce que vers la fin du projet, ayant bien compris ce stade de l'algorithme, jai préféré me concentrer sur d'autres aspects du sujet (mais d'après moi, il suffirait d'une ou deux heures de déboguage). Saurez vous le déceler? (indice: utiliser un morphisme avec le ballon !)

Par contre un problème beaucoup plus sérieux sur lequel je me suis penché en fin de projet concerne les erreurs numériques. Ce qui nous mène au dernier paragraphe...

Problèmes rencontrés, et évolutions futures

Je ne ferai pas ici une liste exhaustive des problèmes rencontrés: le déboguage fut ardu, et les petits bugs légions. Ceci fut très instructif pour moi mais n'intéressera pas beaucoup le lecteur (changer un i en j par exemple, n'a rien de passionnant: c'est la manière de déceler le bug qui est instructive). Citons quand même deux ou trois points qui m'ont frappé: il fallait penser éventuellement à "inverser" les intersections obtenues sur les edges du modèle A en fin d'étape 2; il fallait penser à traiter le cas des points n'ayant pas de côtés à intersections dans l'étape 3 (sinon on n'obtient pas la face correspondante (maptoa) ); il fallait faire attention à ne pas boucler avec les cas des faces à 4 côtés en étape 6, etc. Evidemment, il faudrait se plonger dans le code source pour comprendre ce jargon technique...

Conceptuellement (c'est à dire déboguage mis à part), quels sont les problèmes ?

Tout d'abord la méthode de projection. Celle-ci ne s'applique qu'à des objets étoilés. Une fois le projet abouti, j'ai comencé à réfléchir à d'autres méthodes de projection adaptées à des objets plus complexes. J'encourage le lecteur à y réfléchir aussi; quels sont les problèmes qui se posent, pour tel ou tel objet? Ma réflexion m'a permis d'aboutir à la conclusion qu'il est difficile de trouver un algorithme général! Les essais que j'ai tenté se basent sur un contrôle humain de la méthode de projection.

Mon deuxième axe de réflexion s'est axé sur les problèmes numériques. Ceci suite à la constatation suivante, qui m'a beaucoup choqué: essayez le morphisme ballon -> isocaèdre, en supprimant dans le fichier main.c le "bruit" ajouté au coordonnées des centres. On obtient avec des centres de coordonnées (0,0,0): Segmentation fault !! Et changez le centre en (0,0,2): tout marche parfaitement ! J'ai effectué un déboguage intensif de la segmentation fault: l'erreur vient bien d'un problème de calcul numérique. Ceci a lieu lors de l'étape 2 et provoque la défaillance du programme à l'étape 3 (ce qui est normal).

Ceci est choquant, pour plusieurs raisons. J'ai rapidement décidé d'ajouter du "bruit" lors de l'écriture du programme, pour éliminer les cas pathologiques. Par "bruit" j'entends une petite variation aléatoire des coordonnées de chaque point des modèles. Mais une fois ce bruit ajouté j'ai cru que tous les problèmes numériques étaient définitivement résolus. Il n'en est rien et c'est ca qui est passionnant... car il faut bien comprendre que normalement le bruit rajouté au coordonnées des points devrait suffire. En théorie le bruit rajouté au coordonnées des centres ne rajoute rien. Or si! Ce qui veut dire que dans l'état actuel des choses l'algorithme n'est pas fiable: il existe une probabilité très faible d'erreur à chaque éxécution. Et ceci même avec du bruit. Il existe des cas où les erreurs numériques feront échouer le programme, et cette probabilité -dont j'étais absolument persuadé qu'elle était nulle initialement- ne l'est pas comme le montre l'exemple précédent, qui, il faut le reconnaitre, m'a bouleversé.

Les erreurs numériques me paraissent donc une excellente ouverture du problème, celle qui m'intéresserait le plus, à vrai dire. Ce n'est qu'après avoir été confronté à ce problème que j'ai apprécié à leur juste valeur les remarques de l'article "Shape Transformation for Polyhedral Objects", p. 52: "basing the sort on this information avoids inconsistencies in the topology due to small numerical errors in the intersection calculations" ...

Jean-Noël Rivasseau (jean-noel.rivasseau@polytechnique.edu)