Approximate medial axis as a voronoi subcomplex

ABSTRACT

Medial axis as a compact representation of shapes has evolved as an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to approximate them. One line of research considers the point cloud representation of the boundary surface of a solid and then attempts to compute an approximate medial axis from this point sample. It is known that the Voronoi vertices converge to the medial axis for a curve in 2D as the sample density approaches infinity. Unfortunately, the same is not true in 3D. Recently, it is discovered that a subset of Voronoi vertices called poles converge to the medial axis in 3D. However, in practice, a continuous approximation as opposed to a discrete one is sought. Recently few algorithms have been proposed which use the Voronoi diagram and its derivatives to compute this continuous approximation. These algorithms are scale or density dependent. Most of them do not have convergence guarantees, and one of them computes it indirectly from the power diagram of the poles. In this paper we present a new algorithm that approximates the medial axis straight from the Voronoi diagram in a scale and density independent manner with convergence guarantees. The advantage is that, unlike for others, one does not need to fine tune any parameter for this algorithm. We present extensive experimental evidences in support of our claims.

REFERENCES

• 1: Nina Amenta , Sunghee Choi , Ravi Krishna Kolluri, The power crust, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.249-266, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376986]
• 2: D. Attali and J.-O. Lachaud. Delaunay conforming iso-surface, skeleton extraction and noise removal. Comput. Geom.: Theory Appl., 2001, to appear
• 3: Dominique Attali , Annick Montanvert, Computing and simplifying 2D and 3D continuous skeletons, Computer Vision and Image Understanding, v.67 n.3, p.261-273, Sept. 1997 [doi>10.1006/cviu.1997.0536]
• 4: Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995 [doi>10.1145/218380.218424]
• 5: F. Bernardini and C. L. Bajaj. Sampling and reconstructing manifolds using $alpha$-shapes. it Proc. 9th Canadian Conf. Comput. Geom.,(1997), 193--198
• 6: Chandrajit L. Bajaj , Edward J. Coyle , Kwun-Nan Lin, Arbitrary topology shape reconstruction from planar cross sections, Graphical Models and Image Processing, v.58 n.6, p.524-543, Nov. 1996 [doi>10.1006/gmip.1996.0044]
• 7: Gill Barequet , Micha Sharir, Piecewise-linear interpolation between polygonal slices, Computer Vision and Image Understanding, v.63 n.2, p.251-272, March 1996 [doi>10.1006/cviu.1996.0018]
• 8: Sylvain Bouix , Kaleem Siddiqi, Divergence-Based Medial Surfaces, Proceedings of the 6th European Conference on Computer Vision-Part I, p.603-618, June 26-July 01, 2000
• 9: Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984 [doi>10.1145/357346.357349]
• 10: Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336208]
• 11: Jonathan W. Brandt, Convergence and continuity criteria for discrete approximations of the continuous planar skeleton, CVGIP: Image Understanding, v.59 n.1, p.116-124, Jan. 1994 [doi>10.1006/ciun.1994.1007]
• 12: Jonathan W. Brandt , V. Ralph Algazi, Continuous skeleton computation by Voronoi diagram, CVGIP: Image Understanding, v.55 n.3, p.329-338, May 1992 [doi>10.1016/1049-9660(92)90030-7]
• 13: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 14: Tim Culver , John Keyser , Dinesh Manocha, Accurate computation of the medial axis of a polyhedron, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.179-190, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304030]
• 15: Tamal K. Dey , Joachim Giesen, Detecting undersampling in surface reconstruction, Proceedings of the seventeenth annual symposium on Computational geometry, p.257-263, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378682]
• 16: T. K. Dey, J. Giesen and J. Hudson. Decimating samples for mesh simplification. Proc. 13th Canadian Conf. Comput. Geom. (2001), 85--88
• 17: T. K. Dey and W. Zhao. Approximating medial axis from the Voronoi diagram with convergence guarantee. Manuscript, 2001. http://www.cis.ohio-state.edu/$sim$tamaldey/paper/medial.pdf
• 18: Herbert Edelsbrunner, Shape Reconstruction with Delaunay Complex, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.119-132, April 20-24, 1998
• 19: H. Edelsbrunner, D. G. Kirkpatrick and R. Seidel. On the shape of a set of points in the plane. IEEE Trans. Information Theory, bf 29, (1983), 551--559
• 20: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 21: Herbert Edelsbrunner , Nimish R. Shah, Triangulating topological spaces, Proceedings of the tenth annual symposium on Computational geometry, p.285-292, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178010]
• 22: M. Etzion and A. Rappoport. Computing Voronoi skeletons of a 3D polyhedron by space subdivision. Tech. Report, Hebrew University, 1999
• 23: P. J. Giblin and B. B. Kimia. A formal classification of 3D medial axis points and their local geometry. Proc. Computer Vision and Pattern Recognition (CVPR), 2000
• 24: Geomview tt http://www.geomview.org
• 25: L. Guibas, R. Holleman and L. E. Kavraki. A probabilistic roadmap planner for flexible objects with a workspace medial axis based sampling approach. Proc. IEEE/RSJ Intl. Conf. Intelligent Robots and Systems, 1999
• 26: H. N. Gursoy and N. M. Patrikalakis. Automated interrogation and adaptive subdivision of shape using medial axis transform. Advances in Engineering Software 13 (1991), 287--302
• 27: C. Hoffman. How to construct the skeleton of CSG objects. The Mathematics of Surfaces, IVA, Bowyer and J. Davenport Eds., Oxford Univ. Press, 1990
• 28: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 29: Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996 [doi>10.1145/231731.231732]
• 30: C. Wayne Niblack , Phillip B. Gibbons , David W. Capson, Generating skeletons and centerlines from the distance transform, CVGIP: Graphical Models and Image Processing, v.54 n.5, p.420-437, Sept. 1992 [doi>10.1016/1049-9652(92)90026-T]
• 31: R. L. Ogniewicz. Skeleton-space: A multiscale shape description combining region and boundary information. Proc. Computer Vision and Pattern Recognition, (1994), 746--751
• 32: Damian J. Sheehy , Cecil G. Armstrong , Desmond J. Robinson, Shape Description By Medial Surface Construction, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.62-72, March 1996 [doi>10.1109/2945.489387]
• 33: A. Sheffer, M. Etzion, A. Rappoport and M. Bercovier. Hexahedral mesh generation using the embedded Voronoi graph. Engineering Comput. 15 (1999), 248--262
• 34: Evan C. Sherbrooke , Nicholas M. Patrikalakis , Erik Brisson, An Algorithm for the Medial Axis Transform of 3D Polyhedral Solids, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.44-61, March 1996 [doi>10.1109/2945.489386]
• 35: Duane W. Storti , George M. Turkiyyah , Mark A. Ganter , Chek T. Lim , Derek M. Stal, Skeleton-based modeling operations on solids, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.141-154, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267771]
• 36: G. M. Turkiyyah, D. W. Storti, M. Ganter, H. Chen and M. Vimawala. An accelerated triangulation method for computing the skeletons of free-form solid models. Computer Aided Design 29 (1997), 5--19
• 37: Marek Teichmann , Seth Teller, Assisted articulation of closed polygonal models, ACM SIGGRAPH 98 Conference abstracts and applications, p.254, July 19-24, 1998, Orlando, Florida, United States [doi>10.1145/280953.282217]
• 38: F.-E. Wolter. Cut locus & medial axis in global shape interrogation & representation. MIT Design Laboratory Memorandum 92--2, 1992
• 39: www.cgal.org
• 40: www.cis.ohio-state.edu/~tamaldey/cocone.html

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
medial axis, point cloud, voronoi diagram