Majeure "Mathématiques et Informatique"  Enseignement d'approfondissement  "Images: Analyse et Synthèse"

Description du projet

    Les techniques d'interpolation sont aujourd'hui très répandues dans l'industrie cinématographique. Ces techniques de "morphing" consistent à transformer une image 2D en une autre image 2D de façon continue. Ici, on interpolera un modèle 3D en un autre modèle 3D, indépendamment de la technique de projection 3D-->2D pour obtenir l'image. Les modèles 3D seront représentés pas des maillages que l'on aura triangulé. Mais comme un dessin vaut mieux qu'un long discours, voici un petit exemple.

    La technique de base utilisée ici se limite à des objets simplement connexe, c'est à dire ne comportant pas de "trous". Ainsi, un cube, une sphère, une vache ou un verre conviendront, mais pas un tore. Il s'agit de créer une "topologie" commune aux deux modèles à partir des maillages initiaux, afin de réaliser un homéomorphisme d'un modèle vers l'autre.  On cherchera en fait à représenter les points du modèle A sur le modèle B et réciproquement. Un triangulation nous donnera alors la topologie commune aux deux modèles. Pour cela, on réalisera un homéomorphisme de chaque modèle sur la sphère unité que l'on appelera par la suite projection. Peut importe la méthode de projection tant qu'elle conserve la topologie du modèle initial, c'est à dire qu'elle réalise un homéomorphisme. Ces bases étant posées, voyons donc les différentes étapes de l'interpolation :

• Lecture des deux modèles
• Projection de chaque modèle sur la sphère unité
• Algorithme de fusion des deux maillages
• Triangulation de ce nouveau maillage (certains points peuvent ne pas rester coplanaires lors de l'interpolation)
• Interpolation linéaire entre les deux nouveaux modèles.


Ce traitement transformera alors deux modèles A et B en A' et B'

A :   A' :    B :  B': 

    Allez un dernier petit gif animé pour le plaisir ...

  ...avant de passer aux choses sérieuses !

Algorithmes utilisés

    Structures utilisées :

• Ap et Bp sont les modèles projetés de A et B sur la sphère
• V, E, F sont des tableaux contenant les points du modèle Ap et du modèle Bp, leurs arêtes et leurs faces
• MapToOpposite est un tableau. Si v appartient à Ap, alors MapToOpposite[v] est la face (portion de sphère) de Bp qui contient v.
• fb est la face de B où l'on place la focalisation
• WL est la liste des arêtes de Ap dont il faut encore chercher les intersections
• CL est la liste des arêtes de Bp qui peuvent intersecter l'arête de Ap en cours de test
• Chaque vertex pointe sur la liste des arêtes qui partent de ce point
• Une arête pointe sur ses extrémités (orientées) et les faces qui l'entourent
• Une face pointe sur ses arêtes et ses vertex
• Une intersection pointe sur les deux arêtes qui la créent

Algorithme de projection :

    J'ai réalisé deux niveaux de projection : un très simple, simpliste même, et un autre un peu plus efficace, mais moins naturel, et moins direct.

    La première projection se contente de normer les vertex par rapport au centre de projection choisi judicieusement. Bien entendu, cela nous limite pour l'utilisation à des objets étoilés, mais a l'avantage de donner un résultat très rapide et proche de ce qu'on cherche intuitivement, car cette méthode s'adapte particulièrement à l'idée que l'on a d'un morphing 3D pour ce type d'objet, et l'on devrait se resteindre à cette méthode pour les objets étoilés. Comparez le résultat de cette projection avec celui créé par l'autre projection.

Avant la fusion	Après la fusion

    La deuxième méthode de projection répond à un but différent de la première : être capable de donner un maillage sphérique à tout objet simplement connexe. Il faut une méthode qui conserve un peu les proportions et qui remplit uniformément la sphère. On ne s'intéressera absolument pas à ce que la méthode couvre naturellement la sphère : peu importe que la forme sur la sphère reflète la forme non projetée, ce qui compte, c'est qu'elle ait la même topologie, et qu'on soit capable de faire les appariements que l'on désire.

    On distingue donc deux étapes :

1.     projection sur la sphère
2.     mise en correspondance et transformation de la projection  pour aligner les vertex qui se correspondent


Première étape :
 

• on répète l'opération de relaxation suivante : (l'étoile signifie qu'on norme le vecteur obtenu)
 


jusqu'à ce qu'il n'y ait plus de déplacement ( < epsilon donné ) (sauf pour 4 points qu'on aura fixé sur chaque 1/4 de sphère)

• il faut vérifier que le maillage ne s'effondre pas sur lui-même c'est-à-dire passe de

 
  à
On vérifie cela quand le maillage obtenu s'est stabilisé. S'il n'est pas bon, on fixe aléatoirement un nouveau tétraèdre et on recommence.
• Il faut ensuite vérifier que tous les triplets de vertex ont la même orientation dans le maillage initial, et sur la sphère. Pour remédier à d'éventuelles inversions, on fixe les vertex opposés aux sommets du tétraèdre (ce sont qui sont le plus stable par la relaxation), et on recommence l'opération de relaxation, en diminuant epsilon jusqu'à ce qu'il n'y ait plus d'inversion.


On obtient alors par exemple les maillages suivants :

pour la sphère (remarquez comme les triangles rectangles au départ sont devenus équilatéraux)

pour une vache

    Deuxième étape : il s'agit de déplacer les points sur la sphère pour aligner des points qui sont censés se correspondre (selon un fichier de paramétrisation que fournit l'utilisateur et qui lui permet de contrôler le déroulement du processus).

• On opère une rotation de la première sphère pour minimiser la somme des carrés des distances des points qui se correspondent.
• Pour toute paire de vertex qui se correspondent, on calcule le déplacement t qu'on doit effectuer.
• On applique ensuite l'opération suivante :
qui a pour effet de ne modifier les vertex que localement
• Si ce déplacement a provoqué une inversion, alors on recommence avec un déplacement plus petit (en baissant d ou t)
• Quand le système ne bouge plus, on a aligné les vertex qui doivent se correspondre (si la topologie du maillage le permet)
Remarque : l'algorithme converge, car même si l'on déplace des vertex pour en aligner un seul, chaque fois, le déplacement est plus faible que ce dont a du déplacer le vertex pour l'aligner.

A la fin de cette étape, on a non seulement deux objets projetés, mais aussi des correspondences entre vertex qui assurent un morphing réaliste.

