RSD-TR-21-87 A NEW CSG TREE RECONSTRUCTION ALGORITHM FOR FEATURE UNIFICATION Yung-Chia Lee Kuen-Fang Jack Jea October 1987 CENTER FOR RESEARCH ON INTEGRATED MANUFACTURING Robot Systems Division COLLEGE OF ENGINEERING THE UNIVERSITY OF MICHIGAN ANN ARBOR, MICHIGAN 48109-1109

ABSTRACT By feature unification we mean the transformation of a specific feature into a desirable and isolated representation. Due to the global nature and non-uniqueness properties of the Constructive Solid Geometry (CSG) scheme, a feature on an object may be represented by different sets of primitives, which may yet scatter around the CSG tree. A tree reconstruction algorithm which groups these primitives as close as possible is therefore needed before the feature can be unified into a desirable format suitable for applications (such as process planning). Lee and Fu earlier proposed such a tree reconstruction algorithm which works well in most cases, but fails to move primitives in some difficult situations. In this paper, we investigate thoroughly the formal properties of moving nodes in CSG trees, and propose a new tree reconstruction algorithm based on a well-defined single-step move-up operation. This new table-driven algorithm is more powerful because the cases failed by the previous algorithm are either overcome or elaborated. It is also simple to understand, easy to implement, and very efficient. 1

Contents 1 Introduction 1 2 Problem and Proposed Approach 3 3 One-level Move Up 5 3.1 Basic Terms.................................... 5 3.2 Node Move-up............................. 7 4 New Algorithm for Feature Unification 12 4.1 Output Table and Next State Table........................ 12 4.2 State Minimization of Tables........................... 14 4.3 The New Algorithm................................ 16 5 Comparison to the Existing Algorithm 20 6 Conclusion and Discussion 22 6.1 Conclusion............................. 22 6.2 Discussion..................................... 23 ii

RSD-TR-21-87 1 Introduction In the areas of computer-aided design and manufacturing (CAD/CAM), the Constructive Solid Geometry (CSG) scheme is one of the most widely used solid modeling schemes for representing 3-D objects. It represents an object as a Boolean combination or construction of solid primitives (e.g., cylinders, cubes, cones, spheres, and tori) via the regularized set operators unions, differences, and intersections. The resulting representation of an object is a tree (called CSG tree) with the solid primitives as terminal nodes and the regularized set operators as non-terminal nodes. The CSG scheme has many advantages [2,12,17]: it is informationally complete (i.e., unambiguous) and concise; it has a wide range of geometric coverage; objects are easy to construct and their validity is automatically ensured by the syntax; application algorithms based on the tree structure of CSG are easy to program, relatively numerically stable, inherently parallel, and efficient for some operations. Therefore, many contemporary solid modeling systems use the CSG scheme; for example, PADL-1 [15], PADL-2 [4], GMSOLID [3], TIPS [11], GDP [16], SYNTHAVISION [6], UNISOLIDS, Applicon SOLIDS MODELING II, Catronix CATSOFT, Control Data ICEM SOLID MODELER, Sperry SOLID MODELER, etc. While the CSG scheme has many advantages, it has two problems with feature applications such as feature recognition and extraction [10,18]. First, its global nature may scatter the solid primitives of a feature throughout a CSG tree. Extracting a feature must go through the whole CSG tree to find these primitives and check their relationships. Second, its non-uniqlueness nature may result in multiple CSG representations for an object, that is, a physical object can be represented by many different CSG trees of different structures and primitives. The task of defining feature models for matching is thus very difficult, if not impossible. The problems resulting from both the global and non-uniqueness natures of the CSG scheme can, however, be alleviated if there exist some reliable tree reconstruction algorithms which can move the solid primitives around in a CSG tree and/or replace a CSG subtree by another equivalent one. The CSG trees after reconstruction must of course represent the same objects and, hopefully, are more suitable for the underlying applications. The tree reconstruction technique has been employed by researchers in different applications. CSG Tree 1

RSD-TR-21-87 Kakazu and Okino [9], in their Group Technology Code generation, first convert an arbitrary CSG tree into a canonical form (i.e., the union of all real existence primitives difference the union of all removal primitives) and are then able to apply a pattern recognition procedure to obtain the GT code. Goldfeather et al. [7] also use a tree reconstruction algorithm to transform a CSG tree into a normal form (i.e., a union of simpler subtrees) which can then be traversed to generate quadratic coefficients and operation codes for fast displaying the object by their Pixel-Powers Graphics System. In a similar work, Sato et al. [14] also reconstruct CSG trees for fast image generation. Feature unification [10] is another application domain where the tree reconstruction technique seems to be useful. By feature unification, a specific feature is transformed into an isolated, desirable representation. Due to the global and non-uniqueness nature of CSG, a feature on an object may be represented by different sets of primitives, which may yet scatter around the CSG tree in a number of different ways. A tree reconstruction algorithm which groups these primitives as close as possible is therefore needed before the feature can be unified or mapped into a desirable format suitable for applications (such as process planning). Lee and Fu [10] earlier proposed a tree reconstruction algorithm based on the move-lup and the shuffle operations. The move-up operation either moves a node up one level in the CSG tree or changes the node's environment so that it can be moved up later. The shuffle operation performs the exchange of a node with its uncle twice so as to pair together two "cousins-german" in the CSG tree. Figure 1 illustrates how to pair together two nodes A and B in a CSG tree rooted at R. Nodes A and B are respectively raised level by level through the move-up operation until becoming the "cousins-german" under the same grandparent R'. They are then brought together under the same parent Y by the shuffle operation. This algorithm sometimes must stop because the move-up operation fails to move primitives. To solve this problem and make it more powerful, we propose in this paper a new tree reconstruction algorithm which follows the same ideas of moving-tip and shuffling nodes but is based on a well-defined single-step move-up operation. All the cases failed by the previous algorithm are either overcome or elaborated. The new algorithm is simple to understand, easy to implement. and very efficient. 2 CSG Tree

