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, finite element mesh generation, performance analysis, manufacturing simulation, path planning, and tolerance specification. In this paper, an algorithm for determining the MAT is developed for general 3D polyhedral solids of arbitrary genus without cavities, with nonconvex vertices and edges. The algorithm is based on a classification scheme which relates different pieces of the medial axis (MA) to one another even in the presence of degenerate MA points. Vertices of the MA are connected to one another by tracing along adjacent edges, and finally the faces of 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 optimizations. A connectivity theorem is proven to show the completeness of the algorithm. Complexity estimates and stability analysis for the algorithms are presented. Finally, examples illustrate the computational properties of the algorithm for convex and nonconvex 3D polyhedral solids with polyhedral holes.