Premium
Fast Force Field Approximation and its Application to Skeletonization of Discrete 3D Objects
Author(s) -
Brunner D.,
Brunnett G.
Publication year - 2008
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2008.01123.x
Subject(s) - skeletonization , force field (fiction) , lattice (music) , computer science , mathematics , boundary (topology) , distance transform , medial axis , voxel , algorithm , topology (electrical circuits) , geometry , mathematical analysis , artificial intelligence , physics , image (mathematics) , combinatorics , acoustics
In this paper we present a novel method to approximate the force field of a discrete 3d object with a time complexity that is linear in the number of voxels. We define a rule, similar to the distance transform, to propagate forces associated with boundary points into the interior of the object. The result of this propagation depends on the order in which the points of the object are processed. Therefore we analyze how to obtain an order‐invariant approximation formula. With the resulting formula it becomes possible to approximate the force field and to use its features for a fast and topology preserving skeletonization. We use a thinning strategy on the body‐centered cubic lattice to compute the skeleton and ensure that critical points of the force field are not removed. This leads to improved skeletons with respect to the properties of centeredness and rotational invariance.