COMPUTATION OF 3D SKELETONS USING A GENERALIZED DELAUNAY TRIANGULATION TECHNIQUE

The skeletal representation of 3D solids based on the medial axis transform has many applications in engineering. However, these applications are seldom realized, owing to the lack of viable computational techniques for generating skeletons. Such a computational technique, based on a notion of the generalized Voronoi diagram of a set of mixed-dimensional entities, is presented. It is shown that the generalized Voronoi diagram of a set of specific mixed dimensional set derived from the set of boundary entities of a polyhedron is, in fact, the exact skeleton of the polyhedron. Rather than the generalized Voronoi diagram being directly computed, its dual, an abstract Delaunay triangulation, is computed, from which the skeleton can be derived. An approach based on the Voronoi diagram of a well chosen representative point set on the boundary is also discussed as a special case; it is shown that the limitations of this approach are overcome by the generalization developed. Overall, it is argued that this generalization of the Voronoi diagram and the notion of the abstract generalized Delaunay triangulation are useful, and that they provide a viable approach to the computation of skeletons. Finally, details of the implementation, results, and an evaluation are presented.