Eliminations des slivers

Lieu :

INRIA , Unité de Sophia Antipolis
Projet Geometrica
BP 93
06902 Sophia Antipolis
FRANCE

Information:

Mariette Yvinec Tel : +33 4 92 38 77 49 e-mail: <Mariette.Yvinec@sophia.inria.fr>

Description:

Le raffinement de Delaunay s'impose comme l'une des méthodes les plus efficaces et les plus souples pour générer des maillages simpliciaux non structurés. En particulier, la méthode permet de générer des maillages qui respectent bien les contraintes géométriques (frontières et structures internes) même si ces contraintes sont des surfaces courbes et qui s'adaptent facilement à la granularité requise même si cette dernière est inhomogène.

Le seul inconvénient des méthodes utilisant le raffinement de Delaunay réside dans le fait que les maillages produits peuvent inclure des tétraèdres quasiment dégénérés relevant de la catégorie des slivers. Un sliver est un tétraèdres plats dont les 4 sommets sont proches de l´équateur d'une sphère et approximativement bien répartis le long de cet équateurs.

La présence de slivers nuit gravement à la robustesse et à l'efficacité de la plupart des applications utiisant les maillages. Dans un générateur de maillages, le processus de raffinement de Delaunay est donc généralement suivi par une phase dédiée à l´élimination des slivers du maillage. Plusieurs méthodes ont été proposées pour éliminer les slivers des maillages. L'une d'elle consiste à chasser les slivers en utilisant une triangulation régulière avec une pondération judicieuse des sommets du maillage. Une autre, qui se rapproche des méthodes d'optimisation locale, consiste à relaxer quelque peu le choix des points de raffinement dans les dernières étapes du processus de raffinement.

Le but du stage est d'expérimenter, de comparer et d'améliorer différentes méthodes d'élimination des slivers en utilisant le générateur de maillages de la librairie CGAL.

Outils :

PC Linux,
langage C++,
Bibliothèque géométrique CGAL

Bibliographie :

• Geometry and topology for mesh generation, by Herbert Edelsbrunner
  Cambridge University Press, 2001.
• Silver Exudation, Cheng, S.-W. Dey, T. K. Edelsbrunner, H. Facello, M. A. Teng, S.-H.
  Journal of the ACM, 2000, 47(5),pages 883-904.
• Generating well-shaped Delaunay meshed in 3D, Li, X.Y. and Teng, S.H.,
  Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms,2001, pages 28--37.
• Variational tetrahedral meshing, Alliez P., Cohen-Steiner D., Yvinec M. and Desbrun M.
  Proceedings of ACM SIGGRAPH 2005, 24(3), pages 617--625.