Local optimisation of meshes

Where :
INRIA , Unité de Sophia Antipolis
Geometrica team
BP 93
06902 Sophia Antipolis

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

Quality mesh generation is still a challenging problem. Meshing algorithms based on Delaunay refinement are becoming highly popular because they provide guarantees on the generated mesh. It is well known that Delaunay refinement banishes from the mesh all the nearly degenerated tetrahedra that have a volume too small with respect to the value of their circumradius. This leaves in the mesh nearly degenerate tetrahedra with a special shape that are called slivers. Several methods have been proposed to get rid of slivers. The CGAL libray meshing packages implement Delaunay refinement algorithms followed by sliver exudation phases. The sliver exudation is obtained, as in the approach pioneered by Edelsbrunner and al. by turning the Delaunay triangulation into a weighted Delaunay triangulation with a carefull choice of the weighting of the mesh vertices. It is clear, looking at the histogram of dihedral angles in the mesh, that the sliver exudation phase greatly improves the mesh quality, knocking down the number of slivers. Still, very often, a few sliver tetrahedra remain in the mesh even after the exudation phase. The efficiency of further computations performed on the mesh, like finite element computations, are highly dependant on the worst shaped elements of the mesh. Therefore it might be rewarding spending some more time to perform on local optimisation of the mesh to improve the mesh quality.

The library CGAL includes a package to mesh surfaces and a mesh generation package for 3D domains will be part of the next public release of CGAL. CGAL has a highly flexible code based on Delaunay refinement and sliver exudation to produce three dimensional meshes. The internship work would consist in implementing and testing state of the art methods to further improve the quality of generated meshes.

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

Bibliographie :

Retour aux autres stages

Mariette Yvinec
Last modified: Thu Nov 30 16:24:50 CET 2006