Andreas Bærentzen and Eva Rotenberg
Dept. of Applied Mathematics and Computer Science,
Technical University of Denmark
ACM Transactions on Graphics 40.5 (Sept. 2021)
We propose a new algorithm for curve skeleton computation which 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 is 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.
The local separator skeletonization method is implemented in the GEL library. Below an example of its use based on PyGEL (Python bindings for GEL)
from pygel3d import hmesh, graph, jupyter_display as jd
jd.set_export_mode(True)
m = hmesh.load('as.obj')
jd.display(m)
g = graph.from_mesh(m)
skel = graph.LS_skeleton(g)
jd.display(skel)
Computed 2476 separators Found 2476 separators Packed 94 separators Finding separators: 1.64388 Packing separators: 0.511532