[back to blog]

Feature-varying skeletonization

Intuitive control over the target feature size and output skeleton topology

Click to go to full publication on Springer Link.

Abstract

Current skeletonization algorithms strive to produce a single centered result which is homotopic and insensitive to surface noise. However, this traditional approach may not well capture the main parts of complex models, and may even produce poor results for applications such as animation. Instead, we approximate model topology through a target feature size ω, where undesired features smaller than ω are smoothed, and features larger than ω are retained into groups called bones. This relaxed feature-varying strategy allows applications to generate robust and meaningful results without requiring additional parameter tuning, even for damaged, noisy, complex, or high genus models.

Overview

Given an input dense 3D mesh, it presents an intuitive algorithm to iteratively contract the mesh into a skeleton.

Simply, you have two forces:

1. You iteratively smooth the mesh, by moving the vertices to their average location in their original one-ring neighbourhood.

2. You iteratively merge the mesh, by moving the vertices to the average position of any nearby vertices within some fixed Euclidean distance ω.

   • For very simple implementations, you can store vertex id's in a grid and fetch nearby grid cells; it works more-or-less the same.

The final force that contracts the mesh is a simple linear interpolation between 1. and 2. governed by the one-ring neighbourhood surface area.

While there are now better ways to generate curve skeletons, the nice little contribution with this at the time was its simplicity, and that it can make skeletons that are useful for animation with just a single parameter to adjust.

It would be nice if this approach could be extended to the imaging domain; I briefly tried expressing similar concepts to the merging and smoothing with convolutions and got some interesting results, but I was unable to stop the skeleton overcontracting. The reason it stops overcontracting in the mesh geometry is because of perhaps an unexpected artifact whereby the vertices get pulled into groups > ω. This is also a limitation of the method, in that the vertices can contract in an unpredictable way impacting the skeleton quality. I haven't thought much about extending this.

Citation

Please cite the paper:

@article{willcocks-2012-feature-varying-skeletonization,
   author    = {Chris G. Willcocks and Frederick W. B. Li},
   title     = {Feature-varying skeletonization - Intuitive control over the target feature size and output skeleton topology},
   journal   = {The Visual Computer},
   volume    = {28},
   number    = {6-8},
   pages     = {775--785},
   year      = {2012},
   url       = {http://dx.doi.org/10.1007/s00371-012-0688-x},
   doi       = {10.1007/s00371-012-0688-x}
}

[return to top]