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. H. Borouchaki, P. L. George, F. Hecht, P. Laug, and E. Saltel. Delaunay mesh generation governed by metric specifications. part I algorithms. Finite Elem. Anal. Des., 25(1-2):61--83, 1997.
3. F. Bossen and P. Heckbert. A pliant method for anisotropic mesh generation. In 5th International Meshing Roundtable, October 1996.
4. S.-W. Cheng, T. K. Dey, E. A. Ramos, and R. Wenger. Anisotropic surface meshing. In SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 202--211, New York, NY, USA, 2006. ACM.
5. F. Labelle and J. R. Shewchuk. Anisotropic voronoi diagrams and guaranteed-quality anisotropic mesh generation. In SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry, pages 191--200, New York, NY, USA, 2003. ACM Press.
6. X.-Y. Li. Sliver-free three dimensional delaunay mesh generation. PhD thesis, University of Illinois at Urbana-Champaign 2000.
7. X.-Y. Li and S.-H. Teng. Generating well-shaped delaunay meshed in 3d. In SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 28--37, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics.
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. J. R. Shewchuk. Tetrahedral mesh generation by delaunay refinement. In SCG '98: Proceedings of the fourteenth annual symposium on Computational geometry, pages 86--95, New York, NY, USA, 1998. ACM.
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. R. Shewchuk. Star splaying: an algorithm for repairing delaunay triangulations and convex hulls. In SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry, pages 237--246, New York, NY, USA, 2005. ACM.
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

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry