System and Method for Converting Boundary Representations to Constructive Solid Geometry Representations for Three-Dimensional Solid Object Modeling

1. Field of the Invention

The present invention relates generally to computer-aided design, manufacture and engineering, and more particularly to a system and method for improved solid object modelling.

2. Description of the Related Art

Boundary representations (b-reps) and constructive solid geometry (CSG) are the two most widely used representation schemes for solids. Properties of CSG representations are summarized in Requicha, A. A. G., and Voelcker, H. B. Constructive Solid Geometry. Tech. Memo 25, Production Automation Project, Univ. of Rochester, Rochester, N.Y., 1977. Central to CSG are notions of closed-set regularity and regularization relative to the topology of the Euclidean space. Regularization of a set X is defined by kiX, where k and i denote, respectively, operations of closure and interior. Regularized set operations .andgate.* and .orgate.*, and -* are defined by regularizing the results of the corresponding standard set operations and have the effect of always producing homogeneously "solid" sets. Properties of closed regular sets have been studied in Kuratowski, K., and Mostowski, A. Set Theory. North-Holland, Amsterdam, 1976, as well as McKinsey, J. C. C., and Tarski, A. On closed elements in closure algebras. Ann. Math. 47, 1 (Jan. 1946), pp. 122-162, and Requicha et al. Constructive Solid Geometry, supra., and are well understood.

While the problem of computing a B-rep (FIG. 1c) from a CSG representation (FIG. 1b) for an example solid (FIG. 1a) is relatively well understood, the inverse problem of B-rep to CSG conversion has not been addressed in general. Important applications of b-rep to CSG conversion arise in a variety of fields, including solid modeling and image processing.

The importance of b-rep to CSG conversion can be seen from the following considerations:

Both of these types of systems are useful when writing production applications for manufacturing or engineering. Depending on the problem one is trying to solve, one may want to represent a solid either as a b-rep or as constructive solid geometry; therefore, having conversions between the two is extremely useful.

The inability to perform b-rep to CSG conversion puts significant constraints on the design of modern solid modelling systems such as a true dual representation architecture of a solid modelling system that allows representation-specific technology to be used on alternative representations through a bilateral b-rep-CSG conversion.

One of the difficult aspects of the b-rep to CSG conversion problem is that the boundary representation of an object is unique. On the other hand, the CSG representation or solution is not unique; there are an infinite number of solutions in CSG for the same b-rep. Moreover, until now there has been no viable solution to the problem for curved three-dimensional solid objects.

In view of the above problems associated with the related art, it is an object of the present invention to provide a system and method for converting a boundary representation of a solid object into a constructive solid geometry representation.

It is another object of the present invention to provide a true dual representation solid modelling system that allows representation-specific technology to be used via alternative representations through a bilateral b-rep-CSG conversion.

Given a boundary representation of a solid object by a union of curved faces, this invention computes and produces a set of geometric separators that allow computation of Boolean set theoretic descriptions of faces, boundaries, and solids. A separator can be a planar surface, an arcuate surface or a piecewise polynomial surface.

The system and method of the present invention involve three steps, repeated for every face of the given boundary representation of the solid. First, separators are constructed through triples of vertices on the face of the solid, until there is a separator passing through every vertex of the face. Second, through every planar edge of the face, a separator is constructed containing the planar edge. Third, for each nonplanar edge of the solid, one or more separators are constructed that separate the edge from the rest of the curve of the face. In this case, it is possible that construction of nonplanar separating surfaces is required. The process described above has been completely implemented in a computing system as a prototype. The prototype reads a b-rep description of the solid object and then computes the required separating planes automatically. Numerous solid objects representing a variety of mechanical parts have been subjected to this process with results verifying the effectiveness of the invention.

The ability to compute separating surfaces contributes to the solution of several important problems such as b-rep to CSG conversion, definition of faces, boundaries, and solids using standard set operations (union, intersection, complement), construction of new representations of surfaces, solids and other point sets, and development of new software and hardware architectures for geometric modeling systems supporting multiple representations.

These and other features and advantages of the invention will be apparent to those skilled in the art from the following detailed description of preferred embodiments, taken together with the accompanying drawings, in which:

FIGS. 1a-1c are schematic illustrations of an example simple solid with its respective boundary (b-rep) and constructive solid geometry (CSG) representations;

FIG. 2a is a schematic drawing of an example two-dimensional solid, while FIGS. 2b is identical to FIG. 2a with the addition of separating surface g;

FIG. 3 is a schematic drawing of an example two-dimensional solid;

FIGS. 4a and 4b are schematic drawings of a further example two-dimensional solid illustrating boundary-based separation according to the present invention;

FIG. 5 is a schematic three-dimensional representation of a solid similar to that of FIG. 3;

FIG. 6a is a flowchart of preferred embodiment of the present invention, while FIG. 6b is a more detailed flowchart of the construct separators portion of the flowchart of FIG. 6a;

FIG. 7 is a schematic drawing of an example system employing the present invention; and

FIGS. 8a-8e are schematic illustrations of a C-clamp assembly generated by a system according to the present invention.

The b-rep to CSG conversion procedure employed by the system of the present invention generally consists of the following steps:

First, induce a set of natural half spaces, H.sub.b, associated with the boundary .differential.S of a solid S. The natural half spaces in H.sub.b partition the Euclidean space into a number of open connected "cells". All cells fall into one of two categories: those that are inside solid S and those that are outside of S. If CSG representations of (closures of) all cells inside S are known, then their union is a valid CSG representation of S. Thus, the shaded two-dimensional solid in FIG. 2a is a union of the closures of the three two-dimensional cells: C.sub.11, C.sub.22, and C.sub.13.

Unfortunately, some cells inside S may not admit any CSG representation using natural half spaces H.sub.b of S. In FIG. 2a any CSG representation using half spaces h.sub.1 and h.sub.2 that "covers" cell C.sub.22 also covers cell C.sub.12. Similarly, cell C.sub.13 cannot be represented in isolation from cell C.sub.13. Since C.sub.23 and C.sub.12 are outside the solid, it follows that S cannot be represented in CSG by h.sub.1 and h.sub.2 alone. Thus, a set of additional half spaces is constructed that "separate" some cells inside S from those outside of S. Such half spaces are called separating half spaces, separating surfaces, or simply separators. A set H.sub.s of separating half spaces is sufficient if solid S can be represented by some CSG representation of H=H.sub.s .orgate.H.sub.b. For example, separating half space g in FIG. 2b separates cells C.sub.22, C.sub.13 from cells C.sub.23 and C.sub.12, respectively, thus allowing a CSG representation of S.

