Constructing shape skeletons of 3d objects using generalized voronoi

Abstract

Starting with a solid model of a 3D object, an accurate skeleton is produced by minimizing internal and edge errors of an initial approximate skeleton. To produce the initial approximate skeleton, the boundary of the solid is densely sampled to obtain a set of surface data points. Delaunay triangulation is performed on the surface data points and exterior and spurious tetrahedra are removed, leaving substantially interior tetrahedra. Circumspheres are constructed that enclose the tetrahedra, and the centers of the circumspheres are connected based on tetrahedra adjacency, to form a Voronoi diagram. Closed Voronoi cells are identified comprising the initial approximate skeleton. The position of skeleton interior vertices are then adjusted to minimize their error, producing a refined polygonal approximation of the skeleton interior geometry. Positions of the skeleton edge vertices are adjusted to minimize the edge error, yielding an accurate polygonal approximation of the skeleton.