Boundry-Based Separation for B-rep?CSG Conversion* Vadim Shapiro** Donald L. Vossler*** TR 91-1222 August 1991 Department of Computer Science Cornell University Ithaca, NY 14853-7501 *This document is also available as CPA Technical Report CPA91-5, Cornell Programmable Automation, Sibley School of Mechanical Engineering, Ithaca, NY 14853. It describes the research supported by the General Motors Corporation (through a Corporate Fellowship), the McDonnell Douglas Corporation, and in part by the National Science Foundation under grant MIP-8719196, and by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research Contract N00014-88-K-0591. **On leave from the Computer Science Department, General Motors Research Laboratories, Warren, MI 48090, shapiro?gmr.com. Current address: Department of Computer Science, Cornell University, Ithaca, NY 14853, shapirn?cs.cornell.edu. ***McDonnell Douglas Corporation, Cypress, CA 90630, vossler?vxd.mdcbbs.com Boundary-Based Separation for B-rep?CSG Conversion* Vadim Shapirot Donald L. Vosslert July 1991 *This document is also available as CPA Technical Report CPA9i-5, Cornell Programmable Automation, Sibley School of Mechanical Engineering, Ithaca, NY 14853. It describes the research supported by the General Motors Corporation (through a Corporate Fellowship), the McDonnell Douglas Corporation, and in part by the National Science Foundation under grant MIP-8719196, and by The Advanced Research Projects Agency of the Department of Defense under Office of Naval Research Contract N00014-88-K-o591. ton leave from the Computer Science Department, General Motors Research Laboratories, Warren, MI 48090, shapiro?gmr.com. Current address: Department of Computer Science, Cornell University, Ithaca, NY 14853, shapiro?cs.cornell.edu. tMcDonnell Douglas Corporation, Cypress, CA 90630, vossler?vxd.mdcbbs.com Abstract We have shown earlier that one of the most difficult steps in performing brep--HCSG conver- sion for a curved solid object consists of determining a set of halfspaces that is sufficient for a CSG representation of the solid. This usually requires the construction of additional halfspaces whose boundaries do not contribute to the boundary of the solid. Such halfspaces are called separating halfspaces because their purpose is to separate certain subsets of E3 inside the solid from those outside of the solid. Construction of separating halfspaces is specific to a particular geometric domain, but several generic appro&hes are possible. A boundary.based separation is a construction of separating halfsp&es that relies on the information present in the boundary of the solid being converted. While boundary-based sep? ration for solids with non-planar edges is not well understood, we study the constraints on the degree of separating halfspaces, and show that a set of line& separating halfspaces exists for any solid whose boundary contains only planar edges. We apply the boundary-based separation to solids bounded by general quadric surfaces. Specifically, we prove that a sufficient set of linear separating halfspaces exists for any such solid, and consider the required constructions in several common situations. Implications for more general solids are also discussed. 2 1 Motivation Boundary representations (b-rep) and Constructive Solid Geometry (CSG) are two representation schemes that are most widely used in solid modeling. While the problem of computing a b-rep from a CSG representation is relatively well understood [RV85j, the inverse problem of b-rep?CSG conversion has not been systematically studied until recently. The importance of the conversion problem, earlier results, and related literature are discussed in [SV9l], [SV9o]. Solution to the general b-rep?CSG conversion for a solid 5 has been developed systematically in [SV91], and roughly consists of the following steps. 1. Induce a set H6 of natural halfspaces associated with the boundary as of a solid 5. 2. Construct a sufficient set of additional separating halfspaces Ha so that solid 5 can be repre- sented by some CSG representation on H = Ha U H6. 3. Compute a decomposition of the Euclidean space Ed into "cells" such that each cell has a CSG representation using halfspaces from H, and determine which of these cells are subsets of 5. 4. The union of the cells inside 5 is a canonical CSG representation of 5, which can be subse- quently optimized using Boole? iwninuz?ion techniques. Construction of a sufficient set of separating halfspaces (step 2 above) is the single most difficult task that in many ways determines the success and practicallty of the conversion. Various strategies for separation are discussed in [SV9l]. A boundary-based separation is a construction of separating halfspaces that relies on the information present in the boundary of the solid being converted. The advantage of the boundary-based separation is that it attempts construction of a sufficient set of halfspaces of a reasonable size a priori, without invoking expensive geometric tests or planning algorithms. This approach to b-rep?CSG conversion has been used successfully in [SV9Oj to solve the conversion problem for a large class of tw?dimensional solids. Recent results in [Sha91] general- ize some boundary-based separation techniques for higher-dimensional solids. This paper studies boundary-based separation techniques that have allowed us to implement an experimental b- rep?CSG conversion for solids bounded by quadric surfaces (though some results apply to more general solids as well). Specifically: o+ Iii section 3.3, we study the constraints on the degree of separating halfspaces; we show in section 3.4 that a set of linear separating halfspaces (whose boundaries are planes) exists for any solid 5 whose boundary as contains only planar edges. o+ A sufficient set of linear separating halfspaces is constructed in section 3.5 for solids whose faces lie in convex surfaces and intersect on planar edges. o+ We apply these results to solids bounded by quadric surfaces in section 4. It is shown that a sufficient set of linear separating halfspaces exists for any solid bounded by general quadric surfaces. Specific constructions are discussed for several common situations. 3 2 Preliminaries This section presents background material on the b-rep?CSG conversion problem. The original formulation appears ill [SV9l] and [SV9O]. The following presentation is somewhat modified to reflect the results in [Sha91], but is consistent with the earlier formulations. 2.1 Boundary representation of solids A solid 5 is a compact regular semi-analytic set, or an r-set [Req77]. Boundary representation (b-rep) of 5 is a representation of 5 by its boundary, as(for more precise definitions see [Sil81j, [Sha9l]). The boundary as defines 5 completely and unambiguously in the following sense [Req77]: (1) complement of the boundary, --Has, is a disconnected subset of Ed; and (2) interior iS and exterior eS are unions of some connected components of --Has. The boundary ascan be represented in many different ways, typically as a collection of closed two-dimensional sets called faces Q?, i.e. as=UQi Various types of faces are considered in [Sil8lj; for our purposes, the exact choice is immaterial. Faces in asmay not be disjoint, but intersect on edges Ek defined by Ek = Qa' fl Similarly, edges Ek may intersect ouly at vertices. An edge Ek may have two vertices, or no vertices. Each face Q? is a subset of a surface (homogeneously two-dimensional subset of E3); the surface itself is a subset of a set (f? = 0), where fj(x, y, z) is a real analytic (or algebraic) function. A closed analytic (algebraic) ha(fspace hj is induced from (or associated with) a face Q? as hi=fPIf(P)>OYE(fi >0). An open halfspace is defined similarly by (f? > 0). The halfspaces induced from a b-rep of 5 are called natiral halfspaces of 5. If hj is a closed halfspace, then ?hj = (f? = 0), but the equallty does not hold in general for open halfspaces, and halfspaces need not be regular sets. 2.2 CSG representation of solids A CSG representation ? of a solid 5 is a syntactic expression constructed using regularized set operations on a set of regularized halfspaces [RV77]. We write 5 = i? to denote the fact that ? represents set 5. Regularization operation is defined by rX = kix = Regularized set operations fl*, U*, ? are defined by regularizing the results of the corresponding standard set operations, respectively. Properties of closed regular sets have been studied in [MT46], [KM76], [RT78], and are well understood. Given a finite set H of halfspaces hi, an infinite number of CSG representations can be con- structed, but they represent at most a finite number of distinct closed regular sets 5. The set of 4 all such sets (5? is a finite Boolean algebra with operations n., u?, and --H?. Each such set 5 can be represented by a unique disjunctive canonical CSG representation as 5 = UiflkI, k where 11k is a canonical intersection term defined by 11k = X1fl?...fl?n, x:E?(fi>?O),(fiO),(f? 0) if and only if sign[f(a)] $ sign[f(b)j. Two disjoint point sets A and B are separated by a family of ha(fspaces G = fy?) if and only if Va E A,Vb E B, Sgj E G such that a and bare separated by g?. Two distinct points a, b E Ed are strictly separated by a halfspace g = (f > 0) if f(a) $ 0, f(b) $ 0, and a and b are separated by 9. Similarly, we define two sets A and B to be strictly separated by a set of halfspaces G if all a E A are strictly separated from all b E B by some g? E G. Using these definitions, two distinct components A and B are strictly separated by the halfspaces in H if and only if A and B are not components of the same canonical intersection term 11k. The describability theorem states that a sufficient set of separators must separate any component inside 5 from those outside of 5. A sufficient set of separators exists for any semi-algebraic set 5 and can be computed, at least in principle, using techniques based on cylindrical algebraic decomposition [Col75], [CR88]. (Examples and various properties of separators are also discussed in [SV91].) Algebraic techniques result in a large number of separators of degree much higher than that of the natural halfspaces, and no such practical algorithms are available. Alternatively, one could compute all pairs of components that must be separated for 5 to be describable and use this information to construct necessary separators, but this leads to difficult problems similar to those in motion planning. The boundary-based separation is a practical alternative to the algebraic and planning methods. It aims to construct a sufficient set of separators a priori, based on various topological and geometric properties of solids. For example, let 5 be a tw?dimensional solid with "faces" that are curved arcs, with each arc being a subset of a curve with a constant curvature sign. Figure 2(a) shows a planar solid 5 represented by its boundary. But 5 is not describable by H because several pairs of two-dimensional components must be separated (e.g. those containing points ? and P4, Pi and P3, etc.). Figure 2(b) shows that the set C = (9i ,92,93,94) of linear separators associated with the chords of OS is sufficient for CSG representation of 5. Indeed 5 is describable by H U C, since no other pairs of components need to be separated. We have shown in [SV9O] that for such solids, the set of linear halfspaces associated with the arc chords is always sufficient. This result can be generallzed for higher-dimensional solids (see theorems 5 and 3 below), but, in general, constructing a sufficient set of separators in E3 is much more difficult. Below we study some separation techniques for higher-dimensional solids. 3.2 Separation properties A path ab is a one-dimensional closed submanifold of Ed with boundary consisting of points a and b. An arbitrary path is a member of an (homotopy) equlvalence class of all possible paths joining a and b. Consider a (d--H 1)-dimensional set X such that its complement --HX, is a disconnected subset of Ed, and two points a, b ? X. By definition, path ab and X have complementary dimensions, since dim(ab) + dimX = d. Assuming that ab and X intersect transversally in the topological sense,2 ab fl X is a finite set of points (refer to Figure 3). The number of such intersection points modulo 2 is called the mod 2 intersection number of path ab with respect to X and is denoted by 2Intuitively this means that at every point of ab fl X, the sum of tangent spaces of ab and X span Ed. Sard's theorem implies that almost all intersections are transversal [GP74]. 8 p5 0. nZ (a) S is not describable by H, because severai pairs of tw??dimensioiiai components (marked by points) must be separated. pi p3 g2 (b) Boundary-based separation by G = ....... , ???. Not an 9j'5 are necessary. Figure 2: Boundary-based separation for two-dimensionai solids 9 Figure 3: Any transversal path abintersects X at an odd number of points, i.e. 12(ab,X) = 1 12(ab,X). (For formal definitions of these concepts and related discussion the reader is refered to [GP74].) Using the above terminology, we make two observations. o+ IfS is a solid, the Jordan-Brouwer theorem [GP74] implies that for every pair of points a E iS. b E eS, and any transversal path ab, 12(ab,as) = 1. o+ Points a,b?8h are strictly separated by a halfspace h if and only if 12(ab,?h)= 1 whenever an arbitrary path ab and ah intersect transversally. The above concepts provide basic tools for studying separation properties. Note that all paths abare equivalent in the sense of having the same intersection number 12(ab,X). On the other hand, some paths can be more accommodating than others. For example, straight lines are convenient because the degree of a polynomial f? determines the maximum number of times an arbitrary line can intersect the set (f? = 0). In particular, suppose (f2 = 0) is a hyperplane and ab is a line segment connecting points a,b ? = 0). The points a and b are strictly separated by hj if and only ifabn(f? = 0) # ?. 3.3 Degree of separators We say that two components A and B touch each other if 8A fl 8B # ?. Components A and B of the same canonical intersection term cannot touch along a tw?dimensional surface, because they would be separated by the halfspace associated with that surface. If A and B touch along a curve C, neighborhood of every point c E C contains points a E A and b E B. Hence the boundary of any halfspace locally separating points of A and B must contain the curve C. The degree3 of such an intersection curve C limits the choices for the required separators. 3Here, by degree of the curve C we mean the degree of the real irredudble algebraic variety W containing C. Intuitively, deg(W) is the number of times W can be intersected by a hyperplane. 10 Neighborhood of c U : : : : : : : : : : o+ . : : : : : : : : : : : v Figure 4: If components A and B of canonical intersection term 11k are touching at the point c. then surfaces U and V intersect at c with even multiplidty Theorem 2 Let H be a set of halfipaces of degree k, and components A and II of the same canonicai intersection term flk touch aLong a curve C. Then the degree of C is < k2/2. Proof By assumption, the neighborhood of any point c E C must contain points a E A and b E B. Pick such points a and b and consider the path acb. C is an intersection of two surfaces U and V of degree k and, by assumption, a and b are not separated by halfspaces associated with U and V. Hence, perturbing the path ab we get a transversai intersection of ab and U (or V) such that 12(ab, U) = 12(ab, V) = 0. In other words, U and V each intersects the path acb at the point c with even multiplicity (see Figure 4). But then U and V intersect along the curve C with even multiplicity. By Bezout's theorem, the degree of C is less than or equal to deg(U)deg(V)/2 --H k2/2 (for example see [Ken77]). 0 Whenever two components A and B of the same canonical intersection term touch along an edge in the boundary &S of a solid 5, theorem 2 can be used to estimate the lowest possible degree of the required separator. Specifically, since U and V intersect along C with even multiplicity m> 1 U and V intersect with G'n-1 continuity along C [GW9l]. Any halfspace locally separating points of A and B must contain C, and intersect both U and V along C either transversally or with an odd multiplicity greater than one. Therefore, if the degree of C is k2/2, the degree of the required separating halfspace is > k/2. 3.4 Case of planar edges We now restrict ourselves to solids whose boundary contains only planar edges, i.e. every edge E C P for some plane P, and show that a sufficient set of linear separators exists for any such 5. The following result is the key to the corresponding boundary-based construction. 11 Theorem 3 (Face Separation [Sha91]) Suppose 5 is a solid, H6 is a set of natural halfipaces induced from as, and every face Qi C 8hj is separated from "the rest of the surface," Ri = 8hj --H Qi, by a family of linear halfspaces Cj (i.e. Vg E Ci, ag is a plane). Then 5 is describable by H6 u Ha with Ha = u,?=1C1. Proof (This is a special case of the result in [Sha91]). Consider any two components A C is and B C e5 in the decomposition of Ed by Hb, that are not separated by Hb. Pick two arbitrary points a E A, b E B, such that the line segment ab intersects 85 and 8hi, i = 1n, transversally. Then 12(ab, as) = 1, which implies there exists a face Qi which is intersected by ab an odd number of times. By assumption, a and b are not separated by hi E H6, the natural halfspace induced from Q:; hence 12(ab, 8hi) = 0, and ab intersects 8hj an even number of times. Thus the segment ab intersects both Qa, and Ri = Ohi --H Qi. But Q? and Ri are separated by a family of linear halfspaces Ci, and so ab must intersect some plane. It follows that a and b are also separated by Cj. Hence, any two components A C iS and B c e5 are separated either by H6 or by Ha = Ui Ci. By the describability theorem, 5 is describable by H6 u Ha. E The assumption that Ci is a set of linear separators is crucial to the proof, because a surface = 0) associated with a non-linear halfspace g E Gj, could be intersected by the line segment ab more than once. Thus, the conditions of the face separation theorem require that all faces Q? intersect on planar edges; therefore, for every face Q?, there exists some polyhedral (piecewise linear) surface passing through its edges that separates Q? from the rest of the surface, as required by the theorem. Corollary 4 For any solid 5 whose boundary 85 contains only planar edges, there exists a suffi- cient set of linear separators. While planarity of edges is a significant limitation, there are many geometric objects that naturally satisfy this requirement (for example, it is true by construction in [SedS5j and [PKS9]). Furthermore, the conditions in theorem 3 are sufficient but not necessary for the describability of solid 5. 3.5 Convex surfaces We now assume that 85 contalns only planar edges, and give a sufficient construction required by theorem 3 in a restricted but common situation. Specifically, suppose that every natural halfspace hi E Hb is a convex set. Well known generalizations of the Hadamard theorem state various sufficient conditions on the surface 8hj [dC76, p. 387]. For example, hi, is a convex set whenever 8hj is a connected surface whose Gaussian (total) curvature k > 0, and k > 0 for at least one point p E 8hj. We call hi a convex halfspace and 8hj a convex surface. If a face Q is a subset of a convex surface and is bounded by n planar edges, then it is easy to separate Q from the rest of the surface using only 0(n) linear separators. First, let us consider a simply-connected (without holes) face Q. Recall that faces and edges of a solid 5 are topological ?dimensional polyhedra [Req77]. In other words, for any face or edge X there exists a triangulation (K, ?) of X, where A' is an abstract pdimensional simplicial complex, and ? is a homeomorphism with X = 12 Ko triangulate ???/ Figure 5: Construction of all edge triangulation (K0, ?o) for a face Q. Each 2-simplex ill K0 is embedded in E3 as a planar triangle through some vertices of the face Q. The boundary of Q is a loop of n edges which is topologically a one-dimensional simplicial complex L containing n 1-simplices (refer to Figure 5). L can be also viewed as a graph (a cycle) with n nodes that can be triangulated to obtain a two-dimensional complex K0 containing n --H 2 triangles (2-simplices). Let us now define a map ?o that embeds every 2-simplex in K0 as a planar triangle VjVjVk in E3 through the three vertices of the face Q (Figure 5). Note that the planar triangle Vj VjVk cannot intersect the surface 8h anywhere except at the three vertices, because Oh is a convex surface, but different triangles could penetrate each other. Thus ?0(K0) is a piecewise linear triangular surface with possible self-intersections. We will call the pair (K0, ?o) an edge triangulation of the face Q. Edge triangulations are easy to construct (for example, by traversing the vertices of Q as shown in Figure 5), even though they are not unique. Theorem 5 Suppose h is a convex halfspace, a simply-connected face Q c Oh planar edges, and (K0, ?o) is an edge triangulation of Q. Let G be the set of associated with the set of planes: (1) containing every curved edge of Q, and (2) triangle in ?(K0). Then G separates Q from the rest of the surface R =--H Oh --H is bounded by n linear halfspaces containing every Proof Ifthe number of edges n < 2, the proof is trivial. So assume that n > 3. Let (K1, ?i) be a triangulation of the face Q, as shown in Figure 6. Each planar segment bounded by a curved edge Ej and a chord ViVi can also be triangulated. So let (K2, ?) be a triangulation of the union of all such planar segments, i.e. ?(K2) is a union of all such planar segments on the face Q. Let us "glue" the three abstract complexes K0, K1, K2 into a single abstract complex K by requiring that 13 (po ??.,, , ,? K2 glue," Figure6:Constructionofanabstractdosedtwc-dimensionalsimplidal surface. simplices x = y whenever ?(x) = tkj(y), i # j, i,j = 0,1,2 (Figure 6). By construction, K is an abstract closed surface, or a 2-manifold [Hop89]. We now construct an immersion ?`: K E3, ?(x), if x E K0 `k(x)--H= ?(:r), ifxEK1 ?2(x), if x E K2 that partitions E3 into a finite number of connected components (C1,C2,... , Ck). It is important that ali points of ?0(K0) and ?2(K2) lie in the planes through the edges of Q or triplets of vertices of Q, as assumed in the theorem hypothesis. Consider two arbitrary points q E Q and r E R. We now show that the straight line segment qr must intersect the surface ?(K) at some point x lying in one of the constructed planes. Since h is a convex set, the line segment qr is completely contained in h and intersects 8h only at the points q and r. Thus there exists a point q' E h lying on qr in the neighborhood of the point q (see Figure 7). Consider the path q'qr where qr is any path restricted to the surface ah and intersecting some edge Ej of Q an odd number of times. The path q'qr also intersects the plane through Ej and the surface ?(K) every time it intersects Ej. Furthermore, this path cannot intersect `k(K) anywhere else, because ?(K) n R = ?. It follows that points q' and r belong to different connected components Cj and Cj. Hence the straight line segment q'r must intersect the surface ?( K) at some point x lying between q and r, but x cannot be a point on the face Q. Therefore x E ?(K0) or x E ?(K2), and so x must lie on one of the defined planes. Thus any two points q E Q and r E R are separated by one of the linear halfspaces in G. 0 14 r h Figure7:Linesegmentqrmustintersectoneoftheconstructedplanes Theorem 5 generalizes to faces with holes in a straightforward fashion. Suppose H is a hole (i.e. part of the surface ?h) in the face Q satisfying the conditions of the theorem 5. Using the theorem, we separate H from the rest of the surface ah --H H1 and hence from the face Q itself. Repeating the construction for every loop of edges on the face Q, we obtain a set of linear separators that separate Q from the rest of the surfaces ah --H Let 5 be a solid with boundary, as = Ui Qi, where each face Q? is a subset of convex surface and contains only planar edges. ff every face Q? is separated by linear haifspaces Gj from the rest of the surface ?hj --H Q?, solid 5 is describable by H6 u Ha with Ha = U1?'=1Gj, by the face separation theorem 3. Thus, theorem 5 specifies how to construct a sufficient set of 0(n) separators for any such 5. 15 4 Solids Bounded by Quadric Surfaces 4.1 Existence of linear separators Suppose 5 is a solid, and H6 is a set of quadric halfspaces induced from as, i.e. boundary ?hj of every hj E H6 is a surface (f? = 0), where f1(x, y, z) is a polynomial of second degree. We 110W show that a sufficient set of linear separators exists for any such solid. If components A and B of the same canonical intersection term flk do not touch, a polyhedral surface P can be constructed such that any line segment ab, a E A, b E B would intersect P. In this case, it is clear that there exists a set of linear halfspaces (whose boundaries are planes defining P) that separate A and B. Similarly, if aA n aB touch at a point p (or a finite set of points), a plane P through p can be chosen to separate all points a E A and b E B in the neighborhood of p. Finally, if A and B touch along a curve C, the boundary of any halfspace separating A and B must contain the curve C. But theorem 2 implies that the degree of such a curve C is at most k2/2 = 2, since k = 2. To summarize, for a set of quadric halfspaces H, components A and B of the same canonical intersection term 11k may not touch at all, touch at a finite set of points, or touch along a planar curve. When A and B touch along a planar curve C c p, theorem 2 implies that the linear halfspace associated with the plane P separates points a E A and b E B in the neighborhood of points on the curve C. In all cases, there exists a finite set of linear halfspaces separating all points of A and B. Thus we arrive at the following result. Theorem 6 Let 5 be a solid and H6 a set of quadric haifspaces induced frorn as. There ezists a ?ufficient set of linear separators H9 such that 5 is describable by H = H6 u Ha. On the other hand, constructing such a set Ha of linear separators can be difficult. Below we briefly describe some constructions that were useful in our implementations. 4.2 Some constructions of linear separators When the boundary as of a solid 5 contains only planar edges lying in a quadric surface, the face separation theorem 3 states that a sufficient set of linear separators may be constructed by separating every quadric face Q? of as from the rest of the quadric surface ?hj --H Qi. In particular, we could use the techniques described in theorem 5, but they require hj to be a convex set. Clearly, some of the quadric halfspaces are not convex. But hyperboloid of one sheet and hyperbolic paraboloid are the only two quadric surfaces with the negative Gaussian curvature. For the rest of the quadric surfaces, the Gaussian curvature is greater or equal to zero, and their connected sheets bound convex subsets of E3. Thus, the construction of theorem 5 can be applied, once such components are separated by an additional set of halfspaces. The two sheets of a quadric surface ?hj are easily separated by a linear halfspace associated with one of the principaL planes of the quadric surface ?hj. Principal planes of a quadric ?hj are also its planes of symmetry and can be determined by a simple procedure involving not much more than finding the roots of a characteristic cubic equation [SSl4]. We know from theorem 6 that a sufficient set of linear separators exists for any solid 5 whose natural halfspaces are all quadric. Suppose as contains a non-planar edge Ej. Theorem 2 implies that components A and B of the same canonical intersection term flk cannot touch along Ej, and so it should be "easy" to separate A and B. But, because boundaries aA and ?B can be arbitrarily 16 close to each other, this is not a simple task. It may be difficult to construct a sufficient set of separators a priori, without computing ?A and aB. If a face Q? is bounded by non?planar edges, Q? cannot be separated from the rest of the quadric surface Rj by a set of linear separators, because these must contain edges of Q?. On the other hand, the conditions of the face separation theorem 3 are stronger than necessary, since Q? does not have to be separated from the rest of the surface Rj, but only from some subset of Rj. If a face Q? is separated from some subset of Rj by linear halfspaces, then all edges of Q? are also separated from that subset by the same linear separators. Even though the reverse statement is not true in general, this observation suggests that separating every edge from the rest of the intersection curve may be a reasonable heuristic approach to separation. This conjecture seems to be supported by our experiments involving general second-degree surfaces. 17 Table 1: Current state of boundary-based separation Halfspace Halfspace Halfspace Edge Linear Construction Domain Convexity connected? type separators? known? linear convex yes line segments none required --H quadrics convex yes planar yes(4) yes(5) non-planar yes(6) no non-convex one-sheet planar yes(4) yes(5) non-planar yes(6) no two-sheet planar yes(4) yes(5) non-planar yes(6) no general convex yes planar yes 4) yes(5) The number in parenthesis refers to the theorem or corollary in this paper. 5 Conclusion This paper deals with the construction of separating halfspaces for b-rep?CSG conversion, which is the single most difficult step in performing the conversion. Other aspects of b-rep?CSG conversion, including optimization of the resulting CSG representations, are discussed in [SV9l, SV9o]. The collection of the results presented here has allowed a successful implementation of an experimental b-rep?CSG conversion system that converts natural quadric b-reps in ParasolidTM to efficient CSG representations in PADL-2 [Bro82]. A C-clamp assembly shown in Figure 8 is a simple example computed by the system. Our experience indicates that the heuristic constructions work well for boundary-based separa- tion, because we aim to construct a sufficient set of separators that may be larger than necessary. Given a sufficient set, a non-umque necessary set can be computed as described in [Sv9l, SV9o]. Computing a minimum set of separators remains an open issue. Determining a sufficient and reasonable set of separators in the presence of non-planar edges is another issue that need to be resolved. The use of algebraic methods for that purpose remains to be explored. The current methods would significantly raise both the number and the degree of the separators. In contrast, our results suggest that, if Hb is a set of n natural halfspaces of degree k, it is likely that there exists a sufficient set of 0(n) separators of degree > k/2. Construction of separators has to be studied in a particular setting. Table 1 summarizes the current state of proven separation techniques. The number of different b-rep systems is large and is continuing to grow. In view of our results, it may be reasonable to ask which of these b-reps are better suited for dual-representation systems. For example, planar edges and associated linear separators occur naturally in many piecewise aigebraic surfaces [Sed85j, [PK89j. 18 (B+D+E)ACFG BDE+A+C B A (cyI?nder) 0-Clamp Assembly F A G ? core)?-----H? B m, cone) 0-Clamp Screw k c 0-Clamp Handle (GHI+IJP)(N+n)(K+k)((B+c)A+D+F+e)CELMO K -A' (Th7? A C B G ,\(?everseside, ?araIIeIto G) I cy??roe? E Fi )N ?/ n 0-Clamp Body 0-Clamp Body Separators Natural Halfspaces Figure8:AsolidmodelofC-clampassemblyandthecomputedCSG representations 19 References [Bro82] C. K. Brown. PADL-2: a technical summary. IEEE Computer Graphics and Applications, 2(2):69--H84, March 1982. [Col75] [CR88j G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decompo- sition. In Proceedings Second CI Conference on Automata Theory and Formal Languages, pages 134--H183, Berlin, 1975. Springer Lecture Notes in Computer Science 33. M. Coste and M. F. Roy. Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets. Journal of Symbolic Computation, 5(1):121--H129, 1988. [dC76] M. P. do Carmo. Differential geometry of curs'es and surfaces. Prentice-Hall, Inc., 1976. [GP74] v. Guillemin and A. Pollack. Differential Topology. Prentice-Hall, 1974. [Gri88j D. Yu. Grigor'ev. Complexity of deciding Tarski algebra. Journal of Symbolic Computa- tion, 5(1):65--H108, 1988. [GW91] T. Garrity and J. Warren. Geometric continuity. Computer Aided Geometric Design, 8(1):51?5, February 1991. [Hei83j J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theo- retical Computer Science, 24:239--H278, 1983. [Hop89] H. Hopf. Differential Geometry in the Large. Spnnger?Veilag, second edition, 1989. Lecture Notes in Mathematics, No. 1000. [Ken77] K. Kendig. Elementary Algebraic Geometry. Springer-Verlag, 1977. jKM76] K. Kuratowski and A. Mostowski. Set theory. North-Holland Publishing Co., 1976. [MT46] J. C. C. McKinsey and A. Tarski. On closed elements in closure algebras. Annals of Mathematics, 47(1): 122--H162, January 1946. [PK89] N. M. Patrikalakis and G. A. Kriezis. Representation of piecewise continuous algebraic surfaces in terms of B-splines. The Visual Computer, 5:360--H374, 1989. [Req77J A. A. G. Requicha. Mathematical models of rigid solid objects. Tech. Memo 28, Production Automation Project, University of Rochester, Rochester, NY, November 1977. [RT78] A. A. G. Requicha and R. B. Tilove. Mathematical foundations of constructive solid ge- ometry: General topology of closed regular sets. Tech. Memo 27a, Production Automation Project, University of Rochester, June 1978. [RV77] A. A. G. Requicha and H. B. Voelcker. Constructive solid geometry. Tech. Memo 25, Production Automation Project, University of Rochester, November 1977. [RV85] A. A. G. Requicha and H. B. Voelcker. Boolean operations in solid modeling: Boundary evaluation and merging algorithms. Proceedings of the IEEE, 73(1):30-44, January 1985. 20 [Sed85] T. W. Sederberg. Piecewise aigebraic surface patches. Computer Aided Geometric Design 2(1?3):53--H59, 1985. [Sha9l] [51181] V. Shapiro. Representations of Semi-Algebraic Sets in Finite Aigebras Generated by Space Decompositions. PhD thesis, Cornell University, Cornell Programmable Automation, Ithaca, NY, 14853, February 1991. C. E. Silva. Alternative definitions of faces in boundary representations of solid objects. Tech. Memo. 36, Production Automation Project, University of Rochester, November 1981. [5514] V. Snyder and C. H. Sisam. Analytic geometry of space. Henry Holt and Company, 1914. [5V9o] V. Shapiro and D. L. Vossler. B-rep?CSG conversion II: Efficient CSG representations of planar solids. Tech. Report CPA89?4a, Cornell Programmable Automation, Cornell University, Ithaca, NY, May 1990. [5V91] V. Shapiro and D. L. Vossler. Construction and optimization of CSG representations. Computer-Aided Design, 23(1)4--H20, January/February 1991. 21