AN ALGORITHM FOR THE MEDIAL AXIS TRANSFORM OF 3D POLYHEDRAL SOLIDS

The medial axis transform (MAT) is a representation of an object which has been shown to be useful in design, interrogation, animation, fini te element mesh generation, performance analysis, manufacturing simula tion, path planning, and tolerance specification. In this paper, an al gorithm for determining the MAT is developed for general 3D polyhedral solids of arbitrary genus without cavities, with nonconvex vertices a nd edges. The algorithm is based on a classification scheme which rela tes different pieces of the medial axis (MA) to one another even in th e presence of degenerate MA points. Vertices of the MA are connected t o one another by tracing along adjacent edges, and finally the faces o f the axis are found by traversing closed loops of vertices and edges. Representation of the MA and associated radius function is addressed, and pseudocode for the algorithm is given along with recommended opti mizations. A connectivity theorem is proven to show the completeness o f the algorithm. Complexity estimates and stability analysis for the a lgorithms are presented. Finally, examples illustrate the computationa l properties of the algorithm for convex and nonconvex 3D polyhedral s olids with polyhedral holes.