Feature-Varying Skeletonization


Chris Willcocks, Frederick Li

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

This was my first paper!

Given an input dense 3D mesh, it presents an extremely simple algorithm to iterateively contract the mesh into a skeleton.

Basically, 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 iterateively 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.

Key Advantages:

• Simplicity
• Speed
• Low parameters

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 our 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},
bibsource = {dblp computer science bibliography, http://dblp.org},
}