Computational Geometry：lecnotes14_fixed

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 classi cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Su ciency 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 su ciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 di erence). Primitives are sized, positioned and oriented rst. 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 nite height, the sphere, the cone of nite height and the torus. Figure 14.2 shows two collections of CSG primitives. These primitives may be de ned as intersections of halfspaces (de ned by algebraic inequalities of the form f(x;y;z) 0). 2 (a) (b) Figure 14.2: Two collections of CSG primitives. 14.3 Boolean operators De nition: 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 so, see Figure 14.4 for example. a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a3a2a3a1a3a1a3a2a3 a3a2a3a1a3a1a3a2a3 a3a2a3a1a3a1a3a2a3 a3a2a3a1a3a1a3a2a3 a3a2a3a1a3a1a3a2a3 a3a2a3a1a3a1a3a2a3 a3a2a3a1a3a1a3a2a3 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a0a1a0a1a0a2a0a1a0a1a0a2a0a1a0 a3a2a3a1a3a1a3 a3a2a3a1a3a1a3 a3a2a3a1a3a1a3 a3a2a3a1a3a1a3 a3a2a3a1a3a1a3 a3a2a3a1a3a1a3 a3a2a3a1a3a1a3 a3a1a3a2a3a1a3a1a3 a3a1a3a2a3a1a3a1a3 a3a1a3a2a3a1a3a1a3 a3a1a3a2a3a1a3a1a3 a0a1a0a2a0a1a0a1a0 a0a1a0a2a0a1a0a1a0 a0a1a0a2a0a1a0a1a0 a0a1a0a2a0a1a0a1a0 a0a2a0a1a0a1a0 a0a2a0a1a0a1a0 a0a2a0a1a0a1a0 a0a2a0a1a0a1a0 a3a2a3a1a3a1a3 a3a2a3a1a3a1a3 a3a2a3a1a3a1a3 a3a2a3a1a3a1a3 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 classi cation 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 classi cation. 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 = ATB typically involves inter- sections 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 a4a5a4a6a4a5a4 a4a5a4a6a4a5a4 M = A B A B A B X X X Figure 14.7: Example of membership classi cation for point a7 a7 a7 a7 a7 a7 a7 a7 a7 a7 a7 a7 a7 a7 a7 a7 A B Figure 14.8: Example of membership classi cation 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 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 nal 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 De nition: 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) a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8 a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8 a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8 a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8 a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8a10a8a9a8 Figure 14.9: Boundary of a cube. A two-manifold B-rep is an explicit representation of a single object (volume) by its bound- ary which is assumed to be: Compact (closed and bounded), Orientable, and Two-manifold. De nitions 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 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 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 gure 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. 9 ). a11a12a11 a11a12a11 a11a12a11 a11a12a11 a11a12a11 a11a12a11 a11a12a11 Figure 14.11: Non two-manifold surfaces. a13a14a13a15a13 a13a14a13a15a13 a13a14a13a15a13 a13a14a13 a13a14a13 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 di erent kinds of information necessary in a B-rep, geometrical information and topological information, see Figure 14.13. Geometrical information provides a complete speci cation of the object and topological information is an abstraction, which provides a \fuzzy" de nition of the object correct within \genus" speci cation (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 dimension- 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 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 Topology Geometry complete information No Information "fuzzy" definition of an object without geometry Figure 14.13: B-rep model idealization Topological information Topology is an abstraction, and it contains the incidence information of various elements. It is incomplete information which can \ideally" be derived from the complete geometric speci ca- tion. Topology deals with the adjacency relationships between corresponding entities, namely physical proximity or order of a group of topological elements of one type (such as vertices, edges or faces) around some other speci c single topological elements. Adjacency relationships are illustrated in Figure 14.14. The typical topological elements are: Vertex: A unique point in space. A vertex lies in one or more faces. Edge: A nite, non-self-intersecting curve bounded by two not necessarily distinct ver- tices. An edge lies on the boundaries of exactly two faces of a two-manifold object. Loop: An ordered alternating sequence of vertices and edges de ning a unique point or directed non-self-intersecting, closed space curve. Face: A nite connected non-self-intersecting oriented piece of a surface bounded by one or more loops. A loop lies in a single face and forms a bound of the face. The number of faces is equal to the number of peripheral loops. Shell: The collection of consistently oriented faces forming the boundary of a single, connected, closed volume (region). Region: Unique, identi able volume in space. There is one region with in nite extent, all others are nite. Model: 3-D modeling space, consisting of one or more regions. In a two-manifold representation there is a one-to-one correspondence between a region and its bounding shell. Therefore it is su cient to have just one of them represented explicitly. In general regions are not represented explicitly in most existing B-rep data structures. 11 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18 a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18 a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18 a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18 a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16 a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16 a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16 a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16 a19a17a19a17a19 a19a17a19a17a19 a19a17a19a17a19 a19a17a19a17a19 a19a17a19a17a19 a19a17a19a17a19 a19a17a19a17a19 a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18 a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18 a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18 a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18a17a18 a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16 a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16 a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16 a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16 a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16a17a16 v v(E) v v(F) e e(V) e e(F) f f(E) f(F) a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20a17a20 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 f v V(V) e(E) e a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 a16a17a16a17a16 f f(V) Figure 14.14: Adjacency relationships. 14.6.2 Characteristics of domain for two-manifold solid object representa- tions Surfaces: compact, orientable, two-manifold embedded in the 3-D Euclidean space. Faces: no self-intersection is permitted but they are allowed to intersect with each other at edges or vertices. Remarks: Adjacency topology explicitly carries all surface intersection information through adja- cency information. No non two-manifold situations are allowed. Therefore, in a traversal of edges bounding faces, every edge is traversed exactly twice. Orientability guarantees that the interior of a solid volume is distinguishable from its exterior (See Figure 14.15). The orientability guarantees that the interior of a solid volume is distinguishable from its exterior. 14.6.3 Euler-Poincar e equation This equation is a relationship between topological elements for a single two-manifold shell: V E + F Li = 2(1 G) (14.2) 12 orientable surface Figure 14.15: Orientable surface. where, V : Number of vertices. E: Number of edges. F: Number of faces. Li: Number of interior loops. G: Genus, the number of closed paths on a surface which do not separate the surface into more than one region. Or, genus is the number of handles to be added to a sphere to make it homeomorphic to the object. genus = 1 genus = 0 Figure 14.16: Torus and sphere. Another form of the Euler equation is V E + 2F L = 2(1 G) (14.3) ( using the relations L = Lp + Li and Lp = F, Lp: number of peripheral loops ) For multiple shelled objects (objects with cavities), the Euler equation becomes V E + F Li = 2(S G) (14.4) S: number of shells. Euler equation is a necessary but not su cient condition for validity of a B-rep. 13 Conditions for topological validity 1. V;E;F;Li;S;G 0, 2. If V = E = F = Li = 0 =) S = 0;G = 0, 3. If S 0 =) V S and F S, and 4. For a shell to exist, there must be at least one vertex and one face on the shell. Examples Example 1: A tetrahedron (see Figure 14.17) Figure 14.17: Tetrahedron. V = 4;E = 6;F = 4;Li = G = 0 4 6 + 4 0 = 2 = 2(1 0) Example 2: A cube with or without a hole (see Figure 14.18) (a) (b) Figure 14.18: (a) Cube; (b) Cube with a hole. (a) Without hole V = 8;E = 12;F = 6;Li = G = 0 8 12 + 6 0 = 2 (b) With a hole V = 10;E = 15;F = 7;Li = 2;G = 1 10 15 + 7 2 = 2(1 1) = 0 14 Figure 14.19: Cube with a loop Example 3: A cube with a loop, (see Figure 14.19) { Original case V = 12;E = 16;F = 7;Li = 1;S = 1;G = 0 12 16 + 7 1 = 2 = 2(1 0) { Connecting the interior loop with one corner vertex of the cube V = 12;E = 16 + 1 = 17;F = 7;Li = 1 1 = 0;S = 1;G = 0 12 17 + 7 = 2 = 2(1 0) Example 4: A sphere with a handle, (see Figure 14.20) Figure 14.20: Sphere with a handle. { Original case V = 2;E = 2;F = 2;Li = 2;S = 1;G = 1 2 2 + 2 2 = 0 = 2(1 1) { Add one more edge on the handle (namely connect the two loops) V = 2;E = 3;F = 2;Li = 1;S = 1;G = 1 2 3 + 2 1 = 0 = 2(1 1) 15 14.6.4 Su ciency of a geometric modeling representation Su ciency of a geometric modeling representation is the ability to completely and unambigu- ously represent all adjacency topological relationships of elements. Theoretical su ciency is the absolute minimum information required to reproduce un- ambiguously a complete adjacency topology. In general, adjacency relationship informations V(E) (cyclicly ordered edges around ver- tices) and F(E) (cyclicly ordered edges around faces) are individually su cient to represent all adjacency relationships. Some combinations of single insu cient adjacency relationships are su cient under certain conditions. 14.6.5 Boundary representation model V1 V2 V3 V4 e1 e2 e3 e5 e6 e4 f4 f3 f1 f2 V4 V1 V2 V3 e1 e3 e2 f2 f3 f4 e4 e5e6 Top View Figure 14.21: Boundary representation model. Figure 14.21 shows an example of a tetrahedron. The boundary representation model for this example is shown in Figure 14.22. See also Table 14.1. 14.7 Data structures for manifold representations Three di erent edge-based data structures for representing manifold topologies useful in solid modeling are: 1. the winged-edge data structure 2. the vertex-edge data structure 3. the face-edge data structure The winged edge data structure keeps the edge information as a single unit while the face-edge and vertex-edge structures split the information related to each edge into two parts based on the speci c usage of the edge in the adjacency relationships. 16 Object definition (region) Boundary definition Faces: f1 f2 f3 f4 Loops: Edges: Vertices: Topological Information Vertex assignment (Geometry) L1 L2 L3 L4 e1 e2 e3 e4 e5 e6 V1 V2 V3 V4 (x1,y1,z1) (x2,y2,z2) (x3,y3,z3) (x4,y4,z4) Figure 14.22: Boundary representation model for a tetrahedron 17 V(V) V(E) V(F) V1(V ) = (V2 V3 V4) V1(E) = (e1 e3 e2) V1(F) = (f2 f3 f4) V2(V ) = (V3 V1 V4) V2(E) = (e5 e3 e4) V2(F) = (f1 f3 f2) V3(V ) = (V1 V2 V4) V3(E) = (e6 e2 e5) V3(F) = (f1 f4 f3) V4(V ) = (V2 V1 V3) V4(E) = (e4 e1 e6) V4(F) = (f1 f2 f4) E(V) E(E) E(F) e1(V ) = (V1 V4) e1(E) = [(e3 e2)(e6 e4)] e1(F) = (f2 f4) e2(V ) = (V1 V3) e2(E) = [(e1 e3)(e5 e6)] e2(F) = (f3 f4) e3(V ) = (V1 V2) e3(E) = [(e2 e1)(e4 e5)] e3(F) = (f2 f3) e4(V ) = (V2 V4) e4(E) = [(e5 e3)(e1 e6)] e4(F) = (f1 f2) e5(V ) = (V2 V3) e5(E) = [(e3 e4)(e6 e2)] e5(F) = (f1 f3) e6(V ) = (V3 V4) e6(E) = [(e2 e5)(e4 e1)] e6(F) = (f1 f4) F(v) F(E) F(F) f1(V ) = (V2 V4 V3) f1(E) = (e4 e6 e5) f1(F) = (f3 f2 f4) f2(V ) = (V4 V2 V1) f2(E) = (e4 e3 e1) f2(F) = (f1 f3 f4) f3(V ) = (V1 V2 V3) f3(E) = (e3 e5 e2) f3(F) = (f2 f1 f4) f4(V ) = (V1 V3 V4) f4(E) = (e2 e6 e1) f4(F) = (f2 f3 f1) Table 14.1: Adjacency relationships for boundary representation of tetrahedron. ev ptr [1] ev ptr [2] ee cw ptr [1] ee cw ptr [2] ee ccw ptr [1] ee ccw ptr [2] ef ptr [1] ef ptr [2] e ptr (edge attribute) Table 14.2: Winged-edge data structure. 14.7.1 Winged-edge data structure (1) Data structure Topological information stored for each edge is composed of the adjacencies of that edge with four other edges, two faces, and two vertices, see Figure 14.23. (2) Application of winged-edge data structure, see Figure 14.24 and Table 14.3. Question: adjacency relationship f4(E)? Start with edge \e1" and traverse data structure e1(CCW[2]) ! e6, check f4 = f[2] and e6(CCW[2]) ! e2, check f4 = f[2] and e2(CCW[2]) ! e1 (3) Supporting data structure (see Figure 14.25) \Shell" shell attribute ptrface ptr (doubly linked list of faces) 18 ee_cw_ptr [1] ee_ccw_ptr [2] ev_ptr [2] f2 f1 ev_ptr [1] ee_ccw_ptr [1]ee_cw_ptr [2] ef_ptr [2] ef_ptr [1] Figure 14.23: Winged-edge data structure. V1 V2 V3 V4 e1 e2 e3 e5 e6 e4 f4 f3 f1 f2 f [1]f [2] V[2] V[1] CW[1]CCW[2] CCW[1] CW[2] Figure 14.24: Application of winged-edge data structure. 19 edge V [1] V [2] f[1] f[2] CW[1] CCW[1] CW[2] CCW[2] e1 V1 V4 f2 f4 e4 e3 e2 e6 e2 V3 V1 f3 f4 e3 e5 e6 e1 e3 V1 V2 f3 f2 e5 e2 e1 e4 e4 V2 V4 f1 f2 e6 e5 e3 e1 e5 V2 V3 f3 f1 e2 e3 e4 e6 e6 V4 V3 f1 f4 e5 e4 e1 e2 Table 14.3: Application of winged-edge data structure. Shell face list f1 f2 ... fnφ ... φ edge list edge ...... em φφ Winged?edge data structure Figure 14.25: Supporting data structure. \face" next face ptr previous face ptr edge ptr or vertex ptr vertex vertex attribute (geometry) 14.7.2 Vertex-edge data structure (V-E) V-E data structure represents the adjacency information of the edge by splitting it into two structures, each of which is related to one of the two edge end vertices, see Figure 14.26 and Table 14.4. Each edge is used exactly twice in opposite directions by two adjacent faces. This results in the concept of \edge-use" ev ptr ee cw ptr ee ccw ptr ef ptr ee mate ptr (other end of edge) e ptr (edge attribute) Table 14.4: Vertex-edge data structure. 20 ee_ccw_ptr ee_cw_ptr edge use face ef_ptr ev_ptr f1 f2 two edge uses ("mates") other part Figure 14.26: Vertex-edge data structure. ev ptr ee cwe ptr ee ccwe ptr ef ptr ee mate ptr (other half of the edge) e ptr (edge attribute) Table 14.5: Face-edge data structure. 14.7.3 Face-edge data structure (FE) The F-E structure represents the adjacency information of the edge by splitting it into two structures, each of which is related to one of the two edge sides as found around the periphery of faces, see Figure 14.27 and Table 14.5. This results in the concept of \edge-use" . 14.8 Operators for manipulating manifold topologies The Euler operators are a set of operators which can manipulate manifold boundary based topology representations in a low level, incremental and systematic fashion, constructing a topology primarily edge by edge. They can be used with any of the previously described edge based data structures. They are, relatively speaking, low level operators since they act on topological primitive elements (vertices, edges and faces). We can also see them as high level operators because they allow us to construct a manifold adjacency topology without getting into the details of the underlying data structures. Indeed while implementation of the Euler operators is speci c to the data structure actually used, the external interface to the operators can remain the same, and the implementation of all higher level operations can be identical regardless of the data structure chosen, see Figure 14.28. 21 ee_cwe_ptr edge use ef_ptr ev_ptr two edge uses("mates") V ee_ccwe_ptr face other part Figure 14.27: Face-edge data structure. Five basic Euler operators presented below are su cient to create any topology but others are also de ned to add convenience and exibility to the surface construction process. MSFLV: make-shell-face-loop-vertex MEV : make-edge-vertex ME : make-edge GLUE : glue faces (merge two simple loop faces together) KE : kill-edge Examples of Euler operators are shown in Figure 14.29 and Figure 14.30. Figure 14.31 shows an application of Euler operators in the construction of a box. At every step, V E +F Li = 2(S G), or in this case V E + F = 2 User Level Applications Euler Operators Queries Data Structure Figure 14.28: Abstraction levels using Euler operators. 22 MSFLV New Vertex MEV e V e V new V new e ME e1 e2 V1 V2 e1 e2 V1 V2 new emefl mekl V1 V2 V1 V2 new e meksfl S1 V1 V2 S2 S1 V1 V2new e dir dir1 dir2 Figure 14.29: Euler operators (I) 23 GLUE kflevmg: kill?face?loop?edge?vertex?make?genus kflevs V1 V2 V1 V2 kefl keml V1 V2 kemsfl S1 V1 V2 S1 V1 V2 e1 e2 e1 e1 f1 f2 e2 e1 f KE e e s2 KSFLEV: delete an object from model Figure 14.30: Euler operators (II) 24 (a) msflv [V=1, E=0, F=1] (b) mev [V=2, E=1, F=1] (c) mev, mev [V=4, E=3, F=1] (d) mef [V=4, E=4, F=2} (e) mev mev mev mev [V=8, E=8, F=2] (f) mef mef mef mef [V=8, E=12, F=6] Figure 14.31: Making a box using Euler operators 14.8.1 Basic operators Constructive { MSFLV { MEV { ME me mekl meks { GLUE k evmg k evs Destructive { KSFLEV { KEV { KE ke keml 25 kems { UNGLUE m evkg m evs A brief description of these operators follows: 1. MSFLV (new-face, new-loop, new-vertex) \Make shell, face, loop, vertex" creates a new manifold surface in the topology and it is the rst operator used in any topology construction. MSFLV creates a new shell, the face \new-face", the loop \new-loop", and the vertex \new-vertex". The single vertex created, \new-vertex" can be used as a starting point for subsequent construction of additional topological features on the manifold surface. 2. MEV (vertex, edge, direction, new-edge, new-vertex) \Make edge, vertex" creates a new edge and vertex. The new edge, \new-edge", starts at the existing vertex \vertex", and ends at the new vertex \new-vertex". If the optional placement arguments \edge" and \direction" are speci ed, \new-edge" will be positioned in direction \direction" from \edge" about \vertex" as seen when looking towards the manifold surface from outside above \vertex". 3. ME (ver1, edge1, dir1, ver2, edge2, dir2, new-edge, new-face, new-loop) \Make edge" creates an edge between existing vertices ver1 and ver2. If optional place- ment is speci ed, the new edge, \new-edge", will be direction \dir1" from \edge1" about vertex \ver1" and direction \dir2" from \edge2" about vertex \ver2". me : \make edge, face, loop" occurs when the new edge will close o one portion of the face it is on from the rest of the face. In this case, the new face \new-face" and loop \new-loop" will lie to the \dir1" side of \new-edge" about \ver1". mekl: \make edge, kill loop" occurs when the new edge will not close o one portion of the face it is on from the rest of the face. In this case, the vertices \ver1" and \ver2" were on di erent loops of the same face, but afterwards will be located on the same loop. The surviving loop is the loop associated with \ver1". meks : \make edge, kill shell, face, loop" occurs when the two speci ed vertices are on di erent shells. The new edge links together the two shells into a single shell. The shell of \ver1" is the surviving shell. 4. GLUE (face1, edge1, face2, edge2) \Glue faces" merges two single loop faces (simply connected faces) together, deleting both faces and vertices, with the e ect of joining together the volumes which the two faces are bounding. Both loops must have the same number of edges and vertices, and must have no edges in common. The merge is performed so that edge1 of face1 and edge2 of face2 are merged into the same edge. The surviving set of edges and vertices are those of face1. k evmg: \Kill face, loop, edge, vertex, make genus" occurs when both faces exist on the same shell. The glue operation increases the genus of the shell by one. 26 k evs: \kill face, loop, edge, vertex, shell" occurs when the two faces exist on di erent shells. The glue operation merges the two shells together into a single shell, with the shell of face1 being the survivor. 5. KE (edge, vertex, new-loop) \Kill edge", deletes the speci ed edge \edge". ke : \kill edge, face, loop" occurs when the edge to be deleted separates two di erent faces. In this case, the edges of the two loops using the deleted edge are merged and one face and loop are deleted. The surviving face and loop are those found to the right of the edge to be deleted, when transversing the edge from the optionally speci ed vertex \vertex" to the other vertex. Any other loops of the deleted face are moved to the surviving face. keml: \kill edge, make loop" occurs when the edge to be deleted occurs twice on a loop of a single face. In this case a new loop, \new loop" will be generated on the same face. kems (edge, vertex, new-face, new-loop): \kill edge, make shell, face, and loop" deletes the speci ed edge, \edge", which is required to have the same face on both sides. The two disconnected graph components that result are treated as separate shells. ks ev (vertex): \kill shell, face, loop, edge, vertex" determines the shell of the speci ed vertex and deletes the shell and all its topological elements. kev (edge, vertex, vsurvivor): \kill edge, vertex" squeezes the ends of the speci- ed edge \edge" together, deleting the edge and a vertex \vertex" while preserving adjacencies. The topological parameter \ vertex", if speci ed, designates which ver- tex of the edge will survive. In any case, the surviving vertex is indicated by the \vsurvivor" return parameter. 6. UNGLUE (edge, face, newf1, newf2, loop, newl1, newl2) \Unglue faces" takes a single loop of edges starting with edge \edge", separates the model along the loop. The process creates two new faces \newf1" and \newf2" and their respective loops \newl1" and \newl2". The loop marked for the UNGLUE must be complete and must not cross itself. m evkg: \make face, loop, edge, vertex, kill genus" occurs when the separation induced by the operation leaves the object still connected. In this case the speci ed loop lies on a handle of the shell which has a genus of one or more. The handle is removed and the single shell with genus reduced by one in the result. m evs: \make face, loop, edge, vertex, shell" occurs when the separation induced by the operation creates disconnected shells. Each component of the result is treated as a separate shell. Thus two separate volumes are created. The e ects of the basic Euler operators on topological elements are summarized in Ta- ble 14.6. 27 Operator Change in number of topological elements Shells Faces Loops Edges Vertices Genus MSFLV +1 +1 +1 +1 MEV +1 +1 ME me +1 +1 +1 mekl -1 +1 meks -1 -1 -1 +1 GLUE k evmg -2 -2 ne nv +1 k evs -1 -2 -2 ne nv KSFLEV -1 nf nl ne nv ng KEV -1 -1 KE ke -1 -1 -1 kekl +1 -1 kems +1 +1 +1 -1 UNGLUE m evkg +2 +2 +ne +nv -1 m evs +1 +2 +2 +ne +nv Table 14.6: E ects of basic Euler operators on topological elements 14.8.2 Building high level functions on the Euler operators Euler operators provide a exible basis for higher level operators while insulating those new operators from the details and complexities of the actual data structures used. They are exible, because they are fairly low level operators which systematically manipulate the model on an edge by edge basis. They also provide automatic topological integrity checking. Almost any other kind of commonly found modeling operator or procedure can be built on top of the Euler operators, including parametric primitives and sweeps. 14.9 Non Two-Manifold B-rep Non two-manifold (NTM) representations are geometric modeling representations which allow volume, both manifold and non-manifold surface, curve and point elements in a single uniform environment. This allows topological surfaces which are not constrained to be homeomorphic to a two-dimensional topological disk at every point, such as the objects in Figure 14.32. A NTM representation therefore allows a general wire mesh with surfaces and volumes embedded in space and can be a superset of wireframe, surface and traditional manifold solid modeling forms. This section will discuss a representation of NTM topologies and introduce the Radial Edge Data Structure, a data structure developed for NTM topologies. 28 (a) FE meshing (b) Design (c) Mixed?dimension model Figure 14.32: Examples of non-two manifold models. 14.9.1 Topological elements in NTM topologies At least seven distinct element types, including six basic topological element types are involved in a NTM topology representation. A model is a single 3D topological modeling space, consisting of one or more distinct regions of space. A model is not strictly a topological element but acts as a repository for all topological elements contained in a geometric model, allowing the naming and manipulation of multiple models by a geometric modeling system. A region is a volume of space. There is always at least one in a model. Only one region in a model may have in nite extent; all others have a nite extent, and when more than one region exists in a model, all regions have a boundary. a21a22a21a22a21 a21a22a21a22a21 a21a22a21a22a21 solid region with infinite extent A shell is an oriented boundary surface of a region. A single region may have more than one shell (such as a solid object with a void contained within the solid). A shell may consist of a connected set of faces which form a closed volume or may be an open set of adjacent faces, a wire frame or a combination of these or even a single point. A face is a bounded portion of a shell. It is orientable, though not oriented, as two region boundaries (shells) may use di erent sides of the same face. Thus only the \use of a face" by a shell is oriented. A loop is a connected boundary of a single face. A face may have one or more loops. Loops normally consist of an alternating sequence of edges and vertices in a complete circuit, but many consist of only a single vertex. Loops are also orientable but not oriented as they bound a face which may be used by up to two di erent shells. Thus the \use of a loop" is oriented. An edge is a portion of a loop boundary between two vertices. Topologically an edge is a bounding curve segment which may serve as part of a loop boundary for one or more faces 29 which meet at that edge. Every edge is bounded by a vertex at each end (possibly the same one). An edge is orientable, though not oriented. The \use of an edge" is oriented. A vertex is simply a topologically unique point in space. Single vertices may also serve as boundaries of faces and as complete shell boundaries. At least four additional types of topological element adjacency \uses" associated with the face, loop, edge and vertex elements may be de ned. A face-use is one of two sides of a face. Face-uses, ie. the uses of a face by a shell, are oriented with respect to the face geometry. A loop-use is one of the uses of a loop associated with one of the two uses of a face. It is oriented with respect to the associated face use. An edge-use is an oriented bounding curve segment on a loop-use of a face-use and represents the use of an edge by that loop-use or if a wire frame edge by the point vertices. Orientation is speci ed with respect to edge geometry. There may be many uses of a single edge in a model, but there will always be an even number of edge-uses (since each use by a face produces two edge uses with one for each side). A wireframe edge produces two edge-uses, one for each end of the edge. A vertex use is a structure representing the adjacency use of a vertex by an edge as an end point, by a loop in the case of a single vertex loop or by a shell in the case of a single vertex shell. 14.9.2 Topological su ciency Thirty six topological element adjacency relationships are possible in a NTM boundary rep- resentation with respect to six basic topological elements (vertex, edge, loop, face, shell and region). There is no complete theory available yet concerning the identi cation and proof of the theoretical minimal amount of topological information required to reconstruct a NTM topology. The radial edge data structure developed for NTM topologies has been proven to be su cient and complete. 14.10 Radial edge data structure The radial edge data structure explicitly represents eleven topological element types. A hi- erarchical representation of topological elements in the radial edge structure is shown in Fig- ure 14.33. Key ideas in design of the Radial Edge data structure are: Top-down and bottom-up hierarchical relationships are represented. Face-use, loop-use, edge-use and vertex-use are utilized to represent the adjacencies of topological elements. Radial ordering of faces around common edges is represented directly (this information allows representation of a NTM condition along an edge, see Figure 14.34). Adjacency information pointing from vertex level to higher levels is represented (this information allows representation of a NTM condition at a point, see Figure 14.34 ). The radial edge data structure can be implemented in terms of a set of doubly linked lists (DLL) and supporting data structures, see Figures 14.35- 14.38. The Euler-Poincare formula is 30 shell face?use loop?use edge?use vertex?use face loop edge vertex (wireframe case) (single vertex loop case) (single vertex shel l case) model region Figure 14.33: Radial edge data structure (up-down point for boundary and ownership relation- ships; left-right pointer for de nition and attributes of an element). (a) NTM condition at a point (b) NTM condition along an edge Figure 14.34: NTM conditions. 31 no longer valid for NTM topologies. NTM topology operators similar to Euler operators have been speci ed and de ned by Weiler.A minimal su cient set of NTM operators to construct any model are: M-MR = create the model and initial region M-SV = make shell vertex (for every vertex) M-E = make edge M-F = make face K-E = kill edge. 32 (1) model attributes region listprevious modelnext model two adjacenct elements in a DLL: "next" element = next item in a DLL with respect to an item "previous" element = previous item in a DLL with respect to an item (2) region attributes next region owning model shell listprevious region face attributes (3) shell attributes next shell owning region face listprevious shell edge?use vertex?use or or (shell is wireframe) (shell is single vertex) (4) (a) face?use list (b) face?use owning shell next face?use previousface?use attributes face orientation mate face?use loop?use list (opposite side of a face) List head e1 e2 eNφ φ tail Figure 14.35: Implementation of radial edge structure. 33 loop attributes (5) (a) loop?use list (b) loop?use owning face?use next loop?use previousloop?use attributes loop mate loop?use edge?use list (loop?use on the other side of a face) orvertex?use(loop is one vertex only) edge attributes (6) (a) edge?use list (b) edge?use attributes vertex?use owning shell or loop?use mate edge?use edge cw?edge?use ccw?edge?use radial?edge?use owning?loop orientation (7) (a) vertex attribute vertex?use list (b) vertex?use attribute vertex shell next vertex?use previous vertex?use or loop?use or edge?use (wireframe edge) Figure 14.36: Implementation of radial edge structure (continued). 34 eu1 eu2mate f1 f2 eu3 eu4mate radial radial Figure 14.37: Radial edge representation of two faces joining along a common edge showing how the four edge uses of the common edge (each side of each face uses the edges) are connected. 35 fu1 fu2 face?use mate pointers edge? use mate pointers e1 e1 f1 f2f3 edge use radial pointer f3 f2 fu3 fu4 fu5 fu6 Figure 14.38: Cross-section of three faces sharing a common edge in the radial edge represen- tation 36 Bibliography [1] L. Bardis and N. M. Patrikalakis. Topological structures for generalized boundary repre- sentations. MITSG 94-22, MIT Sea Grant College Program, Cambridge, Massachusetts, September 1994. [2] B. G. Baumgart. Winged edge polyhedron representation. Technical Report STAN-CS- 320, Computer Science Department, Stanford University, 1972. [3] E. Brisson. Representing geometric structures in d dimensions: Topology and order. Discrete and Computational Geometry, 9:387{426, 1993. [4] E. L. G urs oz and F. B. Prinz. Node-based representation of non-manifold surface bound- aries in geometric modeling. In M. Wozny, J. Turner, and K. Preiss, editors, Geometric Modeling for Product Engineering. North-Holland, 1989. [5] C. M. Ho mann. Geometric and Solid Modeling: An Introduction. Morgan Kaufmann Publishers, Inc., San Mateo, California, 1989. [6] M. M antyl a. An Introduction to Solid Modeling. Computer Science Press, Rockville, Maryland, 1988. [7] M. E. Mortenson. Geometric Modeling. John Wiley and Sons, New York, 1985. [8] J. Rossignac and M. O’Connor. SGC: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In M. Wosny, J. Turner, and K. Preiss, editors, Geometric Modeling for Product Engineering, pages 145{180. North-Holland, 1989. [9] V. Shapiro. Solid modeling. Invited paper in Handbook of Computer Aided Geometric Design, Chapter 20, pages 473{518, July 2002. [10] K. Weiler. Edge-based data structures for solid modeling in curved surface environments. IEEE Computer Graphics and Applications, 5(1):21{40, January 1985. [11] K. Weiler. Topological Structures for Geometric Modeling. PhD thesis, Rensselaer Poly- technic Institute, Troy, NY, 1986. [12] P. R. Wilson. Euler formulas and geometric modeling. IEEE Computer Graphics and Applications, 5(8):45{60, August 1985. 37