Cut Locus and Medial Axis in the Euclidean Space and on Surfaces
Written by Franz-Erich Wolter (external)
Franz-Erich Wolter
University of Hannover, Germany
Keynote talk in English
WSCG 1999
February 9, 1999
University of West Bohemia
Abstract
(download in PDF)
The first part of the lecture gives an overview on the concepts and new results on the Cut Locus and Medial Axis in the Euclidean Space. We show that Cut Locus and Medial Axis are natural tools to be used in Global Shape Interrogation and Representation.
The cut locus CA of a closed set A in the Euclidean space E is defined as the closure of the set containing all points p that have at least two shortest (straight line) segments to A. We present a theorem stating that the complement of the cut locus i.e. E \ (CA E A) is the maximal open set in (E \ A) where the distance function with respect to the set A is continuously differentiable. This theorem includes also the result that this distance function has a locally Lipschitz continuous gradient on (E \ A).
The medial axis of a solid D in E is a subset of D containing all points being center of a disc of maximal size that fits in the domain D. We associate with the medial axis of a domain D the maximal disc radius function assigning to a medial axis point p the radius of the maximal disc with center p . We assume in the medial axis case that D is closed and that the boundary ?D of D is a topological (not necessarily connected) hypersurface of E. Under these assumptions the Medial Axis of D equals that part of the Cut Locus of ?D which is contained in D. The main result states that the Medial Axis has the homotopy type of its reference solid if the solid's boundary surface fulfills certain regularity requirements. The Medial Axis with its related maximal disc radius function can be used to reconstruct its reference solid D because D is the union all maximal discs that fit in D. Keeping the medial axis of a reference solid D fixed and modifying the associated disc radius function e.g. by shrinking or expanding the maximal disc radius function for some subsets of the medial axis yields a natural design tool allowing in a simple way global shape modifications like slimming or fattening the shape.
The cut locus concept offers a common frame lucidly unifying different concepts such as Voronoi diagrams, Medial Axes and equidistantial point sets. In this context we explain that the equidistantial set of two disjoint point sets is a subset of the Cut Locus of the union of those two sets and that the Voronoi diagram of a discrete point set equals the Cut Locus of that point set. We present results which imply that a non-degenerate C1-smooth rational B-spline surface patch which is free of self-intersections avoids its Cut Locus. This implies that for small enough offset distances such a spline patch has regular smooth offset surfaces that are diffeomorphic to the unit sphere. Any of those offset surfaces bounds a solid (which is homeomorphic to the unit ball) and this solid's medial axis is equal to the progenitor spline surface. The spline patch can be manufactured with a ball cutter whose center moves on the regular offset surface and the radius of the ball cutter equals the offset distance.
The second part of the lecture explains how Medial Axis and Cut Locus concepts presented above in the Euclidean case can be generalized to (curved) surfaces. ? (Even higher dimensional generalizations are possible i.e. instead of a surface one might consider an arbitrary n-dimensional Riemannian manifold.) ? As ambient space serves now e.g. in the surface case ? (not the 2- or n-dimensional Euclidean space but) ? a domain on a curved free form surface. Shortest Euclidean segments (straight line segments) are now in the surface case replaced by shortest paths contained in the surface. Those shortest paths are given by geodesic paths on the surface. Fundamental for the computation of Cut Locus, Medial Axis, and Voronoi diagrams within the Euclidean setting was the computation of equidistantial sets. We need here e.g. equidistantial sets with respect to two points for Voronoi Diagram computations or equidistantial sets with respect to two arcs for Medial Axis computations of planar domains bounded by curved boundary curves. On a surface a medial curve with respect to two sets F , G contains the surface points that have shortest geodesics of equal length to each of the sets F and G . This medial curve on a surface may be called geodesic medial curve. It is the fundament to construct the geodesic Medial Axis . The geodesic Medial Axis of a bounded surface domain contains the centers of all maximal geodesic dics that fit into the domain. On a surface S a geodesic disc with center x and radius r contains all points on S that can be joined with x by a geodesic path contained in S whose length is shorter or equal to r . The geodesic medial axis is the natural generalization of the medial axis ? (originally defined for bounded planar domains) ? to a bounded surface domain. We show how geodesic medial curves on surfaces can be computed efficiently by using methods from Riemannian geometry. These methods can be applied to compute efficiently Geodesic Voronoi Diagrams on surfaces and to compute the Geodesic Medial Axis for a surface the boundary of which is given by a finite union of piecewise curvature continous arcs.
