13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lectures 14 and 15 N. M. Patrikalakis Massachusetts Institute of Technology Cambridge, MA 02139-4307, USA Copyright 2003 Massachusetts Institute of Technology Contents Constructive Solid Geometry(CSG) 14.2 Primitives of CSG 14.3 Boolean operators 14.3.1 Regularized Boolean operators 14.4 Set membership classification 14.5 Properties of CSG 7 Boundary Representation 14.6 Two-manifold B-rep 14.6. 1 Information contained in a B-rep 14.6.2 Characteristics of domain for two-manifold solid object representations. 12 14.6.3 Euler-Poincare equation 12 14.6.4 Sufficiency of a geometric modeling representation 14.6.5 Boundary representation model 14.7 Data structures for manifold representations 14.7.1 Winged-edge data structure 14.7.2 Vertex-edge data structure(V-E) 14.7.3 Face-edge data structure (FE) 14.8 Operators for manipulating manifold topologies 14.8.1 Basic operators 14.8.2 Building high level functions on the Euler operators 14.9 Non Two-Manifold B-rep 14.9.1 Topological elements in NTM topologies 58290 14.9.2 Topological sufficiency 14.10Radial edge data structure Bibliography
13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lectures 14 and 15 Prof. N. M. Patrikalakis Massachusetts Institute of Technology Cambridge, MA 02139-4307, USA Copyright c 2003 Massachusetts Institute of Technology Contents Constructive Solid Geometry (CSG) 2 14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 14.2 Primitives of CSG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 14.3 Boolean operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 14.3.1 Regularized Boolean operators . . . . . . . . . . . . . . . . . . . . . . . 4 14.4 Set membership classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 14.5 Properties of CSG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Boundary Representation 8 14.6 Two-manifold B-rep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 14.6.1 Information contained in a B-rep . . . . . . . . . . . . . . . . . . . . . . 10 14.6.2 Characteristics of domain for two-manifold solid object representations . 12 14.6.3 Euler-Poincar´e equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 14.6.4 Sufficiency of a geometric modeling representation . . . . . . . . . . . . 16 14.6.5 Boundary representation model . . . . . . . . . . . . . . . . . . . . . . . 16 14.7 Data structures for manifold representations . . . . . . . . . . . . . . . . . . . . 16 14.7.1 Winged-edge data structure . . . . . . . . . . . . . . . . . . . . . . . . . 18 14.7.2 Vertex-edge data structure (V-E) . . . . . . . . . . . . . . . . . . . . . . 20 14.7.3 Face-edge data structure (FE) . . . . . . . . . . . . . . . . . . . . . . . 21 14.8 Operators for manipulating manifold topologies . . . . . . . . . . . . . . . . . . 21 14.8.1 Basic operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 14.8.2 Building high level functions on the Euler operators . . . . . . . . . . . 28 14.9 Non Two-Manifold B-rep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 14.9.1 Topological elements in NTM topologies . . . . . . . . . . . . . . . . . . 29 14.9.2 Topological sufficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 14.10Radial edge data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Bibliography 37 1
Constructive Solid Geometry (CSG) 14.1 Introduction CSG is a method in which an object is constructed from the standard primitives using regu larized Boolean operations. The model is represented in the data structure as a CSg tree, see Figure 14.1, whose terminal nodes are primitives and non-terminal nodes are Boolean operators intersection, union and difference). Primitives are sized, positioned and oriented first b11 Figure 14. 1: An example of Csg tree 14.2 Primitives of CSG Typical primitives are the rectangular box, the circular cylinder of finite height, the sphere, the cone of finite height and the torus. Figure 14.2 shows two collections of CSG primitives. These primitives may be defined as intersections of halfspaces(defined by algebraic inequalities of the form f(x,y,2)≥0
Constructive Solid Geometry (CSG) 14.1 Introduction CSG is a method in which an object is constructed from the standard primitives using regularized Boolean operations. The model is represented in the data structure as a CSG tree, see Figure 14.1, whose terminal nodes are primitives and non-terminal nodes are Boolean operators ( intersection, union and difference). Primitives are sized, positioned and oriented first. diff. un. cy. bl1 bl2 Figure 14.1: An example of CSG tree 14.2 Primitives of CSG Typical primitives are the rectangular box, the circular cylinder of finite height, the sphere, the cone of finite height and the torus. Figure 14.2 shows two collections of CSG primitives. These primitives may be defined as intersections of halfspaces (defined by algebraic inequalities of the form f(x, y, z) ≥ 0). 2
Figure 14.2: Two collections of CSG primitives 14.3 Boolean operators Definition: A set S is regular if s=(int(S)), where int means the interior, and cl means losure. Taking the interior of s means constructing a subset of s where all points in the subset have an E-neighborhood homeomorphic to a ball. CI sure imeans a dding the limit points(or boundary) to the interior points to produce a new set Let A, b denote regular sets in R, then b(AUB)=(bA∩cB)U(bB∩cA) b(A∩B)=(bA∩iB)∪(bB∩iA) (141 b (A-B)=(bancB)U(bb nia where bX is the boundary of the set X, ix is its interior and cX is its complement. See Figure 14.3. Obviously, Boolean operators require the execution of surface intersections, and postprocessing to evaluate the correct boundary of the resulting set using(14. 1) b(A∩B)
(a) (b) Figure 14.2: Two collections of CSG primitives. 14.3 Boolean operators Definition: A set S is regular if S = (int(S))cl , where int means the interior, and cl means closure. Taking the interior of S means constructing a subset of S where all points in the subset have an ε-neighborhood homeomorphic to a ball. Closure means adding the limit points (or boundary) to the interior points to produce a new set. Let A, B denote regular sets in R3 , then b(A ∪ B) = (bA ∩ cB) ∪ (bB ∩ cA) b(A ∩ B) = (bA ∩ iB) ∪ (bB ∩ iA) (14.1) b(A − B) = (bA ∩ cB) ∪ (bB ∩ iA) where bX is the boundary of the set X, iX is its interior and cX is its complement. See Figure 14.3. Obviously, Boolean operators require the execution of surface intersections, and postprocessing to evaluate the correct boundary of the resulting set using (14.1). A B A B b (A B ) A B b (A B ) A B b (A B ) − Figure 14.3: Boolean operators 3
14.3.1 Regularized Boolean operators Manifold objects are not closed under Boolean operations. Regularized set operations make it 多多 set-theoretic regularized intersection intersecti。n Let n* be a regularized set operation, and C*= An* B, then to compute C, we proceed conceptually as follows 1.C=A∩B 3. C*= closure C Figure 14.5 shows the procedure with an example. Stepl Step2 Step3 inter closure A∩B A∩B (AI IB) Figure 14.5: Procedure for regularized intersection
14.3.1 Regularized Boolean operators Manifold objects are not closed under Boolean operations. Regularized set operations make it so, see Figure 14.4 for example. ✁✁✂✁✁✂✁ ✁✁✂✁✁✂✁ ✁✁✂✁✁✂✁ ✁✁✂✁✁✂✁ ✁✁✂✁✁✂✁ ✄✂✄✁✄✁✄✂✄ ✄✂✄✁✄✁✄✂✄ ✄✂✄✁✄✁✄✂✄ ✄✂✄✁✄✁✄✂✄ ✄✂✄✁✄✁✄✂✄ ✄✂✄✁✄✁✄✂✄ ✄✂✄✁✄✁✄✂✄ ✁✁✂✁✁✂✁ ✁✁✂✁✁✂✁ ✁✁✂✁✁✂✁ ✁✁✂✁✁✂✁ ✁✁✂✁✁✂✁ ✄✂✄✁✄✁✄ ✄✂✄✁✄✁✄ ✄✂✄✁✄✁✄ ✄✂✄✁✄✁✄ ✄✂✄✁✄✁✄ ✄✂✄✁✄✁✄ ✄✂✄✁✄✁✄ ✄✁✄✂✄✁✄✁✄ ✄✁✄✂✄✁✄✁✄ ✄✁✄✂✄✁✄✁✄ ✄✁✄✂✄✁✄✁✄ ✁✂✁✁ ✁✂✁✁ ✁✂✁✁ ✁✂✁✁ ✂✁✁ ✂✁✁ ✂✁✁ ✂✁✁ ✄✂✄✁✄✁✄ ✄✂✄✁✄✁✄ ✄✂✄✁✄✁✄ ✄✂✄✁✄✁✄ A B A B set−theoretic intersection regularized intersection Figure 14.4: Regularized set operations. Let ∩ ∗ be a regularized set operation, and C ∗ = A ∩ ∗ B, then to compute C ∗ , we proceed conceptually as follows: 1. C = A ∩ B 2. Ci = interior C 3. C ∗ = closure Ci Figure 14.5 shows the procedure with an example. Step1 Step2 Step3 A B A B interior (A B) closure (A B) Figure 14.5: Procedure for regularized intersection. 4
14.4 Set membership classification Given a CSG model M and an object X in the scene, the function Classify (M, X) will indicate if (see Figure 14.6) X is in M, Is on .X is out of m t of M ●X2 Figure 14.6: Membership classification Divide-and-conquer paradigm CLASSIFY(M, X) Is a h then PRIM-CLASSIFY(M, X) else COMBINE(CLASSIFY (left-subtree(M), X) CLASSIFY(right-subtree(M), X), operation of M) For the example shown in Figure 14.7, CLASSIFY (M, X)= COMBINE(PRIM-CLASSIFY(A, X), PRIM-CLASSIFY(B, X) COMBINE(X-in-A, X-in-B, intersection) Similarly, classifying a line with respect a CSg model M= Anb typically involves inter- ections of the line with A and B, and then checking to see if the intersections which are line
14.4 Set membership classification Given a CSG model M and an object X in the scene, the function Classify(M, X) will indicate if (see Figure 14.6): • X is in M, or • X is on M, or • X is out of M. M X1 X2 X3 X1 out of M X2 in M X3 on M Figure 14.6: Membership classification. Divide-and-conquer paradigm CLASSIFY(M,X) 1 if M is a primitive 2 then PRIM-CLASSIFY(M,X) 3 else COMBINE(CLASSIFY(left-subtree(M),X), CLASSIFY(right-subtree(M),X), operation of M) For the example shown in Figure 14.7, CLASSIFY(M,X) = COMBINE(PRIM-CLASSIFY(A,X), PRIM-CLASSIFY(B,X), intersection) = COMBINE(X-in-A, X-in-B, intersection) = X-in-M Similarly, classifying a line with respect a CSG model M = A T B typically involves intersections of the line with A and B, and then checking to see if the intersections which are line segments have a common segment, see Figure 14.8. 5