Then, if a sufficient set of half spaces is known, the system according to the present invention computes the decomposition of the Euclidean space and identifies the cells inside S. The union of CSG representations of closures of these cells is a unique canonical CSG representation of S.

One of the most difficult steps in performing a b-rep.fwdarw.CSG conversion for a curved solid object is determining a sufficient set of separators for a CSG representation of the solid. This usually requires the construction of additional half spaces whose boundaries do not contribute to the boundary of the solid. Such half spaces are called separating half spaces because their purpose is to separate certain subsets inside the solid from those outside of the solid. The notions of cells, separation, and separators are set forth below, including separation techniques that enabled an implementation of an experimental b-rep.fwdarw.CSG conversion system for three-dimensional solids bounded by quadric surfaces (though results discussed below apply to more general solids as well).

While the present invention primarily addresses separation in three-dimensional Euclidean space E.sup.3, two-dimensional examples will be used occasionally to convey the main ideas. Furthermore, it is often more convenient to discuss examples in a general d-dimensional Euclidean space E.sup.d, bearing in mind that the statements apply equally well in two- and three-dimensional cases.

As a matter of background to the understanding of the present invention, definitions as well as the concepts of describability and separation issues will be addressed first.

Boundary and CSG Representations of Solids. Solids may be modeled by sets of points in E.sup.d that are compact, regular and semianalytic; such sets are called "r-sets". A two-dimensional solid is an r-set in E.sup.2 while a three-dimensional solid is an r-set in E.sup.3. The boundary .differential.S defines S completely and unambiguously in the following sense: (1) Complement of the boundary, -.differential.S, is a disconnected subset of E.sub.d ; and (2) interior iS and exterior eS are unions of some connected components of -.differential.S.

The b-rep of a solid S is a representation of .differential.S. Comprehensive surveys of properties and different types of b-reps, including historical background, can be found in recent books on solid modeling such as Hoffmann, C. H. Geometric and Solid Modeling. Morgan Kaufmann, San Mateo, Calif., 1989 or Mantyla, M. An Introduction to Solid Modeling. Computer Science Press, Rockville, Md., 1988. Typically, a b-rep of a three-dimensional solid S is a collection of closed two-dimensional sets called faces Q.sub.1 ; that is,

Faces in .differential.S may not be disjoint but may intersect on edges, which are assumed to be connected one-dimensional sets. For purposes of the present invention, the particular type of b-rep is not important, as long as it specifies all surfaces containing the faces of S.

Each face Q.sub.i is a subset of a set (f.sub.i =0), where f.sub.i (x, y, z) is a real analytic (or algebraic) function. A half space h.sub.i is induced from (or associated with) a face Q.sub.i as

The half spaces induced from a b-rep of S are called natural half spaces of S. Note that half spaces need not be regular or connected sets.

It is important to distinguish between a solid S and its CSG representations. A CSG representation .PHI.(H) of a solid S is a syntactic expression constructed using regularized set operations on a set of half spaces. A CSG expression .PHI. is a Boolean expression composed of halfspace literals h.sub.1, . . . , h.sub.n, and symbols denoting regularized set operations, defining a Boolean function. Properties of CSG representations are further considered in Appendix A. S=.vertline..PHI..vertline. denotes the fact that .PHI. represents set S. For example, the shaded solid in FIG. 2b can be represented by CSG as

but many other CSG representations using half spaces (h.sub.1, h.sub.2, g) are also possible.

Describability. Given a finite set H=(h.sub.1, . . . ,h.sub.n) of half spaces, with every half space h.sub.1 defined as (f.sub.i .gtoreq.0), an infinite number of CSG representations can be constructed, but they represent at most a finite number of distinct closed regular sets S. The set of all such sets is a finite Boolean algebra with operations .andgate.*, .orgate.*, and -*. Accordingly, each such set S can be represented by a unique disjunctive canonical CSG representation as ##EQU1## where .sub.k is a canonical intersection term defined by

The interior of every set .vertline. .sub.k .vertline. defines a set of all points in the space that have identical classification (in or out) with respect to all of the half spaces in H. In other words,

If H is a set of n algebraic half spaces of degree k, it follows that the partition {.vertline. .sub.k .vertline.} of the d-dimensional space E.sup.d has at most (1+nk).sup.d distinct nonempty elements. Therefore, at most 2.sup.(1+nk)d distinct sets can be represented by CSG expressions on H.

Note that the interior of a set .vertline. .sub.k .vertline. in eq. (2) need not be connected. Thus, ##EQU2## where C.sub.jk are connected open three-dimensional components of the interior of .vertline. .sub.k .vertline. and a connected set .vertline. .sub.k .vertline. can contain more than one component C.sub.jk. The number of all distinct components C.sub.jk can be much larger than the number of canonical intersection terms, but is bounded by (2nk).sup.2d+1, for n algebraic half spaces of degree k in E.sup.d. These estimates on size of partitions {.vertline. .sub.k .vertline.} and {C.sub.jk } are rather conservative, and tighter bounds are known in many special cases.

Suppose that solid S is represented by a b-rep and that H.sub.b is a set of all natural half spaces induced from the b-rep. In two-dimensions a boundary representation is a description of the edges that bound a two-dimensional object and a description of the faces that bound a three-dimensional object. As FIGS. 2a and 3 demonstrate, components of some canonical intersection terms .sub.k (using half spaces in H.sub.b) may be separated by the boundary .differential.s: some of its components are in the interior iS, whereas others are in the exterior eS. FIG. 2a is a schematic drawing illustrating a shaded solid as a union of three cells: C.sub.11, C.sub.22, and C.sub.13. As can be seen from the illustration, cells C.sub.22 and C.sub.13 do not admit any CSG representations with half spaces h.sub.1 and h.sub.2. Therefore, S is not describable by H.sub.b and the components in FIG. 2a are not describable in isolation from each other.

