Last update: Oct. 11, 2001
Friday, February 11, 2000
Brown University
Seminar at 2pm-3h30, CIT bldg., Lubrano (4th floor)
Jointly organized by Eng./LEMS,
CS/Graphics
and the SHAPE
Lab.
Currently visiting professor at MIT
Institute of Computer Science, University of Hannover
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 second part of the lecture explains how Medial Axis and Cut Locus concepts can be generalized to (curved) surfaces.
The Cut Locus, C_{A}, 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\(C_{A}\cup 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 solid 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 \partial 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 \partial 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 thinning or fattening the shape.
The Cut Locus offers a framework lucidly unifying different concepts such as Voronoi diagrams, medial axes and equidistance point sets. In this context we explain that the equidistance 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 C^{1}-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 patch. The shape of 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 the medial axis and Cut Locus concepts presented above in the Euclidean case can be generalized to (curved) surfaces in E^{3}. - Even higher dimensional generalizations are possible, i.e., instead of a surface one might consider an arbitrary n-dimensional Riemannian manifold. - Consider a domain on a curved freeform surface. Shortest Euclidean segments (straight line segments) are now replaced by shortest paths contained in the surface, i.e., geodesic paths.
Fundamental for the computation of Cut Locus, Medial Axis, and Voronoi diagrams within the Euclidean setting was the computation of equidistance sets. What we need here are, e.g., equidistance sets with respect to two points, for Voronoi Diagram computations, or equidistance sets with respect to two arcs, for Medial Axis computations of planar domains bounded by curved boundaries.
On a surface a medial curve with respect to two sets F and 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. The latter construction represents the fundamental building block to obtain the geodesic medial axis. The geodesic medial axis of a bounded surface domain contains the centers of all maximal geodesic discs 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 continuous arcs.
PDF
Compressed PostScript
PDF (compressed with
gzip)
Compressed PostScript
PDF (compressed with gzip)
Compressed PostScript
PDF (compressed with gzip)
Illustrative Figures ....
Last Updated: Oct. 11, 2001
Page created & maintained by Frederic Fol Leymarie,
2000-1.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu
