Homotopy-Preserving Medial Axis Simplification
Avneesh Sud
Mark Foskey
Dinesh Manocha

Abstract: We present a novel algorithm to compute a simplified medial axis of a polyhedron. Our simplification algorithm tends to remove unstable features of Blum's medial axis. Moreover, our algorithm preserves the topological structure of the original medial axis and ensures that the simplified medial axis has the same homotopy type as Blum's medial axis. We use the separation angle formed by connecting a point on the medial axis to closest points on the boundary as a measure of the stability of the medial axis at the point. The medial axis is decomposed into its parts that are the sheets, seams and junctions. We present a stability measure of each part of the medial axis based on separation angles and examine the relation between the stability measures of adjacent parts. Our simplification algorithm uses iterative pruning of the parts based on efficient local tests. We have applied the algorithm to compute a simplified medial axis of complex models with tens of thousands of triangles and complex topologies.
Homotopy-Preserving Medial Axis Simplification.

In Proceedings of the ACM Symposium on Solid and Physical Modeling (to appear) Boston, 2005.
Avneesh Sud, Mark Foskey and Dinesh Manocha

pdf file (3MB).

Geometric and Solid Modeling by GAMMA group.

An Approximate, Simplified Medial Axis.

Exact Computation of the Medial Axis of a Polyhedron.

DiFi: Fast 3D Distance Field Computation Using Graphics Hardware.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

sud [at] cs.unc.edu
last updated: 04/01/05