FIG. 3 is a schematic drawing of another example of a two-dimensional solid (planar solid). Five half spaces are depicted, namely a circle, h.sub.1, and the four edges h.sub.2, . . . ,h.sub.5. The desired object is shown shaded. Cells A and B do not admit any CSG representations with illustrated half spaces because, as with the solid of FIG. 2a, using Boolean algebra, one cannot describe these two pieces separately.

In both of these examples, as well as innumerable other solids, there is no CSG representation of S using only half spaces from H.sub.b. In other words, S is not describable by H.sub.b and the components in FIGS. 2a and 3 are not describable in isolation from each other. More generally, the following states the necessary and sufficient conditions for a solid S to be "describable" by a set of half spaces:

(Describability). Given a set H=(h.sub.1, . . . ,h.sub.n) of half spaces such that .differential.S .differential.h.sub.1 .orgate.. . . .orgate..differential.h.sub.n, solid S is describable by H if and only if (iff) all components C.sub.ik of every canonical intersection term .sub.k have the same classification with respect to S.

The components C.sub.jk can classify as either in S (i.e., C.sub.jk iS) or out of S (i.e., C.sub.ik eS). If components of every .sub.k have the same classification with respect to S, the set H is sufficient for CSG representation of S. Otherwise, additional half spaces must be constructed that separate the components C.sub.jk into distinct intersection terms.

Separation Issues. Two distinct points a,b.epsilon.E.sup.d are defined as separated by a half space g=(f.gtoreq.0) iff f(a).apprxeq.0, f(b).apprxeq.0, and sign [f(a)].apprxeq.sign [f(b)]. Moreover, two disjoint point sets A and B are separated by a family of half spaces G=(g.sub.i) iff, for all a .epsilon.A, b.epsilon.B, there exists a half space g.sub.i .epsilon.G such that a and b are separated by g.sub.i.

Using these definitions, two distinct components A and B are separated by a set of half spaces H iff A and B are not components of the same canonical intersection term .sub.k. Recall describability sets forth the concept that a sufficient set of separators must separate any component inside S from those outside of S.

The two-dimensional solid in FIG. 2b is describable by the two natural half spaces h.sub.1 and h.sub.2 and a single separating half space g added according to the theory embodied in the present invention. The separating surface is used to keep connected components apart so they can be described separately. It should be noted that separating half spaces may intersect the components they separate. Furthermore the two-dimensional shaded solid in FIG. 3 can be made to be describable by the addition of a single separation half space g (not shown) and the four natural half spaces h.sub.1, h.sub.2, h.sub.3, h.sub.5. Such separation half space g could intersect the solid, for example, at points Y and Z.

It should be understood at this point that there are often infinite locations and orientations for separating surface g to adequately separate connected components such as A and B of FIG. 3. However, for a computer to understand what a user would intuitively observe is another matter. For this reason, and for computational ease, it is preferred that a separating surface connect the endpoints of the curved edges of two-dimensional solids. This is because end points are already defined by the b-rep.

It should also be remembered that a separator may be planar or arcuate or a piecewise polynomial. According to the present invention, while one may not always have the choice of type of separating surface because of the particular object being modelled, planar separating surfaces are greatly preferred because one does not introduce a secondary problem into the b-rep when using planar separating surfaces. Recall that any separating surface introduced into a representation ends up in all of the geometric calculations for an object. Furthermore, arcuate surfaces in general give increased opportunity that the problem has not been solved because they have more than one place where they cross an object. Moreover the mathematics that describe planes are much simpler than even for the simplest arcuate surface--a sphere.

There are at least three separation strategies, namely:

(1) Global separation. Construct a set of separating half spaces H.sub.s such that every canonical intersection term .sub.k in the decomposition of E.sup.d by H.sub.b .orgate.H.sub.s represents a single component. The cylindrical algebraic decomposition can achieve this. But this expensive construction is excessive and unnecessary, since only some of the components need to be separated.

(2) Test-based separation. Compute all pairs of components that must be separated for S to be describable, use this information to construct necessary separators, and add separating half spaces incrementally until the conditions of describability are satisfied. To use this strategy, one must first compute the boundaries of components to be separated and then use various planning algorithms. Such an approach often leads to difficult problems similar to those in motion planning, and this tends to be quite computationally intensive.

(3) Boundary-based separation. Recall that only the components inside S need to be separated from components outside of S. By using the boundary of a solid to guide the required separation, a sufficient H.sub.s that is much smaller than the one resulting from the global separation is thereby produced. With this strategy, a sufficient set of separators is constructed a priori, based on various topological and geometric properties of solids.

Of the three separation strategies, the boundary-based strategy is the most general. A system which can accomplish this type of separation can also accomplish the remaining two strategies listed. The system and method of the present invention preferrably employs the boundary-based strategy for constructing a sufficient set of separators. This approach has been used successfully to solve the conversion problem for a large class of two-dimensional solids and much more recently for three-dimensional solids. For example, let S be a two-dimensional solid with "faces" that are curved arcs, with each arc being a subset of a curve of a constant curvature sign. FIG. 4a shows a planar solid S represented by its boundary. But S is not describable by H because several pairs of two-dimensional components must be separated (e.g., those containing points P.sub.2 and P.sub.4, and P.sub.1 and P.sub.3). FIG. 4b shows that the set G={g.sub.1, g.sub.2, g.sub.3, g.sub.4 }of linear separators associated with the chords of .differential.S is sufficient for CSG representation of S. Indeed, S is describable by H.orgate.G, since no other pairs of components need to be separated. Moreover, after thoughtful consideration of FIG. 4b, it becomes apparent that not all g.sub.i s are necessary, but such an approach is always sufficient. For such solids the set of linear half spaces associated with the arc chords is always sufficient. While this result can be generalized to higher dimensions, the general separation problem in E.sup.3 is much more difficult.

One way to see if two points a and b are separated by a half space h.tbd.(f.gtoreq.0) is to trace a path from a to b and to count how many times the real function f changes its sign. Only if this number is odd, are the points a and b separated by h.

Consider a (d-1)-dimensional set X such that its complement -X is a disconnected subset of E.sup.d and two points a,b.epsilon.X. By definition, a one-dimensional path ab and X have complementary dimensions, since dim(ab)+dim X=d. Assuming that ab and X intersect transversely in the topological sense, ab.andgate.X is a finite set of points. Intuitively, this means that at every point of ab .andgate.X the sum of tangent spaces of ab and X span E.sup.d. Sard's theorem implies that almost all intersections are transversal. 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 I.sub.2 (ab,X).

