A GEOMETRIC INVESTIGATION OF THE SKELETON OF CSG OBJECTS Debasish Dutta Design Laboratory, Departrmen" of Mechanical Engineering The University of Michigan Ann Arbor, Michigan 48109 Christoph M. Hoffmann Computer Science Department, Purdue University West Lafayette, Indiana 47907 UM-MEAM-90-02

f/f' /1 4.)t US~~: P'cft.. u I f -c 11

A Geometric Investigation of the Skeleton of CSG Objects Debasish Dutta Design Laboratory Department of Mechanical Engineering University of Michigan Ann Arbor, MI 48109 and Christoph M. Hoffmann* Computer Science Department Purdue University West Lafayette, IN 47907 February 14, 1990 Abstract We describe an algorithm for computing the skeleton (medial-axis surface) of an object defined using constructive solid geometry (CSG). This surface is the locus of all points in the object's interior that have equal minimum distance from at least two distinct parts of the boundary. The skeleton can be used in blending, motion planning, medical tomography, computer vision, and in mesh generation. We also present a geometric analysis of Voronoi surfaces from which the skeleton is composed. 1 Introduction A common design paradigm in mechanical engineering is to create complex mechanical parts from primitive shapes by regularized Boolean operations. This paradigm became well-known as Constructive Solid Geometry (CSG), notably Supported in part by NSF Grants CCR 86-19817 and DMC 88-07550, and by ONR Contract N00014-86-K-0465.

with the work by Requicha and Voelcker, e.g., [13], who proposed five primitives: block, sphere, cylinder, cone, and torus. We refer to all objects created from the named primitives as CSG objects. They provide an unambiguous computer representation of manufacturable objects of realistic complexity and shape. We consider in this paper the formation of the skeleton of CSG objects, defined precisely below. Skeletons can be used in shape representation and shape recognition [1], in robot motion planning [14], and for the purpose of defining certain blending surfaces [3]. Moreover, skeletons can be used to decompose objects as a first step in mesh generation [10]. The balance of this section defines the skeleton and its constituent elements, Voronoi surfaces and Voronoi curves. It also gives more details of the applications of the skeleton. Section 2 develops a conceptual approach to constructing the skeleton from its elements and explains the geometric and comlbihlatorial properties skeleton construction has to account for. A general procedule for constructing Voronoi surfaces is outlined in Section 3. This procedure would be used in situations in which the bounding surfaces of the CSG object are complicated. Simpler surfaces admit special constructions, and these are investigated in Section 4, from a geometric perspective. Section 5 concludes the paper. 1.1 Skeleton of CSG Objects The locus of all points in an object that have equal minimum distance frolli at least two bounding faces of the object forms the interior skeleton of the object. In the literature, the interior skeleton has also been referred to as the medial-adis surface [9]. Definition 1.1 (Blum) The interior skeleton of a 3D object is the locus of the centers of all its maximal inscribed spheres. The interior skeleton of a 2D object is the locus of the centers of all its maximal inscribed circles. The dotted lines in Figure 1 shows the skeletons of simple 2D and 3D objects. For example, the skeleton of the rectangular block shown in Fig l(c) consists of 13 planar faces, each of which is the locus of all points equidistant to a pair of bounding faces of the block. Twelve skeleton faces are equidistant to a pair of adjacent faces of the block. The horizontal skeleton face is equidistant to the top and the bottom faces of the block. Note that these two faces are not adjacent. Therefore, possibly all face pairs must be considered when constructing the skeleton. The faces of the block's skeleton can be thought of as polygons in equidistant planes. To construct the skeleton, we must construct the individual faces. The faces lie in Voronoi surfaces, well-studied in computational geometry. We consider them next.

L "2 \ W I Figure 1: Skeletons of Sphere, Rectangle, Box 1.2 Voronoi Curves and Surfaces Voronoi diagrams are widely used in computational geometry. Given a set S of points in the plane, the Voronoi diagram is a tesselation of the plane by polygons such that every point p of S is contained in a polygon whose interior points are closer to p than to any other point of S. The Voronoi diagram of a finite set S contains closed and open polygons, where an open polygon is bounded by two semi-infinite edges. Proximity problems such as closest'pair, Euclidean minimum spanning tree, triangulation, etc., can be solved efficiently when using Voronoi diagrams [12]. When the elements of S are simple polygons or other extended two-dimensional objects, the Voronoi diagram is more clearly conceptualized as the locus of centers of all maximal circles that are tangent to at least two elements of S from the outside. The Voronoi diagram is then composed of curve segments, as well as straight line segments. When considering extended 2D objects, a similar process within the boundaries of each object yields a new Voronoi diagram; one that is the interior skeleton of the object. We therefore speak of an ezterior and an interior Voronoi diagram. The exterior Voronoi diagram can be thought of as the interior Voronoi diagram of the infinite object obtained by subtracting from the Euclidean plane the interior of the objects in -S. If the elements of S are 3D objects, we obtain a higher-dimensional Voronoi diagram whose faces lie on surfaces. As in the two-dimensional case, we speak of interior and exterior Voronoi diagrams. Note that these are precisely the interior and the exterior skeletons. When the set S contains more than two objects or one object whose shape is bounded by more than one face, the skeleton is not a single surface but consists of faces. Each face lies on a certain surface, called the Voronoi surface. For example, the Voronoi surface with respect to a plane and a point not in the

