PROPOSITION de SUJET de TER Ensimag 2A 2007-08


Titre (1 ligne) : Calcul d'un squelette de déformation dynamique
Laboratoire : LJK
Equipe : EVASION, INRIA Rhône-Alpes
Enseignant Ensimag/Telecom responsable du stage : Marie-Paule Cani et Franck
Hétroy

Thème général :
Ce sujet fait appel à des compétences en algorithmique (plus court chemin dans
un graphe) et programmation C++, appliquées à la géométrie 3D. Un lien existe
avec le cours de modélisation géométrique, sans que le suivi de ce cours soit
indispensable.

Compétences attendues :
Bonne compréhension du cours d'algo 1 et bon niveau en programmation C++. Un
intéret pour la géométrie 3D, le traitement d'images et les IHM seront un plus.

Contexte du travail :
Offrir des outils de déformation d'objets virtuels aussi intuitifs que de
courber, aplatir ou tordre un morceau de pâte à modeler dans le monde réel est
l'un des défis de la modélisation 3D interactive. Dans ce cadre, on aimerait
offrir à l'utilisateur un outil de déformation lui permettant de saisir à la
souris une portion d'un objet virtuel, de la tirer dans le plan de l'écran, et
voir le modèle 3D suivre son mouvement de manière naturelle. Un excellent outil
pour ce faire est de s'appuyer sur un 'squelette', jouant le rôle d'une tige de
fil de fer flexible centrée dans la forme. Les deux co-encadrants ont déjà une
bonne expérience des méthodes à base de squelette dans le cadre d'autres projets
(modélisation par surfaces de convolution et déformation par 'skinning' pour
Marie-Paule Cani, calcul de graphes de Reeb et leur application à l'animation
pour Franck Hétroy). L'originalité de ce travail sera de calculer à la volée un
squelette de déformation dynamique, adapté à chaque action de l'utilisateur.

Sujet :
Etant donnés un objet 3D décrit par un maillage (un graphe de sommets, dont les
arêtes forment des triangles) et un sommet 'saisi' par l'utilisateur, l'objectif
est de développer une méthode calculant par propagation un squelette issu de ce
sommet, et centré dans l'objet. Le squelette, un graphe de Reeb dont la fonction
associée sera la distance sur le maillage au sommet saisi, sera calculé en
adaptant l'algorithme de Dijkstra pour le calcul des plus courts chemin et
d'après un algorithme de la littérature. Il sera interrompu au premier
embranchement rencontré dans la forme. Pour permettre les déformations
attendues, le nombre de points engendrés le long du squelette devra dépendre de
l'épaisseur locale de la forme autour de lui.

Résultats attendus :
- Le calcul du squelette dynamique devra être rapide, si possible temps-réel.
- Il devra être totalement automatique : ainsi, l'utilisateur pourra à terme
déformer des objets de manière naturelle, sans rien connaitre des modèles
mathématiques sous-jacents.
- Le squelette obtenu pourra être couplé avec une méthode développée par Damien
Rohmer (étudiant en thèse) de déformation de type 'skinning', permettant de
déformer la forme à partir d'une déformation du squelette.

Compétences fournies par le stage :
Avoir l'occasion d'expérimenter avec des algorithmes et des structures de
données fondamentaux vus en cours, dans le cadre concret et attractif de la
géométrie 3D. Bonne initiation à la recherche car il s'agit de contribuer à un
sujet chaud, au coeur des préoccupations de l'équipe de recherche. Possibilité
d'extension du sujet sous forme d'un stage d'été au sein du laboratoire.