Several observations can be made concerning a given solid S with boundary .differential.S and n half spaces h.sub.1 .tbd.(f.sub.1 .gtoreq.0), i=1, . . . ,n:

For every pair of points a.epsilon.iS, b.epsilon.eS, and any transversal path ab, I.sub.2 (ab, .differential.S)=1.

Points a,b.epsilon.(f.sub.1 =0) are separated by a half space h.sub.i iff

I.sub.2 (ab, (f.sub.1 =0))=1, whenever an arbitrary path ab and set (f.sub.i =0) intersect transversely.

For any two points a and b, all paths ab are equivalent in the sense of having the same intersection numbers I.sub.2 (ab, .differential.S) and I.sub.2 (ab, (f.sub.1 =0)).

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.sub.i determines the maximum number of times an arbitrary line can intersect the set (f.sub.i =0). In particular, suppose that (f.sub.i =0) is a hyperplane and that ab is a line segment connecting points a,b.epsilon.(f.sub.i =0). The points a and b are separated by h.sub.i iff the line segment ab intersects the hyperplane. As noted above, this property of linear half spaces makes them very attractive for separation properties.

As discussed above, as A and B get closer, it may become more difficult to separate them using linear separators alone. But, if the boundaries of A and B overlap, linear separators may not exist at all. Therefore, according to a preferred embodiment there are constraints on the degree of separating half spaces.

Consider two components A and B of the same canonical intersection term .sub.k, with A iS and B eS. When A and B are far apart, it is always possible, at least in principle, to construct a piecewise linear surface passing between A and B. The linear half spaces induced from this surface will separate all points of A from all points in B. As A and B get closer, the required number of planes in the surface may grow arbitrarily large, and construction of such a polyhedral surface becomes more and more difficult. But no matter how close A and B are, they are always on different sides of the boundary .differential.S. Therefore, the type of surfaces and edges used in the b-rep of S has a direct relationship to the type of required separators.

Two sets A and B are said to touch each other if .differential.A.andgate..differential.B.apprxeq..phi.. Components A and B of the same canonical intersection term .sub.k cannot touch along a two-dimensional surface because they would be separated by the half space associated with the surface. Thus, if A and B touch each other, they must do so at a finite set of points or along some curve.

If c is a point where A and B touch, every neighborhood of c contains points a.epsilon.A and b.epsilon.B. Hence, the boundary of any half space separating points of A and B in the vicinity of c must contain the point c. Suppose now that A and B touch along a curve C that is formed by an intersection of some two surfaces. It follows that C must lie entirely in the boundary of any separator. The degree of the intersection curve C places the lower bound on the degree of any such separator. Here, degree of the curve C means the degree of the real irreducible algebraic variety W containing C. Intuitively, deg(W) is the number of times W can be intersected by a hyperplane.

THEOREM 1. Let H be a set of half spaces of degree k, and let components A and B of the same canonical intersection term .sub.k touch along a curve C, formed by intersection of two half spaces in H. Then the degree of C is .ltoreq.k.sup.2 /2. Proof for Theorem 1: By assumption, the neighborhood of any point c.epsilon.C must contain points a.epsilon.A and b.epsilon.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 half spaces associated with U and V. Hence, perturbing the path ab yields a transversal intersection of ab and U (or V) such that I.sub.2 (ab, U)=I.sub.2 (ab, V)=0. In other words, U and V each intersect the patch acb at the point c with even multiplicity. But then U and V intersect along the curve C with even multiplicity. By Bezout's theorem, the product of the degree and the multiplicity of the intersection of U and V cannot be greater than the product deg(U) deg(V). Hence, the degree of C is less than or equal to deg(U) deg(V)/2=k.sup.2 /2.

Whenever two components A and B of the same canonical intersection term touch along an edge in the boundary of .differential.S of a solid S, Theorem 1 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.sup.m-1 continuity along C. Any half space locally separating points of A and B must contain C and must intersect both U and V along C either transversely or with an odd multiplicity greater than one. Since the degree of U and V is k and the degree of C could be as high as k.sup.2 /2, the degree of the required separating half space is .gtoreq.k/2.

For this reason, solids whose boundaries contain nonplanar edges may require nonlinear separators in the vicinity of such edges. Once the separation in the vicinity of the edges is achieved, a sufficient set of linear separators (whose boundaries are planes) can be found for any solid S.

However, solids whose boundaries contain only planar edges will first be considered. Every edge of such solids lies in some plane. It will be shown that a sufficient set of linear separators exists for any such solid S. It should be understood that in two dimensions, "faces" are one-dimensional curve segments, and "edges" correspond to end points, which are always planar. The following result is the key to the corresponding boundary-based construction:

