Skeletonization via Local Separators
- 24 September 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 40 (5), 1-18
- https://doi.org/10.1145/3459233
Abstract
We propose a new algorithm for curve skeleton computation that differs from previous algorithms by being based on the notion of local separators. The main benefits of this approach are that it is able to capture relatively fine details and that it works robustly on a range of shape representations. Specifically, our method works on shape representations that can be construed as spatially embedded graphs. Such representations include meshes, volumetric shapes, and graphs computed from point clouds. We describe a simple pipeline where geometric data are initially converted to a graph, optionally simplified, local separators are computed and selected, and finally a skeleton is constructed. We test our pipeline on polygonal meshes, volumetric shapes, and point clouds. Finally, we compare our results to other methods for skeletonization according to performance and quality.Keywords
Funding Information
- Independent Research Fund Denmark (2020-2023 (9131-00044B), 2018-2021 (8021-00249B))
- Villum Foundation (37507)
This publication has 40 references indexed in Scilit:
- Curve skeleton extraction by coupled graph contraction and surface clusteringGraphical Models, 2013
- Graph-based representations of point cloudsGraphical Models, 2011
- Curve skeleton extraction from incomplete point cloudACM Transactions on Graphics, 2009
- Skeleton extraction by mesh contractionACM Transactions on Graphics, 2008
- Robust on-line computation of Reeb graphsACM Transactions on Graphics, 2007
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivityJournal of the ACM, 2001
- Vojtěch Jarnı́k's work in combinatorial optimizationDiscrete Mathematics, 2001
- An optimal algorithm for approximate nearest neighbor searching fixed dimensionsJournal of the ACM, 1998
- Building Skeleton Models via 3-D Medial Surface Axis Thinning AlgorithmsCVGIP: Graphical Models and Image Processing, 1994
- Convolution surfacesACM SIGGRAPH Computer Graphics, 1991