RSD-TR-21-87 / \ X Locate R', the latest common ancestors of A & B Figure 1: Pairing of Two Nodes. This paper consists of six sections. The next section defines the problem to be studied and describes the proposed set-theoretical approach to solving this problem. In Section 3, basic terms necessary for this study are defined and various ways to move nodes are discussed. Four useful properties are observed from this section. In Section 4, two state tables are derived and then optimized by the state reduction technique. A new table-driven algorithm is also developed to move nodes for feature unification. In Section 5, a comparison of this new algorithm with the previous one is made with respect to their primitive operations, control strategy, number of inputs used, and their power of moving up nodes. Finally the last section concludes this paper and describes two future works. 2 Problem and Proposed Approach As mentioned before a tree reconstruction algorithm which groups primitives for feature nification may be based on the move-up and the shuffle operations. Since the existing algorithm [10] does not guarantee the success of moving up nodes in all cases, it appears essential to closely CSG Tree 3

RSD-TR-21-87 reexamine all possibilities that a node in different environments can be moved up. The problem can be reduced to the problem of one-level move-up, as it is the basic step for moving a node up several levels to a desirable position. If an operation with well-formed behavior can be defined, it can then be plugged into any tree reconstruction algorithm which needs to move up nodes. In sum, the main problem to be studied in this paper can be stated as follows: Given a CSG tree in which solid primitives are constructed by the regularized set operators unions and differences only, how can a node in different situations be moved lip one level yet without duplicating the node itself? In this problem, the intersection operator is not included because it can be implemented by the difference operation (e.g., A n B = A - (A - B)) and it is less important than the union and difference operations which are sometimes analogous to the welding of assembly operation and the machining operation [8], respectively. In addition, a criterion we must insist in this study is that no duplication of the nodes being moved should be made. The purpose of feature unification is to group together all the primitives of a feature and convert them into another form, while the duplication of these nodes will ultimately leave their copies ungrouped and unconverted. Note however that the sibling of the node being moved is allowed to be duplicated if necessary. Our approach to solving this problem is purely set-theoretical. A CSG tree can be one-to-one mapped to a mathematical set expression where variables are the solid primitives, operators are the regularized set operators1 unions and differences, and parentheses enforce the CSG tree structure. Since this mapping can be isomorphic, a tree reconstruction can be achieved by applying settheoretical identities to a set expression and transforming it to an equivalent one. The study of moving a node up one level in the CSG tree is therefore equivalent to the search of appropriate set-theoretical identities which can be applied to the corresponding set expression to yield a new expression in which the node is effectively one level higher than it was before. lHereafter we will omit the word regularized in the context. 4 CSG Tree

RSD-TR-21-87 U Figure 2: Up-two-level Environment of A. 3 One-level Move Up 3.1 Basic Terms We will first define some necessary terms. A working node is defined as the node or subtree to be moved in a CSG tree. The level of a node or a subtree is defined as the number of ancestors along its parent chain to the root of the CSG tree. The level of the root is defined as 0. A move is an application of one set-theoretical identity to the CSG tree which results in the changes of the environment (defined below) of a working node. One-level move-up is defined as the result of one or several moves such that the level of a working node is one less than it was before the move or moves (i.e., the working node is at the same level as its original parent). An environment of a working node is characterized by, along its parent chain, the positions of itself to its ancestors and the operator types of these ancestors. A up-two-level environment of a working node is thus defined as a state which specifies the operator types of the working node's parent and grandparent, and the relationship of this node to its parent (either leftchild or rightchild) and that to its grandparent (either in leftsubtree or in rightsubtree). This term is so named because only two levels of ancestors (i.e., parent and grandparent) are referenced. In the example of Figure 2, the up-two-level environment of the working node A is characterized by the U, - operators, and A as in the leftsubtree of its grandparent and a rightchild of its parent. From the Up-two-level environment point of view, a working node can only be in one of the 16 possible environments because the operators of its parent and grandparent can be either unions CSG Tree 5

