Projets image 2006
Calcul de plus courts chemins sur des surfaces triangulées
Contexte
En informatique, les objets 3D sont le plus souvent représentés sous forme de surfaces triangulées : une telle surface représente le bord (on dit la frontière) de l'objet, et elle est constituée d'un ensemble de sommets (dont les coordonnées sont généralement obtenus par scannérisation d'un modèle réel), d'un ensemble d'arêtes reliant ces sommets, et d'un ensemble de faces triangulaires délimitées par ces arêtes (voir la figure ci-dessous).
Un modèle 3D de cheval, représenté par 19851 sommets et 39698 triangles.
On a souvent besoin de faire des calculs automatiques sur ces surfaces : par exemple, pour modifier les modèles qu'elles représentent, les animer, les compresser, les classer dans une base de données, ... Le thème commun aux trois projets proposés ici rentre dans ce cadre : il s'agit dans les trois cas de calculer automatiquement des courbes particulières (qui sont en fait des plus courts chemins, pour différentes fonctions de distance) sur des surfaces triangulées.
Chacun des projets consiste en l'implémentation d'un ou de plusieurs algorithmes existant(s), décrit(s) (en anglais) dans un article publié dans une revue scientifique spécialisée. Mais comme vous vous destinez à être ingénieurs (ou éventuellement chercheurs), c'est-à-dire plus que de simples programmeurs, ces projets comportent également une part de réflexion : je vous demande d'analyser les résultats produits par ces algorithmes sur différentes données, et éventuellement, de proposer des améliorations à ces algorithmes.
Détails techniques
Voir ma page principale sur les projets image pour les aspects pratiques.- Niveau correct en anglais nécessaire (pour comprendre les articles et les références).
- Programmation en C/C++.
- Cette année, une petite interface écrite en C++ et fonctionnant sous QGLViewer et CGAL est fournie. Vous devrez néanmoins vous
familiariser un peu avec ces deux bibliothèques, pour pouvoir utiliser et
éventuellement compléter l'interface.
- QGLViewer est construit sur Qt et OpenGL, et offre des outils pour construire très facilement une application 3D (visualisation d'une scène, mais aussi animation, par exemple).
- CGAL est une bibliothèque de calcul géométrique, en particulier sur des surfaces. Elle permet de faire plein de choses, mais en contrepartie elle est un peu "indigeste" ...
- Pour tout souci ou question, me contacter par mail. Je passerai en salle Mac une à trois fois par semaine.
Les sujets
- Sujet 1 : trois algorithmes de plus courts chemins.
- Sujet 2 : calcul itératif de géodésiques discrètes.
- Sujet 3 : contours actifs 3D.