Medial axis approximation and unstable flow complex

ABSTRACT

The medial axis of a shape is known to carry a lot of information about it. In particular a recent result of Lieutier establishes that every bounded open subset of Rⁿ has the same homotopy type as its medial axis. In this paper we provide an algorithm that, given a sufficiently dense but not necessarily uniform sample from the surface of a shape with smooth boundary, computes a core for its medial axis approximation, in form of a piecewise linear cell complex, that captures the topology of the medial axis of the shape. We also provide a natural method to freely augment this core in order to enhance it geometrically all the while maintaining its topological guarantees. The definition of the core and its extension method are based on the steepest ascent flow induced by the distance function to the sample. We also provide a geometric guarantee on the closeness of the core and the actual medial axis.

REFERENCES

• 1: N. Amenta and M. W. Bern. Surface reconstruction by voronoi filtering. Discrete & Computational Geometry, 22: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. Choi, and R. K. Kolluri. The power crust, unions of balls, and the medial axis transform. Computational Geometry, 19(2-3):127--153, 2001.
• 4: D. Attali, J.-D. Boissonnat, and H. Edelsbrunner. Stability and computation of the medial axis—a state-of-the-art report. Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, 2004.
• 5: J.-D. Boissonnat and F. Cazals. Smooth surface reconstruction via natural neighbour interpolation of distance functions. Computational Geometry, 22(1-3):185--203, 2002.
• 6: Frédéric Chazal , André Lieutier, The "λ-medial axis", Graphical Models, v.67 n.4, p.304-331, July 2005 [doi>10.1016/j.gmod.2005.01.002]
• 7: Tim Culver , John Keyser , Dinesh Manocha, Exact computation of the medial axis of a polyhedron, Computer Aided Geometric Design, v.21 n.1, p.65-98, January 2004 [doi>10.1016/j.cagd.2003.07.008]
• 8: Tamal K. Dey , Joachim Giesen , Edgar A. Ramos , Bardia Sadri, Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based surface reconstruction, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064126]
• 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: 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
• 11: K. Grove. Critical point theory for distance functions. Symposia in Pure Mathematics, 54(3):357--385, 1993.
• 12: A. Hatcher. Algebraic Topology. Cambridge University Press, 2001.
• 13: A. Lieutier. Any bounded open subset of Rn has the same homotopy type as its medial axis. Computer-Aided Design, 36(11):1029--1046, 2004.

INDEX TERMS

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

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

Keywords:
flow complex, gradient flow, medial axis approximation, stable and unstable manifolds, topological guarantee