Algorithme de fusion :

       Il s'agit d'un parcours du maillage de Ap en profondeur, en considérant à chaque fois l'intersection avec un nombre d'arêtes limité de Bp. On ne notera pas dans l'algorithme toutes les étapes de marquage qui permettent de n'énumérer chaque arête qu'une seule fois.

  Soit  v1a le premier point de Ap.  Calcul de MapToOpposite[v1a] (calcul de déterminants).

        On ajoute à WL toutes les arêtes qui partent de v1a.

        Tant queWL n'est pas vide, considérer ea, l'arête suivante de WL. v1a = origine de ea, v2a = fin de ea.

                      CL = toutes les arêtes de MapToOpposite[v1a]
                      fb = MapToOpposite[v1a]

                   Tant que CL n'est pas vide, considérer eb, l'arête candidate suivante, v2a et v2b ses extrémités.
                               Si ea et eb s'intersecte,
                                    rajouter l'intersection au modèle (ainsi qu'à ea, eb et leurs opposées)
                                    changer la focalisation : fb = autre face qui jouxte eb
                                     rajouter à CL toutes les autres arêtes de fb
                    Fin tant que CL n'est pas vide

                        MapToOpposite[v2a] = fb (c'est-à-dire la dernière face où on a placé la focalisation)

         Fin tant queWL n'est pas vide.

Ici, les seules arêtes qu'on essaie d'intersecter avec (v1a,v2a) sont (b0,b1), (b0,b2), (b0,b3), (b2,b3), (b0,b4), (b4,b3),(b4,b5) et (b3,b5).

Pour toute arête eb de Bp, v1b et v2b ses extrémités
    Trier les intersections de eb en utilisant les informations topologiques de Ap. (La première et la dernière intersection ont une face qui n'apparait qu'une fois ...)
    En déduire MapToOpposite[v1b] et MapToOpposite[v2b].
Fin pour toute arête de Bp

Pour tout vertex v ed Ap
    Trouver ses coordonnées barycentriques en fonction des sommets de MapToOpposite[v]
    En déduire ses coordonnées dans B
Fin pour tout

Même chose pour Bp

Algorithme de triangulation

Mettre à jour toutes les arêtes, en incluant les intersections.

Pour chaque vertex, trier la liste des arêtes qui partent de ce point (ordre trigonométrique).

Ensuite, on prend toujours l'arête la plus à droite : un dessin est la meilleure explication qui soit.
(Note : il s'agit d'intersections de triangles, donc on sait que l'on aura au maximum 6 points.)

On triangule la face obtenue.

Résultats obtenus

Encore une fois, mieux vaut un bon dessin qu'un long discours :

		Oui, je veux voir le gif animé ! Je ne maudirais pas l'auteur de ce gif pour la taille démesurée de ses fichiers, je le bénirai jour et nuit, et euh non, ça ira comme ça.

Techniques utilisées et problèmes rencontrés

Parlons maintenant effectivement des problèmes rencontrés, des limites de l'algorithme, des résultats (même si c'est censé être dans la section précédente ;^)

Le premier problème rencontré, c'est les cas dégénérés (mais si fréquents qu'on pourrait les croire denses ou s'estimer maudit par les dieux ;^). Pour éviter cela, on utilise une méthode de perturbation infinitésimale pour lever l'ambigüité, comme expliqué par Edelsbrunner (Simulation of Simplicity, A Technique to Cope with Degenerat Cases in Geometric Algorithms). On obtient ainsi un algorithme beaucoup plus robuste et fiable.

Autre problème, les imprécisions de calcul font qu'on doit le plus s'abstraire du problème et ne s'intéresser quasiment qu'aux informations topologiques plutôt qu'aux informations géométriques. Ainsi, on est obligé de réaliser un tri topologique pour ne pas mélanger deux intersections ce qui causerait l'anéantissement de tous nos efforts, la destruction de l'univers, la fin des vacances et peut-être même des bugs d'affichage...

L'algorithme avec projection simpliste est extrêmement rapide (en fait c'est le temps d'écriture des fichiers qui prend tout le temps d'exécution), mais est vite confronté à ses limites : il faut avoir un objet étoilé, sinon, on boucle ou commet une erreur d'exécution, mais c'est normal, car il n'est prévu que pour ces objets. Il n'offre aucun contrôle sur la transformation mis à part le choix du centre de projection.

L'algorithme avec projection plus évolué est par contre plus lent : il faut presque une minute pour calculer la projection d'une vache, puis il faut rajouter le temps d'aligner les vertex mis en correspondance (ce qui dépend du nombre d'intersection). Mais il permet d'aller beaucoup plus loin et de contrôler la transformation.

Cependant, on se sent limité au cas de la sphère : on ne voit pas trop comment projeter sur un tore aussi facilement ... Bref, il faut changer le principe, et découper le maillage principal en différentes parties simplement connexes. Ceci est expliqué par Kanaï ici.

Voilà, j'espère que ceci vous incitera à vous y mettre aussi et que vous connaitrez la fièvre créatrice, ce sacerdoce amer qu'est la programmation avec vi, avec un réseau qui foire, vous passerez autant de nuits blanches que moi, et enfin je serai vengé et le fils des ténèbres reviendra sur ... mais je m'égare ...