ALGORITHMIC APSECTS OF ALTERNATING SUM OF VOLUMES, PART I. DATA STRUCTURE AND DIFFERENCE OPERATION Kai Tang Tony Woo Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 90-29 October 1990

ALGORITHMIC ASPECTS OF ALTERNATING SUM OF VOLUMES Part I. Data Structure and Difference Operation Kai Tang Tony Woo University of Michigan * Send corespondence to: Tony Woo Dept. of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 U.S.A. Accepted by Journal of Computer Aided Design, to appear in April 1991.

1 Abstract From the point of view of basic theorey, a unique conversion from a boundary representation to a CSG representation is of importance. From the point of view of application, the extraction of features by convex decomposition is of interest. The Alternating Sum of Volumes (ASV) is a technique that offers both. However, some algorithmic issues are still unresolved. This paper is the first of a two-part paper that addresses specialized set operations and the convergence of the ASV process. In this part, a fast difference operation for the ASV process and a data structure for pseudo polyhedra are introduced. A fast difference operation between an object and its convex hull is enabled by the crucial observation that it only takes linear time to distinguish them. However, it takes O(NlogN) time to construct a data structure with the proper tags. The data structure supporting the operation is a pseudo polyhedron, capturing the special relation between an object and its convex hull. That the data structure is linear in space is also shown.

2 1. INTRODUCTION The idea of the Alternating Sum of Volumes (ASV) is to represent an object by a series of convex components with alternating signs (for volume addition and subtraction). It is a technique to extract "features" from the boundary representation of a three-dimensional component [12]. As an example, consider the object in Figure 1. It shows a block with a slot and a hole. The ASV series of this object is Ho - H1 + H2 - H3 where the Hi's are convex. fa Ho Ho H1 H2 H3 Figure 1. Alternating Sum of Volumes Formally, the ASV series of an object fl is defined as Qo = (-l)iH where Qo = f Hi is the convex hull of li, CH(Qi) Qi is the deficiency and is defined as the regularized set difference between Hi-i and gi-1.

3 Figure 2 shows how the terms in an ASV are derived for the object in Figure 1. The deficiency Ri is obtained by subtracting Qi1l from Hi-, i=1,2,.... As Qi+ becomes the null set 0, the Hi's are collected starting with Ho. The ASV expression is formed by alternating "-" and "+" signs as in Ho-HI+H2 -.... ff0 CH r 2Q CH —,./ Fa Ho = CH(ao) Hi = CH(Ri) V /ICH o H2 = CH(Q2) CH _ 13 = CH(Q3) 0 CH: convex hull operation -: difference operation 0: null set Figure 2. Derivation of ASV series Consider the machining process of the mechanical component in the previous example. There are two features: a slot and a hole. They can be extracted by algebraic manipulation of its