plane is evidently a paraboloid of revolution, with the point as focus. Voronoi surfaces are considered in Sections 3 and 4. 1.3 Applications of Skeletons Object skeletons can be used in shape representation and recognition [1]. Briefly, the skeleton defines a decomposition of the object into simpler figures that call be described separately. These descriptions are then combined into a single, canonical object description that is independent of the original design sequence. In robot motion planning, the exterior skeleton of a set S of 3D obstacles can be used to define paths that maximize the distance of a moving robot to each obstacle;' [14] uses the exterior skeleton to find collision free paths. In computer-aided design and modelling, variable-radius (rolling-ball) blends can be defined via a spine curve and a radius-variation function. The exterior skeleton surface can be used for an analytic definition of the spine curve [3] when the blend is a fillet. The interior skeleton can be used for an analytic definition of the spine in the case of rounds. In [10] it is argued that the interior skeleton can be used to decompose objects for the purpose of finite-element mesh generation in 2D domains that have been defined in a CSG style from disks and rectangles. Similarly, we consider decomposing 3D CSG objects with the skeleton. In solid mechanics, the interior skeleton would be required.' In fluid mechanics, the exterior skeleton would be used, e.g., when studying an airfoil in turbulent media. Despite great practical demand and potential, automatic interfaces of solid modelers with analysis codes appear to be severely limited [4]. The ability to generate skeletons automatically from a solid model would facilit'ate constructing more sophisticated interfaces of this kind. Algorithms have been proposed for the two-dimensional version of the problem, for computing interior and exterior Voronoi curves, [11, 10]. Methods for constructing simple Voronoi surfaces have also been considered [9, 3]. However, complex Voronoi elements (i.e. complicated curves and surfaces) arise when skeletons of moderately complex CSG objects are considered, and there seems to be no work on this subject. In this paper, we take a deeper look at such skeleton surfaces by investigating the individual Voronoi elements that make up the interior skeleton of CSG objects. It is shown that the geometry of such skeletons are inherently complex. An investigation into the geometry of the associated Voronoi surfaces brings to light the necessity of going beyond natural quadrics in existing solid mod1ellers. 1For an automatic method to generate rectangular grids for three-dimensional polyhedral domains efficiently see [15].

1.4 Preliminaries Our usage of the term skeleton refers to the composite of Voronoi curves and surfaces that result from appropriate pairs of bounding faces of the object. A Voronoi curve is defined with respect to a pair of curves., and a Voronoi surface with respect to a pair of surfaces. It suffices to restrict attention to the interior skeleton, since the exterior skeleton may be obtained by considering the (regularized) complement of the object, in 3-space. Mathematically, a Voronoi surface can be defined as follows. Let f and g be two surfaces. Then their Voronoi surface, denoted Vor(f,g) is the locus of all points equidistant from f and from g: Vor(f,g) = {p E R3 I df(p) = dg(p)} where df(p) and dg(p) are the perpendicular distances of point p from f and from g, respectively. Similarly, we define the Voronoi curve of curves f and g as the locus of points in R2 that are equidistant from f and g. If f or g are curves in 3-space, then the equidistant points form a surface, again called the Voronoi surface of f and g. It can be shown that Voronoi curves and surfaces are semi-algebraic whenever f and g are. All CSG objects are bounded by faces that lie on planes, natural quadrics, and tori. When the entire surfaces are considered, e.g., the entiie plane, the infinite cylinder, the infinite double cone, etc., their pairwise Voronoi surfaces will usually be algebraic surfaces. However, there are cases in which a Voronoi surface is only semi-algebraic, that is, it is a subset of an algebraic surface. This situation arises because certain Voronoi surfaces may end abruptly, and we give an example of this phenomenon later in Section 3. 2 On the Construction Skeletons The skeleton of a CSG object consists of Voronoi elements. These elen-llts are obtained by considering the bounding surfaces of the object, individullally or pairwise. In this section, we illustrate the nature of the skeleton and argue that the construction of the skeleton consists of trimming Voronoi surfaces between pairs of boundary elements of equal or mixed dimensionality. 2.1 Reflexive Voronoi Surfaces Reflezive Voronoi surfaces are lower-dimensional Voronoi surfaces that arise ill the skeleton of certain primitive shapes. Consider a sphere. Its skeleton is just a point, namely the center of the sphere. Since such a sphere could lIe

1. Figure 2: Block with blind hole and the partial skeleton the CSG object under consideration, it is necessary to identify the reflexive Voronoi surface of a given surface, defined to consist of all points p in space with the property that there exists more than one point on the given surface, at a minimum distance from p. It is evident that the given surface must necessarily be non-planar. Examples of CSG objects whose reflexive Voronoi surfaces are actually the interior skeletons include the cylinder, cone and torus. For the cyclinder and the cone, the reflexive Voronoi surfaces are their respective axes. In the case of the torus it is the spine - a circle that is the locus of centers of the generating spheres. In the following, we will refer to such curves as Voronoi surfaces and not Voronoi curves, because they arise from considering surfaces. Moreover, for complicated surfaces they need not degenerate to points and curves. 2.2 A Procedural Construction for Skeletons Let object S be a rectangular block with a blind hole, as shown in Figure 2. Let g denote the cylinder used in the CSG construction and f the plane where the hole begins. It will be shown later that the skeleton of this object includes part of a circular cone which has for its base the circle of intersection of g and f. See also Figure 2. The entire cone is the Voronoi surface of the plane f and the (infinite) cylinder g. In principle, the construction of the skeleton of this object could be described as follows. 1. For each bounding surface, fi of S, construct the reflexive Voronoi sulllface Vor(f,). 2. For each pair of bounding surfaces, fj,fk of S, construct the Voronoi surface vor(fj,fit). 6~~~~~~~~i l j~

