July 13, 2000

BACK

Publications by Christof M. Hoffmann's group & collaborators, Computer Science Dept., Purdue University:

• A Framework for Object Modeling, 1999.
• On User-Defined Features, 1998.
• A Road Map To Solid Modeling, 1996.
• Geometric Constraints for CAGD, 1995.
• Summary of main topics considered at a Conference on Freeform Curves and Surfaces, 1995.
• MAT to Boundary Representation Conversion, P.J.Vermeer, PhD Thesis, 1994.
• On the Skeleton of Simple CSG Objects, 1993.
• Computer Vision, Descriptive Geometry, and Classical Mechanics, 1991.
• Fundamental Techniques for Geometric and Solid Modeling, 1991.
• How to Compute Offsets Without Self-Intersection, 1991.
• How to Construct the Skeleton of CSG Objects, 1990.
• A Geometric Investigation of the Skeleton of CSG Objects, 1990.
• Curvature Computations on Surfaces in n-Space, 1990.
• A Dimensionality Paradigm for Surface Interrogations, 1990.
• Visualization of Surfaces in Four-Dimensional Space, 1990.
• Conversion Methods Between Parametric and Implicit Curves and Surfaces, 1990.
• Geometric and Solid Modeling - an Introduction, 1989.
• Algebraic and Numerical Techniques for Offsets and Blends, 1989.

BibTeX references.

(1) Investigate geometric structures of Voronoi surfaces of simple CSG pairs. (2) Discuss trimming surfaces.

Simple CSG objects: Natural quadrics: block, sphere, cylinder and cone, as well as the torus.

Voronoi surface parity:

Given 2 surfaces f and g, their Voronoi surface Vor(f,g) has 2 components:

1. Even component: medial surface that lie either on the outside of both f and g or on their inside.
2. Odd component: medial surface that lie on the inside of f (g) and the outside of g (f).

Reflexive Voronoi surfaces:

Higher order symmetry: either part of a Voronoi curve or node.

Simple Voronoi curves

• Straight line and point: parabola. If the point is on the line, the Voronoi curve is the perpendicular to the line at that point.
• Circle and a straight line: parabolas (odd & even) with the center of the circle as their focus. If the circle is tangent to the line, then one of the parabola degenerates to a half-line.
• Two nonintersecting circles with different radii: hyperbola; for circles of equal radii it degenerates to a straight line.
• Two intersecting circles with different radii: Odd Voronoi curve is an ellipse, the even Voronoi curve is a hyperbola (which degenerates to a straight line for equal radii intersecting circles).

Mixed Dimensional Pairs

Consider e.g. the interior skeleton of a rectangular block with a blind hole. In the vicinity of the bottom of the hole, the skeleton has 3 elements:

Voronoi surfaces of CSG pairs

Consider a Voronoi surface as the projection into (x,y,z) space of the intersection of two hypersurfaces in (x,y,z,r)-space. Each hypersurface is a generic r-offset. Two positive (negative) r-offsets intersect into an even Voronoi surface, while positive and negative offsets intersect into an odd Voronoi surface.

Voronoi surface of a plane and CSG

• The degree of Vor(f,g) does not exceed the degree of the simple CSG, given by g.
• The odd and even Voronoi surfaces are the same.

Theorem - f : plane

Let h = Vor(f,g), where f is a plane; then

Theorem - f : sphere

Let h = Vor(f,g), where f is a sphere; then

Theorem - f : cylinder

Let h = Vor(f,g), where f is a cylinder ; then

1. If g is a cylinder of equal radius, then h is a hyperbolic paraboloid if the axes are skew, a pair of planes if the axes intersect, and a single plane if the axes are parallel. If g is a cylinder of different radius, with a parallel axis then h is an elliptic or a hyperbolic cylinder.
2. If g is a cone and the axes of f and g coincide, h is a cone.
3. If g is a torus and the axes of f and g coincide, then h is a paraboloid of revolution. If the cylinder diameter does not exceed the smaller radius of the torus, then h does not contain a spindle, otherwise it does.

Theorem - f : cone

Let h = Vor(f,g), where f is a cone ; then

1. If g is a cone, and the axes of f and g coincide, then the components of h consists of cones.
2. If g is a torus and the axes of f and g coincide, then h is a figure of revolution obtained by rotating a parabola about a line NOT perpendicular to the axis of symmetry.

Theorem - f : torus

Let h = Vor(f,g), where f is a torus ; then

1. If g is a torus whose axis coincide with the one of f, then h is a figure of revolution obtained by rotating an ellipse or a hyperbola about a line perpendicular to one of their axes. If the minor radii of the tori are equal, then h (even) is a cylinder or a cone. If f and g are congruent with a common center, then h (even) is a pair of planes containing the intersection curves.

Skeleton Face Boundaries and Trimming Surfaces

A suitable strategy for trimming away irrelevant surface areas must be devised that determines where the "influence region" of a face ends on an associated Voronoi surface. This is made difficult (numerically) by the fact that adjacent components of the skeleton can meet with tangent continuity.

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 recognition 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 determined and thereafter refined using iteration as in 2D.

