The medial axis transform is a fundamental shape operation with applications in many fields. In solid modeling, the MAT has proven a useful tool for finite element meshing, model simplification, and feature recognition. The MAT is also a complete shape representation that could be used in place of a boundary representation. Yet the MAT is not widely used because computing it is difficult both in theory and in practice. For a three-dimensional polyhedral solid, the medial axis consists of quadric surfaces and degree-four algebraic space curves. Computing with high-degree curves and surfaces requires high numerical precision. Most previous methods attempt to avoid such computation by discretizing, or otherwise approximating, the medial axis. The few existing continuous methods are based exclusively on floating-point arithmetic, which leads to reliability problems.

I present a new reliable, continuous algorithm for accurately computing the medial axis of a polyhedron. It is the only continuous medial axis algorithm that is insensitive to roundoff error. Further, my algorithm handles the most common forms of degeneracy. The algorithm is also efficient in a practical sense. The foundation of my approach is exact computation. My MAT representation uses arbitrary-precision rational numbers to describe the medial geometry. My algorithm is based on a point-ordering predicate that is always evaluated correctly.

By its nature, exact computation requires high-precision arithmetic, which is significantly more expensive than hardware-supported floating-point arithmetic. However, my approach avoids the extra expense where feasible, using techniques such as floating-point filters and lazy evaluation. The result is an algorithm whose running time approaches that of floating-point methods when high precision is not required. I demonstrate this assertion by applying my implementation to several complex polyhedral solids.

PDF version

Postscript version

• Print 1-152.ps.gz (2324 KB). This represents the entire dissertation, excluding six rendered images on pages 16, 120, and 122. The images are replaced with blank white boxes. (The actual total is 172 pages.)
• Print 15-16.ps.gz (808 KB).
• Print 119-120.ps.gz (224 KB).
• Print 121-122.ps.gz (836 KB).
• Use the last three print jobs to replace the corresponding pages in the original.

The document is designed to be printed double-sided, with wider left margins on odd-numbered pages, and occasional blank even-numbered pages. There are 20 pages of frontmatter before page 1; some software, when told to print page 1, will print both pages numbered 1.

Dissertation graph