Approximate medial axis for CAD models

ABSTRACT

Several research have pointed out the potential use of the medial axis in various geometric modeling applications. The computation of the medial axis for a three dimensional shape often becomes the major bottleneck in these applications. Towards this end, in a recent work, we suggested an efficient algorithm that approximates the medial axis of a shape from a point sample. The input to this algorithm is only the coordinates of the sample points. As a result the approximation quality is limited by the input sample density. However, in geometric applications involving CAD models, the surfaces from which samples need to be derived are known. In this paper we present heuristics to take advantage of this a priori knowledge in our medial axis approximation algorithm. The quality of the approximation achieved by the method is surprisingly high as our experimental results exhibit.

REFERENCES

• 1: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom. 22 (1999), 481--504.
• 2: N. Amenta, S. Choi and R. K. Kolluri. The power crust, unions of balls, and the medial axis transform. Comput. Geom. Theory and Applications 19 (2001), 127--153.
• 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: 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]
• 5: 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]
• 6: 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]
• 7: 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]
• 8: 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), 566--575.
• 9: 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.
• 10: C. Hoffman. How to construct the skeleton of CSG objects. The Mathematics of Surfaces, IVA, Bowyer and J. Davenport Eds., Oxford Univ. Press, 1990.
• 11: R. L. Ogniewicz. Skeleton-space: A multiscale shape description combining region and boundary information. Proc. Computer Vision and Pattern Recognition, (1994), 746--751.
• 12: 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]
• 13: 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]
• 14: F.-E. Wolter. Cut locus & medial axis in global shape interrogation & representation. MIT Design Laboratory Memorandum 92-2, 1992.
• 15: www.cgal.org.
• 16: 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
        I.4.10 Image Representation
      I.4.5 Reconstruction

General Terms:
Algorithms

Keywords:
Voronoi diagram, medial axis, point cloud