Interpolation d'objets 3D
Projet Réalisé par Yéong
Sy (promo 96)
Description du projet
Communément appelée "morphing 3D", l'interpolation
d'objets 3D aborde le problème du passage continu d’une forme tridimensionnelle
à une autre.
Les objets 3D sont décrits par des modèles
orientés points et facettes. La visualisation est assurée
par un programme auxiliaire sous Unix.
Le but est de réaliser un programme, prenant
en entrée un objet A et un objet B, qui génère une
série d'objets intermédiaires en vue de réaliser une
animation non brutale d'une transformation de l’objet A vers l’objet B.
L’intérêt de la méthode que l’on se propose d’implémenter
est de pouvoir effectuer toute cette transformation de façon complètement
automatique, sans nécessiter d'intervention humaine, contrairement
à ce que l'on rencontre encore dans beaucoup de logiciels grand
public du commerce.
Etude du problème
Le problème de l’interpolation d’objets
3D peut se diviser en 2 parties :
La correspondance et l’interpolation
à proprement dite.
La correspondance
Cette partie consiste à déterminer où
un point de l’objet A va se retrouver sur l’objet B. Tout le travail va
être de fusionner les 2 modèles en ajoutant des points afin
d’obtenir pour A et B de nouveaux modèles avec des points qui pourront
être mis en correspondance de façon simple.
Toute l’idée de l’algorithme de fusion consiste
à projeter les modèles sur la sphère unité
et à trouver toutes les intersections entre arêtes des 2 modèles.
(cliquer ici pour
une description plus détaillée de l'algorithme de fusion
en pseudo-code)
Une fois tous les points du modèle fusionné
établis, il faut énumérer les faces de (Ma)n et (Mb)n
par un certain algorithme de parcours de graphe.
L’interpolation
Cette partie de la transformation consiste à
calculer les modèles intermédiaires de la transformation
à différents instants t, en vue de l’animation.
En fait, elle est extrêmement simple car la
correspondance est immédiate entre un point va de l’objet
A et son vis-à-vis vb sur l’objet B.
Et la détermination des coordonnées
d’un point interpolé entre ce point va et vb se réduit alors
à un calcul du type :
f(t) x (coordonnées
de va) + (1-f(t)) x (coordonnées de vb)
f : fonction comprise entre
0 et 1 qui donne le chemin de la transformation.
Pour les facettes, c'est encore plus simple puisqu'il
n'est pas nécessaire de les recalculer.
Il suffira de mettre ces données dans un
fichier tampon et de faire un copier-coller.
Limites de la méthode
L’algorithme décrit est limité dans sa
phase de correspondance.
D’abord, il ne peut traiter que des objets topologiquement
équivalents à la sphère - étoilé - à
cause de la projection sur la sphère unité.
Une extension possible du problème consisterait
à passer par les enveloppe convexes des objets pour des objets non
étoilés.
Ensuite, il ne peut résoudre le problème
de points tombant exactement sur une arête, puisque l’algorithme
repose sur la détermination de la facette de l’objet B qui contient
les points de l’objet A.
Dans toute la phase de test, afin d'éviter
tous les cas pathologiques, on fait subir à un des 2 modèles
de petites rotations selon les 3 axes.
Résultats
Voici une suite d'images de l'interpolation d'une sphère
vers un cube.
Les résultats obtenus sont assez décevants.
Même sur des modèles d'objets relativement simples - sphère
et cube -, des défauts d'affichage apparaissent.
De plus, le nombre d'intersections explose assez rapidement. De ce
fait, les temps de calcul augmentent et l'animation devient alors très
lente.
En outre, cette projection sur la sphère, du
fait du choix plus ou moins arbitraire du centre de la projection, a tendance
à grossir de façon "inharmonieuse" certaines parties des
objets.
Retour à la liste des projets réalisés
