Interpolation de formes 3D
 

Projet Réalisé par Loïc GUIGNOT (promo 96)

Description du projet

. Le projet consiste en l'utilisation d'une nouvelle méthode de "morphing", qui consiste à faire partager aux polyèdres de départ et d'arrivée la même topologie (ie les mêmes points/arêtes) pour minimiser durant la transformation les distortions locales. Il gère de plus intelligemment la recherche de cette topologie en évitant un maximum de calculs inutiles.

La fusion des deux topologies se fait par projection sur la sphère avec création des points intersections de segments de chacun des deux objets d'origine A et B.
 

Algorithmes utilisés

Algorithme global :

Lecture des fichiers triangulés

Pour chaque arête de A

Trouver la face de B où l'extrémité de l'arête se projette

Ajouter les trois segments supports de la face trouvée à la WorkList

Tant que la WorkList n'est pas vide
 

Si l'arête de A intersecte celle de la WorkList (en projection)
  Alors calculer la position sur les deux segments du point d'intersection

Noter les 2 faces de A et les 2 faces de B qui s'appuient sur ce point

Rajouter les arêtes de la face de B où vient de déboucher l'arête projetée de A à la WorkList
 

 Supprimer la première arête de la WorkList
  Ajouter les extremités de l'arête de A à la structure finale en notant les faces de A et de B s'appuyant sur ces points Pour chaque point de B Trouver la face de A où le point se projette

Noter toutes les faces de B et celle de A qui s'appuient sur ce point

 Regrouper les points (à double coordonnées : initiale et finale) en fonction des faces de A et B notées

Reconstituer ainsi les faces avec les points en ordre trigonométrique (face sortante)

Trianguler les faces

Générer les fichiers de sortie .OFF par barycentrage des coordonnées initiales et finales de chaque point
 
 

En ce qui concerne la recherche de la face sur laquelle un point se projette, une méthode qui évite une liste exhaustive de tests consiste à trouver la position du point relativement au plan formé par le centre et une arête, puis à procéder ainsi de face en face en testant uniquement les arêtes de la face candidate. Ci-dessous on trouve la face 2.

.

Résultats obtenus

On fait le morphing obtenu entre deux tétraèdres pour avoir ceci :

A l'heure actuelle, le programme a encore du mal à traiter tous les cas de figure et ne donne pas toujours de résultat?
 
 

Problèmes rencontrés et solutions apportées

Le sujet initial proposait de calculer les intersections des arcs (projections des segments sur la sphère) pour former les nouveaux points En pratique, le calcul de l'intersection ne s'appuyait que sur la direction des points supports des segments, de sorte que l'on peut éviter de transiter par la sphère en combinant cette étape avec la projection du point créé sur les polyèdres d'origine.

Le projection des points ainsi crées sur les segments et les faces des polyèdres d'origine n'est malheureusement pas immédiate. Grâce à la géométrie, on trouve néanmoins des formules épargnant l'approximation d?une résolution numérique.

La génération des faces finales n'est pas évidente.. En fait, ces faces sont, crées comme intersection des projections sur la sphère d'une face de A et d'une face de B. En notant ces informations de face avec les points crées, on regroupe face par face les points supports . Sachant que les objets initiaux étaient triangulés, et que les faces obtenus n'ont ainsi qu'entre 3 et 6 points, il suffit alors de parcourir ces points dans l'ordre " face sortante ". Une dernière étape de triangulation est nécessaire car si les points de la face sont coplanaires au début et à la fin de la transformation, ils ne le restent pas durant le mouvement.
 
 

Limites rencontrées


La conception même de la méthode de résolution implique de ne traiter que le cas d?objets étoilés. Trois problèmes se posent donc :

Jusqu'ici, la méthode d'interpolation bute dès qu'un point d?un objet se projette sur un point ou un segment de l'autre objet. Deux solutions complémentaires sont envisageables :

 

Retour à la liste des projets réalisés