Bilisim
octree
OCTREESolid modelers must be based on reliable and fast algorithms for Boolean operations. The octree model, as well as several generalizations (polytrees, integrated polytrees, extended octrees), is specially well suited for these algorithms and can be used either as a primary or as a secondary model in solid modeling systems. This paper is concerned with a precise definition of the extended octree model that allows the representation of nonmanifold objects with planar faces and, consequently, is closed under Boolean operations on polyhedrons. Boolean nodes and nearly vertex nodes are introduced, and the model is discussed in comparison with related representations. A fast algorithm for the direct generation of the extended oclree from the geometry of the base polygon in extrusion solids is presented, and its complexity is studied. Boolean operation algorithms are introduced. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems-geometrica problems and compututions; 1.3.5 [Computer Graphics]: Computational Geometry and Object Modeling-curue, surface, solid, and object representatioms; J.6 [Computer Applications]: Computer-Aided Engineering-computer-aided design (CAD) General Terms: Algorithms Additional Key Words and Phrases: Computer-aided geometric design, geometric modeling, octrees, solid modeling INTRODUCTION Solid modeling systems are based on an unambiguous representation of threedimensional solid objects and contain specific tools for their operation and representation. Most existing systems use either the boundary representation model or constructive solid geometry (CSG) [24]. The boundary model is very suitable for obtaining visualizations and graphical output of the model, as well as for computing its volumetric properties. However, Boolean operations between solids become complex. If a CSG representation is adopted, Boolean operations are simple, but the computation of volumetric properties and the conversion to a final boundary model are cumbersome. Other representation schemes, based on a recursive cell deco:mposition of the space, are well suited for Boolean operations. Examples of this type are octrees [16] and bintrees [28]. However, they have other drawbacks: They are approximate and require a large amount of memory, since they approximate the slanted surfaces of the object by a set of very small cubic nodes. In [l] and [3], a new cell decomposition model, called extended octrees, is presented. This model incorporates terminal nodes that contain parts of the surface of the object, and solves the above-mentioned drawbacks of octrees, as proved in [19]: The model is exact for the representation of two-manifold polyhedral objects (as defined in Section 2), the boundary representation can be obtained from the octree model, and the model is much more compact in general. Due to the simplicity of the Boolean operation algorithms [19], extended octrees have been used as a secondary representation model in the DMI solid modeling system [22]. However, in the initial extended octree model only vertices with three or four converging faces are supported, and the object’s surface is restricted to be a two-manifold. As a consequence, the set of representable objects is not closed under regularized set operations [II]. On the other hand, when the extended octree model is used for the computation of Boolean operations between solids either in solid modeling [22] or in the simulation of NC machining programs [7], it has been observed that conversion from the boundary representation to the extended octree model is more time consuming than the Boolean operation itself and the back conversion from octrees to the boundary representation. The same applies to the conversion from CSG to octrees [23] (it must be observed that throughout the paper only firstorder, that is, planar, CSG models are considered). Therefore, alternative and faster algorithms for the generation of the extended octree representation have become necessary. The present paper is concerned with a precise definition of the extended octree model that avoids these limitations. The associated algorithms are also discussed. In the first part of the paper, the extended octree model is presented and compared with several related representations. It is shown that local CSG information in vertex nodes, the so-called vertex configuration, can be stored in a very simple way for general n-valenced vertices. Configurations can then be used in the point membership classification algorithms. In Section 2 it is proved that the extended octree model is closed under Boolean operations, provided that a new node, the Boolean node, is considered. Section 3 is concerned with the direct generation of the extended octree model, in extrusion solids, from the geometry of the base polygon. The corresponding algorithms are faster than those based on the generation of the boundary model of the solid and are specially suited for processes involving a sequence of Boolean operations with swept volumes, as in the case of the simulation of numerical control programs. Finally, Section 4 deals with the associated Boolean operation algorithms. Considerations of robustness and the inclusion of the Boolean node are discussed in particular. 1. OCTREE REPRESENTATION OF POLYHEDRONS Octrees are solid models that are generated by a recursive subdivision of a finite cubic universe and that represent the tree of the subdivision process [12, 18, ,271. The root of the octree represents the universe. It is a cube of edge length 2”, ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. 172 l P. Brunet and I, Navazo called the maximum scaie. The scale of an octree node is defined as the length of the edges of the corresponding cube. The root cube is divided into eight identical cubic octants of scale 2n-1, which are represented by the tree nodes pointed at by the root at tjhe second level of the tree. Valid terminal nodes include white nodes (completely outside the solid) and black nodes (completely inside it). Whenever an octant cannot be represented as a valid terminal node, it is denoted as a gray node and is divided into eight other identical cubes, which are represented as descendants of the octant in question. This process is repeated recurisvely until either terminal nodes or cubes of minimum scale are reached. The user can fix the subdivision and the depth of the tree through the specification of both the maximum and minimum scales. Several representation schemes for the octree model have been proposed up to now. In [16] a complete tree with information and pointers in the nodes is used, whereas [lo] is based on a linear list including only black nodes. A compact depth-first (DF) expression including the ordered list of nodes that are generated in a DF traversal of the tree has also been proposed [ 14,271. Boolean operations, like any other operation based on the traversal of the octree, require O(N0) operations in every representation, NO being the total number of nodes in the octree. However, specific operations such as the point-solid classification require O(log NO) operations in pointer-based representations, against 0 (NO) operations in linear representat.ions. The main advantage of the octree model is the linear complexity of the Boolean operation and rendering algorithms [17]. However, they are approximate models, as the slanted surfaces of the objects must be represented by a set of minimumscale black nodes. On the other hand, if the minimum scale is reduced in order to increase the precision, a large amount of storage is needed. In recent years, several new octree models have been proposed in order to avoid these drawbacks: They can be defined as vector octrees [29,30] and include data structures describing the solid geometry in the octree leaves, either as a topdown approach [5, 291 or as a bottom-up approach 18, 291. In [9] and [31], a hybrid structure octrees CSG has been introduced. In [32] a spatially segmented solid representation based! on the splitting and pruning of a CSG model is used in the generation of continuous-tone shaded images. Concerning schemes that include geometry from a boundary representation, two new octree models have been independently proposed: polytrees [4, 51 and extended octrees [l, 31. Both models incorporate new terminal nodes that contain parts of the object surface, and yield exact representations for polyhedrons. They also reduce the degree of subdivision and therefore require less storage than classical octrees [19]. The new terminal nodes in poiytrees and extended octrees are (Figure 1) face nodes that are crossed only by a single planar face of the solid, edge nodes that contain two neighboring faces and a part of their common edge, and vertex nodes that contain one vertex of the polyhedron and part of the faces and edges converging to it. The main difference between both schemes is the way they represent face, edge, and vertex terminal nodes. In particular, -the geometric information that is stored in the new terminal nodes is different in both schemes: In polytrees, the exact geometry, polygons, of the surface of ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. the object inside the node is computed and stored explicitly, whereas in the extended octrees, only the configuration and the set of pointers to a unique list of planar half-spaces are included in the nodes. The configuration [3, 19] is the auxiliary information that is necessary to classify a point [25] inside the node with regard to the object in face, edge, and vertex nodes. -In extended octrees, the configuration stores the same information as the local CSG tree of the solid within the node [20]. As the neighborhood of the surface in the node is homogeneous (a face, edge, or vertex), configuration can be considered as a different way to represent the neighborhood information [25] that is used in Boolean operation algorithms. Polytrees, on the other hand, use only explicit boundary information in terminal nodes. Several consequences derive from these differences. Among the most important are the following: -Point classification in extended octrees can be based on CSG algorithms, which have been proved to be robust. -In extended octrees, both the configurations and face pointers in the extended nodes (face, edge, vertex) preserve the nonredundancy of the geometric information and allow coherent local decisions in separate nodes (Section 4.2). On the other hand, independent explicit representation of the geometry of the polygons in the surface nodes in polytrees is redundant and can generate inconsistencies between local decisions in Boolean operation algorithms. -Extended octrees can be considered as a representation intermediate between CSG and boundary representations, due to the fact that node configurations are equivalent to local CSG trees [23]. Therefore, algorithms can be devised for conversion between extended octrees and boundary representations [3], and also for conversion between CSG and extended octrees [13, 23]. -Extended octrees can represent two-manifolds, whereas polytrees allow the representation of general nonmanifolds (Section 2 provides a discussion of nonmanifolds and extended octrees). -Both polytrees and extended octrees can be used for the representation of polyhedrons. Extended octrees, however, can be used also to model free-form closed surfaces [2] without computing explicitly the geometry of the boundaries and intersections of the patches inside the nodes. ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. Fig. 2. Subdivision near a vertex of the polyhedron. Two-dimensional pictures are shown for simplicity. (a) A vertex node ca:n generate zones of very deep subdivision. (b) Subdivision is stopped if terminal gray nodes are allowed. (c) Vertex’ nodes avoid unnecessary subdivision. In [ 191, only vertex nodes with three or four faces per vertex were allowed (three-, or four-valenced vertices). An extended octree, however, can represent general polyhedrons with m-valenced vertices if vertex configurations are coded as the cyclic set of the configurations of the edges converging to it [20, 211. In this case, the point classification algorithm in vertex nodes can be based on a very simple exclusiue or of a set of dihedral half-spaces associated with the edges of the vertex [21]. A basic disadvantage of both polytrees and extended octrees is that it is possible to produce subtrees of arbitrary depth near edges and vertices of the object (Figure 2a). This depends on the relative position between the solid and the octree grid [6] and can produce minimum-scale nonterminal nodes that must be coded as approximate white or black nodes: These are the so-called “blackholes” in [6]. In extended octrees, this problem is partially avoided by coding black holes as terminal gray nodes [ 191. Terminal gray nodes are gray nodes of minimum scale that contain a set of faces that converge to the same vertex outside the node (Figure 2b). Since they are coded to include the same information as the corresponding vertex node, Boolean operations algorithms can support them without becoming more complex. In [6], a new model of octrees is presented in order to avoid the black-hole problem. The model, called integrated polytrees, incorporates three new types of nodes-edge’, vertex’, and vertex”-which are similar to the terminal gray nodes except that they are not coded at the minimum-scale level. They are coded at the maximum scale in the subdivision process (Figure 2~). Integrated polytrees need less storage than other classes of octrees, and an upper bound for the storage amount can be obtained [ 61. 2. EXTENDED OCTREE REPRESENTATION OF NONMANIFOLDS Two-manifold polyhedrons are a special class of planar-faced objects that satisfy (see, for instance, [ 151) the following statements: (1) Every edge belongs to exactly two planar faces. (2) Every vertex is surrounded by a single cycle of edges and faces. (3) Faces may not intersect each other except at common edges or vertices. ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. Solid Representation and Operation Using Extended Octrees. 175 Definition 1. The surface proximity, d min, of a two-manifold polyhedron is defined as FORMULLER SAYFA 5 and ei, fi, Vk indicate the individual edges, faces, and vertices of the polyhedron, respectively. On the other hand, ei 0 ej = 0 must be understood in the sense that ei and ej have no common endpoints. From this definition, it is straightforward to show that the minimum distance between any two nonadjoining geometric elements (faces, edges, vertices) of the surface is always rdmin. This is true when comparing pairs of edges or vertices with other geometric elements, since d,, L dmin, dvf 1 dmin, dve L dmin, and dvv 2 dmin from eq. (1). It is also true for the distances face-face, face-edge, vertex-edge, and vertex-vertex. In fact, defining FORMULLER the minimum distance must occur in the boundary of faces and edges. Consequently, dff 2 min(d,,, d,) and dfe 2 min(d,,, d,). On the other hand, as vertices are the endpoints of the edges, dve I d,, and dvv L de,. This completes the proof that the minimum distance between any two nonadjoining geometric elements of the surface is always rdmin. By statement (3) of the definition of two-manifolds, de, > 0, dv, > 0, dve > 0, and dvv > 0. As a consequence, the surface proximity, dmin, is always positive in two-manifold polyhedrons. Its value depends on the specific geometry of the object. With Definition 1, it can be concluded that either the extended octrees or the integrated polytrees represent exactly, without loss of information, any twomanifold polyhedron, provided that minimum scale < 3-‘12 * dmin. In fact, according to eq. (l), any node of minimum scale in the tree containing a part of the surface of the object will only contain adjacent geometric elements. Therefore, it must fall into one of the:. following categories: (a) It contains a single planar face, (b) it contains an edge and part of the adjacent faces, (c) it contains a vertex and the converging faces and edges, ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. 176 l P. Brunet and I. Navazo (d) it contains two adjacent planar faces that intersect in an edge outside the node, or (e) it contains two or more planar faces that converge in a vertex outside the node. As case (d) reduces to (e) (two adjacent faces meeting in an edge also converge to both end vertices of this edge) and case (e) has a valid representation through terminal gray nodes, we (can conclude that these classes of octrees represent twomanifold polyhedrons in an exact way. However, two-manifolds are not closed under Boolean operations: The result of an operation between two-manifold polyhedrons can be a nonmanifold, which is nonrepresentable in the described extended octree model. Let us assume that nonmanifold solids are represented as pseudomanifolds. Pseudomanifolds are topologically considered as two-manifolds, but their geometric model allows distinct surface points to coincide in space [ 151. They have a surface proximity dmin = 0, since at least one of the distances d,,, . . . , dvv vanishes. As a consequence, a null minimum scale would be necessary in order to represent them. Let us now define nonseparable octree nodes and Boolean nodes, in order to provide a representation scheme for nonmanifold solids. Definition 2. An octree node N, is nonseparable if (1) it is not possible to represent it by means of a subtree with extended terminal nodes and finite depth, and (2) at every level of its subtree there exists a gray node containing the same geometric information 8,s in N,. In a nonseparable octree node, for any positive value s, there always exists a cube c of size s contained in the node, such that the surface of the polyhedron restricted to the inside of c is too complex to be represented by an extended terminal node (white, black, face, edge, vertex). Nonseparable octree nodes appear in the generation of the extended octree of a nonmanifold solid. Definition 3. A Boolean Node is a nonseparable node that can be represented as a list of face, edge, and vertex nodes of the same scale and spatial location. In the DF representation of the octree, it will be represented in turn by its code, followed by the whole coding of each of the individual extended nodes. We also assume that the configuration of the first node in the list is well defined (the classification of any point in the neighborhood of its surface and not in the neighborhood of the rest of surfaces is given by its configuration). Note that depending on the nonseparable node it may be necessary to complement the first extended node in order to orient it. PROPOSITION 1. The extended octree model can represent any nonmanifold solid, provided that Boolean nodes are allowed in addition to white, black, gray, face, edge, vertex, and terminal gray nodes. PROOF. In fact, nonmanifold solids have a bounded and orientable surface, and their faces must not intersect except in vertices and edges [ll], as in twomanifold polyhedrons. However, statements (1) and (2) in the above definition of two-manifolds may not be fulfilled: The surface of the object contains points whose neighborhoods are not homoeomorphic to a disk. ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. Solid Representation and Operation Using Extended Octrees. l 177 Obviously, the whole cubic universe, except nonseparable nodes, can be represented as an extended octree. Nonseparable nodes contain a complex surface that can be interpreted as a set of nonintersecting simple surfaces that coincide either in a point or along an edge (Figure 3). Any coincidence must fall into one of the following classes: (1) edge-edge coincidence, either in a point (Figure 3a) or along both edges (Figure 3d); (2) vertex-face coincidence; (3) vertex-edge coincidence (Figure 3d); (4) vertex-vertex coincidence (Figures 3-b and c); or (5) edge-face coincidence. It can be observed that, except for the last one, these classes correspond to the distances that form the expression for dmirz in Definition 1. Coincidences are directly related to the vanishing of dmin in pseudomanifolds, as has already been noted. Class five, however, can cause the vanishing of any of the d,,, . . . , dvv, depending on the geometry. As the simple nonintersecting surfaces in the above coincidence classes can be modeled by face, edge, and vertex nodes, it is possible to model the whole surface inside the nonseparable node by a set of space coincident extended nodes. Now, in order to finish the proof of Proposition 1, it only remains to show that point classification inside the nonseparable node is possible when the Boolean node representation is used. But this is immediate, since it is always possible to connect the point Q being classified with a point in the neighborhood of the welloriented node through a path that avoids surface coincidences. From the properties of nonmanifold solids, the number of surface crossings in this path uniquely determines the classification of Q. El Furthermore, the solid inside the Boolean node can be represented as a Boolean expression involving the individual extended nodes that compose it. In other words, the configuration of a Boolean node is generated from the configurations of the component nodes. Figures 3b and c show two simple cases where locally the nonmanifold solid can be represented either as the union of two convex vertices or as the intersection of concave vertices. The case in Figure 3d is more complex and unusual, and includes two edges and five vertices. Obviously, all vertices converge to the same point P, but V,, V,, and V, are convex, whereas Vb and V6 are concave, being represented in white. The diagram in Figure 3e represents the intersection of all the surfaces involved in Figure 3d, with a small sphere centered at P. In general, once the corresponding diagram of the Boolean node being considered has been generated, it can be mapped onto a set of polygons with holes. Then, the Boolean expression representing the solid inside the node is the union of the terms associated with the polygons, which in turn are either extended nodes or intersections of extended nodes, depending on the type of polygon (with or without holes). In the case of Figure 3d, we obtain e3 U e4 U V, U V, U (V, fl V, n V,). As a consequence, it can be concluded that if the extended octree incorporates white, black, gray, face, edge, vertex, and Boolean nodes, and if terminal gray ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. (SAYFA9 SEKILLER) Fig. 3. Some examples of nonseparable nodes. (a) Point coincidence between two edges. (b) Vertex- Vertex coincidence convex vertices. (c) Vertex-Vertex coincidence concave vertices. (d) A complex case with two edges and five vertices. (e) Sphere diagram of (d). nodes are allowed, any nonmanifold topology is representable, and Boolean operations are closed. However, in order to reduce the required amount of storage, and following [6], from now on we consider extended octrees as a model that includes white, black, gray, face, edge, vertex, Boolean, and nearly vertex nodes: Definition 4. A nearly vertex node is a terminal node that contains two or more faces converging to a vertex outside the node (see, for instance, Figure 2~). Section 4 is concerned with Boolean operation algorithms based on extended octrees. These algorithms are very useful either in the simulation of NC programs [7] or in the modeling process itself. Extended octrees can be used as a secondary model in solid modeling systems, in order to efficiently perform Boolean operations [22]. In this case, and assuming that nonmanifolds are represented in the boundary model as pseudomanifolds [Xi], the boundary to extended octree conversion algorithms [3, 221 need only be changed in order to include a ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. Solid Representation and Operation Using Extended Octrees. l 179 separability test in gray nodes. Since the boundary information is still retained, the set of faces causing nonseparable nodes is known. Therefore, the test consists only of a classification of the set of faces within the gray node: They either do or do not all belong to the same coincidence of geometric elements in the pseudomanifold. In the first case, the node is coded as Boolean; in the second, the node is considered as gray and subdivided. The conversion algorithm from extended octrees to boundary representation is based on a single traversal of the tree and the generation of a list of vertices, each pointing to a cyclic list of the corresponding face equations [3, 191. This is already a valid boundary representation, which can be converted, in a second step, into the required representation in the solid modeler. If the extended octree contains any Boolean node, the same process must be performed, but vertices in the lists associated with Boolean nodes must also be considered. Finally, a postprocess can be included in order to represent the resulting nonmanifold as a valid pseudomanifold. 3. ALGORITHMS FOR THE GENERATION OF THE OCTREE OF EXTRUSION SOLIDS The extended octree representation of a polyhedral solid can be generated either from its boundary representation or from the CSG model. In the first case [3], a recursive clipping algorithm obtains the part of the object’s boundary that is inside every node in the octree and concludes whether it is a valid terminal node or a complex gray node that must be subdivided. In the conversion from CSG to the extended octree representation [23], the initial first-order CSG tree is recursively localized into every cubic node. By pruning these local CSG trees, terminal nodes of the octree and gray nodes are generated and written in the output tree. Both algorithms are O(NO), where NO is the number of nodes in the resulting octree [3, 231. For instance, the number of operations in the conversion from boundary representations to extended octrees is n.operBR-Eo = cmN0 (2) where c3g is the average cost per node. The number NO of nodes can be shown to be bounded by a linear function of the surface area of the different d-thick zones on the surface of the object (a d-thick zone is the set of points P so that dist(P, Q) 2 d for all points Q fulfilling face(P) n face(Q) = 0). As stated in the Introduction, it has been observed that the conversion from boundary representation to the extended octree model is much more time consuming than the Boolean operation algorithm and the back conversion from octrees to the boundary model. Therefore, it is necessary to investigate alternative and faster methods for the generation of extended octree representation. In the rest of this section, a faster algorithm for a restricted class of polyhedral solids is presented. Let us consider the class S of prismatic, extrusion solids in which the base polygon is parallel to one of the coordinate planes (say X-Y) and the generatrix is perpendicular to this plane. These solids can be generated by a parallel sweep of the base polygon. For every solid S E S, we denote zmin, zmax as its maximum ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. 180 l P. Brunet and I. Navazo extents in the direction of the sweep (Figure 4). Furthermore, h = zmin - zmax, 1 = max(length(e;)), 1 (3) where el, . . . , e, are the ed.ges of the base polygon. The extended quadtree of the base polygon is defined as a quadtree containing white, black, gray, edge, and vertex nodes; terminal gra,y nodes that contain two edges converging to a vertex outside the node are also allowed. Besides classical definitions, edge nodes contain a piece of one edge ek of the polygon [l], and a vertex node contains part of two consecutive edges el, elcl together with the point el n el+l (a cyclic representation is assumed with e,,, = el).We define the scale of a quadtree node as the length of the edges of the corresponding square. Two of the boundaries of a node will be considered open, and the other two, closed [3]; in other words, a node extending from xl to x2 and from yl to y2 is the set of points xl < x % x2, yl < y 5 y2. 3.1 Generation of the Octree from the Extended Quadtree of the Base Polygon PROPOSITION 2. For every object s E S, its extended octree model depends only on the extended quadtree of its base polygon and the maximum extents zmin, zmax. Generation of the extended octree is based on a single preorder traversal of the initial quadtree and involves only comparisons and no 3-D clipping operations. In the case h P 1, a preprocess of the quadtree must be performed in order to subdivide edge and vertex nodes having scale 2 h. PROOF. Let us first suppose that h > 1. Depending on its z-position, every node in the octree extending from zl to 22, zl < 22 will belong to one of the following sets cl, c2, cg, cq (Figure 5): cl: a set of nodes such that ((~1 < zmin and zmin I 22 < zmax) or (zmin 5 zl c zmax and zmax I: 22)), c2: a set of nodes such that (zmin I zl < zmax and zmin I 22 C zmax), c3: a set of nodes such that (zl < zmin and zmax 5 z2), or cq: a set of nodes such that (22 < zmin or zl 2 zmax). Then, the following statements are derived immediately: -Every node of the octree belonging to c4 is a white node. -For every other node, its type is automatically derived from the type of the node of the extended quadtree that has the same scale and position restricted to x-y, as shown in Table I. It can be observed that c3 nodes with E or V homologous quadtree nodes cannot exist (case (2) in Table I), as a consequence of the hypothesis that h > 1. Furthermore, gray nodes, that derive from black nodes in the quadtree (case (1)) generate very simple subtrees in the octree: All nodes belonging to cg in the subtree are gray nodes containing two parallel faces, whereas nodes belonging to cq are black. This is the only case in which a terminal node in the quadtree does not lead to a single terminal node in the octree. Finally, every node having a homologous gray node in the quadtree, G* nodes in Table I, is also gray. The four sons of the G node of the quadtree transform ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. Solid Representation and Operation Using Extended Octrees.SAYFA 12 SEKILLER onto two sets of nodes in the octree node G*: The x-y partition of the quadtree is repeated on two layers in the z direction. In a second step, every node in these subtrees must be modified according to Table I. As a consequence, the whole conversion process can be achieved if a preorder traversal of the quadtree is performed and the transformations in Table I are applied to every node. Octree node classification into c, . . . c4 is based only on comparisons and does not require any explicit 3-D geometric calculations. This completes the proof of Proposition 2, for the case in which h > 1. 0 If h I I, cases (2) in Table I can occur, and the corresponding new subtrees in the octree are generated. ‘The subdivision of these nodes requires true clipping operations in 3-D in order to classify the sons into W, B, F, E, and V nodes. However, if a quadtree preprocess is performed in order to subdivide every edge or vertex node with scale zh, the new quadtree nodes cannot be homologous to c3 nodes in the octree, which satisfy size 2 h. As a consequence, cases (2) are avoided by the preprocess, and Proposition 2 also holds. Observe that the subdivision of edge and vertex nodes in the quadtree is performed only once and involves simple 2-D clipping operations. COROLLARY 1. When, in addition to the hypothesis of Proposition 2, the base polygon is sufficiently thin in the sense that its extended quadtree does not conta,in black nodes of scale ~1, case (1) in Table I cannot occur. In this case, every terminal node in the quadtree generates a set of terminal nodes of the same size in the octree. The preorder traversal of the quadtree to octree conversion allows a simple DF encoding of both trees; the algorithm from Proposition 2 is really a single traversal of the associated linear DF lists, involving no geometric operations other than coordinate comparisons. 3.2 Computation of the ExItended Quadtree of the Base Polygon The extended quadtree of the base polygon can be obtained through either of the following two algorithms: The first algorithm (Al) is based on the clipping of the geometric information within a square node of the quadtree, and its subdivision in the case of being too complex [l]. In this case, the type of the node depends on the number of vertices NV of the polygon that are inside the node and the number of edges NE that intersect the node while having endpoints outside it (Table II): Algorithm Al generates the quadtree in preorder, and therefore, a DF representation is possible. Its complexity is linear with regard to the number of nodes NQ of the quadtree [3, 281: The number of operations involved is n.operAl = C&Q (4) where cZD is the average cost of the 2-D clipping, which is performed on every node of the quadtree. The second algorithm (‘~2) is a straightforward generalization of [26]. Let us suppose, without loss of generality for well-behaved polygons, that the scale of the initial node is unity and that there exists a positive minimum distance dmin between geometric entities (in the same sense as Definition 1, but using only dvv and d,) in the base polygon. A mesh of m X m square cells, m = 2”, cx being the ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. Solid Representation and Operation Using Extended Octrees. l 183 Table II. Type of Quadtree Node, as a Function of the Number of Edges that Intersect (NE) and the Number of Vertices Inside (NV) SAYFA 14 TABLO smallest integer such that 2-” = scale I dmin * 2-l/‘, will divide the initial node into small squares with no more than one vertex or edge inside. As a consequence, the depth of the resulting extended quadtree will be (Y + 1, with node sides 2-k, k=O .a. a. The algorithm works in two steps. In the first step, it walks along the edges of the polygon and characterizes the cells containing a part of the boundary as vertex or edge nodes in a Bresenham-like way. In this phase a pseudoquadtree is built, which has only minimum-scale terminal nodes and nonterminal gray nodes with probably less than four pointers to sons [26]. The edges of the initial polygon can be treated in a similar way as in discrete boundary codes. They are traversed in a closed way along the boundary of the polygon: For (every edge in the base polygon) write-quadtree (vertex) /* First vertex of the edge being considered compute next edge node while (next edge node # node containing the second vertex of the edge) If (not 4-connected) then write-quadtree (black) endif write-quadtree (edge) compute next edge node end while end For The procedure “write-quadtree” writes a node in the output quadtree. The procedure “compute next edge node” computes the position of the next cell, in the m x m grid, that contains the following part of the edge being considered. It depends on which side the edge leaves the present node and relies on simple point-straight-line classifications: Only one of the corners of the node must be classified against the edge, depending on its slope. However, as the ordered set of minimum-scale edge and vertex nodes must be treated as a boundary code in the second step and must be four-connected, an extra black node must be written onto the output quadtree when the edge of the polygon contains a corner joining two open or two closed boundaries of the node. Writing in the quadtree generates the necessary nonterminal gray nodes [26] by looking for a common ancestor for the last and present nodes and then creating mirror images of the nodes traversed. The second step of algorithm A2 first completes the missing terminal nodes with white and black nodes (this is straightforward, as every node created during the first step is equivalent to a black node in a classical quadtree approximation of the polygon) and then compacts the quadtree, based on repeated application of the rule of the similarity of brothers [23, 261. The complexity of algorithm A2 is n.opcrAz = O(long * a), where long is the perimeter of the initial polygon, measured by the number of cells visited during the first step. ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. 184 - P. Brunet and I. Navazo In order to compare bot.h algorithms, we first note that in centered and very narrow polygons, as in Figure 6a (where NQ = 5, long = 0(2”)), algorithm Al behaves better than A2. This is due to the fact that long is determined by the closest pair of vertices: Unnecessary terminal nodes are generated in step 1 of A2 and must then be removed during step 2. In the case of very small polygons (Figure 6b), NQ = 1 +‘4cu, long = 4, and both algorithms perform similarly. On the other hand, Figure 6c presents an example where a maximal quadtree is generated. A maximal quadtree is a quadtree that has all its terminal nodes at the deepest level CY. The number of nodes is then NQ = (4a+1 - 1)/3 = O(49. Every gray node at level 01 - 1 must contain either two vertices, one vertex and part of an edge, or two parts of nonadjacent edges; therefore, long must be at least half the number of terminal nodes; in Figure 6c, long is obviously 4”. As a consequence, both algorithms also perform similarly in polygons that lead to maximal quadtrees. On the other hand, if tk and gk are defined as the total number of terminal nodes and gray nodes at level k of the quadtree and the polygon boundary crosses on average two of the sons of every gray node (this is a most usual case), tk = gh, and long = 2”, NQ = 2”+’ -. 3 = 0(2a). Therefore, both algorithms have the same complexity. Finally, when ,gk > tk, we approach the situation in Figure 6c: Both NQ and long increase, and the algorithms remain similar. In conclusion, we can state that both algorithms for the generation of the quadtree of the base polygon (Al and A2) perform similarly in most practical situations. Their comparison in practical implementations will depend on the particular implementation of the clipping algorithms and the two steps of algorithm A2. 3.3 Complexity of the Octree Generation Algorithm In order to study the com:plexity of the proposed algorithm, it is necessary to compare the total number of nodes NQ of the quadtree of the base polygon with the number of nodes NO of the final octree. The following proposition relates the size of both trees: PROPOSITION 3. If the extended quadtree of the base polygon has depth cy + 1 and gk gray nodes at level k, k = 0 . . . CY, then No g 4g,Wl + - - - + 4&-l% 4go + 4g, + * * * + 4g,-1 (NQ - 1) + 1 where ah, k = 1 . .. a, are a set of integers 2 9 ok 5 2k that depend on the maximum extents zmin, zmax of the object. PROOF. Let us observe that the following relations derive directly from the definition of a quadtree, where there are tk terminal nodes at level k: go = 1, gcT = 0, gk > 0, k = 0 . . . CY, tk + gk = %!k- 1, k= 1 ... 01. ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. (5) Solid Representation and Operation Using Extended Octrees. - Fig. 6. Extended quadtree generation for different classes of polygons. The polygons have been shaded for clarity. (a) Narrow rectangle. (b) Minimum-scale square. (c) A polygon that visits every minimum-scale node. Consequently, we can write a a--l a 0-l NQ = c tk + c g, = 1 + 2 (tk + gk) = 1 + 4 c gk. 1 0 1 0 Let us assume, without loss of generality, that the initial cubic node of the octree is 0 5 x 5 1, 0 I y 5 1, 0 5 z 5 1. Let us first also suppose that the conditions in Corollary 1 of Proposition 2 hold. When the maximum extension of the object is greater than that of the initial node, zmin 5 0, zmax I 1, there will be no nodes in the final extended octree belonging to the class cq. In this case, the quadtree nodes, which incorporate x-y information, are repeated 2k times at every level k as they transform into octree nodes. In fact, the conversion process can be understood as a Cartesian product between the quadtree and a binary tree governing the z-partition. In the most usual case, 0 5 zmin < zmax 5 1, terminal white nodes above zmin and below zmin will be produced. Now, the binary tree governing the z-partition will have ‘dk = 2k - d; - d: (7) nodes at level k, where d; and cl: are the number of nodes that disappear at this level due to the location of zmin and zmax, respectively. It is easy to show, however, that both d: and d: can be generated recursively in the following way: PO = 0, Pk = 2Pk--1 + bindig(k, zmin) d: = 2&-l (8) Yo = 0, Tk = 2ykel + bindig(k, 1 - zmax) d: = 2y,-, (9) where bindig(k, U) is a function that returns the digit k in the radix 2 representation of U, 0 5 u < 1. Therefore, from Corollary 1 we can conclude that NO = 1 + i uk(tk + g,J. 00) k=l In the general case, Proposition 2, the number of nodes in the extended octree can be greater because of the new subtrees that appear in the generation process. ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. 186 * P. Brunet and I. Navazo Then, and defining w0 = 1, NO 2 i: wk(tk + g,J. k=O (11) Observe that wk 2 2, wk 2: ok-1 Vk 2 1. Using (5), NOrw,.,+4 ; w&&l. k=l (12) If we now define K = (NO - l)/(NQ - l), using (6) and (12) we can write NO=K*(NQ-l)+l, (13) KZ 4g,w, + . . . + 4ga-1wm 4go + 4g, + . * . + 4gm-1 = K,,,. This completes the proof of Proposition 3. 0 When h is small and zmin - zmax, the values wk approach their lower bound, for instance, if h = 0.1, wA = 2, k = 1, 2,3,4, and w5 = 4. On the other hand, large values of h lead to significant amplification factors wk: when h = 0.8, W, = 2, w2 = 4, w3 = 8, w4 = 14, and w5 = 28, approaching the limit value wk = 2k. In the worst case, when h + 0, ‘dk = 2 tlk, K 2 j$$ = 2. k Since & > 0 tlk < 01, (13) can be interpreted as a weighting of the coefficients wk. In most practical cases, it can be observed that gk increases with k: gk = 1, 2, 9, 30, 62 and & = 1, 1, 2, 6, 17, 36, 44, 63, 80 for the objects in Figure 7. In other words, tk % 3&, following (5). As a consequence, the highest wk elements in (13) are weighted by the high.est gk values. In all these cases, the assumption that gi = gk = 1 Vi, k will prov:ide a lower bound for K, (13). In Table III we present a set of values for this lower bound of Km, (CY wJa). Now, the total number of operations involved in the algorithm presented in Sections 3.1 and 3.2 will be, following (4), n.operEo = czDSDNO + czDNQ (14) where czD3D is the average per node cost of the transformation from 2-D to 3-D (Section 3.1). Of course, CODED < cpg < CUD (Eq. (2)), since cpg3D involves no geometric operations and clipping in 2-D is much simpler than clipping in 3-D. Using (13), n.operEO 5 C2D3DNo + cpD ~++~)~((c,,:,,,+~)NO+C,,,. (15) Comparing with eq. (2) and taking into account Proposition 3 and the results presented in Table III, we can conclude that cZD3D + 2 K CYD, ln ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. (16) Solid Representation and Operation Using Extended Octrees. l 187 and that the proposed algorithm is much more efficient than the standard BR + EO conversion. However, the efficiency depends on h and LY (Table III): Objects with high h values and small edges in the base polygon are specially well suited, as K,,, is rather high. Objects with small h and very long edges in the base polygon can produce small values for Km. However, even in this case, it is easy to see that (16) holds. 4. BOOLEAN OPERATIONS IN THE EXTENDED OCTREE MODEL The main advantage in using octree models for the representation of solids is the simplicity of the algorithms that implement Boolean operations. These algorithms are based on a parallel traversal of the two input trees while comparing homologous nodes-same size and spatial location-and handling them according to the rules of the Boolean algebra [16]. Boolean operations with extended octrees are based on the same rules, and only the operation between pairs of individual nodes must be modified. In comparison with boundary representation algorithms for set operations: -Extended octree algorithms need only incorporate tools for set operations between pairs of extended nodes (mainly face, edge, and vertex). As the geometry of these nodes is rather simple, the overall algorithm is not too complex, since it must consider only a restricted set of special cases. Spatial location and pairing of the geometric information of the objects being operated on are automatically supplied by the octree structure. As a consequence, the complexity of the whole process is linear with regard to the total number of nodes [6, 191. -0ctrees are based on the independent codification of the local geometry inside every node. As a consequence, special care must be taken in order to avoid inconsistent decisions in different but geometry-related nodes during the Boolean operation algorithm [ll, 151, if robust algorithms are to be designed. The basic ideas and Boolean operation algorithms used in the DMI solid modeling system have appeared in [3], [ 191, and [20], where the whole set of Boolean operations is defined in terms of two basic operations, complement and regularized intersection [3], since it is known that A U B = l(lA n 1B) and A - B = 1B n A. Recently, it has indeed been observed [ll] that for robustness considerations regularized set operations must be implemented in terms of a basic operation plus complement. In this case, incoherent results in Boolean expressions that could be evaluated in a nonunique form are avoided. In [4], Boolean operation algorithms working on the polytree structure are presented. As has already been observed, independent explicit representation of the geometry of the polygons in the surface nodes may lead to inconsistencies in the result of the Boolean operation within neighbor nodes, which can only be avoided if nonredundant representation schemes are used [ 111. In what follows, the basic Boolean operation algorithms used in the DMI solid modeling system [20] are described. The handling of Boolean nodes is discussed, and robustness considerations are included. ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. Fig. 8. Face-edge intersection. The part of the nodes in the solid has been shaded. (a) Face node. (b) White node. (c) Edge node. (d) Edge node. (e) Gray node. (fJ White node. (g) Edge node. (h) Edge node. (i) Face node. (j) Edge node. (k) Boolean node. (1) White node. (m) Edge node. (n) Face node. (0) Gray node. configuration can be immediately computed from the configuration of the edge node and the configuration of the two new convex edges. -Both lines cross the node (test T3), but intersect outside it (test T2). Here, the output node is a gray node (a nearly vertex node, if a vertex node involving these faces has already been found). -Two lines exist, but only one of them crosses the node, following test T3. The output node is either nearly vertex, gray, or a convex edge, depending on the relative position between the edge of the edge node and r.V, which can be computed through the point-on-a-plane test. ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. 194 - P. Brunet and I. Navazo -Two lines exist, but rmne of them cross the node. The output node is gray or a simpler part of it (edge, face, or white), depending on the relative position between the face and the edge (see Figure 81-80 for a 2-D simplified representation of these cases). Case 5. edge (I edge. In this case, up to four lines obtained from the intersection between pairs of different edge nodes can cross the output node. Some special cases arise when less than four lines are obtained as a result of test Tl or when some of these lines coincide. A detailed study of the different cases leads to an output node type that can be white, edge, vertex, nearly vertex, gray, or Boolean [20]. However, this case can often be recast in terms of the previous cases: In fact, if we represent the edge nodes as El, E2, and the planes associated with EP by rl, az, we can write, assuming that hk is the half-space associated to rk and that E2 is convex, E, n E2 = E, n (h, II h,) = (E, f-I h,) n hz or, if E2 is concave, EL n E:! = El n (hl U hz) = (El n hl) U (E, n hz) = l(l(El n hl) n -(El r-3 hz)). In both expressions, all the edge-face intersections in parentheses correspond to Case 4. When the corresponding results are white, face, or edge, the whole intersection is obtained in a second step using the rules in Cases 1-4. It is important to note that Boolean nodes always appear as a by-product of the coincidence tests in the handling of extended nodes, as happened in the faceedge case. Therefore, it is not necessary to include specific tests for the detection of nonseparable nodes. Case 6. vertex n face, edge, or vertex node. In a first step, test Tl is applied to every plane of the vertex node intersected with the planes in the other node. Test T2 checks for coincidences, and then, a set of simple cases are completely solved: -The vertex of the vertex node is classified as in the other node, and the faces of the vertex node do not intersect the surface of the second node inside it. The result is either a vertex node or a gray node, depending on the configurations. -The vertex of the vertex node is classified as out the other node, and the faces of the vertex node do not intersect the surface of the second node inside it. In this case, the result is either white or the second node, depending also on the configurations. -The vertex of the vertex node is on the other node. Depending on the result of the tests Tl, T2, and T3, the output node is either a Boolean node, a gray node, or an extended terminal node, much as in Case 4. In more complex cases, the operation is not solved at this level, in order to avoid the discussion of a large number of special cases. The resulting node is declared as gray, and the algorithm proceeds subdividing and comparing homologous ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. Solid Representation and Operation Using Extended Octrees. l 195 descendants. An alternative solution for these cases would be to compute explicitly the boundary representation inside both nodes and to use a boundary merging algorithm for the computation of the regularized intersection [ 15, 25 1. Case 7. gray n Any extended terminal node (extended terminal nodes include face, edge, vertex, nearly vertex, and Boolean nodes). In this case, the extended node is subdivided, as in the process of building the extended octree from the boundary representation [3, 191, and the nodes obtained in the subdivision are intersected with the homologous descendants of the gray node. Case 8. Boolean n Any extended terminal node. As the Boolean node can be expressed as a Boolean expression involving the component extended nodes, this case reduces to the preceding ones. For instance, if the Boolean node is the union of the nodes A, B and we represent by C the extended terminal node being dealt with, (A U B) n C = (A II C) U (B n C). Now, (A n C) and (B n C) can be independently computed using one of Cases l-6; as A, B are components of the Boolean node and have null regularized intersection, (A n C) and (B fl C) also have null regularized intersection. Therefore, the result of their union is either a simple terminal node if one of them is white, or a Boolean node if they have any coincident point, or a gray node if their boundaries do not have any point of coincidence. In this case, (A fl C) U (B n C) is separable, and the gray node must be subdivided. On the other hand, if the Boolean node is the intersection of the nodes A, B, the Boolean operation is computed by using the associative property: (A n B) n C = (A n C) n B. In some cases, use of the rules in Cases l-8 generates an output octree with a subdivision in complex zones that is higher than necessary. For this reason, it is convenient to include a compaction algorithm in the routine that writes nodes to the output octree [23] or, alternatively, to perform the whole compaction process after the Boolean operation. The compaction algorithm replaces every set of eight brother terminal nodes that are similar (in the sense that they can be obtained from the subdivision of a valid terminal node) with the equivalent terminal father node. 5. CONCLUSIONS The extended octree model has been presented and compared with similar representations. It has been shown that general nonmanifold planar faced objects can be represented if the node type Boolean is allowed. Boolean nodes consist of a list of extended nodes (face, edge, and vertex), and consequently they use already supported geometries and do not complicate the associated algorithms. A method for the direct generation of the extended octree representation of extrusions has been presented and discussed. The algorithm has been used in the simulation of numerical control machining operations, where a large number of set operations must be performed between the workpiece and a set of tool swept ACM Transactions on Graphics, Vol. 9, No. 2, April 1990. 196 l P. Brunet and I. Navazo volumes. As has been shown, it is considerably less complex than the usual boundary representation to extended octree conversion process. Finally, Boolean operation algorithms supporting Boolean nodes have been introduced, together with techniques for the detection of nonseparable nodes and robustness considerations. Extended octrees can be used efficiently as a secondary model in solid modeling systems, as a tool for boundary merging processes. ACKNOWLEDGMENTS The authors would like to thank Donald M. Esterling for his useful ideas and comments, and Josep Fontdecaba and Francesc Bate for their help in the implementation of some of the proposed algorithms.