THEOREM 2 (Face Separation). Let S be a solid, (Q.sub.i) a set of faces in .differential.s, and H.sub.b ={h.sub.i } a set of natural half spaces induced from these faces. Suppose that the interior of every face Q.sub.i is separated from the rest of the half space surface, R.sub.i .tbd..differential.h.sub.i -Q.sub.i, by a family of linear half spaces G.sub.i (i.e., for all g.epsilon.G.sub.i, .differential.g is a hyperplane). Then S is describable by H.sub.b .orgate.H.sub.s with H.sub.s =.orgate..sub.i G.sub.i. Proof for Theorem 2: Consider any two components A iS and B eS in the decomposition of space by H.sub.b that are not separated by H.sub.b. It is always possible to pick two points a.epsilon.A, b.epsilon.B, such that the line segment ab intersects .differential.S and .differential.h.sub.i, i=1, . . . n, transversely and does not cross any edges. Then I.sub.2 (ab, .differential. [S)=1, which implies that there exists a face Q.sub.i that is intersected by ab an odd number of times. By assumption, a and b are not separated by h.sub.i .epsilon.H.sub.b, the natural half space induced from Q.sub.i ; hence, I.sub.2 (ab, .differential.h.sub.i)=O, and ab intersects .differential.h.sub.i and even number of times. Thus, the segment ab intersects both the interior of Q.sub.i and R.sub.i =.differential.h.sub.i -Q.sub.i. But the interior of Q.sub.i and R.sub.i are separated by a family of linear half spaces G.sub.i, and so ab must intersect the planar boundary of some separator in G.sub.i. It follows that a and b are also separated by G.sub.i. Hence, any two components A iS and B eS are separated by either H.sub.b or H.sub.s =.orgate..sub.i G.sub.i. By the describability theorem, S is describable by H.sub.b .orgate.H.sub.s.

The assumption that G.sub.i is a set of linear separators is crucial to the proof, because a surface (g=0) associated with a nonlinear half space g.epsilon.G.sub.i could be intersected by the line segment ab more than once. Thus, the conditions of the face separation theorem require that all faces Q.sub.i intersect on planar edges. For every such face Q.sub.i, there exists some polyhedral (piecewise linear) surface passing through its edges, and so the interior of Q.sub.i can be separated from the rest of the surface at least in principle. Therefore, for any solid S whose boundary .differential.S contains only planar edges, there exists a sufficient set of linear separators.

In two dimensions, a sufficient set of linear separators exists for any solid. Although planarity of edges is a significant limitation for three-dimensional solids, there are many geometric objects that naturally satisfy this requirement. Finally, the conditions in Theorem 2 are sufficient but not necessary for the describability of solid S.

A sufficient set of linear separators can also be constructed for solids whose faces lie in convex surfaces and intersect on planar edges. Specifically, when all faces of the b-rep lie in convex surfaces and are bounded by planar curves, with the system and method of the present invention it is easy to construct a sufficient set of O(n) linear separators.

Assume now that the boundary of a solid .differential.S contains only planar edges and give a sufficient construction required by Theorem 2 in a restricted but common situation. Specifically, suppose that every natural half space h.sub.i .epsilon.H.sub.b is a convex set. Well known theorems in differential geometry state various sufficient conditions on .differential.h.sub.i (e.g., the Hadamard theorem and its various generalizations). For example, h.sub.i is a convex three-dimensional set whenever .differential.h.sub.i is a connected surface whose Gaussian (total) curvature k.gtoreq.0 and k>0 for at least one point p.epsilon..differential.h.sub.i. Call h.sub.i a convex half space and .differential.h.sub.i a convex surface (or curve). If a face Q is a subset of a convex surface and is bounded by m planar edges, the construction described below separates the interior points of Q from the rest of the surface using only O(m) linear separators.

First, consider a simply connected (without holes) face Q. Recall that faces and edges of a solid S are topological p-dimensional polyhedra, with p=2 and p=1, respectively. In other words, for any face or edge X there exists a triangulation (K,.phi.) of X, where K is an abstract p-dimensional simplicial complex and where .phi. is a homeomorphism with X=.phi.(K).

The boundary of Q is a loop of m edges that is topologically a one-dimensional simplicial complex L containing m 1-simplixes. L can be also viewed as a graph (a cycle) with m node that can be easily triangulated in many different ways. As a result, a two-dimensional complex K.sub.0 containing m-2 triangles (2-simplices) is obtained. Now define a map .phi..sub.0 that embeds every 2-simplex in K.sub.0 as a planar triangle v.sub.i v.sub.j v.sub.k in E.sup.3 through some three vertices of the face Q. The pair (K.sub.0,.phi..sub.0) is a loop triangulation of the face Q.

Informally, construction of a loop triangulation of Q amounts to subdividing the set of vertices of Q into adjacent triples and associating a planar triangle with every triple of vertices. Note that the planar triangle v.sub.i v.sub.j v.sub.k cannot intersect the surface .differential.h anywhere except at the three vertices, because .differential.h is a convex surface, but different triangles could penetrate each other. Thus, .phi..sub.0 (K.sub.0) is a piecewise linear triangulated surface with possible self-intersections, constructed by unionizing all the planar triangles in the loop triangulation. Loop triangulations are easy to construct by picking any vertex on the face Q and by traversing the vertices of Q along the loop, taking three vertices at a time.

By assumption, every edge of Q lies in some plane. In addition, each triangle in a loop triangulation defines a plane through some three vertices of the face Q. Every plane defined by an edge or a triple of vertices is a boundary of a linear half space g. Let G denote the collection of all such linear half spaces for a given face Q. Then, as required by the conditions of Theorem 2, G separates the interior of Q from the rest of the surface containing Q.

THEOREM 3. Suppose that h is a convex half space, a simply connected face Q .differential.h is bounded by n planar edges, and (K.sub.0,.phi..sub.0) is a loop triangulation of Q. Let G be the set of linear half spaces associated with the set of planes: (1) containing every curved edge of Q, and (2) containing every triangle in .phi..sub.0 (K.sub.0). Then G separates the interior of Q from the rest of the surface R.tbd..differential.h-Q. Proof for Theorem 3: If the number of edges m.gtoreq.2, the proof is trivial. Therefore, assume that m.gtoreq.3. Let (K.sub.1,.phi..sub.1) be a triangulation of a face Q. Each planar segment bounded by a curved edge E.sub.i and a chord v.sub.i v.sub.j can also be triangulated. So let (K.sub.2,.phi..sub.2) be a triangulation of the union of all such planar segments; that is, .phi..sub.2 (K.sub.2) is a union of all such planar segment on the face Q. "Glue" the three abstract complexes K.sub.0, K.sub.1, K.sub.2 into a single abstract complex K by requiring that simplixes x =y whenever .phi..sub.i (x)=.phi..sub.j (y) , i.apprxeq.j, i, j=0, 1, 2. By construction, K is an abstract closed surface or a 2-manifold. A continuous map .psi. of manifold into Euclidean space is a topological immersion if each point of the manifold has a neighborhood mapped homeomorphically onto its image by .psi., i.e., the image is allowed to have "self-intersections". Now construct an immersion .psi.K.fwdarw.E.sup.3,

.phi..sub.0 (x), if x.epsilon.K.sub.0,

.phi..sub.1 (x)=.phi..sub.1 (x), if x.epsilon.K.sub.1,

.phi..sub.2 (x), if x.epsilon.K.sub.2

that partitions E.sup.3 into a finite number of connected components {C.sub.1,C.sub.2, . . . C.sub.k }. Intuitively, .psi.(x) is a possibly self-intersecting surface "glued" from the three pieces: the original face Q=.psi..sub.1 (K.sub.1), the union of all planar triangles in the loop triangulation .psi..sub.0 (K.sub.0), and the union of all planar segments bounded by edges and their respective chords .psi..sub.2 (K.sub.2). It is important that all points of .psi..sub.0 (K.sub.0) and .phi..sub.0 (K.sub.0) and .phi..sub.2 (K.sub.2) lie in the planes through the edges of Q or triplets of vertices of Q, as assumed in the theorem hypothesis. It follows that the union .phi..sub.0 (K.sub.0).orgate..phi..sub.2 (K.sub.2)is a polyhedral surface that separates the interior of Q from the rest of the surface R.

Consider two arbitrary points q in the interior of Q and r.epsilon.R. The straight-line segment qr must intersect the surface .psi.(K) at some point x lying in one of the constructed planes. Since h is a convex set, the line segment gr is completely contained in h and intersects .differential.h only at the points q and r. Thus, there exists a point q'.epsilon.h lying on qr in the neighborhood of the point q. Consider the path q'qr, where gr is any path restricted to the surface .differential.h and intersecting some edge E.sub.i of Q an odd number of times. the path q'qr also intersects the plane through E.sub.i and the surface .psi.(K) every time it intersects E.sub.i. Furthermore, this path cannot interest .psi.(K) anywhere else, because .psi.(K).andgate.R=.phi.. It follows that point q' and r belong to different connected components C.sub.1 and C.sub.j. Hence, the straight-line segment q'r must intersect the surface .psi.(K) at some point x lying between q and r, but x cannot be a point on the face Q. Therefore, x.epsilon..phi..sub.0 (K.sub.0) or x.epsilon..phi..sub.x (K.sub.2), and so x must lie on one of the defined planes. Thus, q and r (and, therefore, the interior of Q and R) are separated by one of the linear half spaces in G.

Theorem 3 generalizes to faces with holes in a straightforward fashion. Suppose H is a hole (i.e., part of the surface .differential.h) in the face Q satisfying the conditions of Theorem 3. Using the theorem the interior of H is separated from the rest of the surface .differential.h-H and, hence, from the face Q itself. Thus, every loop of edges on the face Q can be treated independently from other loops. Repeating the separation for every loop of edges on the face Q, obtains a set of linear separators that is sufficient to separate the interior of Q from the rest of the surfaces .differential.h-Q.

To summarize, given a solid S such that all n faces in its b-rep lie in convex surfaces and all edges lie in planar curves, Theorem 3 specifies how to construct a sufficient set of O(n) separators. Namely, this set includes all linear half spaces induced from all curved planar edges and all loop triangulations in the b-rep of S. Since the interiors of all faces are separated from the rest of the surfaces containing them, S is describable by the face separation Theorem 2.

As a final note, consider these results with respect to two-dimensional solids. Convex surfaces in E.sup.3 become convex edges in E.sup.2, and the requirement of planar edges in E.sup.3 is always satisfied in E.sup.2. An edge loop in E.sup.3 reduces to a pair of vertices, and the simplest loop triangulation corresponds to putting the chord between them.

A sufficient set of linear separators can also be constructed for solids bounded by general quadric surfaces. Specific constructions will now be discussed for several common situations.

Let S be a three-dimensional solid, such that the set of natural half spaces H.sub.b induced from .differential.S contains at most quadric half spaces; that is, boundary .differential.h.sub.i, of every h.sub.i .epsilon.H.sub.b is a polynomial surface (f.sub.i =0) of at most the second degree.

If components A and B of the same canonical intersection term .sub.k do not touch at all or touch at a finite set of points, a polyhedral surface P can be constructed such that any line segment ab, a.epsilon.A, b.epsilon.B would intersect P. In either case, there exists a set of linear half spaces (whose boundaries are planes defining P) that separate A and B. The only other possible situation arises when components A and B touch along a curve C. Then the boundary of any half space separating A and B must contain the curve C. But Theorem 1 implies that the degree of such a curve C is at most k.sup.2 /2 =2, since k=2. Therefore, C is a planar curve, and the plane containing C is the boundary of a linear half space separating points of A and B in the neighborhood of points on C. Thus, under all conditions, the following must be true:

If S is a solid, and H.sub.b is a set of quadric half spaces induced from .differential.S, then there exists a finite set of linear separators H.sub.s such that S is describable by H=H.sub.b .orgate.H.sub.s,

On the other hand, the number of needed linear separators can grow arbitrarily large, and the construction of such a set H.sub.s of linear separators can be difficult. Below, some separator constructions are briefly described that were useful in the implementations of the present invention.

When the boundary .differential.S of a solid S contains only planar edges lying in quadric surfaces, the face separation Theorem 2 states that a sufficient set of linear separators may be constructed by separating the interior of every face Q.sub.i in .differential.S from the rest of the quadric surface .differential.h.sub.i -Q.sub.i. In particular, the techniques described in Theorem 3 could be used, but they require h.sub.i to be a convex set. Clearly, some of the quadric half spaces are not convex.

But a hyperboloid of one sheet and a 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 E.sup.3. Thus, the construction of Theorem 3 can be applied, once such components are separated by an additional set of half spaces. The two sheets of a quadric .differential.h.sub.i are easily separated by a linear half space associated with one of the principal planes of the quadric surface .differential..sub.i. Principal planes of a quadric .differential.h.sub.1 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.

Suppose now that .differential.S contains a nonplanar edge E.sub.j. Theorem 1 implies that no components A and B of any canonical intersection term .sub.k can touch along E.sub.j, and so it should be a simple matter to separate such A and B. But, because the boundaries .differential.A and .differential.B can be arbitrarily close to each other, this may not be a simple task. It may be difficult to construct a sufficient set of separators a priori, without computing .differential.A and .differential.B. Nor can the face separation Theorem 2 be used, because the interior of a face Q.sub.i, bounded by nonplanar edges cannot be separated by a set of linear separators (since edges must lie in the boundaries of separators).

On the other hand, the conditions of Theorem 2 are stronger than necessary: The face Q.sub.i need only be separated from some subset of the remaining surface R.sub.i. Observe that whenever the interior of Q.sub.i is separated from some subset of R.sub.i by linear half spaces, all edges of Q are also separated from the subset by the same linear separators. Thus separating every edge from the rest of the intersection curve is a reasonable heuristic approach to separation which is supported by a prototype system employing the present invention and involving general second-degree surfaces.

As an illustrative example, FIG. 5 is a schematic drawing of a three-dimensional object similar to that of FIG. 3: namely, a sphere intersecting a beam with triangular cross-section; the beam and sphere intersect in three curved edges. The desired object is shaded and consists of the sphere plus one end of the beam. As with FIGS. 2a and 3, the connected components cannot be described separately from each other by use of the natural half spaces induced from the b-rep.

Before considering the solution to this particular example, consider now FIGS. 6a and 6b, which are flowcharts of a preferred embodiment of the present invention. The boundary representation is input (Block 610) to the system according to the present invention where every face of the b-rep is subjected to a number of steps. At Block 620 the natural half spaces H.sub.B are defined by and induced from the boundary representation input. Separator(s) H.sub.S are constructed (Block 630) as will further be described below. The system at Block 640 determines the CSG representation using decomposition based on the union of H.sub.B and H.sub.S and then minimizes, if necessary, the representation at Block 650. This latter step reduces the number of Boolean operators. The CSG representation is then output from the system for use in an application such as image processing or further solid modelling.

Turning now to FIG. 6b, a more detailed flowchart of Block 630 of FIG. 6a is shown. At Block 632 the system according to the present invention constructs separating surfaces through triples of vertices. This step is very similar to what was described above in connection with two-dimensional solids, namely connecting the two end points with a half plane. However, in three-dimensional space, one requires three points to define a planar surface, not two. The system then constructs separating surfaces through any planar edges (Block 634) and lastly constructs separating surfaces to separate any nonplanar edges (Block 636).

Return now to FIG. 5. To obtain a CSG representation of this object from its b-rep, and to solve this problem so it can be computed automatically, the steps discussed with respect to FIGS. 6a and 6b are repeated for every face of the b-rep. Therefore, during the first step the system constructs separators, in this case preferrably separating planes, through the triple of end points (vertices; designated X, Y, and Z in FIG. 5) of the object's edges. Thus the first step is sufficient in this particular example. The system would look for planar edges and nonplanar edges to construct additional separating surfaces through, but these steps would yield no separators for the example depicted in FIG. 5.

But in general such might not be the situation. Assume now that the triangular beam of FIG. 5 is actually a cylindrical beam. In such a case, the system will construct no separators as a result of (Block 632) because there are no vertices; the connected components have round edges (circles)--no edges that meet in points. The system continues to Block 634 (separator through every planar edge) and this time constructs separators because when a cylinder intersects a sphere (assuming exact alignment), there are circles which are planar edges. No separators result from the last step of separating nonplanar edges (Block 636) and the system then proceeds to determine the CSG representation based on the induced natural half spaces and the constructed separating surfaces.

Assume for now that the triangular beam of FIG. 5 is instead a cylindrical beam which intersects with the sphere, and which is not exactly aligned through the center of the sphere. Instead of the circles achieved in the previous example, now the intersecting edges are fourth degree algebraic curves. No separators will be constructed during the first two steps of FIG. 6b because there are no vertices and there are no planar edges. Proceeding to Block 636, the system constructs one or more separating surfaces to separate the nonplanar edge from the rest of the curve on the surface. This yields something which looks like two distinct connected curves, but mathematically both connected components are part of the same curve, each of which will fall on opposite sides of the separating surface.

There are at least two preferred ways to separate these nonplanar components. The first is constructing a tangent separating surface (preferrably a plane) and the other is constructing a polar plane as a separating surface. Polar planes work quite well for second degree surfaces (conics) while tangent planes work for both second and higher degree objects.

In generating the former, one constructs the separator tangentially as close as possible to the nonplanar edge without crossing it. Specifically, achieving separation when nonplanar edges appear in the boundary of S involves isolating the nonplanar edge from the rest of the intersection curve. Suppose C.sub.ij is a nonplanar intersection curve of two convex quadric halfspaces, h.sub.i and h.sub.i. Let E.sub.ij be the edge of solid S on curve C.sub.ij bounded by end points P.sub.1 and P.sub.2 (we will consider the case when E.sub.ij is closed, subsequently). Further, let R.sub.ij be the rest of the curve C.sub.ij not on E.sub.ij, R.sub.ij =h.sub.i *h.sub.j -E.sub.ij. One or more planes are constructed tangent to edge E.sub.ij and these planes are good separating halfspaces.

Suppose C.sub.ij is a fourth degree, nonplanar intersection curve. A plane T containing P.sub.1 and P.sub.2 and one other point on E.sub.ij, P.sub.t can be constructed, such that T is tangent to E.sub.ij at P.sub.t. Thus the tangent plane T cannot intersect curve C.sub.ij again and tangent plane T separates edge E.sub.ij from the rest of curve R.sub.ij. Even in the case where curve C.sub.ij has multiple components, this construction achieves the desired separation.

If E.sub.ij is a closed curve, the two end points P.sub.1 and P.sub.2 are arbitrarily selected and a plane tangent to each piece is constructed. Another approach using a polar plane instead of two tangent planes through P.sub.1 and P.sub.2 achieves the desired separation using a single plane.

Now suppose E.sub.ij is a cubic nonplanar edge with end points P.sub.1 and P.sub.2. P.sub.1 and P.sub.2 determine a line L.sub.12. Construct a second line Lt.sub.1 that is tangent to edge E.sub.ij at P.sub.1. Lines L.sub.12 and Lt.sub.1 determine a plane T.sub.1 that separates E.sub.ij from R.sub.ij locally at P.sub.2. Therefore, the intersection of T.sub.1 and E.sub.ij at P.sub.2 must be transverse; otherwise, there would be two double points at P.sub.2, which is impossible.

Construct another line L.sub.t2 that is tangent to edge E.sub.ij at P.sub.2. Lines L.sub.12 and L.sub.t2 determine a second plane T.sub.2 that separates E.sub.ij from the rest of the curve R.sub.ij locally at P.sub.1. Planes T.sub.1 and T.sub.2 together separate edge E.sub.ij from the rest of the curve R.sub.ij.

The set of separating planes constructed using the tangent planes described above separates all components A and B, and works especially well for convex quadrics.

The other preferred way to separate nonplanar edges of connected components is to look at the object mathematically as if it were a great distance away. In the present example, if the sphere is viewed from this distance, its silhouette is perceived at the maximum extent of the sphere. If a separating plane is put through the sphere's silhouette (polar plane) it will also separating the nonplanar edges of an object.

Specifically, this second approach uses polar planes containing the silhouette edges of halfspaces as separating halfspaces. It turns out that the polar plane of a quadric with respect to a point contains the silhouette edges of the halfspace. If the point is inside the halfspace, silhouette edges are not useful, but in the theory of poles (the point) and polars (the plane), there is a "conjugate" point (and plane) which are useful.

Thus, a point is defined for every halfspace in the domain. The following points are preferred based on surface type (referred to as "special" points below):

1. Sphere--center point

2. Cylinder--point at infinity on axis

3. Cone--apex point

4. Plane--point at infinity (axis undefined, however)

The plane can be a problem since an infinite number of points are available "at infinity" however the present invention preferably employs b-rep edge information to select one or several appropriate points.

Look at the pair of halfspaces forming each edge in the b-rep. Let PP(P.sub.n,h.sub.m) represent the polar plane of point P.sub.n with respect to halfspace h.sub.m (one may need to consider the conjugate point/plane). This results in the following two polar planes for each edge formed by h.sub.1 and h.sub.2 --PP(P.sub.1,h.sub.2) and PP(P.sub.2,h.sub.1). The end points of the edge are used to determine direction when a plane is involved.

This technique may eliminate the need to put planes through each triplet of vertices. It also handles planar and nonplanar edges correctly and is extendable to other quadrics (poles and polars).

The above innovations have enabled a successful implementation of an experimental b-rep.fwdarw.CSG conversion system that converts natural quadric b-reps in Parasolid.RTM. (registered trademark and product of Electronic Data Systems Corporation) to efficient CSG representations in PADL-2. A schematic diagram of a system 700 employing the present invention is shown in FIG. 7.

For the sake of discussion herein, system 700 is capable of modelling a desired object, and incorporates at least one workstation or client/server 710 and/or at least one mainframe computer 720. The exact composition of such workstation 710 or mainframe 720 is well-known and will not be described herein. There is a CAD/CAM system of the user's choice, such as Unigraphics.RTM. (registered trademark and product of Electronic Data Systems Corporation), residing on said workstation 710 and/or mainframe 720, depending upon the particular configuration of system 700. Such CAD/CAM systems are well-known in the art and will not be further described herein. Moreover, while the current prototype resides on a VAX (trademark and product of Digital Equipment Corporation) computing system, it should be understood that the system and method of the present invention could instead employ other computing systems from microprocessors to mainframes.

System 700 provides input to modelling program 750 by accessing memory 730 via bus 740. It should be understood that a number of commercially available products could be used to generate an object representation used herein as input. The representation is provided as input to the definition editor 760 of geometric modelling program 750 which in turn provides such representation to either conversion program 770 (b-rep to CSG) or to conversion program 780 (CSG to b-rep) depending upon the application. Since there are a variety of systems and methods to convert from CSG to b-rep, many of which are commercially available in various geometric modelling systems, converter 780 will not be further described. The output of converters 770,780 is provided to applications 790,795,800. These applications could entail further modelling, object analysis, image processing, etc.

Considering specifically converter 770, for a two-dimensional object, perhaps a piece of sheet metal, the b-rep input is a list of lines and arcs which bound and describe the object. The list normally includes the X,Y coordinates of all the corners, and the radius of any arcs and is kept in a computer file. Such a file could be generated by any number of commercially available geometric modeling systems such as Unigraphics.RTM. and in fact, it can be entered manually on the keyboards of workstation 710 or mainframe 720.

In three-dimensions the b-rep input is not as simple because a description of a three dimensional object is needed. Therefore, instead of a list of lines and arcs, one could employ a solid or geometric modelling system such as Parasolid.RTM. to generate a list of the faces of the solid which describes the natural half spaces. It should be understood that a number of other commerically available products that could be used to generate the boundary representation input.

Regardless of object dimension of the input, converter 770 preferrably generates a human readable text listing as output on a terminal or in a file of a valid CSG for a specific application 790,795,800. It can also generate a text listing to be provided to a PADL-2 CSG solid modelling system. Numerous CAD/CAM vendors have built products on PADL-2. Moreover the converted description found in the text listing for a two-dimensional object could be swept into a three-dimensional object.

A C-clamp assembly, shown in FIGS. 8a-8e, is a simple example three-dimensional solid object computed by the system of the present invention. This example shows a three piece C-clamp assembly (FIG. 8a) which consists of three independent parts: a C-shaped body (FIGS. 8d, 8e), a threaded screw for tightening the C-clamp (FIG. 8b), and a handle (FIG. 8c). The system of the present invention took as its input a boundary representation of each of these objects, as constructed using Unigraphics.RTM. and Parasolid.RTM., and computed the CSG representation for each of those objects, shown above each part in bold print. This representation amounts to the Boolean expression that represents the particular object. Thus the CSG expression for the C-clamp screw is (B+D+E)ACFG, while the CSG expression for the C-clamp handle is BDE+A+C, based on the boundary representations shown in the respective drawings.

Looking now at FIGS. 8d and 8e which show the separators and the natural half spaces induced from the boundary representation of the C-clamp body, respectively. The dotted lines are the separators required for the representation of the body of the C-clamp in CSG. The natural half spaces, H.sub.B s, are the uppercase letters in the Boolean CSG expression, and the lowercase letters are the separators, H.sub.S s. Thus the C-clamp body cannot be described unless the five separators indicated are unioned with the natural half spaces. It can also be seen that by using the present invention, one can define real objects using standard (as opposed to regularlization) operators thereby making a whole range of mathematics developed over the centuries available to solid modeling problems.

The program listing (found in the Appendix) demonstrates an embodiment of the invention contained therein. It should be understood by those skilled in the art that such is provided only by way of illustrative example and should in no manner be construed to limit the invention as described herein. Numerous modifications and alternate embodiments of the invention will occur to those skilled in the art. Accordingly, it is intended that the invention be limited only in terms of the following claims: ##SPC1##