Dynamic Skeletonization via Variational Medial Axis Sampling
Article No.: 66, Pages 1 - 11
Abstract
We present a novel method for computing a discrete skeleton from a shape represented by a point cloud or triangle mesh. Inspired by variational shape approximation, our approach optimizes the partitioning of the input shape by minimizing an error metric defined between medial axis samples (medial spheres) and their corresponding clusters. The metric combines plane-sphere and point-sphere distance terms and the balance between these two terms enables coarse skeletons to capture the main geometric features while denser skeletons achieve a uniform distribution of medial axis samples. The sampling of the medial axis is progressively refined through an automatic process that splits medial spheres with the highest errors. Our method’s efficiency also allows users to dynamically add or remove medial axis samples locally while the optimization process continuously updates the underlying partition. Skeleton connectivity is efficiently constructed by computing the dual of the optimized shape partition. Unlike previous approaches, our method does not rely on a predefined set of candidate spheres or an initial medial axis representation.
Supplemental Material
MP4 File
Supplementary video
- Download
- 65.82 MB
References
[1]
Nina Amenta and Marshall Bern. 1998. Surface reconstruction by Voronoi filtering. In Proceedings of the Fourteenth Annual Symposium on Computational Geometry (Minneapolis, Minnesota, USA) (SCG ’98). Association for Computing Machinery, New York, NY, USA, 39–48.
[2]
Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. 2001. The power crust. In Proceedings of the sixth ACM symposium on Solid modeling and applications. 249–266.
[3]
Frédéric Chazal and André Lieutier. 2005. The “λ -medial axis”. Graphical models 67, 4 (2005), 304–331.
[4]
Mattéo Clémot and Julie Digne. 2023. Neural skeleton: Implicit neural representation away from the surface. Computers & Graphics 114 (2023), 368–378.
[5]
David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2004. Variational shape approximation. In ACM SIGGRAPH 2004 Papers. 905–914.
[6]
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.
[7]
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. Computer Graphics Forum 41, 2 (2022), 419–432.
[8]
Noura Faraj, Jean-Marc Thiery, and Tamy Boubekeur. 2013. Progressive medial axis filtration. In SIGGRAPH Asia 2013 Technical Briefs. 1–4.
[9]
Mark Foskey, Ming C Lin, and Dinesh Manocha. 2003. Efficient computation of a simplified medial axis. In Proceedings of the eighth ACM symposium on Solid modeling and applications. 96–107.
[10]
Michael Garland and Paul S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques(SIGGRAPH ’97). ACM Press/Addison-Wesley Publishing Co., USA, 209–216.
[11]
Mengyuan Ge, Junfeng Yao, Baorong Yang, Ningna Wang, Zhonggui Chen, and Xiaohu Guo. 2023. Point2MM: Learning medial mesh from point clouds. Computers & Graphics 115 (2023), 511–521.
[12]
Joachim Giesen, Balint Miklos, Mark Pauly, and Camille Wormser. 2009. The scale axis transform. In Proceedings of the twenty-fifth annual symposium on Computational geometry. 106–115.
[13]
Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.
[14]
Q. Huangfu and J.A.J. Hall. 2018. Parallelizing the dual revised simplex method. Mathematical Programming Computation 10, 1 (2018), 119–142.
[15]
Pierre Kraemer, Sylvain Thery, et al. 2020. CGoGN. https://github.com/cgogn/CGoGN_3.
[16]
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), 17 pages.
[17]
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.
[18]
Cheng Lin, Changjian Li, Yuan Liu, Nenglun Chen, Yi-King Choi, and Wenping Wang. 2021. Point2skeleton: Learning skeletal representations from point clouds. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 4277–4286.
[19]
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.
[20]
Lin Lu, Yi-King Choi, Wenping Wang, and Myung-Soo Kim. 2007. Variational 3D Shape Segmentation for Bounding Volume Computation. Computer Graphics Forum (2007).
[21]
Jaehwan Ma, Sang Won Bae, and Sunghee Choi. 2012. 3D medial axis point approximation using nearest neighbors and the normal field. Vis. Comput. 28, 1 (jan 2012), 7–19.
[22]
Balint Miklos, Joachim Giesen, and Mark Pauly. 2010. Discrete scale axis representations for 3D geometry. In ACM SIGGRAPH 2010 papers. 1–10.
[23]
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.
[24]
William Roshan Quadros. 2014. LayTracks3D: A New Approach to Meshing General Solids using Medial Axis Transform. Procedia Engineering 82 (2014), 72–87. 23rd International Meshing Roundtable (IMR23).
[25]
Martin Skrodzki, Eric Zimmermann, and Konrad Polthier. 2020. Variational shape approximation of point set surfaces. Computer Aided Geometric Design 80 (2020), 101875.
[26]
Avneesh Sud, Mark Foskey, and Dinesh Manocha. 2005. Homotopy-preserving medial axis simplification. In Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling (Cambridge, Massachusetts) (SPM ’05). Association for Computing Machinery, New York, NY, USA, 39–50.
[27]
Feng Sun, Yi-King Choi, Yizhou Yu, and Wenping Wang. 2015. Medial meshes–a compact and accurate representation of medial axis transform. IEEE transactions on visualization and computer graphics 22, 3 (2015), 1278–1290.
[28]
Andrea Tagliasacchi, Thomas Delame, Michela Spagnuolo, Nina Amenta, and Alexandru Telea. 2016. 3D Skeletons: A State-of-the-Art Report. Computer Graphics Forum 35, 2 (2016), 573–597.
[29]
Jean-Marc Thiery, Émilie Guy, and Tamy Boubekeur. 2013. Sphere-meshes: Shape approximation using spherical quadric error metrics. ACM Transactions on Graphics (TOG) 32, 6 (2013), 1–12.
[30]
P. Viville, P. Kraemer, and D. Bechmann. 2023. Meso-Skeleton Guided Hexahedral Mesh Design. Computer Graphics Forum 42, 7 (2023), e14932. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.14932
[31]
Ningna Wang, Hui Huang, Shibo Song, Bin Wang, Wenping Wang, and Xiaohu Guo. 2024b. MATTopo: Topology-preserving Medial Axis Transform with Restricted Power Diagram. arXiv preprint arXiv:https://arXiv.org/abs/2403.18761 (2024).
[32]
Ningna Wang, Bin Wang, Wenping Wang, and Xiaohu Guo. 2022. Computing medial axis transform with feature preservation via restricted power diagram. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–18.
[33]
Zimeng Wang, Zhiyang Dou, Rui Xu, Cheng Lin, Yuan Liu, Xiaoxiao Long, Shiqing Xin, Taku Komura, Xiaoming Yuan, and Wenping Wang. 2024a. Coverage Axis++: Efficient Inner Point Selection for 3D Shape Skeletonization. arxiv:https://arXiv.org/abs/2401.12946 [cs.CV]
[34]
Jianhua Wu and Leif Kobbelt. 2005. Structure Recovery via Hybrid Variational Surface Approximation. In Comput. Graph. Forum, Vol. 24. 277–284.
[35]
Dong‐Ming Yan, Wenping Wang, Yang Liu, and Zhouwang Yang. 2012. Variational mesh segmentation via quadric surface fitting. Comput. Aided Des. 44 (2012), 1072–1082. https://api.semanticscholar.org/CorpusID:16945984
[36]
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 Proceedings of the Symposium on Geometry Processing (Berlin, Germany) (SGP ’09). Eurographics Association, Goslar, DEU, 1445–1454.
[37]
Baorong Yang, Junfeng Yao, and Xiaohu Guo. 2018. DMAT: Deformable Medial Axis Transform for Animated Mesh Approximation. Computer Graphics Forum 37, 7 (2018), 301–311. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.13569
[38]
Baorong Yang, Junfeng Yao, Bin Wang, Jianwei Hu, Yiling Pan, Tianxiang Pan, Wenping Wang, and Xiaohu Guo. 2020. P2MAT-NET: Learning medial axis transform from sparse point clouds. Computer Aided Geometric Design 80 (2020), 101874.
[39]
Tong Zhao, Laurent Busé, David Cohen-Steiner, Tamy Boubekeur, Jean-Marc Thiery, and Pierre Alliez. 2023. Variational Shape Reconstruction via Quadric Error Metrics. In ACM SIGGRAPH 2023 Conference Proceedings (, Los Angeles, CA, USA,) (SIGGRAPH ’23). Association for Computing Machinery, New York, NY, USA, Article 45, 10 pages.
Index Terms
- Dynamic Skeletonization via Variational Medial Axis Sampling
Recommendations
Medial-axis-driven shape deformation with volume preservation
The medial axis is a natural skeleton for shapes. However, it is rarely used in the existing skeleton-based shape deformation techniques. In this paper, we propose a novel medial-axis-driven skin surface deformation algorithm with volume preservation ...
Spectral Analysis on Medial Axis of 2D Shapes
Shape analysis finds many important applications in shape understanding, matching and retrieval. Among the various shape analysis methods, spectral shape analysis aims to study the spectrum of the Laplace-Beltrami operator of some well-designed shape-...
Transitions of the 3D Medial Axis under a One-Parameter Family of Deformations
The instabilities of the medial axis of a shape under deformations have long been recognized as a major obstacle to its use in recognition and other applications. These instabilities, or transitions, occur when the structure of the medial axis graph ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2024
1620 pages
Copyright © 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 03 December 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SA '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 178 of 869 submissions, 20%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 366Total Downloads
- Downloads (Last 12 months)366
- Downloads (Last 6 weeks)366
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format