Anisotropic Mesh Generation

Mael Rouxel-Labbé 1, 2, 3
2 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : In this thesis, we study the generation of anisotropic meshes using the concepts of Delaunay triangulations and Voronoi diagrams. We first consider the framework of locally uniform anisotropic meshes introduced by Boissonnat, Wormser and Yvinec. Despite known theoretical guarantees, the practicality of this approach has only been hardly studied. An exhaustive empirical study is presented and reveals the strengths but also the overall impracticality of the method. In a second part, we investigate the anisotropic Voronoi diagram introduced by Labelle and Shewchuk and give conditions on a set of seeds such that the corresponding diagram has a dual that is an embedded triangulation in any dimension; an algorithm to generate such sets is devised. Using the same diagram, we propose an algorithm to generate efficiently anisotropic triangulations of low-dimensional manifolds embedded in high-dimensional spaces. Our algorithm is provable, but produces disappointing results. Finally, we study Riemannian Voronoi diagrams and introduce discrete Riemannian Voronoi diagrams, which employ recent developments in the numerical computation of geodesic distances and whose computation is accelerated through the use of an underlying anisotropic graph structure. We give conditions that guarantee that our discrete structure is combinatorially equivalent to the Riemannian Voronoi diagram and that its dual is an embedded triangulation, using both straight and curved simplices. We obtain significantly better results than with our other methods, but the overall utility of our techniques remains limited.
Complete list of metadatas
Contributor : Mael Rouxel-Labbe <>
Submitted on : Monday, December 19, 2016 - 2:52:27 PM
Last modification on : Tuesday, April 2, 2019 - 2:38:11 AM
Long-term archiving on: Tuesday, March 21, 2017 - 1:11:09 PM


Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License


  • HAL Id : tel-01419457, version 1



Mael Rouxel-Labbé. Anisotropic Mesh Generation. Computational Geometry [cs.CG]. Université Côte D'Azur, 2016. English. ⟨tel-01419457v1⟩



Record views


Files downloads