Restricted delaunay triangulations and normal cycle

ABSTRACT

We address the problem of curvature estimation from sampled smooth surfaces. Building upon the theory of normal cycles, we derive a definition of the curvature tensor for polyhedral surfaces. This definition consists in a very simple and new formula. When applied to a polyhedral approximation of a smooth surface, it yields an efficient and reliable curvature estimation algorithm. Moreover, we bound the difference between the estimated curvature and the one of the smooth surface in the case of restricted Delaunay triangulations.

REFERENCES

• 1: N. Amenta , S. Choi , T. K. Dey , N. Leekha, A simple algorithm for homeomorphic surface reconstruction, Proceedings of the sixteenth annual symposium on Computational geometry, p.213-222, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336207]
• 2: Nina Amenta and Marshall Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom., 22(4):481--504, 1999.
• 3: Stefan Funke , Edgar A. Ramos, Smooth-surface reconstruction in near-linear time, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.781-790, January 06-08, 2002, San Francisco, California
• 4: H. Edelsbrunner and N. R. Shah. Triangulating topological spaces. Int. J. on Comp. Geom., 7:365--378, 1997.
• 5: Herbert Edelsbrunner , John Harer , Afra Zomorodian, Hierarchical morse complexes for piecewise linear 2-manifolds, Proceedings of the seventeenth annual symposium on Computational geometry, p.70-79, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378626]
• 6: Th. Banchoff, Critical points and curvature for embedded polyhedra, J. Diff. Geom 1 (1967) 245--256.
• 7: M. Berger, B. Gostiaux, Géométrie différentielle : variétés, courbes et surfaces, Presses Universitaires de France.
• 8: H.Cartan, Cours de calcul différentiel, Hermann.
• 9: H. Federer, Curvature measure theory, Trans. Amer. Math. Soc 93 (1959) 418--491.
• 10: H. Federer, Geometric Measure Theory, Springer-Verlag, New York, 1983.
• 11: J. Fu, Convergence of curvatures in secant approximations, J.Differential Geometry 37 (1993) 177--190.
• 12: F. Morgan, Geometric measure theory, Acad. Press, INC. 1987.
• 13: J. Steiner, Jber Preuss. Akad. Wiss. 114--118,(1840). In Gesammelte Werke, vol 2, New York, Chelsea 1971.
• 14: P. Wintgen, Normal cycle and integral curvature for polyhedra in Riemmannian manifolds, Differential Geometry (Gy. Soos and J. Szenthe, eds.), North-Holland, Amsterdam, 1982.
• 15: M. Zahle, Integral and current representations of Federer's curvature measures, Arch. Math. (Basel) 46, (1986), 557--567.
• 16: J.M. Morvan, On generalized curvatures, in preparation.
• 17: S. Petitjean, A survey of methods for recovering quadrics in triangle meshes, accepted.
• 18: M. Desbrun, M. Meyer, P. Schroder and A. Barr Discrete differential-geometry operators in nD, preprint, the Caltech Multi-Res Modeling Group.
• 19: D. S. Meek , D. J. Walton, On surface normal and Gaussian curvature approximations given data sampled from a smooth surface, Computer Aided Geometric Design, v.17 n.6, p.521-543, July 2000 [doi>10.1016/S0167-8396(00)00006-6]
• 20: G. Taubin, Estimating the tensor of curvature of a surface from a polyhedral approximation, Proceedings of the Fifth International Conference on Computer Vision, p.902, June 20-23, 1995
• 21: P. Alliez, D. Cohen-Steiner, M. Desbrun, O. Devillers and B. Lévy, Anisotropic Polygonal Remeshing, to appear in SIGGRAPH 2003.

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

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Theory

Keywords:
curvature, geometric measure theory, mesh