Robust Medial Axis research at UNC

The medial axis of a solid is the locus of the center of a maximal sphere, as the sphere rolls around the object interior. The locus is a central surface for the solid. The medial axis is a kind of skeleton, and the closely related medial axis transform is a complete shape representation based on the skeleton.

For a 3-D polyhedral solid, the medial axis is composed of bisectors of boundary features (the vertices, edges, and faces). These bisectors are planes and quadric surfaces. The bisectors meet along their intersection curves, which are degree-four algebraic space curves. Computing an accurate medial axis requires reliable computation with these curves and surfaces. Our method is based on exact computation, which avoids some of the difficulties associated with round-off error in geometric computation.

Current implementation results

Input complexity Output complexity Current running time

Polyhedron 1
6 faces
9 edges
5 vertices
14 sheets
13 seams
4 junctions
10 seconds

Polyhedron 2
16 faces
38 edges
24 vertices
69 sheets
88 seams
36 junctions
2.5 minutes

Dented box
9 faces
16 edges
9 vertices
? sheets
56 seams
16 junctions
35 seconds

Pizza box
56 faces
124 edges
70 vertices
? sheets
2116 seams
946 junctions
23 minutes

148 faces
222 edges
76 vertices
734 sheets
1091 seams
404 junctions
3.4 hours

252 faces
378 edges
124 vertices
950 sheets
1439 seams
453 junctions
3.8 hours

Venus de Milo
250 faces
375 edges
127 vertices
1627 sheets
2223 seams
933 junctions
5.6 hours

Star torus
48 faces
72 edges
24 vertices
? sheets
190 seams
60 junctions
8 minutes

104 faces
156 edges
52 vertices
745 sheets
1032 seams
437 junctions
18.5 minutes

The implementation is a C++ program based on the MAPC library. The medial axis images were rendered with Mathematica and OpenGL.

Times are on an SGI MIPS R12000 processor. (Similar times have been achieved on PCs running Linux.)


The medial axis transform is a fundamental shape operation with many applications. It was proposed by Blum in 1967 for biological shape measurement. It has also been used for path planning, automated injection molding simulation, and feature recognition. One of the best-known applications is finite-element mesh generation [Srinivasan92, Sheffer98].


Tim Culver, John Keyser, Dinesh Manocha.
Accurate Computation of the Medial Axis of a Polyhedron.
Proc. Fifth Symposium on Solid Modeling and Applications, pp. 179-190, 1999.

John Keyser, Tim Culver, Dinesh Manocha, Shankar Krishnan.
MAPC: A library for Efficient and Exact Manipulation of Algebraic Points and Curves.
Proc. Fifteenth Annual Symposium on Computational Geometry, pp. 360-369, 1999. (An earlier version is available as UNC-CS Technical Report TR98-038. [compressed Postscript]) kcmk-mapc-99

V. Srinivasan, L. R. Nackman, J.-M. Tang, S. N. Meshkat.
Automatic Mesh Generation Using the Symmetric Axis Transform of Polygonal Domains.
Proc. IEEE, 80:9 (1992), pp. 1485--1501. sntm-amgus-92

A. Sheffer, M. Etzion, A. Rappoport, M. Bercovier.
Hexahedral Mesh Generation Using Voronoi Skeletons. Seventh International Meshing Roundtable, Michigan, October 1998.


Supported in part by an Alfred P. Sloan Foundation Fellowship, ARO Contract DAAH04-96-1-0257, NSF Career Award CCR-9625217, ONR Young Investigator Award (N00014-97-1-0631), Honda, Intel and NSF/ARPA Center for Computer Graphics and Scientific Visualization.
Tim Culver
Last modified: Tue Sep 5 20:58:30 EDT 2000