4 ASV as illustrated in Figure 3. Parenthesizing H1 and H2 forces a change in the sign from + to -. Subtracting H2 from H1 yields a new H1' for a disjunctive expression: Ho - (H1 - H2) - H3 = Ho' - H1' - H2 If Ho' is the stock, H1' and H2' can be thought of as volumes to be removed to create the slot and the hole. H1 +- 3 H2 D-I H __-( HO Hi H2 0 T-. Ho' H,' 2 H2' Figure 3. Algebraic Manipulation of ASV Series into Disjunctive Form As another illustration of the material joining process, consider Figure 4. The components adjacent to the - sign are parenthesized yielding a conjunctive expression: Ho- HI + H2 = (Ho - H1 ) +H2 = Ho' + H'. Here, Ho' is the base plate on which a protrusion H1' is to be joined. These two examples illustrate that through the manipulation of an ASV series, features of a given object can be

5 extracteded automatically, which in turn can help the process planners in deciding the suitable manufacturing operations such as machining or welding. The ability to "disassemble" allows conversion from boundary based solid modeling systems to those that are CSG-based [8]. H1 + H2 Ho Hi 5 + H2 =.+5 Ho' H1' Figure 4. Algebraic Manipulation of ASV Series into Conjunctive Form As implied in the examples, the terminating condition of an ASV series expansion is when the deficiency Qn becomes convex, that is, when H. identifies with f4. This condition, however, is not guaranteed. Figure 5 illustrates an example of an infinite ASV series. It has been shown [12] that an ASV series is non-terminating if and only if there is an integer i such that Hl = Hi. In such a case, the deficiency i is said to be non-convergent. When a non-convergent deficiency Qi is encountered, the ASV expansion can not continue.

6 lZi =i+l1 Q2i+2 TI / TI / Hi Hi+1 cycles Figure 5. An example of ASV non-convergence When a deficiency CQ becomes non-convergent, one solution is to divide it into convex subsets [12]. But there is a drawback. It is known [4] that there can be O(n3) convex subsets, where n is the number of concave edges, each subset requires further polynomial time to determine. An alternative is to decompose it into subsets which are themselves convergent so that the ASV series can expand further. For example, the object Q in Figure 6 is non-convergent. By separating it along the edge "e" into two parts P1 and P2, and performing the ASV expansion on each of them, a finite ASV series of two branches, each of which is a finite ASV series, results. The observation that the type of edges such as "e" in Figure 6 may be a very small subset of the set of all concave edges encourages inquiry.

7 Pi e P2 Figure 6. Remedy for non-convergence This is the first of a two-part paper. Part I deals with a special difference operation. While general difference operation [10] may be invoked, the relation between an object and its convex hull merits investigation. This relation is made concrete by the notion of a pseudo manifold, as illustrated by n in Figure 6. It is an entity that is between a two-manifold [2] and a non-manifold [11]. With the aid of a data structure for pseudo manifolds, an O(nlogn) time algorithm for computing a convex deficiency is made possible, where n is the number of faces of the pseudo manifold. The data structure is shown to be O(n) in space which gives an absolute upper bound to the number of edges of the type "e" in Figure 6. The characterization of non-convergence and its remedy as illustrated by Figure 6 is given in the sequel, Part II of the paper.

8 2. DOMAIN AND DATA STRUCTURE In this section the domain of objects and a data structure to represent them are given. An object Q is a set of points in three-dimensional Euclidean space E3. It must satisfy certain restrictions. Because ASV performs operations on the boundary of volumes, each object must be a closed surface that forms the closure of an open set of finite extent in E3. In other words, an object must be the surface of a volume and must not have "dangling" faces and edges [8]. In addition to this restriction of homogenous three-dimensionality, the objects must also be closed under the (regularized) difference operation, i.e., they should have differential preservability [8]. To define a domain of objects that will meet both the restrictions, some definitions regarding the interior and boundary points of a three-dimensional point set need to be clearified. Definition 1. A point p of a set S in E3 is called an interior point of S if there exists an open three-dimensional neighborhood that consists of points in S only. A point p is called a boundary point of S if it is not an interior point. The set B(S) of all boundary points of S and the set I(S) of all the interior points of S are defined as the boundary and the interior of S respectively. The relation between a boundary point and its neighboring points of a set S in E3 is described by three characterizations, namely, manifold, pseudo manifold, and non-manifold. A point p in B(S) is called a two-manifold point if it has a three-dimensional neighborhood such that the subset of the points of S contained in that neighborhood is topologically equivalent to a hemisphere [11]. A point p is a pseudo manifold point if every three-dimensional neighborhood of it contains some points in I(S). If a point p has a three-dimensional neighborhood such that the subset of the points of S contained in that neighborhood entirely belong to B(S), then it is called a non-manifold point. As an example, the boundary surface of the object in Figure 7 consists of the six faces of the cube and that dangling face ". All the boundary points except "fT (including edge "e") are two-manifold points. The boundary points on the six faces of the cube, including edge "e", are pseudo manifold points. The non-manifold points are those on face "f" but not on edge "e".

9 Figure 7. Points characterizing a Manifold, a Pseudo-manifold, and a Non-manifold Definition 2. A point set S in E3 is a two-manifold if I(S) is connected and every point in B(S) is a two-manifold point. S is a pseudo manifold if every point in B(S) is a pseudo manifold point. S becomes a non-manifold if B(S) contains some non-manifold points. A pseudo manifold point is a relaxation of two-manifold, i.e., it only requires that every neighborhood of the point contains some interior points of the set, but with no topological constraint on the neighborhoods. A pseudo manifold need not be a connected set either. The relation of these three sets can be best described by Figure 8. Because an object must have homogenous three-dimensionality, non-manifolds are immediately excluded from the consideration. Although two-manifolds satisfy the homogenous three-dimensionality, they are not closed under regularized difference operation [8]. The generality of pseudo manifolds, while still conforming to homogenous three dimensionality but also guarantees differential preservability [8], prove to be the only suitable clan of objects suitable for ASV representations. Figure 9 illustrates several examples of two-manifolds, pseudo manifolds and non- manifolds. Figure 8. Set relation between Two-manifolds, Pseudo manifolds and Non-manifolds

10 (a) Two-manifolds (b) Pseudo manifolds (c) Non-manifolds Figure 9. Illustration of Two-manifolds, Pseudo manifolds and Non-manifolds A data structure for the pseudo manifolds is crucial to both the development and analysis of algorithms. A data structure for polyhedra [13] is not suitable because a pseudo manifold could have more than two faces meeting at an edge (see Figure 9b). The representation of general non-manifolds [11] are more than what is needed here, because of the difference preservability of pseudo manifolds. The concept of pseudo polyhedra is proposed. A pseudo polyhedron is "almost" a polyhedron except that it allows edges to have more than two adjacent faces. Definition 3. A pseudo polyhedron P is a finite collection of planar faces such that (a) every edge of P has at least two adjacent faces, and (b) if any two faces meet they meet at a common edge. Specifically, a pseudo polyhedron with nv vertices, ne edges and nf faces is a quintuple < V, E, F, NORM, Ef > which is defined as:

11 (a) V = (v.1, v2,., nv,) is a list storing the n, vertices; each vi is a coordinate triple (xi, Yi, i ). (b) E = { <Vl,lVl,2>, <V2,,v2,2>,, *<V,ne,l,Vne,2> ) is the edge list. Each entry <vil,vi,2> stands for an edge with vi1, and vi,2 being indices of the two end points; e.g., <vi,,Vi,2> =<3,10> means the end points of the ith edge are v3 and v10. (c) F = {F1, F2,..., Fnf} stores face information. Each element Fi is itself an array of the form {<el,1, el2,..., el.fl>, <e2., e22,,..., e2,f2>, *., <ek,1 ek2,..., ekfk> }, where k is the total number of polygons in face Fi. Each <ej.,, ej2,..., e.fj> is a simple polygon, and each ejl is the index of an edge in E. For example, by Fi = ( <2,4,1>, <5,7,6,3>), we mean face Fi is bounded by two simple polygons; the indices of the edges of the outer polygon are 2,4,1 and are 5,7,6,3 for the inner polygon. The edges are ordered clockwise (for outer) or counter-clockwise (for inner). (d) NORM = { N1, N2,..., Nnf ) stores the outward normals of the nf faces. (e) Ef = { <f1,, f1,2,.-, fl,kl>, <f2,1, f2,2, * — f2,k2>.. <fne,.l fne,2, —, fne,kne> ) is a list which describes the edge-face adjacency relation. An entry <fil,fi.2sfiki> says that edge Ei has ki adjacent faces and the indices for them are fi,1, fi.2,..., fi,ki. For example, if <fi,,fi2,...fi ki> is <1,7,6,2>, then edge Eihas four adjacent faces and their indices in F are 1,7,6 and 2. Each ki is defined as the face adjacency index of edge Ei. The data structure given above, although quite simple, completely describes one family of pseudo manifolds: planar pseudo manifolds. (Pseudo manifolds with non-planar boundary surfaces are not considered in this paper.) In the Appendix a detailed proof that the space requirement of a pseudo polyhedron is linear in the number of its faces is given. It should be noted that though a pseudo polyhedron completely describes the boundary of a pseudo manifold, it itself carries no set theoretic information. It is the pseudo manifold, which a pseudo polyhedron represents, possesses the set in E3.

12 3. DIFFERENCE OPERATION To study the difference operation between a pseudo manifold and its convex hull, the following notations are used: Q denotes a pseudo manifold object, Qh for its convex hull, and Qd for the deficiency Qh - Q. The same notations are used to represent their defining pseudo polyhedra unless noted otherwise. Consider the convex hull Qh of an object Q. The set Qh can be divided into four disjoint subsets. They are, Si: {I(20)}, the interior points of Q, th: {B(Oh)), the boundary (hull) points of Qh Up: (B(Q)nI(Qh), the boundary points of Q excluding those which are also in Ih, d: {I(Qh) - Q}, interior (deficiency) points of Qh excluding Q. Figure 10 illustrates these subsets in two dimensions. Qa~~~ n^~~h Figure 10. Illustrations of i, Sh, p and 5d Definition 4. A point pe D~ is a preserved point if for any real number e>0, no matter how small it is, the open neighborhood sphere which centers at p with radius e always

13 has a point in d. A point p is a lost point if it is not a preserved point. The difference operation between fh and Q is defined as follows. Definition 5. The deficiency ld of an object Q is a set in E3 consisting of all the preserved points of fh. The definition of deficiency here agrees with the intuition. The purpose of categorizing the points of 9h is to relate the interior and the boundary of the deficiency ld with that of Q and its convex hull f2h* It is easy to see that because both I(Q) and I(f2h) are open sets, so must be the sets i and E. By definition of the deficiency, all the points of i are lost. Since Ed is an open set, every point in it has a neighborhood sphere of points in td only and thus is interior to Qd. This means Sd must be a subset of the interior of deficiency Qd. For any point in r every neighborhood of it contains some points either in i or in {E3 - Qh), that is, it contains points not belonging to fd, and hence by the definition they can not be the interior of Qd. These observations are summarized in the following lemma. Lemma 1. The deficiency Qd of a pseudo manifold Q is also a pseudo manifold, whose interior set I(Qd) is the d-set of Qh and the boundary set B(fd) is a subset of {Rh As noted by 1, the boundary surface B() of the deficiency is a subset of { h u ] of Qh. Because of the planarity of the faces, B(fd) must be a set of some faces of Q and Qh. The key to the algorithm for finding the deficiency is to find these faces as well as the adjacency relation among them so that the result is a pseudo polyhedron representation of Qd

14 Definition 6. A face of a pseudo manifold Q is a hull face if it is in h; otherwise it is called an internal face. Lemma 2. A hull face f of Q will not exist in the boundary surface B(Qd). Proof. For any point in the interior set I(f) of f, say p, there must exist an open neighborhood e of p that belong to I(f) and hence in 4h only. Since Q is a pseudo manifold, every point in e, including p itself, must have a neighborhood sphere that consists of points in ( 4h U hi u (E3 - Qh)} only. By the way a preserved point is defined, p can only be a lost point. Therefore the entire set I(f) are lost points. Q.E.D. Lemma 2 asserts that the boundary surface B(fd) consists of only the internal faces of Q and the faces of Qh but not the hull faces of Q. This observation leads to the development of the difference algorithm sought. It accepts as input (VEFEf, NORMf) which is the pseudo polyhedron representation of a pseudo manifold Q and outputs the pseudo polyhedron representation of the deficiency Qd- Suppose there is a procedure HULLP which takes as input the pseudo polyhedron (V,E,F,Ef,NORMf) of a pseudo manifold Q. Its output are two: one is the pseudo polyhedron of the resultant convex hull Qh, and the other is two arrays FH and EH, called hull tag arrays which distinguish those faces and edges of Qh that do not belong to Q. Specifically, FH(i)=l means face i of Qh is a face of Q. When FH(i)=O, the meaning is reversed. EH(i)=j means edge i of Qh is edge j of Q, whereas EH(i)=O means edge i is not an edge of Q. Since most available three-dimensional convex hull algorithms[6,7] support data structures that embody our pseudo polyhedra, the feasibility of the output of HULLP is justified. For the convenience of computation it is also assumed that the vertex array V is unchanged through HULLP, although redundant vertices in the V array of Sh are implied. Also, there are two additional arrays, FI and E. They are the Internality tag arrays which identify internal faces and internal edges of U2. Specifically, FI(i)=l means face i of Q is an internal face and, similarly, EI(i)=l means edge i of Q is an internal edge. Likewise, when FI(i) or EI(i) is 0, the meaning is reversed. These two arrays are O(nlogn) derivable

15 from Q because the internality of any face f (or edge e) can be identified by checking the internality of an arbitrary point of I(f) (or I(e) ). Figure 11 demonstrates the functionality of procedure HULLP on a pseudo polyhedron. e2 e3 e e4 FH: EH: FI: EI: FH (f) = 0; all the other FH's are 1. All the EH'S are non-zero. FI (fl) = FI (f2) = FI (f3) = FI (f4) = 1; all the other FI's are 0. EI (el) = EI (e2) = EI (e3) = EI (e4) = 1; all the other EI's are 0. Figure 11. Functionality of procedure HULLP The first algorithm MERGE to be given below adds those edges and faces of 2h that do not belong to Q to the description arrays E and F of r and updates Ef correspondingly. A constant time function named INSERT _E (Ef, ij) is used. It either sets Ef(i) to "j" if Ef(i) is not previously defined, or appends "j" to Ef(i). Procedure MERGE (nv, n,, nf, V,E,F,Ef,NORMf, FI, EI, n'v, n'e, n'f, V',E',F,E'f,NORM'f, FH,EH) /*purpose: Updates the pseudo polyhedron representation of a pseudo manifold Q by adding the newly generated hull faces and hull edges of its convex hull to it. input: (nv, ne, nf, V,E,F,Ef,NORMf, FI, EI) —----— pseudo polyhedron Q, FI and EI

16 are the internality tag arrays of its faces and edges. (nv, ne, n'f, V',E',F',E'f,NORM'f, FH,EH) —pseudo polyhedron representation of the convex hull fh of Q2, FH and EH are the hull tag arrays of its faces and edges. output: (nv, ne, ff, V,EF,Ef,NORMf, FI, Ei) —-— updated pseudo polyhedron of Q with the newly generated hull faces and hull edges of O2h added, FI and EI are updated with the following convention: FI(i) =0 face i is a hull face of O = 1 face i is an internal face =2 face i is a face of fh but not a face of Q Ei(i) = edge i is a hull edge of Q = 1 edge i is an internal edge =2 edge i is an edge of Lh but not an edge of n. */ begin step 1. ETOP = ne FTOP = nf for i=l, n'e do EMAP(i) =0 end do (step 1} step 2. for i=l, n'f do if FH(i) =0 then step 3. FTOP < — FTOP + 1 step 4. (e,e2,..,e ) < — F(i) step 5. forj=l, l do if EH(ej) = O then if EMAP(ej)=O then step 6. ETOP < — ETOP + 1 step 7. EMAP (ej) < — ETOP step 8. E(ETOP) < — E'(ej) step 9. EI(ETOP) < — 2 end if

17 else step 6'. EMAP(ej) < — EH(ej) end if step 10. call INSERT_Ef (Ef, EMAP(ej), FTOP) end do {step 5 step 11. F(FTOP) < — (1, (EMAP(e1),EMAP(e2),..,EMAP(e1))) step 12. NORMf (FTOP) < — NORM'f(i) step 13. FI(FTOP) < — 2 end if end do (step 2} step 14. nf= FTOP ne = ETOP end {MERGE} Comments on MERGE: Step 1 initializes two stack pointers FTOP and ETOP which stand for the numbers of current faces and edges in Q, respectively. Array EMAP is the index mapping between E' and E, e.g., EMAP(i) = j means edge i of Qh is edge j of (current) Q. Steps 3 through 13 are performed once for each face of Qh that is not a face of Q (FH = 0). For each edge of a selected face, whether it is also an edge of Q is first checked. If it is not (when its EH = 0) and it has not been previously added to Q, it is then added to E with its EI set to 2 and its EMAP set to a unique number ETOP (see steps 6 through 9). Otherwise its EMAP is assigned with its EH which is the index of this edge in the original Q (step 6'). At step 10 the face adjacency relation of this edge in Q is updated as reflected by the insertion of this selected face. Steps 11 and 12 append the selected face and its normal to F and NORMf of Q. (Note that, because ZQ is convex, every face of it has only one bounding polygon.) Step 13 assigns 2 to the FI of this face that indicates the added face is not a face of the original Q. To analyze the time requirement of MERGE, notice that each edge of Qh has exactly two adjacent faces in Qh. At most twice will an edge of h be checked, retrieved and stored. Steps 12 and 13 take constant time. As the result, the loop from step 2 through step 13 are O(n'e + n'f).

18 The output of MERGE, let it be called the PS description of n and denoted as tps, is a pseudo polyhedron. Figure 12 lists the V,E,F,Ef entries of the PS description of a pseudo manifold. fps itself, however, no longer represents a legitimate pseudo manifold, as it contains all the intermediate data for obtaining the deficiency f2d. For the pseudo manifold f in Figure 12, the boundary of its deficiency id consists of the faces f4, f5, f6, f7, f8, fg,f10 as defined in the F entry of UPS; the vertices of nd are v2, v3, v4, v5, V6, V7, V8 of Qps; and the edges of ~2d are e4, e5, e6, e7, e8, e9, elo, ell, el2, e13, el4, e15 of fps. The procedure DIFFBUILD given next will generate Qfd utilizing fps. A constant time routine called INSERT(L,i) will be used in the algorithm which appends an integer i into an integer list L. V3 MERGE Vv vi Ups V = {V1, V2, V3, V4, V5, V6, V7, V8} E = (<V1,V2>, <V1,V3>, <V1,V4>, <V5,v6>, <v5,V7>, <V5,V8>, <V5,V2>, <V5,V3>, <V5,V4>, <V2,V3>, <V3,V4>, <V4,V2>, <V6,V7>, <V7,v8>, <V8,V6> } F = {<1,10,3>,<1,2,11>,<3,12,2>,<10,11,12>,<13,4,6>,<5,4,14>,<6,5,15>, <10,7,9>,<8,7,1 1>,<9,8,12>} Ef = (<1,2>,<2,3>,<3,1>,<5,6>,<6,7>,<7,5>,<8,910,8,<1,4>, <2,4>,<3,4>) Figure 12. An example of the PS description lfps

19 Procedure DIFFBUILD (n,, ne, nf, V, E, F, Ef, NORMf, FI, EI, ndv, nde, ndf, Vd, Ed, Fd, Edf, NORMdf ) /* purpose: Finds the deficiency nd of a pseudo manifold Q and outputs the pseudo polyhedron representation of fd to the external. input: (nv, ne, nf, V,E,F,Ef,NORMf, FI, EI ) ---— The P description of 2. output: (ndv, nde, ndf, Vd, Ed, Fd, Edf, NORMdf) —----— The pseudo polyhedron representation of deficiency fd. */ begin step 1. ndf < — 0 nde < — 0 ndv < — 0 step 2. for i=l, nf, do if FI(i)*l then step 3.1 ndf < — ndf + step 3.2 Fd(ndf) < — F(i) step 3.3 FMAP(i) < — ndf if Fi(i) = 0 then step 3.4 NORMd( ndf ) < — NEG(NORM(i)) else step 3.4' NORMdf( ndf) < — NORM(i) end if end if end do (step 2) step 4. for i = 1, nv, do VMAP(i) < — 0 end do {step 4} step 5. for i=l, nn, do step 5.1 <fl,f2,...fk> < — Ef(i)

20 step 5.2 NewEfi < — nil step 5.3 for j=l, k, do if Fi(fj) 1 then step 5.4 call INSERT(NewEfi, FMAP(fj)) end if continue (step 5.3} if NewEfi * nil then step 5.5 nde < — nde + 1 step 5.6 Edf( nde) < — NewEfi step 5.7 EMAP(i) < — nd step 5.8 <Vl,V2> < — E(i) if VMAP(v1) = 0 then step 5.9 ndv < — ndv + Vd (ndv) < — V(vl) VMAP (v1) < — nd end if if VMAP(v2) =0 then step 5.10 ndv < — ndv +1 Vd (ndv) < — V(v2) VMAP (v2) < — nd end if step 5.11 Ed (nd) < —(VMAP(v1), VMAP(v2)) end if end do (step 5) step 6 for i=l, ndf, do <el,e2,...,ek> < — Fd(i) Fd(i) < — <EMAP(el),EMAP(e2),...,EMAP(ek)> end do (step 6} end (DIFFBUILD)

21 Comments on DIFFBUILD: Variables ndf, nde and ndV are the numbers of faces, edges and vertices of Qd that have been found. Three arrays FMAP, EMAP and VMAP are the mappings from the preserved faces, edges and vertices of p to those of Qde For example, FMAP(5)=2 means faces 5 of Qp is face 2 of f2d. At step 1 the total number of faces, edges and vertices in Qd is 0. The loop at step 2 generates the NORMf set NORMdf of d: if a face is an internal face of Q, it is preserved on Ad and its normal should be negated (step 3.4). Otherwise it is also preserved but its normal should be the same as the original (step 3.4'). Step 3.2 retrieves the current preserved face of Qp into the Fd set of Qd while step 3.3 establishes the index mapping FMAP between them. The edge indices of the faces in Fd are still the originals from E and they will be mapped to Ed once EMAP are established. The mapping VMAP is initialized at step 4. The entire loop of step 5 generates the V, E and Ef arrays of fd, Vd, Ed and Edf, as well as establishing the mappings VMAP and EMAP. Step 5.1 retrieves all the faces of Qp that are adjacent at an edge of Qp. By checking their F1, those unpreserved faces (step 5.3 to step 5.4) are filtered out. If the remainder is not empty, this edge as well as its end points must be preserved on Qd. This is done by the following: step 5.6 insert the (Qd) face adjacency relation of the edge into the Ef array Edf of Sid; step 5.7 assigns the mapping EMAP of the edge. Steps 5.9 and 5.10 establish the mapping VMAP of the two end points of the edge and store their coordinates from V of Qp into the V array Vd of fd. At step 5.11 this edge with its new end point indices of Vd is stored into E array Ed of Qd. Finally at step 6, the edge indices in Fd are replaced with their mappings in Ed. Theorem 1. The deficiency fd of a pseudo manifold I can be obtained in O(NlogN+K) time where N is maxtn., nf, n,) of f, and K is the sum of the face adjacency indices of f. Proof. Since the p of Q is O(NlogN) derivable from n (see the comments on procedure MERGE), it is only necessary to analyze the procedure DIFFBUILD. The overall time from step 1 through step 4 is O(N). The total time for the loop at step 5 plus the inner loop at step 5.3 is O(K). Analogously, the loop at step 6 is O(K) as well. Q.E.D. The occurrence of K can be somewhat unpleasant because of its seemingly

22 non-deterministic relation with N. Fortunately, K is shown to be O(nf) where nf is the total number of the faces of the pseudo manifold. (Refer to the Appendix.) Therefore, the deficiency of a pseudo manifold can be obtained in O(NlogN) time.

23 Appendix. Space Linearity of a Pseudo Polyhedron In this appendix, the space required by a pseudo polyhedron is shown to be linear in the number of its faces. Refering to Definition 3, let P=<V,E,F,NORM,Ef > be a pseudo polyhedron with nV vertices, ne edges and nf faces. The numbers n, and ne are shown to be both O(nf) (for the items V and E). In addition, the sum of the face adjacency indices of all the edges are shown to be linear in nf (for F and Ef). The face adjacency index of an edge is the number of the faces that meet at that edge. First, several definitions are introduced. Well-Adjacency of edges: An edge of a pseudo polyhedron is called a well-adjacent edge if its face adjacency index is 2; otherwise it is an ill-adjacent edge. Well-Orientation of vertices: A vertex v of a pseudo polyhedron is said to be well-oriented if the faces that are incident at v bear an order fl, f2,....,fk such that fl is adjacent to f2, f2 is adjacent to f3,..., fk is adjacent to fk, and fk is adjacent to f; otherwise v is an ill-oriented vertex. V (a) All the edges except e are well-adjacent (b) All the vertices except v are well-oriented Figure A-1. Well-Adjacency and Well-Orientation Figure A- illustrates an example of well-adjacency and well-orientation. Based on these two characterizations of edges and vertices, two operations are defined next on those ill-oriented vertices and ill-adjacent edges.

24 Vertex Homogenization: A Vertex Homogenizing Operation (VHO) on an ill-oriented vertex v is a replacement by a set of new vertices (v1, v2,..., Vm) such that all the vi's are welloriented and they have the same coordinates as v. Edge Homogenization: An Edge Homogenizing Operation (EHO) on an ill-adjacent edge e is a replacement by a set of new edges (el, e2,..., em) such that all the ei's are well-adjacent and they have the same coordinates as e. Figure A-2 and A-3 demonstrate VHO and EHO operations respectively. v vl VHO on v Vertices vl and v2 have the same coordinates as v. Figure A-2. Illustration of a Vertex Homogenizing Operation EHO on e e2 e e Edges el,e2, and e3 have the same coordinates as e. Figure A-3. Illustration of Edge Homogenizing Operation

25 By utilizing these two micro operations VHO and EHO, an operation on a pseudo polyhedron is defined below. Polyhedron Homogenization: A Polyhedron Homogenizing Operation (PHO) on a pseudo polyhedron P is a series of VHO's and EHO's such that the resultant pseudo polyhedron P' has well-oriented vertices and well-adjacent edges only. See Figure A-4 for an example. vt Figure A-4. Illustration of a Polyhedron Homogenizing Operation

26 Lemma A. The resultant pseudo polyhedron P' of a PHO on a pseudo polyhedron P is either a single polyhedron or a set of polyhedra. Proof. Note that a polyhedron is a special case of pseudo polyhedra such that (a) all the faces of it are connected, and (b) all its vertices are well-oriented and all its edges are well-adjacent. By definition, PHO bears property (b) but not always (a). Q.E.D. The following theorem is induced by Lemma A. Theorem A. Let P(nv, ne, nf) be a pseudo polyhedron, with nv vertices, ne edges, and nf faces. Then the following three claims are true: (a) nv is O(nf), (b) Ne is O(nf), and (c) K=f1ck is O(nf); where ki is the face adjacency index of edge ei (i=1,2,...,Ne). Proof. Let P1,P2,...,Pm be the polyhedra of P'(nv',ne',nf) which is the resultant pseudo polyhedron of PHO on P. each of them has Vi vertices, Ei edges and Fi faces (i=l,...,m). By Euler formula [2], Vi < 2Fi - 4 and Ei < 3Fi- 6 (i=l,...,m). Summing both sides of the inequality yields nv'=Vl+V2+...+Vm < 2(F1+F2+...+Fm) - 4m = 2nf - 4m, and ne'=E1+E2+...+Em < 3(Fi+F2+...+Fm) - 6m=3nf - 6m. Since n_ < n_' and n_ < ne', n, ~ 2nf - 4m and n, ~ 3nf - 6m. To prove (c), let L be the total number of ill-adjacent edges of P. Each EHO operation replaces an ill-adjacent edge of P with a number of well-adjacent edges. For an ill-adjacent edge ei, exactly (ki / 2) -1 new edges will be generated. This implies, however, that the sum K' = I over all the L ill-adjacent edges of P is 2(ne - n.) + 2L. The sum K" =.ki over the rest ne - L well-adjacent edges of P is certaintly 2(ne-L). Therefore, K=K'+ K" = 2ne' ~ 6nf - 12m. Q.E.D.

27 References [1] A. Baer, C. Eastman, and M. Henrion, "Geometric Modeling: A Survey" Computer -Aided Design, Vol. 11, No. 5, Sept. 1979, pp. 253-272. [2] C. Bollobas, Graph Theore, Springer-Verlag, 1979 [3] A. Cary, "BUILD USERS' GUIDE", University of Cambridge, C.A.D. Group Document,No. 102, Nov. 1979. [4] B.M. Chazelle, "Convex Decomposition of Polyhedra", ACM Symposium on Theory of Computing, Milwaukee 1981, pp. 70-79. [5] H. Chiyokura, F. Kimura, "A Method of Representing the Solid Design Process", IEEE Computer Graphics and Application, April 1985, Vol. 5, No.4, pp. 32-41. [6] F.P. Preparata and M. L. Shamos, Computational Geometry, Springer-Verlag, 1985 [7] F.P. Preparata and S.J. Hong, "Convex Hull of Finite Sets of Points in Two and Three Dimensions", Comm. ACM 2(20), Feb. 1977, pp. 87-93. [8] A.A.G. Requicha, "Representation for Rigid Solids: Theory, Methods and Systems", ACM Computing Surveys, Vol. 12, No 4, Dec. 1980, pp. 437-464. [9] A.A.G. Requicha, H.B. Voelcker, "Solid Modeling: Current Status and Research Directions", IEEE Computer Graphics and Application, Oct. 1983, Vol. 3, No.7, pp. 25-37. [10] A.A.G. Requicha, H.B. Voelcher, "Constructive Solid Geometry", University of Rochester, Production Automation Project, TM-25, Nov. 1977. [11] K. Weiler, "Topologocal Structures for Geometric Modeling", Ph.D dissertation, Rensselaer Polytechnic Institute, Aug. 1986.

UNIVERSITY OF MICHIGAN 3 901504732 7104 [12] T.C. Woo, "Feature Extraction by Volume Decomposition", Proc. Conf. On CAD/CAM Technology in Mechanical Engineering, Cambridge, Mass. 1982 [13] T.C. Woo, "A Combinatorial Analysis of Boundary Data Structure Schemata", IEEE CG&A, Vol. 5, No. 3, March 1985, pp. 19-27.