Locally uniform anisotropic meshing

ABSTRACT

Various definitions of so called anisotropic Voronoi diagrams have been proposed. These diagrams are typically parameterized by a metric field. Under mild hypotheses on the metric field, such Voronoi diagrams can be refined so that their dual is a triangulation, with elements shaped according to the specified anisotropic metric field. We propose an alternative approach to anisotropic mesh generation, relying on the notion of locally uniform anisotropic mesh. A locally uniform anisotropic mesh is a mesh such that the star around each vertex v coincides with the star that v would have if the metric on the domain was uniform and equal to the metric at v. This definition allows to define a simple refinement algorithm which relies on elementary predicates, and provides, after completion, an anisotropic mesh in dimensions 2 and 3.

A practical implementation has been done in the 2D case.

REFERENCES

• 1: J.-D. Boissonnat, C. Wormser, and M. Yvinec. Anisotropic diagrams: Labelle shewchuk approach revisited. Theoretical Computer Science, to appear.
• 2: Houman Borouchaki , Paul Louis George , Frédéric Hecht , Patrick Laug , Eric Saltel, Delaunay mesh generation governed by metric specifications. Part I algorithms, Finite Elements in Analysis and Design, v.25 n.1-2, p.61-83, March 1997 [doi>10.1016/S0168-874X(96)00057-1]
• 3: F. Bossen and P. Heckbert. A pliant method for anisotropic mesh generation. In 5th International Meshing Roundtable, October 1996.
• 4: Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos , Rephael Wenger, Anisotropic surface meshing, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.202-211, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109581]
• 5: Francois Labelle , Jonathan Richard Shewchuk, Anisotropic voronoi diagrams and guaranteed-quality anisotropic mesh generation, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777822]
• 6: Xiangyang Li , Shang-Hua Teng, Sliver-free three dimensional delaunay mesh generation, University of Illinois at Urbana-Champaign, Champaign, IL, 2001
• 7: Xiang-Yang Li , Shang-Hua Teng, Generating well-shaped Delaunay meshed in 3D, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 07-09, 2001, Washington, D.C., United States
• 8: X.-Y. Li, S.-H. Teng, and A. Üngör. Biting ellipses to generate anisotropic mesh. In 8th International Meshing Roundtable, October 1999.
• 9: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 10: J. R. Shewchuk. What is a good linear finite element? Interpolation, conditioning, anisotropy, and quality measures. In http://www.cs.cmu.edu/~jrs/jrspapers.html, Manuscript 2002.
• 11: Richard Shewchuk, Star splaying: an algorithm for repairing delaunay triangulations and convex hulls, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064129]
• 12: K. Shimada, A. Yamada, and T. Itoh. Anisotropic Triangulation of Parametric Surfaces via Close Packing of Ellipsoids. Int. J. Comput. Geometry Appl, 10(4):417--440, 2000.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
anisotropic mesh generation, delaunay refinement, delaunay triangulation