Anisotropic triangulations

Where : INRIA , Unité de Sophia Antipolis Geometrica team BP 93 06902 Sophia Antipolis FRANCE Information: Mariette Yvinec Tel : +33 4 92 38 77 49 e-mail: <Mariette.Yvinec@sophia.inria.fr>

Context:

Usually meshes elements are required to be close to the regular simplices. Some applications, on the contrary, require anisotropic meshes, i.e. meshes in which elements are elongated in some prescribed directions. This is for instance the case if one wishes to interpolate functions having an anisotropic Hessian tensor. For a given number of mesh elements, the interpolation error is minimized when mesh elements are elongated in the direction of the Hessian eigen vector with smallest eigenvalue.

An anisotropic meshing problem are usually defined in term of a metric field that is a domain where each point is associated with a symmetric tensor to be used for measuring distances as seen from this point. The goal is to build on such a domain a mesh whose elements are shaped according to the local metric. Various methods have been proposed to build anisotropic meshes. Most of them are heuristic or restricted to work only on two dimensional anisotropic metric fields.

We have recently proposed a new and simple method based on the notion of locally uniform anosotropic meshes. To understand how this method works, it is usefull to notice that an anisotropic mesh can be easily obtain when the metric field is uniform by using an affine transformation that changes the metric to the Euclidean metric, building a Delaunay mesh in the transformed space and applying the reverse transform to the mesh. Our method incrementally build the set of mesh sites. It maintains for each site in the current mesh, a local anisotropic triangulation shaped according to the site metric and including only the site and its neighbors. The mesh is refined by adding new sites until local triangulations of neighboring sites are consistent and can be merged together. If some care is taken in the choice of refinement points, the refinement process ends. The boundary constraints are respected in each local triangulation and therefore in the final mesh.

Description:

The above algorithm has been implemented in dimension 2. It can be extended to work in dimension 3. In 3d the process to choose refinement points can be also tuned to avoid the formation of sliver like tetrahedra. The work proposed for this intership is to implement this anisotropic mesh generation process in dimension 3 and to further study how it can be improved to handle the cases where the input constraints bounding the domain form small angles.

Outils :

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

Bibliographie :

• Star Splaying: an algorithm for repairing Delaunay triangulations and convex hulls.
  Jonathan R. Shewchuk
  Proceedings of the 21th Annual Symposium on Computatinal Geometry, pages 237--246, New-York 2005.
• 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.
• Locally uniform anisotropic meshing.
  J-D. Boissonnat, C. Wormser and M. Yvinec.
  To appear at the next Symposium on Computational Geometry, june 2008 (SOCG 2008)