Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The distance function to surfaces in three dimensions plays a key role in many geometric modeling applications such as medial axis approximations, surface reconstructions, offset computations, feature extractions and others. In most cases, the distance function induced by the surface is approximated by a discrete distance function induced by a discrete sample of the surface. The critical points of the distance function determine the topology of the set inducing the function. However, no earlier theoretical result has linked the critical points of the distance to a sampling of geometric structures to their topological properties. We provide this link by showing that the critical points of the distance function induced by a discrete sample of a surface either lie very close to the surface or near its medial axis and this closeness is quantified with the sampling density. Based on this result, we provide a new flow-complex-based surface reconstruction algorithm that, given a tight ε-sampling of a surface, approximates the surface geometrically, both in Hausdorff distance and normals, and captures its topology.

REFERENCES

• 1: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom., 22 pp. 481--504,(1999).
• 2: Nina Amenta , Marshall Bern , David Eppstein, The crust and the &Bgr;-Skeleton: combinatorial curve reconstruction, Graphical Models and Image Processing, v.60 n.2, p.125-135, March 1, 1998 [doi>10.1006/gmip.1998.0465]
• 3: N. Amenta, S. Chi, T. K. Dey and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. J. Comput. Geom. & Applications, vol.12, 2002, pages 125--141.
• 4: N. Amenta, S. Choi and R. Kolluri. The power crust, unions of balls,and the medial axis transform. Computational Geometry: Theory and Applications, 19 pp. 127--153,(2001).
• 5: J. D. Boissonnat and F. Cazals. Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions. Computational Geometry: Theory and Applications, 22 pp. 185--203,(2002).
• 6: Raphaëlle Chaine, A geometric convection approach of 3-D reconstruction, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 7: T. K. Dey, J. Giesen and S. Goswami. Shape Segmentation and Matching with Flow Discretization. In Proc.8th Workshop on Algorithms Data Strucutres, pp. 25--36,(2003).
• 8: T. K. Dey, J. Giesen, S. Goswami and W. Zhao. Shape dimension and approximation from samples. Discr. Comput. Geom., 29 pp. 419--434 (2003).
• 9: Tamal K. Dey , Wulue Zhao, Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee, Algorithmica, v.38 n.1, p.179-200, October 2003 [doi>10.1007/s00453-003-1049-y]
• 10: Kree Cole-McLaughlin , Herbert Edelsbrunner , John Harer , Vijay Natarajan , Valerio Pascucci, Loops in Reeb Graphs of 2-Manifolds, Discrete & Computational Geometry, v.32 n.2, p.231-244, July 2004 [doi>10.1007/s00454-004-1122-6]
• 11: Joachim Giesen , Matthias John, The flow complex: a data structure for geometric modeling, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: K. Grove. Critical Point Theory for Distance Functions. In Proceedings of Symposia in Pure Mathematics 54 3),pp. 357--385,(1993)

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:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory