Homotopy-preserving medial axis simplification

ABSTRACT

We present a novel algorithm to compute a simplified medial axis of a polyhedron. Our simplification algorithm tends to remove unstable features of Blum's medial axis. Moreover, our algorithm preserves the topological structure of the original medial axis and ensures that the simplified medial axis has the same homotopy type as Blum's medial axis. We use the separation angle formed by connecting a point on the medial axis to closest points on the boundary as a measure of the stability of the medial axis at the point. The medial axis is decomposed into its parts that are the sheets, seams and junctions. We present a stability measure of each part of the medial axis based on separation angles and examine the relation between the stability measures of adjacent parts. Our simplification algorithm uses iterative pruning of the parts based on efficient local tests. We have applied the algorithm to compute a simplified medial axis of complex models with tens of thousands of triangles and complex topologies.

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: Attali, D., Boissonat, J.-D., and Edelsbrunner, H. 2004. Stability and computation of the medial axis. In Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration. Springer-Verlag.
• 3: Robert Blanding , Cole Brooking , Mark Ganter , Duane Storti, A skeletal-based solid editor, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.141-150, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304026]
• 4: Blum, H., and Nagel, R. 1978. Shape description using weighted symmetric axis features. Pattern Recognition 10, 167--180.
• 5: Blum, H. 1967. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Form, W. Wathen-Dunn, Ed. MIT Press, 362--380.
• 6: Chazal, F., and Lieutier, A. 2004. Stability and homotopy of a subset of the medial axis. In Proc. ACM Symposium on Solid Modeling and Applications.
• 7: F. Chazal , R. Soufflet, Stability and Finiteness Properties of Medial Axis and Skeleton, Journal of Dynamical and Control Systems, v.10 n.2, p.149-170, April 2004 [doi>10.1023/B:JODS.0000024119.38784.ff]
• 8: 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]
• 9: Culver, T. 2000. Accurate Computation of the Medial Axis of a Polyhedron. PhD thesis, Department of Computer Science, University of North Carolina at Chapel Hill.
• 10: 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]
• 11: Dimitrov, P., Damon, J. N., and Siddiqi, K. 2003. Flux invariants for shape. In International Conference on Computer Vision and Pattern Recognition.
• 12: Du, H., and Qin, H. 2004. Medial axis extraction and shape manipulation of solid objects using parabolic PDEs. In Proc. ACM Symposium on Solid Modeling and Applications.
• 13: Michal Etzion , Ari Rappoport, Computing Voronoi skeletons of a 3-D polyhedron by space subdivision, Computational Geometry: Theory and Applications, v.21 n.3, p.87-120, March, 2002 [doi>10.1016/S0925-7721(01)00056-6 ]
• 14: Foskey, M., Garber, M., Lin, M., and Manocha, D. 2001. A voronoi-based hybrid planner. Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems.
• 15: Mark Foskey , Ming C. Lin , Dinesh Manocha, Efficient computation of a simplified medial axis, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781623]
• 16: Giblin, P., and Kimia, B. 2000. A formal classification of 3D medial axis points and their local geometry. In Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 566--573.
• 17: Ron Kimmel , Doron Shaked , Nahum Kiryati , Alfred M. Bruckstein, Skeletonization via distance maps and level sets, Computer Vision and Image Understanding, v.62 n.3, p.382-391, Nov. 1995 [doi>10.1006/cviu.1995.1062 ]
• 18: Kruse, B. 1991. An exact sequential Euclidean distance algorithm with application to skeletonizing. In 7th Scandinavian Conference on Image Analysis (SCIA '91), 517--524.
• 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: Frederic F. Leymarie , Benjamin B. Kimia, The Shock Scaffold for Representing 3D Shape, Proceedings of the 4th International Workshop on Visual Form, p.216-228, May 28-30, 2001
• 21: André Lieutier, Any open bounded subset of Rⁿ has the same homotopy type than its medial axis, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781620]
• 22: Malandain, G., and Fernández-Vidal, S. 1998. Euclidean skeletons. Image and Vision Computing 16, 317--327.
• 23: Meyer, F. 1979. Cytologie quantitative et morphologie Mathématique. PhD thesis, École des Mines.
• 24: Milenkovic, V. 1993. Robust construction of the Voronoi diagram of a polyhedron. In Proc. 5th Canad. Conf. Comput. Geom., 473--478.
• 25: M. Naef O. Kuebler G. Szekely , R. Kikinis , M. E. Shenton, Characterization and Recognition of 3D Organ Shape in Medical Image Analysis Using Skeletonization, Proceedings of the 1996 Workshop on Mathematical Methods in Biomedical Image Analysis (MMBIA '96), p.139, June 21-22, 1996
• 26: Ogniewicz, R. L., and Kübler, O. 1995. Hierarchic Voronoi skeletons. Pattern Recognition 28, 3, 343--359.
• 27: Stephen M. Pizer , Kaleem Siddiqi , Gabor Székely , James N. Damon , Steven W. Zucker, Multiscale Medial Loci and Their Properties, International Journal of Computer Vision, v.55 n.2-3, p.155-179, November-December 2003
• 28: Reddy, J., and Turkiyyah, G. 1995. Computation of 3D skeletons using a generalized Delaunay triangulation technique. Comput. Aided Design 27, 9, 677--694.
• 29: Shaham, A., Shamir, A., and Cohen-or, D. 2004. Medial axis based solid representation. In Proc. ACM Symposium on Solid Modeling and Applications.
• 30: D. J. Sheehy , C. G. Armstrong , D. J. Robinson, Computing the medial surface of a solid from a domain Delaunay triangulation, Proceedings of the third ACM symposium on Solid modeling and applications, p.201-212, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218062]
• 31: Sheffer, A., Etzion, M., Rappoport, A., and Bercovier, M. 1998. Hexahedral mesh generation using the embedded voronoi graph. 7th International Meshing Roundtable, 347--364.
• 32: 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 ]
• 33: Kaleem Siddiqi , Benjamin B. Kimia , Chi-Wang Shu, Geometric shock-capturing eno schemes for subpixel interpolation, computation and curve evolution, Graphical Models and Image Processing, v.59 n.5, p.278-301, Nov. 1997 [doi>10.1006/gmip.1997.0438 ]
• 34: Kaleem Siddiqi , Sylvain Bouix , Allen Tannenbaum , Steven W. Zucker, Hamilton-Jacobi Skeletons, International Journal of Computer Vision, v.48 n.3, p.215-231, July-August 2002 [doi>10.1023/A:1016376116653 ]
• 35: Spanier, E. H. 1989. Algebraic Topology. Springer.
• 36: Sud, A., and Manocha, D. 2005. A simple algorithm for bounded-error approximation of voronoi diagrams of 3D polygonal models. Tech. rep., University of North Carolina-Chapel Hill.
• 37: Krishnan Suresh, Automating the CAD/CAE dimensional reduction process, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781621]
• 38: Roger Tam , Wolfgang Heidrich, Shape Simplification Based on the Medial Axis Transform, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.63, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250410]
• 39: 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]
• 40: Vleugels, J., and Overmars. M. 1995. Approximating generalized Voronoi diagrams in any dimension. Tech. Rep. UU-CS-1995--14, Department of Computer Science, Utrecht University.
• 41: Yang, Y., Brock, O., and Moll, R. N. 2004. Efficient and robust computation of an approximated medial axis. In Proc. ACM Symposium on Solid Modeling and Applications, 15--24.
• 42: Zhang, Y. Y., and Wang, P. S. P. 1993. Analytical comparison of thinning algorithms. Int. J. Pattern Recognit. Artif. Intell. 7, 1227--1246.

INDEX TERMS

Keywords:
homotopy, medial axis, separation angle, simplification, voronoi diagram