August 20, 1998

Publications by Christof M. Hoffmann's group, Purdue University:

• MAT to Boundary Representation Conversion, P.J.Vermeer, PhD Thesis, 1994.
• Computer Vision, Descriptive Geometry, and Classical Mechanics, C.Hoffmann, 1991.
• Fundamental Techniques for Geometric and Solid Modeling, C.Hoffmann & G. Vanecek, Jr., 1991.

BibTeX references.

Notes :

The following 3 concepts fundamentally relate to measuring Euclidean distance, from a given geometric structure :

1. The Medial-Axis Transform (MAT) of Blum is a tool for shape reognition and abstraction.
2. Cyclographics maps were developed in classical Descriptive Geometry as a mean to solve the problem of Appolonius, and, more generally, as a device for studying distance maps, surface curvature, and other basic geometric properties.
3. In the Hamilton-Jacobi theory, the function S is related to the previous concepts via the Eikonal equation that describes wave propagation.

Considers compact objects (only) in E² and E³.

3D MAT - complexity of medial surfaces

A specific difficulty is that the surfaces on which faces and edges of the 3D skeleton lie are not easily described using parametric or implicit algebraics that are commonly used by the geometric modeling community. In general, the surfaces can be described exactly and practically only using the dimensionality paradigm, as a system of nonlinear equations.

Cyclographic Maps in Descriptive Geometry

Cycles: Consider all oriented circles tangent at a point p of an oriented plane curve, C. With each such cycle, we associate a point q = (x, y, r), where (x, y) is the center of the cycle and r its radius (which is signed according to the orientation of the curve/cycle). For a given p the associated points q lie on line through p having a slope 1 against the (x,y)-plane. This line, when orthographically projected onto the (x,y)-plane, coincide with the normal of C through p.

Cyclographic map: Ruled surface, S(C), obtained, as p varies along C, by the lines defined by the sets of q's; these lines are called the generators of S. This map contains the distance surface of Blum. The points of S(C) which are not continuously differentiable are the skeleton w/r to C.

Direct recovery of the curve C from the MAT (see Fig.1) :

1. Project the skeleton point P = (x,y,r) orthographically on the (x,y)-plane, obtaining a point p = (x,y).
2. Find the intersection of the tangent to the skeleton with the (x,y)-plane, obtaining a point w.
3. Taking w as the summit of a pencil of rays, find the rays tangent to the circle with radius |r|, centered at p.
4. The contact points, q1 & q2, are points of C.

In 3D, the oriented circles are replaced by oriented spheres. For non-Euclidean metrics, one can choose suitable conics.

Classical Mechanics and the Skeleton

Consider a continuum of particles situated at time t = 0 on a plane, smooth curve C, moving at constant velocity in a direction locally normal to C. By the conservation of momentum, the kinetic energy of each particle is constant, and will be proportional to the squared velocity components in the principal directions. That is, Vx² + Vy² = 1, or

This is the Eikonal equation of geometrical optics (expressed in 2D Cartesian coordinates), where S(x,y) is the time when a particle reaches the point (x,y) (i.e., time of travel). Time can be taken for distance, and the Eikonal equation becomes a differential description of the Euclidean distance function. The 3D version (also expressed in Cartesian coordinates) is as follows:

The Eikonal equation suggests integrating it to compute the Distance surface S, and extract MAT points by processing intersecting characteristics directions, during the integration.

Computational Approaches

In 2D:

• Assume a continuous boundary description has been specified. Then use distance interpolation and locate, at sub-pixel loci, the intersections of characteristics. Formulate a system of equations that describes the skeleton locally, in terms of the coordinates of the skeleton point, its footpoints, and the distance to the boundary. Solve it with Newton iteration.

In 3D:

• More complicated than in 2D since characteristics through the vertices of a grid cube will be skew in general. One interpolates the characteristics along grid edges. Then, intersection curves and surfaces can be detrermined and thereafter refined using iteration as in 2D.

Notes :

nD skeletons as the discontinuites of the graph of the distance map in (n+1)D space. Cyclographic map of Descriptive Geometry (generates the ruled & developable surface); its discontinuites form the skeleton. Relation with the Hamilton-Jacobi equation. The shocks of this PDE correspond to the skeleton.

Page created & maintained by Frederic Leymarie, 1998.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu