Anisotropic surface meshing

ABSTRACT

We study the problem of triangulating a smooth closed implicit surface Σ endowed with a 2D metric tensor that varies over Σ. This is commonly known as the anisotropic surface meshing problem. We extend the 2D metric tensor naturally to 3D and employ the 3D anisotropic Voronoi diagram of a set P of samples on Σ to triangulate Σ. We prove that a restricted dual, Mesh P, is a valid triangulation homeomorphic to Σ under appropriate conditions. We also develop an algorithm for constructing P and Mesh P. In addition to being homeomorphic to Σ, each triangle in Mesh P is well-shaped when measured using the 3D metric tensors of its vertices. Users can set upper bounds on the anisotropic edge lengths and the angles between the surface normals at vertices and the normals of incident triangles (measured both isotropically and anisotropically).

REFERENCES

• 1: Pierre Alliez , David Cohen-Steiner , Olivier Devillers , Bruno Lévy , Mathieu Desbrun, Anisotropic polygonal remeshing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 2: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom., 22 (1999), 481--504.
• 3: N. Amenta, S. Choi, T. K. Dey and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. J. Comput. Geom. Applications, 12 (2002), 125--141.
• 4: J. Bloomenthal, Polygonization of implicit surfaces, Computer Aided Geometric Design, v.5 n.4, p.341-355, Nov. 1988 [doi>10.1016/0167-8396(88)90013-1]
• 5: J.-D. Boissonnat and F. Cazals. Natural neighbor coordinates of points on a surface. Comput. Geom. Theory Appl., 19 (2001), 87--120.
• 6: J. D. Boissonnat , S. Oudot, Provably good surface sampling and approximation, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 7: Jean-Daniel Boissonnat , David Cohen-Steiner , Gert Vegter, Isotopic implicit surface meshing, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007401]
• 8: J.-D. Boissonnat, C. Wormser, and M. Yvinec. Anisotropic diagrams: Labelle Shewchuk approach revisited. CCCG 2005.
• 9: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991 [doi>10.1016/0304-3975(91)90261-Y]
• 10: H.-L. Cheng, T. K. Dey, H. Edelsbrunner and J. Sullivan. Dynamic skin triangulation. Discrete Comput. Geom., 25 (2001), 525--568.
• 11: Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos , Tathagata Ray, Sampling and meshing a surface with guaranteed topology and geometry, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997861]
• 12: J. C. Cuiliere. An adaptive method for the automatic triangulation of 3D parametric surfaces. Computer Aided Design, 30 (1998), 139--149.
• 13: T. K. Dey, G. Li, and T. Ray. Polygonal surface remeshing with Delaunay refinement. Proc. 14th International Meshing Roundable, 2005, 343--351.
• 14: H. Edelsbrunner and J. Harer. Jacobi sets of multiple Morse functions. In Foundations of Computational Mathematics, eds. F. Cucker, R. DeVore, P. Olver and E. Sueli, Cambridge Univ. Press, 2003, 37--57.
• 15: Tasso Karkanis , A. James Stewart, Curvature-Dependent Triangulation of Implicit Surfaces, IEEE Computer Graphics and Applications, v.21 n.2, p.60-69, March 2001 [doi>10.1109/38.909016]
• 16: 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]
• 17: T. S. Lau and S. H. Lo. Finite element mesh generation over analytical surfaces. Computers and Structures, 59 (1996), 301--309.
• 18: Greg Leibon , David Letscher, Delaunay triangulations and Voronoi diagrams for Riemannian manifolds, Proceedings of the sixteenth annual symposium on Computational geometry, p.341-349, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336221]
• 19: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 20: M. Sharir. Almost tight bounds for lower envelopes in higher dimensions. Discrete & Comput. Geom., 12 (1994), 327--345.
• 21: J. R. Tristano, S. J. Owen, and S. A. Canann. Advancing front surface mesh generation in parametric space using a Riemannian surface definition. Proc. 7th Intl. Meshing Roundtable 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

General Terms:
Algorithms, Theory