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.
Description:
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 :
Geometry and topology for mesh generation, by Herbert Edelsbrunner
Cambridge University Press, 2001.
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.
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.
Bryan Matthew Klingner and Jonathan Richard Shewchuk, Aggressive Tetrahedral Mesh Improvement, Proceedings of the 16th International Meshing Roundtable (Seattle, Washington), October 2007.
Variational tetrahedral meshing,
Alliez P., Cohen-Steiner D., Yvinec M. and Desbrun M.
Proceedings of ACM SIGGRAPH 2005, 24(3), pages 617--625.