Notes :

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

Traditional techniques for computing offsets are local in nature and lack good criteria for eliminating possible self-intersections of the offset. Methods based on integrating differential equations or on image processing do not lack such criteria, but seem to require constructing the solution in the ambient space, i.e., in one dimension larger than the offset. We investigate such methods.

Keywords: medial axis transform, skeletons, Eikonal, Euclidean Distance Transforms,

The main ideas:

1. Determine critical points and curves of the skeleton of certain 3D solids; i.e., find initial points on the curves and surfaces comprising the skeleton.
2. Construct all parts of the skeleton by increasing distance form the boundary, in a 4D (x,y,z,r)-space.

The offset of a CSG is not necessarily a CSG object, since the tubular offset surfaces of certain edges are not natural quadrics. But, it is not necessary to construct the offset solid explicitly, for all proximity computations can be expressed in terms of the original boundary elements. Still, determining closest bisecting points between boundary elements requires considerably more machinery than solving two bivariate quadratic equations.

Algorithm:

1. Consider ALL pairs of boundary elements (faces, edges, vertices). Determine for each pair the nearest bisecting "points" (equidistant from both elements).
2. Sort these points by their distance from the boundary.
3. Process these points by increasing distance, while constructing the skeleton.

NB: Some of the closest bisecting "points" are curves or surfaces. The generalization of this algorithm to curved boundary elements will necessitate introducing techniques for solving general systems of algebraic equations. An approximation is possible however (for curved bounding elements): (i) sample the surface, (ii) construct the Voronoi diagram, (iii) eliminate certain Voronoi edges and surfaces.

Determining Nearest Bisecting Points

Carrier of the boundary element: corresponding curve or surface of an edge or face (boundary elements).

Then the problem of finding nearest bisecting points of the boundary elements is reduced to finding the ones of the carriers, with footpoints on the boundary elements.

Consider a face F as a bounding element and its associated carrier, the surface f :

1. Find nearest bisecting points w/r to f and with footpoints inside F (discard others).
2. Find nearest bisecting points w/r/ to the bounding edges of F and with footpoints on these edges.
3. Find nearest bisecting points w/r to the vertices of F.

Finding nearest bisecting points between a pair of carriers f and g :

1. Find pairs of footpoints p on f, q on g, such that d(p,q) is minimum. The connecting line pq must be perpendicular to both f (at p) and g (at q). Thus the Euclidean distance d(p,q) has a local extrema.

A generic procedure for finding closest approach pairs

Solve the following system of algebraic equations:

1. f(p) = 0
2. g(q) = 0
3. perp(p, q, f)
4. perp(q, p, g)

Equations (1) and (2) assert that p is on f and q is on g. If f (or g) is a curve, then consider in lieu of equation (1) or (2) the intersection of two surfaces, f1 and f2: i.e., f1(p) = f2(p) = 0.

Equations (3) and (4) assert that the connecting line pq is normal to f at p, and to g at q, respectively.

• With f an implicit surface, this condition can be expressed via 3 equations.
• With f a curve, then pq must be perpendicular to the tangent to f at p.

Closest Approach Pairs between CSG Surfaces

The alebraic surfaces f and g are either a plane, a natural quadric (sphere, cone, cylinder) or a torus. It is helpful to consider a point to be a sphere of radius zero, a line to be a cylinder of radius zero and a circle to be a torus of minor radius zero.

Closest approach pairs with a Plane

Let g be a plane given by :

• a1 x + b1 y + c1 z + d = 0    , where a1^2 + b1^2 + c1^2 = 1 .

Most CSG surfaces f pose uninteresting problems, except the torus.

• Closest approach with another plane gives a line
• Closest approach with a "natural quadric" gives a point on a conic.

   Theorem - Closest approach between a plane and a torus :

• Requires solving (for minimum distance) 2 systems of 3 equations in 3 unknowns, each system consisting of 2 linear and 1 quadratic equations.

Closest approach pairs with a Sphere

Let g be a sphere given by the vertex/center : q = (a, b, c)

   Theorem - Closest approach to a point/sphere :

• Requires solving (for minimum distance) from
  1. a line/cylinder : 1 linear equation (perpendicular from q to the line)
  2. a cone or a torus : 1 quadratic equation (normals are given by equation of cones).

Closest approach pairs with a Cylinder

Let g be a cylinder given by its axis, as the parametric line:

• (a0 + a1 u , b0 + b1 u , c0 + c1 u) where a1^2+b1^2+c1^2 = 1 .

   Theorem - Closest approach to a line/cylinder :

• Requires solving (for minimum distance) from
  1. a line/cylinder : a system of 2 linear equations.
  2. a cone: a system of 1 linear and 1 quadratic equations.
  3. a torus: a system of 1 linear and 1 quartic equations.

Closest approach pairs with a Cone

Let g be a cone given by

• x^2 + y^2 - u^2 z^2 = 0

