SIMPLIFICATION DE MAILLAGE 3D


Projet Réalisé par Olivier Mellina-Gottardo (promo 96)

Description du projet

Le but du projet est de mettre en oeuvre un algorithme progressif de simplification de maillage 3D. Il doit pouvoir simplifier un maillage jusqu'à un nombre d'arête choisi tout en conservant au maximum l'allure et les caractéristiques du maillage d'origine (forme générale, topologie, éventuellement des détails).

Algorithmes utilisés

L'algorithme utilisé simplifie un maillage constitué de facettes triangulaires en cherchant à minimiser une énergie donnée. La seule opération de simplification autorisée est la suppression d'une arête.

Les arêtes sont classées dans une pile par ordre d'énergie. Celle qui, par sa suppression, entraîne la différence d'énergie la plus faible (une diminution d'énergie la plus importante ou une augmentation la plus faible) sera la première à être supprimée. Les arêtes sont ainsi supprimées une à une dans l'ordre de la pile jusqu'au nombre souhaité ou jusqu'à ce que le maillage devienne trop mauvais. Chaque suppression d'arête entraîne une recomposition locale du maillage qui nécessite le recalcul des énergies attachées à la suppression des arêtes voisines et un reclassement de la pile, qui s'effectue simplement par le déplacement de proche en proche des arêtes réévaluées.
Par ailleurs chaque calcul d'énergie de suppression s'accompagne d'un problème d'optimisation sur la position du sommet issu de l'effondrement de l'arête. On peut se contenter de choisir ce sommet parmi un nombre fini de positions sur l'arête initiale.

L'énergie utilisée est de la forme E=E(dist)+E(long)+E(angle) où E(dist) est une fonction de la distance du maillage simplifié au maillage initial, E(long) dépend des longueurs des arêtes et E(angle) est une fonction croissante de la déformation angulaire créée par une suppression.

Résultats obtenus

Les résultats obtenus dépendent en grande partie de la proportion donnée aux trois termes de l'énergie.
Pour une simplification de moitié du nombre d'arêtes, ces proportions jouent sur la conservation des formes du maillage.
Maillage d'origine, simplification sans énergie de distance, sans énergie de longueur, simplification plus équilibrée

Une simplification plus poussée, si elle ne débouche pas sur des scissions du maillages, peut amener vers un maillage plus grossier, mais qui, si les paramètres sont correctement ajustés, ressemble encore à peu près au maillage initial.

Enfin, s'il reste suffisamment d'arêtes!...

Problèmes rencontrés et solutions apportées

Les problèmes majeurs rencontrés l'ont été au cours de l'implémentation d'une procédure de suppression d'arête, car tous les liens du maillages doivent être mis à jour et un certain nombre de cas particuliers apparaissent dans lesquelles une description par arête devient fastidieuse. Ainsi l'apparition d'un point de scission change-t-il la topologie du maillage et perturbe-t-il l'orientation de la surface. Une telle situation n'a pas été complètement traitée, car cette situation est de toute façon signe d'un problème dans le choix des paramètres d'optimisation.
Enfin il semble difficile de trouver une énergie correcte en général quel que soit le niveau de simplicité du maillage et la voie à explorer pour une amélioration de l'algorithme consisterait à lui permettre d'évoluer en fonction de la phase de simplification.



Retour à la liste des projets réalisés