RSD-TR-21-87 State Set-theoretical Representation 1 (A U B) U C 2 (B U A) U C 3 CU(AUB) 4 C u (B U A) 5 C-(AU B) 6 C - (B U A) 7 (A - B)- C 8 (B - A)- C 9 (Au B) - C 10 (B U A) - C 11 (A- B)u C 12 (B - A) u C 13 C u (A - B) 14 C U (B - A) 15 C - (A - B) 16 C - (B - A) Table 1: Definition of 16 States. or differences and it can be either in rightsubtree or in leftsubtree to its parent and grandparent (2 * 2 * 2 * 2 = 16). Since these 16 possible environments are important in forming the basis of the moving-up analysis, they are defined as 16 states shown in Table I where A is the working node to be moved, B is its sibling, and C its uncle. The 16 states determine how a working node is moved up. However, information on some of these states is not enough for this decision so that more environmental information must be used. The environmental information beyond up-two-level is thus considered as the inputs for moving up the working node. The environmental information (i.e. operator type, and left- or 6 CSG Tree

RSD-TR-21-87 T D T D D T D T Input a Input b Input c Input d Figure 3: Definition of Inputs right-subtree) of each level beyond the up-two-level is regarded as an input, and thus collectively forms an input string starting from the upward third-level to the root. Since each environmental information consists of the operator type (either union or difference) and the position of working node (either in left- or in right- subtree), there are 4 possible combinations for each input. We use a, b, c, d to represent these combinations, as listed in Figure 3 where T is the subtree containing the working node, and the subtree D is the sibling of T. 3.2 Node Move-up In this section, we will investigate how a working node in the 16 different possible states be moved up one level in a CSG tree. Some of these states do not need to reference any input and the working node can be directly moved up, but some of them needs one or more inputs. The results are summarized by several properties. Consider State 1 (i.e., (A U B) U C) in Table 1. According to the precedence rule of the parenthesis, the working node A must operate with B first and then operate with C. Therefore A is at the same level as B and one level below C. However, if adequate set-theoretical identities (e.g., (A U B) U C = A U (B U C)) can be applied to transform State 1 into another expression (A U (B U C), in this case) in which A is outside the parenthesis, and B, C are enclosed in a pair of parenthesis, then A is one level higher than both B and C, which means that A is already moved up one level by the set-theoretical identities. Similarly, a working node in State 2 to State 8 in Table 1 can be directly moved up one level because the following set-theoretical identities hold. (Note that each expression on the left side corresponds to a state, from State 1 to State 8, in Table 1.) CSG Tree 7

RSD-TR-21-87 1. (AuB)uC=(Cu B)U A 2. (BUA)U C=(BUC)U A 3. Cu(AuB)= Au(Cu B) 4. Cu(BuA)=Au(BuC) 5. C-(A U B)=(C- B)- A 6. C-(BuA)=(C-B)-A 7. (A-B) -.C=A-(BuC) 8. (B-A)-C=(B-C)-A Property 1: For one-level move-up in a CSG tree, State 1 to State 8 in Table 1 can directly move the working node up one level without duplicating nodes and referencing any inputs. Consider State 11 (i.e., (A - B) U C) in Table 1. Since there is no simple set-theoretical identities which can be applied to move up A, input information from larger environment will be used. For State 11, the first input (i.e., the upward third-level environment) is enough to decide the movement. 1. Input is a. The environment of the working node A becomes ((A - B) U C) U D. Since the set-theoretical identity ((A - B) U C) U D = (D U C) U (A - B) holds and the A in the expression at right side is one level higher than that at left side, A is moved up one level by this set-theoretical identity. 2. Input is b. The environment of the working node A becomes ((I - B) U C) - D. It can be easily observed that the following set-theoretical identities hold: ((A - B)U C) - D = ((A - B) - D) U (C - D) = (A - (BuD))u(C - D) Comparing the last and first expressions, A has been moved up one level. 8 CSG Tree

RSD-TR-21-87 Present State Input T TUD T-D DUT D-T (A - B)u C (D U C)U(A - B) (A-(B u D))u(C - D) (A - B)u(D u C) (D-C)-(A-B) (B - A) C (DuC)u(B-A) ((B-D)-A)u(C-D) (B-A)u(DuC) (D-C)-(B-A) Cu(A-B) (DUC)U(A-B) (C-D)U(A-(BUD)) (A-B)U(CuD) (D-C)-(A-B) C u (B - A) (C u D)U(B - A) (C - D)u((B - D) - A) (B - A)u (C u D) (D-C)-(B-A) Table 2: Move up A in State 11, 12, 13, 14. 3. Input is c. The environment of the working node A becomes D U ((A - B) U C). Since the set-theoretical identity D U ((A - B) U C) = (A - B) U (D U C) holds, A can be moved up one level by applying this set-theoretical identity. 4. Input is d. The environment of the working node A becomes D - ((A - B) U C). Since the set-theoretical identity D - ((A - B) U C) = (D - C) - (A - B) holds, A can be moved up one level. Similarly, State 12, 13, and 14 can also move up nodes using only one input. The results are shown in Table 2 and Property 2. Property 2: For one-level move-up in a CSG tree, State 11, 12, 13 and State 14 in Table 1 can directly move the working node up one level by only referencing one input. Now let us consider the remaining states. For State 9, (A U B) - C, no simple set-theoretical identities can be applied to directly move A up. However, since the identity (A U B) - C = (A - C) U (B - C) holds, State 9 can be converted by this identity to State 11 (A is a leftchild, in the left subtree of its grandparent, its parent is -, and grandparent is U). Once converted to State 11, the working node A can be moved up one level as shown in Table 2. By the same token, State 10 can be first converted to State 13 by the identity (B U A) - C = (B - C) U (A - C), and A. can then be moved up as the same way in State 13. For State 15, i.e., C - (A - B), it can be converted to State 12 by the identity C - ( - B) = (C - A) U (C - (C - B)). A can then be moved up in the way shown in Table 2 although more nodes (i.e., C) are duplicated. The results CSG Tree 9

