“Computing Medial Axis Transform with Feature Preservation via Restricted Power Diagram” by Wang, Wang, Wang and Guo
Conference:
Type(s):
Title:
- Computing Medial Axis Transform with Feature Preservation via Restricted Power Diagram
Session/Category Title: Distances and Matching
Presenter(s)/Author(s):
Abstract:
We propose a novel framework for computing the medial axis transform of 3D shapes while preserving their medial features via restricted power diagram (RPD). Medial features, including external features such as the sharp edges and corners of the input mesh surface and internal features such as the seams and junctions of medial axis, are important shape descriptors both topologically and geometrically. However, existing medial axis approximation methods fail to capture and preserve them due to the fundamentally under-sampling in the vicinity of medial features, and the difficulty to build their correct connections. In this paper we use the RPD of medial spheres and its affiliated structures to help solve these challenges. The dual structure of RPD provides the connectivity of medial spheres. The surfacic restricted power cell (RPC) of each medial sphere provides the tangential surface regions that these spheres have contact with. The connected components (CC) of surfacic RPC give us the classification of each sphere, to be on a medial sheet, a seam, or a junction. They allow us to detect insufficient sphere sampling around medial features and develop necessary conditions to preserve them. Using this RPD-based framework, we are able to construct high quality medial meshes with features preserved. Compared with existing sampling-based or voxel-based methods, our method is the first one that can preserve not only external features but also internal features of medial axes.
References:
1. Ahmed Abdelkader, Chandrajit L Bajaj, Mohamed S Ebeida, Ahmed H Mahmoud, Scott A Mitchell, John D Owens, and Ahmad A Rushdi. 2020. VoroCrust: Voronoi meshing without clipping. ACM Transactions on Graphics (TOG) 39, 3 (2020), 1–16.
2. Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. 2001a. The power crust. In Proceedings of the sixth ACM symposium on Solid modeling and applications. 249–266.
3. Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. 2001b. The power crust, unions of balls, and the medial axis transform. Computational Geometry 19, 2–3 (2001), 127–153.
4. Franz Aurenhammer. 1987. Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16, 1 (1987), 78–96.
5. Gavin Barill, Neil G Dickson, Ryan Schmidt, David IW Levin, and Alec Jacobson. 2018. Fast winding numbers for soups and clouds. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–12.
6. Harry Blum et al. 1967. A transformation for extracting new descriptors of shape. Vol. 43. MIT press Cambridge, MA.
7. Jonathan W Brandt and V Ralph Algazi. 1992. Continuous skeleton computation by Voronoi diagram. CVGIP: Image understanding 55, 3 (1992), 329–338.
8. Frédéric Chazal and André Lieutier. 2005a. Weak feature size and persistent homology: computing homology of solids in Rn from noisy data samples. In The twenty-first annual symposium on Computational geometry (SCG ’05). ACM New York, NY, USA, 255–262.
9. Frédéric Chazal and André Lieutier. 2005b. The “λ-medial axis”. Graphical Models 67, 4 (2005), 304–331.
10. Yang Chen and Gérard Medioni. 1992. Object Modelling by Registration of Multiple Range Images. Image and Vision Computing 10, 3 (1992), 145–155.
11. Tim Culver, John Keyser, and Dinesh Manocha. 2004. Exact computation of the medial axis of a polyhedron. Computer Aided Geometric Design 21, 1 (2004), 65–98.
12. Tamal K Dey, Hyuckje Woo, and Wulue Zhao. 2003. Approximate medial axis for CAD models. In Proceedings of the eighth ACM symposium on Solid modeling and applications. 280–285.
13. Tamal K Dey and Wulue Zhao. 2002. Approximate medial axis as a voronoi subcomplex. In Proceedings of the seventh ACM symposium on Solid modeling and applications. 356–366.
14. Tamal K Dey and Wulue Zhao. 2004. Approximating the medial axis from the Voronoi diagram with a convergence guarantee. Algorithmica 38, 1 (2004), 179–200.
15. Zhiyang Dou, Cheng Lin, Rui Xu, Lei Yang, Shiqing Xin, Taku Komura, and Wenping Wang. 2022. Coverage Axis: Inner Point Selection for 3D Shape Skeletonization. In Computer Graphics Forum, Vol. 41. Wiley Online Library, 419–432.
16. Noura Faraj, Jean-Marc Thiery, and Tamy Boubekeur. 2013. Progressive medial axis filtration. In SIGGRAPH Asia 2013 Technical Briefs. 1–4.
17. Peter Giblin and Benjamin B Kimia. 2004. A formal classification of 3D medial axis points and their local geometry. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 2 (2004), 238–251.
18. Jianwei Hu, Bin Wang, Lihui Qian, Yiling Pan, Xiaohu Guo, Lingjie Liu, and Wenping Wang. 2019. MAT-Net: Medial Axis Transform Network for 3D Object Recognition. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI’19). 774–781.
19. Tao Ju, Qian-Yi Zhou, and Shi-Min Hu. 2007. Editing the topology of 3D models by sketching. ACM Transactions on Graphics (TOG) 26, 3 (2007), 42–es.
20. Sebastian Koch, Albert Matveev, Zhongshi Jiang, Francis Williams, Alexey Artemov, Evgeny Burnaev, Marc Alexa, Denis Zorin, and Daniele Panozzo. 2019. Abc: A big cad model dataset for geometric deep learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 9601–9611.
21. Lei Lan, Ran Luo, Marco Fratarcangeli, Weiwei Xu, Huamin Wang, Xiaohu Guo, Junfeng Yao, and Yin Yang. 2020. Medial Elastics: Efficient and Collision-Ready Deformation via Medial Axis Transform. ACM Trans. Graph. 39, 3, Article 20 (apr 2020).
22. Pan Li, Bin Wang, Feng Sun, Xiaohu Guo, Caiming Zhang, and Wenping Wang. 2015. Q-mat: Computing medial axis transform by quadratic error minimization. ACM Transactions on Graphics (TOG) 35, 1 (2015), 1–16.
23. Cheng Lin, Lingjie Liu, Changjian Li, Leif Kobbelt, Bin Wang, Shiqing Xin, and Wenping Wang. 2022. SEG-MAT: 3D Shape Segmentation Using Medial Axis Transform. IEEE transactions on visualization and computer graphics 28, 6 (2022), 2430–2444.
24. Lu Liu, Erin W Chambers, David Letscher, and Tao Ju. 2010. A simple and robust thinning algorithm on cell complexes. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 2253–2260.
25. Jaehwan Ma, Sang Won Bae, and Sunghee Choi. 2012. 3D medial axis point approximation using nearest neighbors and the normal field. The Visual Computer 28, 1 (2012), 7–19.
26. Balint Miklos, Joachim Giesen, and Mark Pauly. 2010. Discrete scale axis representations for 3D geometry. In ACM SIGGRAPH 2010 papers. 1–10.
27. Victor Milenkovic. 1993. Robust Construction of the Voronoi Diagram of a Polyhedron.. In CCCG, Vol. 93. Citeseer, 473–478.
28. Yiling Pan, Bin Wang, Xiaohu Guo, Hua Zeng, Yuexin Ma, and Wenping Wang. 2019. Q-mat+: An error-controllable and feature-sensitive simplification algorithm for medial axis transform. Computer Aided Geometric Design 71 (2019), 16–29.
29. Stephen M Pizer, Kaleem Siddiqi, Gabor Székely, James N Damon, and Steven W Zucker. 2003. Multiscale medial loci and their properties. International Journal of Computer Vision 55, 2 (2003), 155–179.
30. WR Quadros, K Ramaswami, FB Prinz, and B Gurumoorthy. 2004. LayTracks: a new approach to automated geometry adaptive quadrilateral mesh generation using medial axis transform. International journal for numerical methods in engineering 61, 2 (2004), 209–237.
31. Punam K Saha, Gunilla Borgefors, and Gabriella Sanniti di Baja. 2016. A survey on skeletonization algorithms and their applications. Pattern recognition letters 76 (2016), 3–12.
32. Peter Sampl. 2000. Semi-structured mesh generation based on medial axis. In 9th International Meshing Roundtable. Citeseer.
33. Evan C Sherbrooke, Nicholas M Patrikalakis, and Erik Brisson. 1996. An algorithm for the medial axis transform of 3D polyhedral solids. IEEE transactions on visualization and computer graphics 2, 1 (1996), 44–61.
34. Kaleem Siddiqi and Stephen Pizer. 2008. Medial representations: mathematics, algorithms and applications. Vol. 37. Springer Science & Business Media.
35. André Sobiecki, Andrei Jalba, and Alexandru Telea. 2014. Comparison of curve and surface skeletonization methods for voxel shapes. Pattern Recognition Letters 47 (2014), 147–156.
36. Andrea Tagliasacchi, Thomas Delame, Michela Spagnuolo, Nina Amenta, and Alexandru Telea. 2016. 3d skeletons: A state-of-the-art report. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 573–597.
37. Dong-Ming Yan, Bruno Lévy, Yang Liu, Feng Sun, and Wenping Wang. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. In Computer graphics forum, Vol. 28. Wiley Online Library, 1445–1454.
38. Yajie Yan, David Letscher, and Tao Ju. 2018. Voxel cores: Efficient, robust, and provably good approximation of 3d medial axes. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–13.
39. Yajie Yan, Kyle Sykes, Erin Chambers, David Letscher, and Tao Ju. 2016. Erosion thickness on medial axes of 3D shapes. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–12.
