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

ABSTRACT

Applications of of the medial axis have been limited because of its instability and algebraic complexity. In this paper, we use a simplification of the medial axis, the θ-SMA, that is parameterized by a separation angle (θ) formed by the vectors connecting a point on the medial axis to the closest points on the boundary. We present a formal characterization of the degree of simplification of the θ-SMA as a function of θ, and we quantify the degree to which the simplified medial axis retains the features of the original polyhedron.We present a fast algorithm to compute an approximation of the θ-SMA. It is based on a spatial subdivision scheme, and uses fast computation of a distance field and its gradient using graphics hardware. The complexity of the algorithm varies based on the error threshold that is used, and is a linear function of the input size. We have applied this algorithm to approximate the SMA of models with tens or hundreds of thousands of triangles. Its running time varies from a few seconds, for a model consisting of hundreds of triangles, to minutes for highly complex models.

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: Dominique Attali , Jean-Daniel Boissonnat, A linear bound on the complexity of the delaunay triangulation of points on polyhedral surfaces, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566304]
• 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: J. August, A. Tannenbaum, and S. Zucker. On the evolution of the skeleton. In Proc. Int. Conf. on Computer Vision, 1999.
• 5: H. Blum. A transformation for extracting new descriptors of shape. In W. Wathen-Dunn, editor, Models for the Perception of Speech and Visual Form, pages 362--380. MIT Press, 1967.
• 6: 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]
• 7: 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]
• 8: Ching-Shoei Chiang, The Euclidean distance transform, Purdue University, West Lafayette, IN, 1992
• 9: H. I. Choi, S. W. Choi, and H. P. Moon. Mathematical theory of medial axis transform. Pacific J. Math., 181(1):56--88, 1997.
• 10: Sung Woo Choi , Hans-Peter Seidel, Linear onesided stability of MAT for weakly injective 3D domain, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566332]
• 11: 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]
• 12: P.-E. Danielsson. Euclidean distance mapping. Computer Graphics and Image Processing, 14:227--248, 1980.
• 13: Tamal K. Dey , Wulue Zhao, Approximate medial axis as a voronoi subcomplex, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566333]
• 14: Tamal K. Dey , Wulue Zhao, Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee, Proceedings of the 10th Annual European Symposium on Algorithms, p.387-398, September 17-21, 2002
• 15: D. Dutta and C. M. Hoffmann. A geometric investigation of the skeleton of CSG objects. In Proc. ASME Conf. Design Automation, 1990.
• 16: Michal Etzion , Ari Rappoport, Computing the Voronoi diagram of a 3-D polyhedron by separate computation of its symbolic and geometric parts, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.167-178, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304029]
• 17: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 18: C. M. Hoffmann. How to construct the skeleton of CSG objects. In Proc. 4th IMA Conf. on The Mathematics of Surfaces, Bath, UK, 1990. Oxford University Press.
• 19: Louisa Lam , Seong-Whan Lee , Ching Y. Suen, Thinning Methodologies-A Comprehensive Survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.9, p.869-885, September 1992 [doi>10.1109/34.161346]
• 20: E. Larsen, S. Gottschalk, M. Lin, and D. Manocha. Fast proximity queries with swept sphere volumes. Technical Report TR99-018, Dept. Comput. Sci., University of North Carolina, 1999.
• 21: V. Milenkovic. Robust construction of the Voronoi diagram of a polyhedron. In Proc. 5th Canad. Conf. Comput. Geom., pages 473--478, 1993.
• 22: Ingemar Ragnemalm, The Euclidean distance transform in arbitrary dimensions, Pattern Recognition Letters, v.14 n.11, p.883-888, Nov. 1993 [doi>10.1016/0167-8655(93)90152-4]
• 23: J. Reddy and G. Turkiyyah. Computation of 3D skeletons using a generalized Delaunay triangulation technique. Computer-Aided Design, 27:677--694, 1995.
• 24: Evan C. Sherbrooke , Nicholas M. Patrikalakis , Erik Brisson, Computation of the Medial Axis Transform of 3-D polyhedra, Proceedings of the third ACM symposium on Solid modeling and applications, p.187-200, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218059]
• 25: Kaleem Siddiqi , Sylvain Bouix , Allen Tannenbaum , Steven W. Zucker, The Hamilton-Jacobi Skeleton, Proceedings of the International Conference on Computer Vision-Volume 2, p.828, September 20-25, 1999
• 26: 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]
• 27: Martin Styner , Guido Gerig , Sarang Joshi , Stephen Pizer, Automatic and Robust Computation of 3D Medial Models Incorporating Object Variability, International Journal of Computer Vision, v.55 n.2-3, p.107-122, November-December 2003 [doi>10.1023/A:1026378916288]
• 28: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 29: 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(1):5--19, Jan. 1997.
• 30: J. Vleugels and M. Overmars. Approximating generalized Voronoi diagrams in any dimension. Technical Report UU-CS-1995-14, Dept. Comput. Sci., Utrecht University, 1995.
• 31: Steven A. Wilmarth , Nancy M. Amato , Peter F. Stiller, Motion planning for a rigid body using random networks on the medial axis of the free space, Proceedings of the fifteenth annual symposium on Computational geometry, p.173-180, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304967]
• 32: Y. Y. Zhang and P. S. P. Wang. Analytical comparison of thinning algorithms. Int. J. Pattern Recognit. Artif. Intell., 7:1227--1246, 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
        I.4.10 Image Representation
      I.4.5 Reconstruction

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
distance field, medial axis