COMPUTATION OF 3D SKELETONS USING A GENERALIZED DELAUNAY TRIANGULATION TECHNIQUE

The skeletal representation of 3D solids based on the medial axis tran sform has many applications in engineering. However, these application s are seldom realized, owing to the lack of viable computational techn iques for generating skeletons. Such a computational technique, based on a notion of the generalized Voronoi diagram of a set of mixed-dimen sional entities, is presented. It is shown that the generalized Vorono i diagram of a set of specific mixed dimensional set derived from the set of boundary entities of a polyhedron is, in fact, the exact skelet on of the polyhedron. Rather than the generalized Voronoi diagram bein g 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 lim itations of this approach are overcome by the generalization developed . Overall, it is argued that this generalization of the Voronoi diagra m and the notion of the abstract generalized Delaunay triangulation ar e useful, and that they provide a viable approach to the computation o f skeletons. Finally, details of the implementation, results, and an e valuation are presented.