/ / Figure 3: Odd and Even Voronoi Surface of two Spheres 3. Trim Vor(fi) and Vor(fj,fk) suitably to yield the interior skcleton of S. This motivates considering the Voronoi surfaces between pairs of bounding surfaces of the object. Note that this approach to constructing a skeleton is too simplistic. It ignores the fact that the presence of edges and vertices may cause other surface elements to appear in the skeleton. 2.3 Voronoi Surface Parity We wish to determine Voronoi surfaces for pairs of adjacent bounding surfaces of the object. Given two surfaces f and g, the surface Vor(f, g) consists of two components. One component consists of points that lie either on the outside of both f and g or on the inside of them. We call such a Voronoi surface the even Voronoi surface of f and g. The other component of Vor(f, g) is the odd Voronoi surface of f and g and consists of points that are on the inside of f and outside of g, or on the outside of f and the inside of g. Figure 3 shows both components for two spheres of equal radius. Here, the even Voronoi surface is a plane that contains the circle in which the two spheres intersect. Points on this plane have equal minimum distance to either sphere, and always lie on the outside of both spheres or on the inside of both of them. As shown later, the odd offset is a prolate. spheroid, i.e., an ellipse rotated about one of its axes. The points of the spheroid have equal minimum distance from the two spheres, but are always outside of one and inside the other. Which component of the Voronoi surfaces is needed depends, roughly speaking, on whether the surfaces bound cavities or protrusions. Miore precisely, in the terminology of [2], it depends on whether the primitives contributing the two faces are used positively or negatively in the CSG tree.

Figure 4: Skeleton at the end of a blind hole 2.4 Mixed-Dimensional Pairs Consider the bottom of the blind hole of Figure 2. In its vicinity, the skeleton has a more complicated structure as illustrated in Figure 4. Here, the skeleton is composed of three elements, labeled hl, h2, and h3 in the figure. The element hi is part of a cone, the Vor(fi, g) of cylinder fi bounding the hole and the opposite face plane g of the block. The surface h3 is part of a plane, the Vor(g, f2) of the plane g and the plane f2 that forms the bottom of the hole. The intermediate surface, h2, consists of points that have equal distance from the plane g and the edge e formed by the intersection of fi and f2. Thus, h2 is part of Vor(fl,e). We will see later that Vor(fi, e) is a parabolic torus - a surface of revolution obtained by rotating a parabola around a line parallel to and away from its axis of symmetry. This shows that not only do we have to consider Voronoi surfaces between pairs of bounding surfaces, but also between surfaces and curves. It will b)e no surprise that we also need to determine Voronoi surfaces -for curve pairs, for points and curves, for points and surfaces, and for pairs of points. Hence, we have to augment our earlier algorithm with a determination of Voiroioi surfaces of such pairs of boundary elements, of lower and of mixed dimensionality. 2.5 Trimming Surfaces The complexity of constructing the skeleton of CSG objects now begins to show: Many Voronoi surfaces have to be constructed, and a suitable strategy for trimrming away irrelevant surface areas will be needed. For this purpose, we should consider where the "influence region" of a face ends on an associated Voronoi surface. This is especially important in view of the fact that since adjacent components of a skeleton may meet with tangent continuity, a determinationi

Figure 5: Trimming Surface at Edge e of the separating edges as intersection curves of the associated Voronoi surfaces may be pose delicate numerical problems. Consider a point p in space. We ask for a point q on a given face f of the CSG object that lies closest to p. If q is interior to f, then the line pq must be normal to f at q. This motivates trimming the Voronoi surface associated with f, by a surface of normals at the boundary of f. This surface is a ruled surface generated by all the normals to f, along its boundary. In simple situations we expect that the trimming curves do not exhibit complicated singularities, and that they delimit a simply connected area that constitutes a face of the skeleton. Note, however, that the trimming surface could have a nontrivial geometry. For example, for a face on the cylinder f bounded by the elliptic edge e, the trimming surface is the ruled surface f, shown in Figure 5. Similar trimming methods can be formulated for edges: Trim the associated Voronoi surface by the normal planes at the vertices of the edges, and by the trimming surfaces of the adjacent faces. In summary, we construct the Voronoi surfaces on which the faces of the skeleton are situated, by considering elements of the boundary individually, and in pairs. Then Voronoi surfaces axe trimmed by the trimming surfaces which are generated by normals to the surfaces and to the edges. The skeleton is then assembled from the patches of Voronoi surfaces that remain. 2.6 Algebraic Complexity Aside from the combinatorial complexity of properly trimming and combinihng patches of Voronoi surfaces, the Vroronoi surfaces themselves can be algebraically quite complex. In response, we present in the next section a general methlodl

that formulates the surfaces in a fairly simple way, as a set of equations using auxiliary variables. These equations can be formulated easily, but their analysis and interrogation is not so simple and is the subject of ongoing research; [6, 7]. So, we give a simplified method for deriving implicit equations of Voronoi surfaces of CSG surface pairs. In addition, in Section 4, we discuss the geometry of Voronoi surfaces for CSG. The geometric properties derived in that section provide shortcuts to the construction and analysis of the elements of the interior skeleton. 3 Methods for Deriving Voronoi Surfaces Recall that the Voronoi surface, Vor(f,g), is the locus of all points equidistant from surfaces f and g. Given f and g, implicitly or parametrically, there is a general method for formulating a mathematical description of Voronoi curves and surfaces, as a set of equations using auxiliary variables. Although wve use this general method for algebraic curves and surfaces in this paper, we note that it can be used for all curves and surfaces that are differentiable. We recall the method from [3, 5, 6, 7]. 3.1 A General Procedure Let f and g denote a pair of algebraic surfaces. Consider two spheres Sf and S., each of radius d, with centers on f and g, respectively. With d the offset distance, the offset surfaces of f and g are given by the envelopes generated by Sf and Sg as they move on f and g. This is equivalent to displacing, in the normal direction, the centres (Ul, U2, u3) of Sf and (V1,V2,v3) of Sg, as they move on f and g, by the radius of the spheres. Denoting the pair of linearly independent tangent directions to f at any point by tl and t2 and similarly to g by t' and t2 we formulate the following eight equations in ten variables f: f(ui,u2,u3) = 0 9 9g(vl,v2,v3) = 0 Sf: (x - u1)2 + (y - u2)2 + (Z - U3)2 - d2 = 0 Sg: ( - V1)2 + (y- V2)2 + (Z -V)2 - d2 0 (VSf.t) = O (VSf t2) = O (VS,.t) = O 10,~t

