Interleaving Delaunay Refinement and Optimization for 2D Triangle Mesh Generation

Jane Tournois 1 Pierre Alliez 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We address the problem of generating 2D quality triangle meshes from a set of constraints provided as a planar straight line graph. The algorithm first computes a constrained Delaunay triangulation of the input set of constraints, then interleaves Delaunay refinement and optimization. The refinement stage inserts a subset of the Voronoi vertices and midpoints of constrained edges as Steiner points. The optimization stage optimizes the shape of the triangles through the Lloyd iteration applied to Steiner points both in 1D along constrained edges and in 2D after computing the bounded Voronoi diagram. Our experiments show that the proposed algorithm inserts fewer Steiner points than Delaunay refinement alone, and improves over the mesh quality.
Type de document :
Communication dans un congrès
Michael L. Brewer and David Marcum. Proceedings of the 16th International Meshing Roundtable, Oct 2007, Seattle, United States. springer, pp.83-101, 2008, 〈10.1007/978-3-540-75103-8_5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01179018
Contributeur : Olivier Devillers <>
Soumis le : mardi 21 juillet 2015 - 14:47:36
Dernière modification le : samedi 27 janvier 2018 - 01:31:33

Lien texte intégral

Identifiants

Collections

Citation

Jane Tournois, Pierre Alliez, Olivier Devillers. Interleaving Delaunay Refinement and Optimization for 2D Triangle Mesh Generation. Michael L. Brewer and David Marcum. Proceedings of the 16th International Meshing Roundtable, Oct 2007, Seattle, United States. springer, pp.83-101, 2008, 〈10.1007/978-3-540-75103-8_5〉. 〈hal-01179018〉

Partager

Métriques

Consultations de la notice

202