RSD-TR-21-87 Present State Input T TUD T-D DUT D-T (AU B) - C (D U (B - C)) (A - (C u D)) (A - C)u (D - (B - C)) U(A - C) U((B - C) - D) (D U (B - C)) -(A - C) (B u A) - C ((B - C)U D) ((B - C) - D) (A - C)u (D - (B - C)) U(A - C) U(A - (C U D) ((B - C)U D) -(A - C) C - (A - B) (D U (C - (C - B))) ((C - D) - A)U (C - A)u (D - (C - (C - B))) U(C - A) ((C - (C - B)) - D) (D U (C - (C - B))) -(C - A) Table 3: Move up A in State 9, 10, 15. State Set-theoretical Representation 16.a (C - (B - A)) U D 16.b (C- (B- A))- D 16.c D u (C - (B - A)) 16.d D - (C - (B - A)) Table 4: Elaboration of State 16. of moving up A are shown in Table 3 and Property 3. Property 3: For one-level move-ip in a CSG tree, State 9, 10 and State 15 in Table 1 can be converted to State 11, 13, 12, respectively, and the working node in these states can then be moved up one level by only referencing one input. Finally let us consider the State 16, C - (B - A). This state is the most difficult one where neither can simple set-theoretical identities be directly applied nor can it be converted to another states in order to move up the working node one level. Since a larger environment and more-inputs must be used, we define four new states by elaborating State 16 with the first input augmented. These new states are defined in Table 4. We will analyze them in detail. Case State 16.a ((C - (B - A)) U D): Now if we temporarily consider (B - A) as a working 10 CSG Tree

RSD-TR-21-87 Present State Input T TUE T-E EUT E-T (C - (B - A))u D (D E)U ((C- E)-(B - A)) (C - (B - A)) (E - D)(C - (B - A)) u(D - E) u(E i D) (C- (B- A)) D u (C - (B - A)) (D u E)U (D - E)U (C- (B - A)) (E - D)(C-(B - A)) ((C - E)-(B - A)) U(Du E) (C - (B - A)) Table 5: Move up A in State 16.a, 16.c. node, then State 16.a becomes State 12, and the operations listed in Table 2 can be applied. Once (B - A) is moved up, so does the A. Since State 12 needs an input, we need the second input to decide the movement of State 16.a. Assume E, from the second input, is the sibling of the subtree denoted as State 16.a. The results are listed in Table 5. Case State 16.b ((C - (B - A)) - D): This state is the easiest one in State 16 because, without referencing any input further, its working node can be moved up by the set-theoretical identity: (C - (B - A)) - D = (C - D) - (B - A). Case State 16.c (D U (C - (B - A))): Similar to State 16.a, if we temporarily consider (B - A) as a working node, then State 16.c becomes State 14, and the operations listed in Table 2 can be applied. Once (B - A) is moved up, so does the A. Since State 14 also needs an input, we need the second input to decide the movement of State 16.c. The results are listed in Table 5. Case State 16.d (D - (C - (B - A))): This is the most difficult case because no simple set-theoretical identities can be used. Even though we temporarily consider (B - A) as a working node, State 16.d become State 16 again. It means there is recursion here. Assume the second input is used, by the analysis of State 16.a, 16.b and 16.c, it is enough to move the working node if this input is b, or it may need one more input if the input is a or c. However, if the second input is d again, then the recursion occurs and more inputs are needed until the input is not d. Property 4: For one-level move-lup in a CSG tree, State 16 needs to reference one, two or more inputs in order to move lip the working node. If the first input is b, then this input is enough. if the input is a or c, then an extra one is enough. However, if the input is d. then more inputs are CSG Tree 11

RSD-TR-21-87 needed until the input is not d. 4 New Algorithm for Feature Unification Last section has shown how to move up a working node one level in different states. However, for the purpose of feature unification, a working node must be kept on moving up until a desirable position. This means that we need to know not only how to move up a node in different states but also what the next states are after the node has been moved. In this section, we will first derive two tables: one is the action table (or output table) for actually moving the working node, the other is the next state table which decides the working node's next state after moving. We will then apply the state minimization technique to reduce the states and also the sizes of these two tables. A driver equipped with these two tables becomes our new algorithm for moving nodes up. Finally, this new move-up algorithm is used to develop a new feature unification algorithm. 4.1 Output Table and Next State Table Two tables will be created in this section for continuously moving nodes up. One is the output table (or action table) which specifies what actions should be taken to move up one level the working node at different states. The other is the next state table which specifies what the next state is after the working node is moved up one level. The next state will determine the next move-up action. In Section 3, we have studied how to move nodes up one level. The results are listed in Table 2, Table 3, Table 5 and those set-theoretical identities in Section 3.2. By combining these tables and identities, we then have an output table, which is shown in Table 6. Although State 1 to State 8 do not need any input for moving nodes, the results after their movement are augmented with the first input for consistency with other states and for the derivation of next states. (Note that, in Table 6, State 16.d needs more inputs until the incoming input is not d, then it is converted to one of the State 16.a, 16.b, or 16.c and the associated action can be performed.) The next state table can be built by observing the states of the working node after it is moved by Table 6. For example, for the State 11, if the input is a, according to the operation specified 12 CSG Tree

RSD-TR-21-87 Present Input State T TuD T-D DUT D-T (AUB) UC (CuB)UA)U D (C U B) U A) - D D U((C UB)UA) D-((CUB)UA) (B u A)u C ((B U C)u A)u D ((B U C) U A) - D D u ((B u C)uA) D -((BUC)u A) C u (A U B) (A U (C u B)) U D (A U (C U B)) - D D U (A U (C u B)) D - (A U (C U B)) C U (B U A) (A U (B U C)) u D (A U (B U C)) - D D U (A U (B U C)) D - (A U (B U C)) C - (A u B) ((C -B) -A)u D ((C - B) - A) - D D u ((C - B)-A) D- -((C-B) - A) C - (B u A) ((C - B) -A)uD ((C - B) -A) - D D u ((C - B) - A) D - ((C - B) - A) (A-B)-C (A -(B C)) C))D (A - (BC))-D D u (A - (B u C)) D - (A - (B u C)) (B-A)-C ((B - C)- A) D ((B - C)- A)- D D U ((B - C)A) D ((BC) - A) (AU B) - C (D u (B - C)) (A - (C u D)) (A - C)u (D - (B - C)) u(A - C) u((B - C) - D) (D U (B -C)) -(A - C) (B u A) - C ((B - C) U D) ((B - C) - D) (A - C)U (D - (B - C)) u(A - C) u(A - (C u D) ((B - C) U D) -(A -C) (A-B)UC (DUC)u(A- B) (A-(BUD))U(C-D) (A-B)U(DUC) (D-C)-(A-B) (B-A) uC (DuC)U(B-A) ((B-D)-A)u(C-D) (B-A)u(DuC) (D-C)-(B-A) Cu(A- B) (DUC)u(A -B) (C-D)u(A-(BuD)) (A-B)U(CuD) (D-C)-(A-B) Cu(B-A) (CuD)u(B -A) (C-D)u((B-D)-A) (B-A)u(CuD) (D-C)-(B-A) C - (A - B) (D U (C - (C - B) ((C - D)- A)u (C-A) U (D (D - (C - (C - B) )) U (C - A) ((C - (C - B))- D) U(C - (C - B))) )) -(C - A) C - (B - A) ( see State 16.a (C - D) - (B - A) (see State 16.c ( need more input in Table 5.) in Table 5.) to resolve.) Table 6: The Output Table (Action Table) for Move-Up. CSG Tree 13

RSD-TR-21-87 by the table, the working node A will be moved to the state (D U C) U (A - B), which is the State 13 as far as A's environment is concerned. Therefore, the next state of State 11 with input a is State 13. State 16 is the one where its next states can not be immediately observed. If the input is b, the next state is State 16 from Table 6. If its input is a or c, Table 5 must be used because another input is required. According to the Table 5, however, each entry in the row for State 16.a or State 16.c specifies that the next state for A is always State 16 even after two inputs are used. For State 16.d, it must wait until an input is not d. Once that input occurs, the states will become one of 16.a, 16.b, or 16.c in order to move up the subtree which contains A. As we just mentioned, the next state of all these three is State 16. Therefore, the next state of 16.d is State 16. The next state table is shown in Table 7. 4.2 State Minimization of Tables If we look into Table 6 and Table 7 carefully, we will soon find that several states seems to be equivalent. Consider State 1 and State 2, for example. Their associated set expressions ((Au B)UC and (B U A) U C) are set-theoretical equivalent. Their corresponding entries in the next state table are identical, and their corresponding expressions in the output table are also equivalent. It seems that we may merge them into a single state. In this section, we will apply the state reduction [5] or state minimization [1] techniques to reduce the number of states in both tables. In the state reduction method, there is a partitioning algorithm which can effectively partition states into blocks of equivalent states. The algorithm first partitions all states into blocks in which every state has the same output for each input symbol. It then applies each input to the states of the same block to see if their next states are in the same block. If true, put them in the same block for next partition; otherwise, put them into different blocks in next partition. This process is iterated until two consecutive partitions are equivalent. Then all the states in the same block in final partition are considered as equivalent and merged to one state. Now we apply this partition algorithm. Consider the Table 6. Two outputs are equivalent if their expressions are set-theoretical equivalent. Therefore, we may partition the 16 states into nine blocks: {1, 2, 3, 4}, {5, 6}, {7}, {8}, {9, 10}, {11, 13}, {12, 14}, {15}, {16}. Then we consider the next state table Table 7, and apply each input to the states in same block to see 14 CSG Tree

RSD-TR-21-87 Present State Input State T TUD T-D DUT D-T 1 (AU B) U C 2 10 4 6 2 (B U A) U C 2 10 4 6 3 C U (A u B) 1 9 3 5 4 CU(B U A) 1 9 3 5 5 C - (Au B) 12 8 14 16 6 C - (B U A) 12 8 14 16 7 (A- B) - C 11 7 13 15 8 (B - A)- C 12 8 14 16 9 (A U B) - C 13 11 11 15 10 (B U A)- C 13 13 11 15 11 (A - B) U C 13 11 11 15 12 (B - A) U C 14 12 12 16 13 C U (A - B) 13 13 11 15 14 C U (B - A) 14 14 12 16 15 C - (A - B) 14 12 12 16 16 C - (B - A) 16 16 16 16 Table 7: The Next State Table for Move-Up. CSG Tree 15

RSD-TR-21-87 State Corresponding Original States 1 { 1,2,3,4 } 2 {5,6} 3 {7} 4 {8} 5 {9,10} 6d~ {11,13} 7 {12, 14} 8 ({15} 9 {16} Table 8: Definition of New States. whether new partitions are generated. After the application, we find that no block needs to be split. This means the initial partition is also the final partition, and all the states in each of the nine blocks are equivalent so that they can be merged into single state. Therefore we define these nine new states in Table 8, and create the reduced output table and next state table as shown in Table 9 and Table 10. 4.3 The New Algorithm With the given output table and next state table in Table 9 and Table 10 respectively, it is very easy to write a driver routine to move up nodes to a desired level in a CSG tree. Table 9 and Table 10 can be implemented by array data structures of two indices. The first index specifies one of the nine states in Table 8, and the second one specifies one of the four possible inputs. Each entry in these two tables can then be addressed (accessed) through the two indices. Listed below is the driver routine MoveUp, which uses the table-lookup technique to move a working node A to a desired level L as specified by its caller. 16 CSG Tree

RSD-TR-21-87 Present Input State T TUD T-D DUT D-T 1 (A U (B U C))u D (A u (B U C)) - D D u (A u (B u C)) D - (A U (B u C)) 2 ((C - B)- A)u D ((C - B)- A)- D D U ((C - B)- A) D-((C-B)-A) (A - (B UC))uD (A - (BuC))- D D u (A - (BuC)) D -(A - (BuC)) 4 ((B - C)- A) U D ((B - C) - A)- D D U ((B - C)- A) D - ((B - C)- A) s5 (D u (B - C)) (A - (C u D)) (A - C)u (D - (B - C)) u(A - C) u((B - C) - D) (D u (B - C)) -(A - C) L6 | (D U C)U(A - B) (A - (B U D))U(C - D) (A - B)U(D U C) (D - C) - (A - B) 7? (DuC)U(B-A) ((B-D)-A)U(C-D) (B-A)U(DUC) (D - C)-(B - A) | 8 II(D U (C - (C - B))) ((C - D)- A)u (C - A)u (D - (C - (C - B))) u(C - A) ((C - (C - B)) - D) (D u (C - (C - B))) -(C - A) |9 ( see State 16.a (C - D) - (B - A) ( ee State 16.c ( need more input in Table 5.) in Table 5.) to resolve.) Table 9: The New Output Table (Action Table) for Move-Up. CSG Tree 17

RSD-TR-21-87 Present State Input T TUD T-D DUT D-T 4 4 7 9 Table 10: The New Next State Table for Move-Up. procedure MoveUp ( A: CSGnode; L:integer); begin S:= current state of A; repeat I:= the input from A's environment; perform the action specified in OutputTable( S, I ); S:= NextStateTable( S, I ); until L = level of A; end; { MoveUp } To illustrate this algorithm, let us consider the example (((w - x) - y) U z) - t. The working node w, at level 4 in the tree, is to be moved up two levels. w is at the state 3, thus S = 3. The environment at the upward third level determines the input, which is a and thus I = a. 18 CSG Tree

RSD-TR-21-87 u - - -u-t- - - - - - - - - I A ~~II X X II -) I UI I I I I I - I /I -I State of w: S=3 S=6 S=6 Inputof w: Ia I b I (no input) Level of w: Lv=4 Lv =3 Lv = 2 Figure 4: Example of Moving Up w Two Levels. To perform the action specified in OutputTable(3,a), the original subtree ((w - x) - y) U z is converted to (A - (B U C)) U D where the working node A = w, its sibling B = x, its uncle C = y, and ancestor D = z. The result is a new tree ((w - (x U y)) U z) - t, in which the w, at level 3, is moved up one level. Now according to NextStateTable(3,a), the next state is 6, that is, S = 6. Then the loop in oveUp is iterated again. The new input I = b, and the CSG tree is replaced by (A - (B U D)) U (C - D), specified in OutputTable(6,b), where A = w, B = (x U y), C = z, and D = t. The final result is the tree (w - ((x U y) U t)) U (z - t), and the working node, now at level 2, is moved up two levels already. This example is shown in Figure 4. With the MoveUp procedure above, we may construct the algorithm for feature unification. As mentioned before, the most important task for feature runification is to group together relevant primitives after they are r by a feae tue recognizer or feature extractor. Once they are grouped together under a subtree, they are ready to be directly converted to other desirable formats. Listed below is the algorithm to group nodes. Assume that all the primitives recognized by a CSG Tree 19 replaced by (A (B U D))U(C - D, specified in 2Ltput~able(6,b, where ~-1 = w B = (a: ii yI CSG Tr~ee 19

RSD-TR-21-87 feature recognizer are collected in a set, call Bag. This algorithm starts with the Bag and, pair by pair, groups together all the nodes in the Bag under a CSG subtree. The Shuffle's function includes two consecutive exchanges: A's sibling is first exchanged with A's uncle, and then B's sibling is exchanged with B's uncle. procedure GroupNode ( Bag: set of CSG subtrees); begin repeat pick up two elements a and b from Bag; r = the latest common ancestor of a and b; Iv = level of r + 2; MoveUp(a, Iv); MoveUp(b, Iv); Shuffle(a, b); put the parent of a and b back into Bag; until only one element in Bag; return the only element in Bag; end; { GroupNode } 5 Comparison to the Existing Algorithm In this section we will compare this new algorithm and the previous one [10] for feature unification. Both algorithms employ the same paradigm to group nodes: first moving them up and then shuffling them together. The real differences between these two algorithms are the operations of moving nodes. Therefore, we will briefly review the moving-up operation, called Up, of the previous algorithm before comparing it with its counterpart, MoveUp, of the new algorithm. The previous algorithm also differentiates the working node's environment as 16 states (as we did in Section 3, Table I), and the procedure Up performs adequate operations in response to these 16 states. The basic operations of Up are the switch of nodes with their uncles provided 20 CSG Tree

RSD-TR-21-87 that appropriate set-theoretical identities are applicable. For those states that can not be supported by the basic operations, they are converted to other states so as to apply the basic operations. States can be converted either by duplication of nodes (e.g., (A U B) - C = (A - C) U (B - C)) or by escaping the working node to its parent and trying to move up the new working node. If an escaped working node needs another escape (which is determined by the states of the working node), it is then released back to the original working node so as to keep on moving. The algorithm fails, unfortunately, if the next operation after a release is still an escape, since it then leads to a cyclic situation where the escape and the release simply alternate the working node and its parent. In the following, we compare the procedures Up and MoveUp from several perspectives: primitive operations, control strategy, number of inputs, power. primitive operations. The primitive operations that Up uses are switch, duplication, escape, and release. The switch exchanges a working node with its uncle with possible update of tree structure and operator types. The duplication copies nodes and, if necessary, updates operator types too. The escape and the release simply modify the pointers to tree nodes. All primitive operations are simple and efficient, but the movement of a node up one level might require several primitive operations. On the other hand, the primitive operations of MoveUp, which are defined in the output table Table 9, are a little bit more complicated. They might also update the tree structure, operator types, and duplicate nodes. However, as far as moving nodes up one level is concerned, each primitive operation always succeeds by itself-no cooperation of others is needed. It is more efficient than its counterpart in which several operations may be involved and the working node is possibly escaped and released back and forth. control strategy. The control strategy that is used in Up for governing the continuation of moving is basically a state-transition paradigm which identifies the current state and performs corresponding actions. This simple control strategy is, however, complicated by the introduction of the escape-release mechanism. In comparison, the control strategy used in MoveUp is a tabledriven mechanism which is defined by the next state table and the output table. It is very simple, uniform, and easy to understand and to implement. number of inputs. The actions of the procedure Up are determined by the current state and CSG Tree 21

RSD-TR-21-87 the status of the control flag for escape and release. After the node is moved, a new current state is formed by its upward two level environment. A new input (i.e., the upward second level information) is augmented here to form the state before operation. Therefore, the procedure Up uses only upward two level information each time to decide operations. On the other hand, the procedure MoveUp uses more input information to determine its operations. It is obvious from Table 9 and Table 10 that more than upward two level information is used. Besides the upward two level information which forms the current state, one, two, or more inputs must be used. power. By the meaning of power we mean the ability of moving a node up at different environment. The new procedure MoveUp is definitely more powerful than the previous procedure Up. The less power of procedure Up is because it does not use enough environmental information to make decisions so that the escape and release control mechanism abandons too early on states which are possible to succeed. There are two categories of states which are failed by Up due to cycles. The first one is those states which need two consecutive escapes. It includes (C - (A - B)) U D, D U (C - (A - B)), D - (C - (A - B)), (C - (B - A)) U D, D U (C - (B - A)), and D - (C - (B - A)) (assume that A is the working node). The second category is those states in which the working node A', which was previously escaped from A, now needs another escape. It includes (Y - A') U Y, Y U (X - A'), and Y - (X - A') where Y, Y are CSG subtrees. However, just from the output table Table 6, or Table 9 in MoveUp, the working node in all these failure cases can actually be moved up except the D - (C - (B - A)), i.e. State 16.d. In the procedure MoveUp, a working node in State 16.d can still have a chance to be moved up if one of its inputs is not d. Therefore, the new procedure MoveUp is more powerful than the previous procedure Up. 6 Conclusion and Discussion 6. 1 Conclusion In this paper, we have studied the problem of how to move a node up one level in a CSG tree without duplicating itself. Mathematical set theory is employed to solve this problem. All 16 possible states in which a working node may reside are identified, and set-theoretical identities are 22 CSG Tree

RSD-TR-21-87 applied to move the node up. Several significant and interesting results are discovered (Section 3): on the feasibility issue, a node at any of the 16 different states is possible to be moved up one level; on the implementation issue, the ways of moving up a node at different states are realized and an algorithm is suggested. Based on this study, the state tables (i.e., output table and next state table) for moving a node up one level are created. They are further refined by the state reduction (minimization) technique so as to have a minimal number of states, i.e., 7, instead of 16. These two tables plus a simple driver routine constitute a new procedure, called MoveUp, which can move up a node several levels. Our new algorithm thus relies on the procedure MoveUp to move nodes around a CSG tree for grouping primitives and unifying features. Finally we compare the new algorithm with its predecessor with respect to moving up nodes. They- Procedure MoveUp and its counterpart, Procedure Up- are compared from four different points of view: primitive operations, control strategy, number of inputs, and power. Although the new procedure MoveUp has slightly complex primitive operations, it is usually more efficient in time because Up sometimes needs several of its primitive operations to move a node up one level while MoveUp needs only one. MoveUp also has a simple and uniform control strategy (i.e., a table-driven control). Since it references more inputs, Procedure MoveUp is more power than Procedure Up in moving up nodes. All the cases failed by Up are identified and overcome in MoveUp except for the case State 16.d. The case State 16.d is elaborated because a working node in that state can still be moved up as long as one of its incoming inputs is not the input d. 6.2 Discussion Although all the cases failed in the previous algorithm are resolved, the new algorithm still can not move up a node if it is at State 16.d and all of its incoming inputs are d. In practice, such a situation seldom happens because designers rarely design features in this way. Nevertheless, for theoretical completeness, we are still in search of adequate set identities that can either directly move the node or convert this state to other states. While the new algorithm MoveUp is designed originally for feature unification, it can be used in other applications where the CSG primitives also need to be moved. Feature recognition CSG Tree 23

RSD-TR-21-87 can be such an example. Since a feature on an object may be represented by different sets of primitives which may yet scatter around the CSG tree, the tasks of defining feature models and matching the models with CSG trees would be difficult and complex. However, if some rough information about a feature is available (e.g., a feature must be composed of certain types of primitives or certain primitives that have specific relationship in their principal axis directions), then these candidate primitives can be moved and grouped together under a CSG subtree before they are matched or recognized. This would reduce the complexity of feature recognition because the feature matching can be performed locally and feature models can be defined with less variety considered. At present, we are also investigating the application of the new algorithm MoveUp along this direction. 24 CSG Tree

RSD-TR-21-87 References [1] A. V. Aho, and J. D. Ullman, Principles of Compiler Design, Addison-Wesley, Reading, Mass., 1977, pp 99. [2] G. Allen, "An Introduction to Solid Modeling," Computer and Graphics, Vol.8, No.4, 1984, pp. 439-447. [3] J. W. Boyse and J. E. Gilchrist, "GMSolid: Interactive Modeling for Design and Analysis of Solids," Computer Graphics and Applications, Vol.2, No.2, March 1982, pp. 2740. [4] C. M. Brown, "PADL-2: A Technical Summary," Computer Graphics and Applications, Vol.2, No.2, March 1982, pp. 69-84. [5] P. J. Denning, J. B. Dennis, and J. E. Qualitz, Machines, Languages, and Computation, Prentice-Hall, Englewood Cliffs, New Jersey, 1978, pp. 110. [6] R. Goldstein and L. Malin, "3D Modeling with the SYNTHAVISION System," Proc. 1st Ann. Conference on Computer Graphics in CAD/CAM Systems, April 1979, pp. 244-247. [7] J. Goldfeather, J.P.M. Hultquist and H. Fuchs, "Fast Constructive Solid Geometry Display in the Pixel-Powers Graphics System," Computer Graphics, Vol.20, No.4, August 1986, pp. 107-116. [8] R. H. Johnson, Solid Modeling: A State-of-the-art Report, Second Edition, CAD/CIM ALERT, Management Roundtable, Inc., Massachusetts, 1985. [9] Y. Kakazu and N. Okino, "Pattern Recognition Approach to GT Code Generation on CSG," Proc. 16th CIRP International Seminar on Manufacturing Systems, Tokyo, 1984, pp. 10-18. [10] Y.C. Lee and K.S. Fu, "Machine Understanding of CSG: Extraction and Unification of Manufacturing Features," Compucter Graphics and Applications, Vol.7, No.1, January 1987, pp. 20-32. CSG Tree 25

RSD-TR-21-87 [11] N. Okino, Y. Kakazu and H. Kubo, "TIPS-i1: Technical Information Processing System for Computer-aided Design, Drawing, and Manufacturing," Computer Language for Numerical Control, Edited by J. Hatvany, North-Holland, Amsterdam, 197 3. [12] A. A. G. Requicha, "Representations for Rigid Solids: Theory, Methods, and Systems," Computing Surveys, Vol.12, No.4, December 1980, pp. 437464. [13] A. A. G. Requicha and H. B. Voelcker, "Solid Modeling: A Historical Summary and Contemporary Assessment," Computer Graphics and Applications, Vol.2, No.2, March 1982, pp. 9-24. [14] H. Sato et al., "Fast Image Generation of Constructive Solid Geometry Using A Cellular Array Processor," Computer Graphics, Vol.19, No.3, July 1985, pp. 95-102. [15] H. B. Voelcker et al., "The PADL-1.0/2 System for Defining and Displaying Solid Objects," Computer Graphics, Vol.12, No.3, August 1978, pp. 257-263. [16] M. A. Wesley, T. Lozano-Perez, L. I. Lieberman, M. A. Levin and D. D. Grossman, "A Geometrical Modeling System for Automated Mechanical Assembly," IBM Journal of Research and Development, Vol.24, No.1, 1980, pp. 64-74. [17] J. R. Woodwark, Computing Shape, Butterworths, Inc., England, 1986. [18] J. R. Woodwark, "Some Speculations on Feature Recognition," International Workshop on Geometric Reasoning, Keble College Oxford, England, June 30 - July 3, 1986. 26 CSG Tree