Then the normals to this cone lie on cones with equation:

• x^2 + y^2 - (z - l0)^2 / u^2 =0

where l0 is the z-coordinate of the intersection of the normals with the cone axis.

   Theorem - Closest approach to a cone :

• Requires solving (for minimum distance) from
  1. a (skew) cone : a system of 2 quadratic equations.
  2. a torus : a system of 1 quadratic and 1 quartic equations.

Closest approach pairs with a Torus

   Theorem - Closest approach between a pair of tori :

• Requires solving (for minimum distance) a system of two quartic equations.

Closest Approach Pairs involving Curves

We represent the edges of CSG objects with carriers given as the intersection of 2 surfaces g and h, of degree 1, 2 or 4. The normal plane to the curve is spanned by the gradients to g and h, denoted Ng and Nh . The tangent vector to the curve is given by the cross product Ng x Nh .

The Curve/Surface Case

The connection line pq between a point p on f and a point q on the curve g ^ h must lie in the normal plane to the curve at p. Let (x0, y0, z0) be a point on the curve where there is a linear combination of the surface normals that is perpendicular to f. For all cases this gives us 2 conditions:

• g(x0, y0, z0) = h(x0, y0, z0) = 0 .

Then additional conditions are found depending on the form of the surface f .

If f is a plane, say z = 0, then we have the 2 additional conditions:

• u1 g_x + u2 h_x = u1 g_y + u2 h_y = 0

If f is a sphere, e.g. with center q = (a,b,c), then we have the additional condition:

• u1 Ng + u2 Nh = (x0 - a , y0 - b , z0 - c)

which states that a certain linear combination of the 2 normals is equal to the vector from the curve point to the center of the sphere. This is equivalent to 3 scalar equations.

The case of the cylinder, cone and torus are also treated.

The Curve/Curve Case

The condition is now expressed as a point, p on a curve g1 ^ h1, which lie on the normal planes of the other point q on a curve g2 ^ h2, and vice-versa. Equivalently, the connection line is in both normal planes.

Local Skeleton Analysis

Admissibility test:

Amongst the computed nearest bisecting points, retain only those which are truly at minimum distance from their pair of bounding elements (and from no other bounding elements).

Each point of closest approach retained, p, will now have up to s (>= 2) boundary elements, Ei (i = 1, ... s). We can then build a list structure:

• (p, r, (E1, p1), ... , (Es, ps))

where r is the minimum distance of p from each boundary element Ei, and pi is a footpoint of p and Ei.

Local Geometry of Nearest Bisecting Points

Each skeleton point p determined above is either on a face (s = 2), edge (s >= 3) or vertex (s >= 4) of the skeleton. The dimension of the tangent space at p of the r-offset intersection determines the topology of the skeleton in the neighborhood of p:

• Consider the r-offset surfaces of E1, ..., Es as intersecting hypersurfaces in R^n ; then:
  • the Jacobian is of rank n     ==>     p is a skeleton vertex,
  • the Jacobian is of rank n-1     ==>     p is on a skeleton edge,
  • the Jacobian is of rank n-2     ==>     p is on a skeleton face.

Local Topology of Nearest Bisecting Points on Skeleton Edges and Vertices

Of all the identified nearest bisecting points above, consider those which are part of skeleton edges (rank n-1) or vertices (rank n-2). We need now to determine their local topology, i.e., find their adjacent faces or edges, respectively.

1. Find all subsets of the boundary elements, Ei, such that the Jacobian of the associated r-offsets, at p, has rank:
   • n-2 <= rank <= n-k-1    (k = 0 or 1 for p on an edge or a vertex, respectively).
2. For each such subset, the intersection of these r-offsets, forms an adjacent Voronoi surface or curve and is one of the carriers we seek.
3. For each such carrier, determine the face or edge which lies on it.
4. For each such face/edge consider a nearby point to p :
   • If its associated distance to the boundary is less than r, then either it is not part of the skeleton (i.e., it is part of the full symmetry set), or it is part of an already found skeleton element.
   • Otherwise, we have found a new edge/face.
   • For new edges, we iterate the process to retrieve their associated faces.

Building a Skeleton Section

The first section is located at ridges (l = 0) if the object surface contains locally convex edges.

It is then proposed to use a Distance Transform, i.e., the (x, y, z, r)-space, and look for possible intersection of faces or edges using a surface tracer like the marching-cube ... (this must not have been tested: no results provided in this or latter papers; might not work).

Sections are constructed by order of increasing distance (radius function).

Let F be a 2D manifold in n-D space, and let pi(F) be its projection int the subsapce of 3 of the variables in which F has been expressed. We give and algorithm that computes the normal curvature of pi(F) directly from the equations of F without variable elimination. We also comment on applications in CAGD.

We present methods for parameterizing implicit curves and surfaces and for implicitizing parametric curves and surfaces, based on computational techniques from algebraic geometry. After reviewing the basic mathematical facts or relevance, we describe and illustrate state-of-the-art algorithms and insights for the conversion problem.

BACK      TOP   

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