Accurate Computation of the Medial Axis of a Polyhedron
Tim Culver, John Keyser, Dinesh Manocha
Proceedings of the Fifth ACM Symposium on Solid Modeling and Applications
Pages 179-190, 1999
The medial axis of an object is a skeleton-like shape that provides
useful information about the structure of the boundary of an object in a
compact way. The medial axis was originally proposed for biological shape
measurement, but has since been used in many applications including path
planning, finite element mesh generation, automated injection molding
simulation and feature recognition.
The authors wish to accurately compute the medial axis of any given
polyhedron with reasonable efficiency.
The authors present an accurate and efficient algorithm to compute the
internal Voronoi region and medial axis of a 3D polyhedron. Accuracy is
achieved using exact arithmetic.
A medial axis is represented as a set of sheets (trimmed quadric surfaces),
seams (algebraic space curves) and junctions (points with algebraic
coordinates). The authors' algorithm for computing the medial axis of a
polyhedron works by recursively finding neighboring junctions along seams.
Spatial decomposition and linear programming speed up this search step.
Central to the authors' medial axis algorithm is a new algorithm for analysis
of the topology of an algebraic plane curve. The authors have designed
specialized algorithms to speed up computation on implicit geometric
structures (such as algebraic curves).
Since this paper's algorithm for medial axis computation uses exact
arithmetic, it computes medial axes of polyhedra accurately. The algorithm
works efficiently and accurately on small polyhedra. The authors have not
described how well the algorithm would work on polyhedra containing hundreds
of faces-this is mentioned as future work. This paper's algorithm deals with
degeneracies but the authors would like to investigate the use of
perturbation techniques to handle degeneracies for future work.
ctj