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
M=A⌒B Figure 14.7: Example of membership classification for point B Figure 14.8: Example of membership classification for line
☎✆☎✝☎✆☎ ☎✆☎✝☎✆☎ M = A B A B A B X X X Figure 14.7: Example of membership classification for point ✞✞✞✞ ✞✞✞✞ ✞✞✞✞ ✞✞✞✞ A B Figure 14.8: Example of membership classification for line 6
14.5 Properties of CSG Here are the basic properties of Csg models · Advantages: validity: CSG model is always valid conciseness: CSG tree is in principle concise computational ease: primitives are easy to handle unambiguity: every CSg tree unambiguously models a rigid solid (maybe more than · Disadvantages non-uniqueness: a solid could have more than one CSG representation limit on primitives: free-form surfaces are excluded, and primitives are typically bounded by a number of simple low order algebraic surfaces redundancy of CSG tree: it may have redundant primitives that do not contribute final solid no explicit boundary information: CSG tree needs to be evaluated(eg. rendered to evaluate surface, such as ray trace it, etc.)
14.5 Properties of CSG Here are the basic properties of CSG models • Advantages: - validity: CSG model is always valid; - conciseness: CSG tree is in principle concise; - computational ease: primitives are easy to handle; - unambiguity: every CSG tree unambiguously models a rigid solid (maybe more than one). • Disadvantages: - non-uniqueness: a solid could have more than one CSG representation, - limit on primitives: free-form surfaces are excluded, and primitives are typically bounded by a number of simple low order algebraic surfaces. - redundancy of CSG tree: it may have redundant primitives that do not contribute to final solid. - no explicit boundary information: CSG tree needs to be evaluated (eg. rendered to evaluate surface, such as ray trace it, etc.) 7
Boundary representation 14.6 Two-manifold B-rep Definition: Boundary models describe solids in terms of their bounding entities, such as faces, loops, · Examples: solid volume bounding faces The bounding relations shown in Figure 14.9 are 6 faces(s square 4 edges(line segment) 2 vertices(points in 3-D space Figure 14.9: Boundary of a cube a two-manifold B-rep is an explicit representation of a single object(volume) by its bound- Compact(closed and bounded) · Orientable,and ●Two- manifold Definitions
Boundary Representation 14.6 Two-manifold B-rep • Definition: Boundary models describe solids in terms of their bounding entities, such as faces, loops, edges and vertices. • Examples: polygon =⇒ bounding edges solid volume =⇒ bounding faces • The bounding relations shown in Figure 14.9 are: cube =⇒ 6 faces (squares) square =⇒ 4 edges (line segment) line segment =⇒ 2 vertices (points in 3-D space) ✟✠✟✡✟✠✟✡✟✠✟✡✟✠✟✡✟✠✟✡✟✠✟ ✟✠✟✡✟✠✟✡✟✠✟✡✟✠✟✡✟✠✟✡✟✠✟ ✟✠✟✡✟✠✟✡✟✠✟✡✟✠✟✡✟✠✟✡✟✠✟ Figure 14.9: Boundary of a cube. A two-manifold B-rep is an explicit representation of a single object (volume) by its boundary which is assumed to be: • Compact (closed and bounded), • Orientable, and • Two-manifold. Definitions 8
1. A surface is closed if it is bounded and has no boundary(eg. a plane is unbounded,a patch is bounded but has boundary and a sphere is closed as its surface is bounded and has no boundary 2. A surface is orientable if it is two sided (not like Mobius strip and Klein bottle) 3. A two-manifold surface is topologically two dimensional connected surface where each point on the surface has a neighborhood which is topologically equivalent to an open disk Orientable and closed surfaces are required to distinguish inside and outside. Counter examples of two-manifold surfaces are shown in Figure 14.11 4. Topological equivalence(Homeomorphism ): A homeomorphism is a one-to-one topologi- cal transformation which is continuous and has a continuous inverse (intuitively, elastic deformations which preserve adjacency properties). Or, more strictly, if there is a one- to-one correspondence between the points of a surface and those of another surface, so that the topological properties of any figure in one of the surfaces are shared by its im age in the other, the two surfaces are said to be homeomorphic to each other, and the mapping from one surface to the other established by the one-to-one correspondence is a homeomorphism 5. Open disk, portion of a 2-D space(surface) which is within a circle of positive radius excluding circle. See Figure 14.12
1. A surface is closed if it is bounded and has no boundary (eg. a plane is unbounded, a patch is bounded but has boundary and a sphere is closed as its surface is bounded and has no boundary). 2. A surface is orientable if it is two sided (not like M¨obius strip and Klein bottle 3. A two-manifold surface is topologically two dimensional connected surface where each point on the surface has a neighborhood which is topologically equivalent to an open disk. • Orientable and closed surfaces are required to distinguish inside and outside. • Counter examples of two-manifold surfaces are shown in Figure 14.11. 4. Topological equivalence (Homeomorphism): A homeomorphism is a one-to-one topological transformation which is continuous and has a continuous inverse (intuitively, elastic deformations which preserve adjacency properties). Or, more strictly, if there is a oneto-one correspondence between the points of a surface and those of another surface, so that the topological properties of any figure in one of the surfaces are shared by its image in the other, the two surfaces are said to be homeomorphic to each other, and the mapping from one surface to the other established by the one-to-one correspondence is a homeomorphism. 5. Open disk, portion of a 2-D space (surface) which is within a circle of positive radius, excluding circle. See Figure 14.12. 9 )
Figure 14.11: Non two-manifold surfaces Disk Figure 14. 12: Neighborhood of point on two-manifold object is a disk 14.6.1 Information contained in a B-rep There are two different kinds of information necessary in a B-rep, geometrical information and topological information, see Figure 14.13. Geometrical information provides a complete specification of the object and topological information is an abstraction, which provides a “fuzy” definition of the object correct within“ genus” specification( number of through hole and subdivision into faces together with their adjacency A geometrical entity S is incident to another geometrical entity $2, if S has dimensi ality one higher than S2, and S2 is a bounding entity of S1. Two geometrical entities S1 and S2 are adjacent, if they have the same dimensionality and share a common bounding entity Geometrical information Complete geometry can be considered to represent all information about the geometric shape of an object including where it lies in space and the precise location of all aspects of its various elements · points curves:eg. line segments, circular arcs, B-spline, and Bezier curves, NURBS curves and surfaces: e. g bounded planes, quadrics, B-spline and Bezier surfaces, NURBS patches i. e. geometry deals with the relationships between surfaces, curves, points and the coordinate
☛☞☛ ☛☞☛☛☞☛ ☛☞☛☛☞☛ ☛☞☛☛☞☛ Figure 14.11: Non two-manifold surfaces. ✌✍✌✎✌ ✌✍✌✎✌ ✌✍✌✎✌ ✌✍✌ ✌✍✌ Disk Figure 14.12: Neighborhood of point on two-manifold object is a disk. 14.6.1 Information contained in a B-rep There are two different kinds of information necessary in a B-rep, geometrical information and topological information, see Figure 14.13. Geometrical information provides a complete specification of the object and topological information is an abstraction, which provides a “fuzzy” definition of the object correct within “genus” specification (number of through holes) and subdivision into faces together with their adjacency. A geometrical entity S1 is incident to another geometrical entity S2, if S1 has dimensionality one higher than S2, and S2 is a bounding entity of S1. Two geometrical entities S1 and S2 are adjacent, if they have the same dimensionality and share a common bounding entity. Geometrical information Complete geometry can be considered to represent all information about the geometric shape of an object including where it lies in space and the precise location of all aspects of its various elements: • points, • curves: eg. line segments, circular arcs, B-spline, and B´ezier curves, NURBS curves and • surfaces: e.g. bounded planes, quadrics, B-spline and B´ezier surfaces, NURBS patches, i.e. geometry deals with the relationships between surfaces, curves, points and the coordinate space. 10