“Discrete scale axis representations for 3D geometry” by Miklos, Giesen and Pauly

This paper addresses the fundamental problem of computing stable medial representations of 3D shapes. We propose a spatially adaptive classification of geometric features that yields a robust algorithm for generating medial representations at different levels of abstraction. The recently introduced continuous scale axis transform serves as the mathematical foundation of our algorithm. We show how geometric and topological properties of the continuous setting carry over to discrete shape representations. Our method combines scaling operations of medial balls for geometric simplification with filtrations of the medial axis and provably good conversion steps to and from union of balls, to enable efficient processing of a wide variety shape representations including polygon meshes, 3D images, implicit surfaces, and point clouds. We demonstrate the robustness and versatility of our algorithm with an extensive validation on hundreds of shapes including complex geometries consisting of millions of triangles.

1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617–625. Google ScholarDigital Library
2. Amenta, N., and Bern, M. 1998. Surface reconstruction by Voronoi filtering. ACM Symposium on Computational Geometry. Google ScholarDigital Library
3. Amenta, N., and Kolluri, R. K. 2000. Accurate and Efficient Unions of Balls. In ACM Symposium on Computational Geometry, 119–128. Google ScholarDigital Library
4. Amenta, N., and Kolluri, R. K. 2001. The medial axis of a union of balls. Computational Geometry 20, 1–2, 25–37. Google ScholarDigital Library
5. Amenta, N., Choi, S., and Kolluri, R. K. 2001. The power crust, unions of balls, and the medial axis transform. Computational Geometry 19, 2–3, 127–153. Google ScholarDigital Library
6. Attali, D., and Montanvert, A. 1996. Modeling noise for a better simplification of skeletons. In Proceedings of International Conference on Image Processing, 13–16.Google Scholar
7. Attali, D., Boissonnat, J.-D., Edelsbrunner, H., and Boissonnat, J.-D. 2009. Stability and Computation of the Medial Axis — a State-of-the-Art Report. Math. Foundations of Scient. Visualization, Comp. Graphics, and Data Exploration.Google Scholar
8. Belyaev, A., Yoshizawa, S., and Seidel, H.-P. 2007. Skeleton-based Variational Mesh Deformations. Computer Graphics Forum 26, 3, 255–264.Google ScholarCross Ref
9. Blum, H. 1967. A Transformation for Extracting New Descriptors of Shape. Models for the Perception of Speech and Visual Form, 362–380.Google Scholar
10. Boissonnat, J.-D., and Oudot, S. 2005. Provably good sampling and meshing of surfaces. Graph. Models 67, 5, 405–451. Google ScholarDigital Library
11. Bruce, J. W., Giblin, P. J., and Gibson, C. 1985. Symmetry Sets. Proc. of the Royal Society of Edinburgh 101, A, 163–186.Google Scholar
12. Chaussard, J., Couprie, M., and Talbot, H. 2009. A discrete lambda-medial axis. DGCI 5810, 421–433. Google ScholarDigital Library
13. Chazal, F., and Lieutier, A. 2005. The lambda-medial axis. Graph. Models 67, 304–331. Google ScholarDigital Library
14. Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Transactions on Graphics (Proc. SIGGRAPH) 28, 3 (Aug.). Google ScholarDigital Library
15. Choi, H. I., Choi, S. W., and Moon, H. P. 1997. Mathematical Theory Of Medial Axis Transform. Pacific J. Math 181, 57–88.Google ScholarCross Ref
16. Cornea, N. D., Silver, D., and Min, P. 2007. Curve-Skeleton Properties, Applications, and Algorithms. IEEE Transactions on Visualization and Computer Graphics 13, 3, 18. Google ScholarDigital Library
17. Culver, T., Keyser, J., and Manocha, D. 2004. Exact computation of the medial axis of a polyhedron. Computer Aided Geometric Design 21, 1, 65–98. Google ScholarDigital Library
18. Dey, T. K., and Zhao, W. 2004. Approximate medial axis as a Voronoi subcomplex. Computer-Aided Design 36, 2, 195–202.Google ScholarCross Ref
19. Dey, T. K., Woo, H., and Zhao, W. 2003. Approximate medial axis for CAD models. ACM Symposium on Solid and Physical Modeling. Google ScholarDigital Library
20. Foskey, M., Lin, M. C., and Manocha, D. 2003. Efficient computation of a simplified medial axis. ACM Symposium on Solid and Physical Modeling. Google ScholarDigital Library
21. Giesen, J., Miklos, B., Pauly, M., and Wormser, C. 2009. The scale axis transform. Annual Symposium on Computational Geometry, 106–115. Google ScholarDigital Library
22. Pizer, S. M., Siddiqi, K., Szekely, G., Damon, J. N., and Zucker, S. W. 2003. Multiscale Medial Loci and Their Properties. Int. J. Comput. Vision 55, 155–179. Google ScholarDigital Library
23. Pizer, S., Siddiqi, K., and Yushkevich, P. 2008. Medial Representations, vol. 37 of Computational Imaging and Vision. Springer Netherlands, Dordrecht.Google Scholar
24. Podolak, J., Shilane, P., Golovinskiy, A., Rusinkiewicz, S., and Funkhouser, T. 2006. A planar-reflective symmetry transform for 3D shapes. ACM Transactions on Graphics (Proc. SIGGRAPH) 25, 3, 549–559. Google ScholarDigital Library
25. Prasad, L. 1997. Morphological analysis of shapes. CNLS Newsletter 139, 1–18.Google Scholar
26. Rumpf, M., and Telea, A. 2002. A continuous skeletonization method based on level sets. In VISSYM ’02: Proceedings of the symposium on Data Visualisation 2002, 151–ff. Google ScholarDigital Library
27. Siddiqi, K., Bouix, S., Tannenbaum, A., and Zucker, S. W. 2002. Hamilton-Jacobi Skeletons. International Journal of Computer Vision 48, 3 (July), 215–231. Google ScholarDigital Library
28. Stolpner, S., and Whitesides, S. 2009. Medial Axis Approximation with Bounded Error. In International Symposium on Voronoi Diagrams in Science and Engineering. Google ScholarDigital Library
29. Styner, M., Gerig, G., Joshi, S., and Pizer, S. 2003. Automatic and Robust Computation of 3D Medial Models Incorporating Object Variability. Int. J. Comput. Vision 55, 2, 107–122. Google ScholarDigital Library
30. Sud, A., Foskey, M., and Manocha, D. 2005. Homotopypreserving medial axis simplification. In Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling, 39–50. Google ScholarDigital Library
31. Svensson, S. 2001. Reversible surface skeletons of 3d objects by iterative thinning of distance transforms. Digital and image geometry: advanced lectures, 400–411. Google ScholarDigital Library
32. Tam, R., and Heidrich, W. 2003. Shape Simplification Based on the Medial Axis Transform. In IEEE Visualization 2003. Google ScholarDigital Library
33. Ward, A. D., and Hamarneh, G. 2009. The Groupwise Medial Axis Transform for Fuzzy Skeletonization and Pruning. IEEE Transactions on Pattern Analysis and Machine Intelligence 99. Google ScholarDigital Library