Majeure "Mathématiques et Informatique"
Enseignement d'approfondissement
"Images: Analyse et Synthèse"
Simplification de maillages
Projet Réalisé par
Lionel Khalil (promo 95)
Description du projet
Ce projet a pour but de créer un système de simplification de maillages triangulaires,
pouvant être utilisé sur des objets (polyèdriques) 3D ou sur des maillages
2D / 2D-1/2 repré sentant par exemple des images ou des terrains.
A partir d'un maillage dense constitué d'un ensemble de triangles,
l'impact visuel de chaque arête du maillage est quantifié selon des critères géométriques
( aire , angles , couleurs... ). Arête après arête,la simplification du maillage se fait
en respectant l'évaluation de l'impact visuel de chaque modification.
En outre, la mémorisation de la séquence d'opérations de simplifications permet de
faire varier le niveau de détail de l'image selon son grès en simplifiant son maillage
ou en l'enrichissant.
Algorithmes utilisés
Le programme est constitué de quatres parties.
Un maillage de type .coff utilisé par geomview permet de créer un tableau
de vertex comportant une liste des voisins directs de chaque vertex.
A partir des critères de simplifications quantifiés sous forme énergétique,
on ordonne une pile constituée des arêtes. Les trois énergies
retenues sont l'énergie de tension, l'énergie d'aire, l'énergie d'isolement.
L'énergie de tension est évaluée par la différence entre le carré
de la distance entre les sommets de l'arête à supprimer et
leurs voisins
et le carré de la distance entre le nouveau vertex et ses voisins.
L'énergie d'aire est évalué par la différence entre l'aire précedent et suivant la simplification.
Enfin, l'énergie d'isolement attribue une energie aux strucures esseulées.
L'impact énergétique de chaque arête supprimée est imédiatement
propagé à ses voisins qui sont repositioné dans la pile selon un algorithme de divide and conquier.
La séquence de simplification est ensuite
affiché sous geomview à une vitesse
t=log( nombres d'arêtes supprimés ).
Résultats obtenus
La suite d'image dépend à la fois de la complexité de l'image et de la pondération des différentes énergies.
Seul un choix empirique sur les pondérations des énergies permet d'obtenir un résultat acceptable.
EXEMPLE de Simplification du Maillage d'une SPHERE
Les résultats les plus intéressants ont été obtenu sur le maillage d'une vache.
EXEMPLE de Simplification du Maillage d'une VACHE
Problèmes rencontrés et solutions apportées
Trois difficultés sont apparues au cours de la réalisation du programme.
O Même si le maillage initial ne comporte pas d'arete commune à plus de
trois triangles, la simplification crée de telles situations.Il est donc essentiel de se défaire totalement de la représentation de geomview
basée sur les triangles.
L'arete A-M est commune aux triangles 1 Rouge, 2 Bleu,3 Rouge.
O Le choix des pondération d'énergie est difficile. Il faut conserver certains détails de l'image tels que les membres tout en enlevant d'autres.
Sur les images suivantes les deux pondérations énergétiques offrent des rendus visuels caractéristiques.
Sans Energie d'isolement Avec Energie d'isolement
O La simplification a une efficacité croissant exponentiellement.
Le meilleur moyen d'affichage est que le nombre de simplification soit égal a
nbr=nbr total d'aretes * ( 1 - exp ( - temps ) ).
Retour à la liste des projets réalisés