Enseignement d'approfondissement
"Images: Analyse et Synthèse"
|
|
Majeure "Mathématiques et Informatique" Enseignement d'approfondissement "Images: Analyse et Synthèse" |
De nombreux logiciels (modeleurs, visionneuses Internet, jeux) représentent des objets en 3D sous forme d'un maillage de triangles.
On cherche à développer un algorithme pour obtenir un maillage visuellement proche de l'original, mais comportant moins de sommets afin d'occuper moins de place en mémoire, ce qui permet d'alléger l'affichage ou les taux de transfert sur un réseau.
On s'appuie sur les travaux de Hugues Hoppe et al. qui définissent les manipulations élémentaires sur les maillages.
La seule manipulation autorisée dans le cadre d'une simplification est l'effondrement d'arête (une arête est réduite à un point, auquel on reconnecte les sommets à la périphérie de l'arête effondrée). L'efficacité d'un effondrement, i.e. la proximité du nouveau maillage à l'original, est mesurée grâce à une fonction d'énergie qui tient compte de trois facteurs : distance du maillage simplifié à l'original, longueur des arêtes, déformation angulaire.
Le sommet est choisi parmi trois positions sur l'arête effondrée (les deux extrémités et le milieu) : on retient celui qui génère la différence d'énergie la plus faible.
On construit alors une pile d'arêtes classées par ordre croissant de différences d'énergies, on effondre l'arête située en haut de la pile, et on réarrange la pile en recalculant les énergies des arêtes voisines de l'arête effondrée.
Le programme prend en arguments un maillage 3D au format Geomview et trois paramètres adaptatifs qui pondèrent les énergies et permet d'obtenir des résultats différents.
On extrait du fichier Geomview deux tableaux : les sommets et les triangles. On en déduit le tableau des arêtes. Plusieurs procédures permettent ensuite de calculer les différentes énergies, de sélectionner celui des 3 sommets sur lequel on va effondrer telle arête, de construire la pile et d'effondrer une arête.
Un système de remise à jour des énergies et de la pile est alors mis en place dans une boucle qui permet d'effectuer des effondrement successifs.Les principales difficultés concernent la gestion en mémoire de la structure de données : conversion du format Geomview, manipulation de fichiers coûteux en mémoire, et reconversion vers le format Geomview.
On rencontre également de nombreux cas particuliers dans la disposition des arêtes qui font que toute arête n'est pas effondrable (problèmes notamment sur l'orientation de la surface).
Il est possible, à l'aide d'une structure chaînée, d'accéder à une suppression/addition progressive (cf. Hoppe) en vue de transmettre des maillages en flux continu dur un réseau. Cependant cette technique demande beaucoup de calculs préliminaires et une grande quantité de mémoire.
On peut ensuite s'intéresser à l'interpolation des couleurs, mon programme ne modifiant pour l'instant que le "côté géométrique" du maillage.
- Source (langage C)
- Source du programme simplifié (langage C)
- Programme simplifié (version UNIX - version PC)
- Fichier d'exemple au format Geomview