By eliminating the variables {u1, u2, U3, vl, v2, V3, d} the implicit equation of the Voronoi surface Vor(f,g) associated with f and g can be obtained, at least in principle. An example helps to illustrate the above procedure. Let f be a cylinder of unit radius, parallel to the z-axis with the line (x = O,y = 2) as its axis. Let g be another cylinder of unit radius, parallel to the x-axis with the line (z = O,y = -2) as its axis: f: X2+(y-2)2-1 = 0 g: z2+(y+2)2 1 = 0 Let d be the radius of the spheres Sf and Sg. At points (u1,u2,u3) and (vl, v2,v3) on f and g respectively, we have the equations Jf: u2 + (U2 - 2)-2 1 = 0 Sf: ( - U1)2 + (y - 2)2 + ( - 3)2 - d2 0=.: V3 + (V2 + 2)-2 1 = O S9: (X - V1)2 + (y - )2 + (Z - 3)2 - d2 = 0 The gradients Vf and VW are given by [2ul, 2u2 - 4, 0] and [O, 2v2 + 4, 2v3]. The two independent tangent vectors at (ul, u2, u3) on f, are t =(O (0, 1) t2 =(2-u2, u, O) At (vl, v2,v3) on g they are t = (1, 0, O0) t = (0, -v3, V2 + 2) Thus, the final system of eight equations is given by u2 + (2 - 2)2 - 1 = 0 (X- U1)2 + (y- U2)2 + (Z - U3)2 -d2 = 0 + (v2+2)2-1 = 0 (X - 1)2 + (y - v2)2 + (z - 3)2 - d2 = 0 z —u3 = 0 (x - u)(2- U2) + (y- 2)u1 = o X - = 0 -(y -V2)V3 (Z -v 3)(v2 2 ) = 0 After elimination, we obtain the equation of the Voronoi surface.

Surface Equation r-Offset Equation Plane z Plane z - d Sphere x2 + y2 + z2 _ r2 Sphere x2 + y2 + z2 _ (r + d)2 Cylinder x2 + y2 -_ 2 Cylinder x2 + y2 _ (r + d)2 Cone x2 + y2 _ z2 tan2(y) Cone x2 + y2 - (z + d/ sin(^y))2 tan2(I7) Torus (x2 + y2 + z2 _ r2)2 Torus (2 + y2 y2+ z2 _ (r + d)2)2 +2c2(z2 _ (z2 + y2 + r2)) + C4 +2c2(z2 - (92 + y2 + (r. + 6)2)) + lC Table 1: d-Offsets of CSG Surfaces Elimination of the additional variables in an attempt to derive an implicit equation for the Voronoi surface is a task well beyond the capacity of currellt elimination procedures known to us; see, e.g., [7]. Instead, we use the equations formulated by the general method only for numerical computations that analyze the surface locally, as in, e.g., [5]. We mention that this method may generate extraneous solutions. Some of these may be eliminated by adding additional equations; see [6]. Whether such additions succeed in all cases is not known at this time. Note also that the general method, as described, cannot distinguish between odd and even Voronoi surfaces. In consequence, the implicit equation derived from the system (1) must be the product of the two surfaces. This fact would be unpleasant for a global surface analysis. For a local surface analysis, however, the additional surface components present no serious obstacle. 3.2 Simplifications for Special Surfaces The explicit derivation of the Voronoi surface, by the procedure just described, requires excessive symbolic computations. Considerable simplifications are possible for specific classes of surfaces, including planes, natural quadrics, and tori. For example, if one of the primary surfaces is a plane and the other a cylinder or a cone, it is easy to see that the associated Voronoi surface is a cone [3]. Such simplifications are based on the idea to replace the four equations describing the d-offset of a surface with a single equation, where possible, thereby eliminatingo up to six variables outright. Note that d-offsets are explicitly known for planes, natural quadrics, and the torus. They are summarized in Table 1. Figures 6 through 8 explain the geometric meaning of the constants in the equations. The offset equations are readily verified. As an example, we derive the even Voronoi surface of the two non-ilntelrsect ing

:/t,,' /',, -/ CIL Figure 6: Plane and Sphere Constants i iiV I;' W~S,,,"a', * II I Figure 7: Cylinder and Cone Constants Figure 8: Torus Constants 13

cylinders discussed before. The equations for the respective d-offsets are then: F: 22 + (y- 2)2- (1 + d)2 = 0 G: z2+(y+2)2-(1+d)2 = 0 Here, d is eliminated in h = F - G, which is the sought equation of the even Voronoi surface of the two cylinders: h: 2- 8y-z2 = 0 It is a hyperbolic paraboloid, as shown in Plate-I. In general, d has to be eliminated in two steps. As an example, consider the odd Voronoi surface of the two cylinders. It is described by F: x2 + (y-2)2-(1+d)2 = 0 G: z2+(y+2)2-(1-d)2 = 0 We obtain F - G = - 8yx2 - y 2 - 4d from which we determine d as a function of x, y and z: d = (x2 - 8y- z2)/4 Substitution into.F then yields the equation of the odd Voronoi surface as h = x2 + (y - 2)2 - (1 + (x2 - 8y - z2)/4)2 This is a quartic surface. Since the cylinders do not intersect, physically there cannot exist a Voronoi surface with an odd component. Algebraically, we might say that the odd Voronoi surface does not contain any real points. If the cylinders have a nonempty intersection, the odd Voronoi surface will contain real points. Such an example is shown in Plate-II. We mentioned in Section 1 that the Voronoi surface of two algebraic surfaces may be semi-algebraic. This is the case with the odd Voronoi surface shown in Plate-II. Here, the algebraic surface has four conical singularities, two of which are visible. The central part of the surface, in shape roughly like a pillow, is the odd Voronoi surface and enrds in the four conical points that lie on the two cylinder axes. The containing algebraic surface continues beyond these singularities.2 Its other points do not belong to the Voronoi surface, since the points of equal distance on the two cylinders minimize the distance locally only, not globally. 2In the picture the four conical surface extensions have been clipped almost entirely.

t-1'Iz...1 U

~~:-?C~~:llI~~ii5 s -- ---,, ~ L - g -;:o ~~i ~; —i — ~;~~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~ ~~~~~~~~~~~~~*1i ~( ~~;~.~ ~Fj — LT~;~.~5~4 ~~~cil~~ ~~~~'~i i. ~-f-~ - ~~~~~~~~~~-=f rT __ ~ ~ — ~-~

4 Voronoi Surfaces between Surface Pairs We now consider the geometry of Voronoi surfaces that result between pairs of bounding surfaces. We restrict the bounding surfaces to be planes, natural quadrics, and tori. Many of the Voronoi surfaces that arise can be analyzed by purely geometric argument, and we do this where appropriate. Note that we consider the bounding surfaces in their entirety. The Voronoi surface of such a pair, as pointed out earlier, is not always a complete algebraic surface, but is always part of an algebraic surface. We do not address how to trim Voronoi surfaces. First, we recall the relevant geometric facts about Voronoi curves for points, circles, and lines. These results are used later to analyze the Voronoi surfaces. In the following, we refer to planes, natural quadrics, and tori, collectively as CSG surfaces. 4.1 Voronoi Curves of Points, Circles, and Lines Proposition 4.1 The Voronoi curve of a straight line and a distinct point is a parabola. If the point lies on the line, the Voronoi curve is the perpendicular to the line at' lthat point. Proposition 4.2 The odd and even Voronoi curves of a circle C and a straight line L are parabolas. Each has the center of C as its focus. If the circle is tangent to L, then one of the parabolas degenerates into a half line. Proof Let the radius of the circle C be r, and consider first the case where L intersects C. Without loss of generality, we orient L such that the center of C lies to the outside of L or on L. Consider the component hi of the even Voronoi curve tlia.t lies outside both L and C. If p is a point on hi at a distance dl from the circle C and the line L, then p is at distance dl + r from the center of the circle. HIence it is also at distance dl + r from a line L1, parallel to and at a distance r from L, on the inside of L. See also Figure 9 left. By Proposition 4.1, the component hi of the even Voronoi curve lies on a parabola P1. Now consider the component h2 of the even Voronoi curve that lies inside C and inside L. If p is a point on h2, at a distance d2 from C and L, it is also at a distance r - d2 from the center of C. Hence it is also at a distance r - d2 from the line L1, and hence is also on the parabola P1. Note that the parabola passes through the intersection points of L and C, has the center of C as its focus and the perpendicular to L passing through the center of C as its axis.

LI P. IL ji IL h,= Pev4 i. "q-Q9 L C I/ I C1 -- ~v eve.. A A —— " of~ outFigure 9: Voronoi Curves of Line and Circle By a similar argument, the odd Voronoi curve can be shown to be another parabola, also passing through the intersection points of L and C, with the same axis, but an opposite orientation. Now assume that L is tangent to C. Then the component h2 of the even Voronoi curve no longer exists, and hi and the point of tangency cover the entire parabola. Moreover, the odd Voronoi curve is the half line on the perpendicular to L at the point of tangency, that lies on the inside of L. See also Figure 9 right. When L and C do not intersect, the odd Voronoi curve does not exist. c Proposition 4.3 The Voronoi curve of two nonintersecting circles is a hyperbola if the circles have different radii, and a straight line if the circles are of equal radius. Proof Let C1 and C2 be the two circles, and consider a point p exterior to both, on the Voroni curve. If d is the distance from either circle, then the distance to the two centers is d + r1 and d + r2, respectively, where r1 and r2 are the radii. Hence the difference of the two distances is constant. If the radii differ, then the constant is not zero, and hence the Voronoi curve is a hyperbola. Otherwise, the difference is zero, i.e., the Voronoi curve is a straight line. o Proposition 4.4 The odd Voronoi curve of two intersecting circles is an ellipse and the even Voronoi curve a hyperbola. If the circles have equal radii, the hyperbola degenerates into a straight line. Proof Let C1 and C2 be the two circles, and consider a point p exterior to both, on the even Voronoi curve. If d is the distance from each circle, then the distance to the two centers is d + rl and d + r2, respectively, where rl and r2 are the radiii. Hence the difference of the two distances is constant, so the even Voronoi clurve 16

I A \ Figure 10: Voronoi Curves of two Circles is a hyperbola if rl 5 r2 and a straight line if rl = r2. Now consider a point q on the odd Voronoi curve, with distance d from both circles, as shown in Figure 10. The distances from the two centers are therefore rl - d and 7'2 + d, so the sum of the distances is constant. Hence the odd Voronoi curve is an ellipse O 4.2 Voronoi Surfaces of CSG Surface Pairs We classify the types of Voronoi surfaces for CSG surface pairs. Although the algebraic degree of a Voronoi surface can be as high as 16, for two tori in general position, there are many cases in which the Voronoi surface is much simpler. Moreover, there are many geometric properties of interest to be reported. We think of 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. The geometry of the Voronoi surface may depend on whether two positive r-offsets are intersected, or whether a positive and a negative r-offset are intersected. We speak of an even Voronoi surface in the positive/positive and in the negative/negative case. In the positive/negative and the negative/positive case, we speak of an odd Voronoi surface. We classify first those Voronoi surfaces in which one member of the pair is a plane. The following is elementary: Proposition 4.5 Consider the Voronoi surface Vor(f,g), where f is a plane and y is a plane, sphere, cylinder, cone, or a torus. Then the degree of Vor(f, g) does not exceed the degree of g. Proof Since the r-offset of f is a plane, we may write r = h(x, y, z), where h is linear. Consider the r-offset of g, where g is a CSG surface. Any term xiyJz'krm hil the 17

r-offset equation satisfies i + j + k + m < 2 for the sphere, cylinder, and cone, and satisfies i + j + k + m < 4 for the torus. Substitution into the equation for g therefore results in an equation of degree at most the degree of g. 0 Note that, when f is a plane, the geometry of the odd and the even Voronoi surface do not differ. This is analogous to Proposition 4.2. The individual Voronoi surfaces are characterized now: Theorem 4.6 Let h = Vor(f,g), where f is a plane. (i) If g is a plane, then so is h. (ii) If g is a sphere, then h is a paraboloid of revolution. (iii) Let g be a cylinder. If the axis of g is parallel to or lies in f, then h is a parabolic cylinder. If the axis of g intersects f in a point, then h is a cone whose baseline is the elliptic or circular intersection of g and f. (iv) If g is a cone, then so is f. If f contains the axis of g, then h has a hyperbola as base. If f does not contain the axis of g, nor its vertex, then h has the intersection of f and g as its base. as base. (v) Let g be a torus. If f is perpendicular to the axis of the torus, then h is a surface obtained by rotating a parabola about the axis. Proof Case (i) is trivial. For Case (ii) observe that Vor(f,g) must be a surface of revolution about the normal to f passing through the center of g. It follows from Proposition 4.2 that h is a paraboloid of revolution. Case (iii): Let the axis of cylinder g be parallel to the plane f, and consider a plane P perpendicular to the axis of g. P intersects f in a line L and y in a circle C. Because P is also perpendicular to the plane f, the points on f and g that are nearest to a given point p in the plane P must also lie on the plane P. So, P intersects the Voronoi surface of f and g in the Voronoi curve of the circle C and the line L, by Proposition 4.2 a parabola. Since the position and size of L and C are independent of the position of P, therefore, Vor(f,g) is a parabolic cylinder. Now assume that the axis of g intersects f. Let C be the curve of intersection between f and g. Clearly, C is either a circle or an ellipse and lies on the Voronoi surface h. Consider the plane P through the axis of g and perpendicular to f. P intersects f in a line L1 and g in the parallel lines Lz and L3. Since tle closest approach on f and g, to any given point p on P must lie on these linies, P intersects h in two lines IHl and H2 that bisect the angle between L1 and Ls,

Figure 11: Structure of the Voronoi Surface of Cylinder and Plane and the angle between L1 and L3. It is not difficult to see that the lines H1 and -H2 intersect in a point v on the axis of the cylinder g. Consider any plane Q through the cylinder axis, and note that Q is not necessarily perpendicular to f. Then Q contains v and a point w in whiich C intersects Q. Note that both points lie on h. We argue that the line vTw lies on the Voronoi surface h. Now the shortest distance of a point q on this line, from the cylinder g, varies linearly with the distance of q from w. Similarly, the shortest distance of q from the plane f varies linearly with the distance of q from w, which is evident when considering the plane Q' through the line v, W that is perpendicular to f. See also Figure 11. Since both v and w are on h, and since the distances from f and g vary linearly, the two distance functions must be the same. That is, the line vT- is on h. We have shown that h contains all lines through points of C and through v. It follows that h is a cone with vertex v and base line C. Case (iv): Assume that f contains the axis of g, so g intersects f in the degenerate conic C consisting of two intersecting lines. Note that C is on It. Consider a point p on h other than the vertex v of the cone. The point of closest approach to p on f is pf and on g it is p9. We consider the line Lf through v and pf, the line L9 through p9 and v, and the line LAh through p and v. We want to show that Lh is on the Voronoi surface. Nowv Lf is in f and Lg in g. Let q(A\) - Ap + (1-A)v be any point on Lh, and qf((A) = APf + (1 - A)v and qg(A) Apg + (1 - A)v the corresponding points on Lf and Lg. By proportionality, the distance (q(A),qf(A,)) is equal to the distance (q(A), q9(A)), and the angles (q(A), q(A), v) anld (q(A), q (A),v) bothl are right. angles. Hlence, the line L, is on the Voronoi surface; i.e., the Voronoi surface is a cone. 19

Figure 12: Section of the Voronoi Surface of a Cone and a Plane We now show that the curve in which h intersects a plane P perpendicular to f is a hyperbola. Consider a point p on h at distance d from both f and g. Then p lies on a plane parallel to f, at distance d, that intersects P in a line If. Moreover, p lies on a cone, of equal apex angle a as g, that intersects P in a circle cg. If rp is the radius of the circle in which g intersects P, then the radius of c9 is rp + d/ cos(a). Referring to Figure 12, we have (rp + d/ cos(a))2 = x2 + d2 Algebraic manipulation brings this equation into the form (d/ cos(a) + rp/ sin2(a))2 - z2 - 4r cot2(a) = 0 (2) For a fixed plane P, rp and a are constants, hence (2) is the equation of a hyperbola. If f does not contain the axis of the cone g, nor the vertex of g, then f and y intersect in the nondegenerate conic C. We consider a plane P perpendicular to f containing the axis of g. P intersects f in the line L1, and g in the intersecting lines L2 and L3. Clearly, the angle bisectors, H1 of the lines L1 and L2, and H2 of the lines L1 and L3 are on the Voronoi surface h. The intersection of H1 and H2 is on the axis of g, because their intersection point v has equal minimum distance from both L2 and L3.3 Therefore, the same argument as in the cylinder/plane case shows that h is a cone with base line C. Finally, if f contains the vertex of g but not its axis, then h is a cone whose vertex is the vertex of G. To argue this case, consider an offset of f by some distance d and a plane parallel to f, at distance d. Their intersection is a 3This argument also applies to case (iii).

L. P / Figure 13: Voronoi Surface when Plane f is perpendicular to Torus axis nondegenerate conic C that lies on h and is the base of the cone. The details are straightforward. Case (v): By Proposition 4.5, h is a quartic surface. Let L be the axis of symmetry of the torus, and consider any plane P containing L. P intersects g in two circles C1 and C2, and f in a line Lf. Let p be a point in P. Since f is perpendicular to L, the point pf in f minimizing the distance p,;pf is in P. Moreover, since L is the axis of symmetry of g, the point p9 on g minimizing the distance pa is also in P. See also Figure 13. Therefore, P intersects the Voronoi surface h in curves that must be the Voronoi curves of C1 and Lf, and of C2 and Lf. These curves are parabolas. Since the distance of the circles from the axis L is fixed, h is a parabolic torus obtained by rotating the Voronoi curves about L. 0 Theorem 4.7 Let h = Vor(f,g), where f is a sphere. (i) If g is a sphere of equal radius, then h is a plane or a prolate spheroid. If g is a sphere of unequal radius, then h is a prolate spheroid or a two-sheeted hyperboloid. (ii) If g is a cylinder whose axis contains the center of the sphere, then h is a plane or a surface obtained by rotating a parabola about a line perpendicular to the axis of symmetry. (iii) If g is a cone whose axis contains the center of the sphere, then h is a figure of revolution, about the axis of the cone. The components of h are obtained by rotating a parabola around a line that is not perpendicular to the axis of symmetry. W7'hen y is tangent to f, then h has a component

/'\ ~\ Figure 14: Voronoi Surface of Cylinder and Sphere that is a right circular cone. (iv) If g is a torus whose axis of revolution contains the center of the sphere, then h is a figure of revolution. Its components are obtained by revolving ellipse, or hyperbola around the torus axis. If the radius of g is equal to the minor radius of the torus, then h contains also a cone, a cylinder, or a plane. Proof Case (i): Consider a plane P containing the centers of both spheres. If p is any point on P, then the points pf on f and pg on g nearest to p are also in P. It follows that h is a surface of revolution whose axis is through the centers of f and g. The statement now follows from Propositions 4.3 and 4.4. Case (ii): If the cylinder axis contains the center of the sphere, then the Voronoi surface must be a surface of revolution about the cylinder axis. By Proposition 4.2, h is obtained by rotating a parabola about its latus rectum.4 It has a spindle as shown in Figure 14. When the radius of the sphere is equal to the cylinder radius, by Proposition 4.1, the even Voronoi surface is a plane through the center of the sphere and perpendicular to the cylinder. Case (iii): Clearly h is a surface of revolution about the axis of the cone. Considering a plane P containing the axis of g, the statement follows from Proposition 4.2. See also Figure 15. Case (iv): Again, h must be a surface of revolution whose geometry is determrined by the section with planes P containing the axis of the torus. By Propositions 4.3 and 4.4, the Voronoi curves of the circles in which P intersects f and g are ellipse, hyperbola, or line. Depending on the axis position, the line can generate a cone, a cylinder, or a plane as component of the Voronoi surface h. a 4The line through the focus of the parabola perpendicular to the axis of symmetry. 22

Figure 15: Voronoi Surface of Cone and Sphere Theorem 4.8 Let h = Vor(f,g), where f is a cylinder. (i) If g is a cylinder of equal radius, then the even Voronoi surface 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. (ii) If g is a cone and the axes of f and g coincide, the odd and even Voronoi surfaces are cones. (iii) 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 the Voronoi surface does not contain a spindle, otherwise it does. Proof Case (i): Assume that f and g have equal radius. If the axes of f and g are parallel and not coincident, then h is a plane by Propositions 4.3 and 4.4. If the axes intersect, then the intersection curve of f and g is a pair of ellipses that lie in two planes, say P1 and P2. Note that these planes bisect the angle between the intersecting axes of f and g. Consider enlarging the radius of both cylinders by the same distance d. Evidently, the intersection curve of the enlarged cylinders is on h, and is also in P1 and P2. Hence h consists of P1 and P2. Assume that f and g have equal radius but skew axes. Without loss of generality, the equation of f is 2 + y2 - r2 = 0, and the equation of g is g(x,y,z)- r2 = 0, where Yl is a quadratic polynomial in x,y,z without a 23

/ j Figure 16: Voronoi Surface Point for two skew Cylinders constant term. The even Voronoi surface is therefore obtained from x2 +y2 (r+d)2 = 0 gl(x,y,z)-(r+d)2 - o by elimination of d, effected by subtraction. Since x2 + y2 - gl is quadratic, the even Voronoi surface is quadratic. Let I be the line of closest approach of the axes of f and g, and assume that the axes of f and g pass at right angle, at distance m. The plane P containing both I and the axis of f intersects f in a pair of lines and g in a circle. It is not hard to see that h intersects IP in a parabola. By symmetry, h intersects the plane P' containing I and the axis of g also in a parabola. Next, consider a plane P1 parallel to P, at distance c. Let p be a point on the intersection of h and P1, at distance d from both cylinders. Referring to Figure 16, we have (m + X)2 + y2 = (r + d)2 and c2 + x2 = (7' + d)2. Subtracting, we obtain m2 + 2mx + y2 _ c2 = 0, hence h intersects P1 in a parabola. It follows that h is a hyperbolic paraboloid. If the angle between the skew axes is not a right one, then a purely algebraic argument can be given, roughly as follows. Consider h = x2 + y2 - gl and compute its invariants. The invariants certify that h is a hyperbolic paraboloid in this case also. If f and g have different radii but have parallel axes, then the statement follows from Propositions 4.3 and 4.4. Case (ii): Consider the even Voronoi surface h. it is a surface of revolution about the common axis. Consider the plane P through the axis. It intersects f in two parallel lines L1 and L2 and g in two intersecting lines L3 and L4 that meet at a point v on the common axis. The bisectors f11 and /2 of the angles formed by L1 3 and L2L4 are lines consisting of points that are equidistant friom f and 9. Also H1 and 1Fz meet at a point u on the common axis. The surface

of revolution, h, formed by H1 and H2 is a cone with vertex at u. Moreover, since the two triangles on P with vertices on L1 and L2 and the common base uv are equal in all respects, the apex angles of h and g are also equal. It is easy to see that the odd Voronoi surface is also a cone since it is generated by the perpendiculars to H1 and H2 at the points of intersection with L1 and L2. Case (iii): Consider any plane P containing the coincident axes of f and g. The point pf on f of closest approach to a given point p in P must lie in P, and the same is true for the point pg on g. Hence h is a figure of revolution. P intersects f in two lines parallel to the axis, and g in two circles. If g and f intersect, By Proposition 4.2, P intersects h in a pair of intersecting and a pair of non-intersecting parabolas. Since the lines in which P intersects f are parallel to the axis of f, the parabolas revolve around a line perpendicular to the line of symmetry. If the cylinder diameter is less than the smaller diameter of the torus, h is a paraboloid of revolution. Moreover, the parabola orientation is such that there is no spindle. If the cylinder diameter is larger than the smaller diameter of the torus, then the odd Voronoi surface contains a spindle. O Theorem 4.9 Let h = Vor(f,g), where f is a cone. (i) If g is a cone, and the axes of f and g are coincident, then the components of h consists of cones. (ii) 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. Proof Case (i): If f and g have the same axis, then h is clearly a figure of revolution. A plane P containing the axis intersects f and g in two pairs of intersecting lines, and the bisectors of two lines, one from f and the other from g, are the generators of h. Therefore, h has right-circular cones as components. Case (ii): Clearly h is a figure of revolution. Let P be a plane containing the common axis of f and g. P intersects f in two lines and g in two circles. By Proposition 4.2, P intersects h in four parabolas. Since the lines in which P intersects f are at an (angle with respect to the axis of f, none of the parabolas revolves around a line perpendicular to the line of symmetry. o Theorem 4.10 Let h = Vor(f,g), where f and g are tori with coincident axes. 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 the even Voronoi surface is a cylinder or a cone. If f and g

are congruent with a common center, then the even Voronoi surface is a pair of planes containing the intersection curve. Proof Obviously h is a figure of rotation. Hence the the first two parts of theorem follows from Propositions 4.3 and 4.4. If f and g are congruent and have the same centers, then their intersection consists of two plane curves, in the planes P1 and P2. The d-offsets of the tori are also congruent with common centers, and their intersection curves lie in P1 and P2. Hence the Voronoi surface has two planes as components. By symmetry, there is no additional component. C 5 Conclusion We have presented a conceptually simple method for constructing the interior skeleton of CSG objects. The individual elements of the skeleton were showni to be the well known Voronoi curves and surfaces. In general, the Voronoi elements have a complicated geometry. We analyzed a number of special cases in which the Voronoi surface of pairs of CSG surfaces has a simple geometric structure. Skeleton surfaces have been proposed for use in a variety of important applications such as computer-aided design, motion planning, mesh generation and shape analysis. Our investigations, while illuminating the intrinsic geometric complexity of such surfaces, provides insights that can be exploited in skeleton construction algorithms. Acknowledgements A. Hadjidimos provided the critical link for Case (iv) of the proof of Theorem 4.6. 6 References 1. H. Blum (1967), "A Transformation for Extracting New Descriptors of Shape," in Models for the Perception of Speech and Visual Form, 362380, Weiant Whaten-Dunn, ed., MIT Press, Cambridge, MA. 2. S. Cameron and J. Rossignac (1988), "Relationship between S-Boulnds and Active Zones in Constructive Solid Geometry," IBM Rept. RC14246, Yorktown Heights.

3. V. Chandru, D. Dutta, C. Hoffmann (1990), "Variable Radius Blending with Cyclides," in Geometric Modeling for Product Engineering, 39-58, K. Preiss, J. Turner, M. Wozny, eds., North Holland. 4. R. Goldman (1987), "The Role of Surfaces in Solid Modeling," in Geometric Modeling: Algorithms and New Trends, 69-90, G. Farin, ed., SIAM Press. 5. C. Hoffmann (1989), Geometric and Solid Modeling, an Introduction, Chapter 6, Morgan Kaufmann, San Mateo, CA. 6. C. Hoffmann (1990), "A Dimensionality Paradigm for Surface Interrogation," Comp.-Aided Geom. Design, to appear. 7. C. Hoffmann (1990), "Algebraic and Numerical Techniques for Offsets and Blends," in Computations of Curves and Surfaces, M. Gasca, W. Dalmen, S. Micchelli, and L. Schumaker, eds., Kluwer Academic Publishers. 8. D.T. Lee (1982), "Medial Axis Transformation of a Planar Shape," IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-4(4), 363-369. 9. L.R. Nackman (1982), "Curvature Relations in Three-Dimensional Symmetric Axes," Computer Graphics and Image Processing, 20, 43-57. 10. N.M. Patrikalakis (1989), "Shape Interrogation," Proceedings of Automation in the Design and Manufacture of Large Marine Systems, MIT Sea Grant College Program, Cambridge, MA. 11. F.P. Preparata (1977), "The Medial Axis of a Simple Polygon," Proceedings of The Sixth Symposium on Mathematical Foundations of Computer Science, 443-450. 12. F. Preparata and M. Shamos (1985), Computational Geometry, Springer Verlag, New York. 13. A. Requicha and H. Voelcker (1977), "Constructive Solid Geometry," Tech. Memo 25, Prod. Automation Proj., University of Rochester. 14. S. Stifter (1990), "The Roider Method: A method for static and dynamic collision detection," in Issues in Robotics and Nonlinear Geometry, C. Hoffmann, ed., JAI Press. 15. G. Vaneek Jr. (1990), "Towards Automatic Grid Generation Using Binary Space Partition Trees," Rept. CER-90-6, Comp. Sci. Dept., Purdue Univ 27~.

3 9015 02229 1689 THE UNIVERSITY OF MICHIGAN DATE DUE 1113,o CIAwm 313O ft4bj