R O B U S T S C U L P T I N G U S I N G B O U N D A R Y R E P R E S E N T E D S O L I D S B y Cedric C . Lee .A.Sc . (Engineering Physics) University of Br i t i sh Columb A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF SCIENCE in T H E FACULTY OF GRADUATE STUDIES COMPUTER SCIENCE We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA September 2000 Â© Cedric C. Lee, 2000 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of Br i t i sh Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Computer Science The University of Br i t i sh Columbia 2075 Wesbrook Place Vancouver, Canada V 6 T 1Z1 Date: F^pjoJotr Q.Rt Q/top Abst rac t Boolean operations are often used in the computer modeling of 3-D mechanical parts and machineries and are known for their predictable behavior and ease of use. The use of Boolean operations in the interactive modeling of free-form models, however, has been rather l imited. Some of the difficulties in realizing this include: selecting a model representation that may be displayed at interactive speed, applying Boolean operations robustly, and creating smooth surface transitions at the junctions between models. This thesis explores the use of the real number package of the Library of Efficient Datatypes and Algori thms ( L E D A ) for computing the Boolean combination of triangu-lated and boundary-represented solids robustly. This thesis also suggests a scheme for removing numerically unstable triangles which are detrimental to the validity of solids, and a surface blending scheme that simulates the smoothing of sharp surface junctions by modifying surface normals. Our scheme for computing Boolean operations is more robust than those used in two popular modeling applications but at the expense of longer computation time. Our scheme for removing numerically unstable triangles is effective in removing invalid surface triangulations while preserving the appearances of models and our simulated surface blending scheme is capable of smoothing non-trivial surface junctions at near-interactive rates. These features were implemented in a simple solid modeler and a set of models was created interactively using this system. i i Table of Contents Abstract ii List of Tables vi List of Figures vii Acknowledgements ix 1 Introduction 1 1.1 Previous Work 3 1.1.1 Volume-Based Modeling 3 1.1.2 Surface-Based Modeling 6 1.2 Our Approach 8 2 Boolean Operations 9 2.1 Boundary Representation 9 2.1.1 Halfedge Data Structure vs. Winged-edge Data Structure 10 2.1.2 Surface Tessellation 11 2.1.3 Vertex Normals 11 2.2 Computing Boolean Combinations 16 i i i 2.2.1 Computing Junction Points and Lines 19 2.2.2 Generating Junction Vertices and Edges 28 2.2.3 Removing Extra Faces 33 2.2.4 Merging Faces Along Junction Edges 36 2.3 Numerical Problems 36 3 Robustness 38 3.1 Problem with Floating-Point Arithmetic 38 3.2 Making Numerical Computations Robust 39 3.2.1 Structure of LEDA-real and the Cost of Using It 40 3.2.2 Computing with LEDA-real 42 3.2.3 Problem with LEDA-real to Floating-point Conversion 43 3.2.4 Skinny Triangle Identification 44 3.2.5 Skinny Triangle Reduction 45 4 Blending Surface Junctions 50 4.1 Basic Operations 54 4.1.1 Measuring and Traversing Distances Along Constrained Surface Paths 54 4.1.2 Estimating Surface Normals . . . 56 4.2 Averaging the Surface Normals at Junction Vertices 58 4.3 Associating Vertices with Points on Junction and Trimlines 59 4.4 Modifying Vertex Normals 61 4.5 Improving The Sampling of Surface Normal 62 5 Implementation and Results 65 5.1 Implementation 65 i v 5.2 Results 66 5.2.1 Robustness 66 5.2.2 Surface Blending 75 5.2.3 Sculpting 79 6 Conclusions and Future W o r k 93 Appendices 95 A Halfedge D a t a Structure 95 References 98 v List of Tables 2.1 Differences between our boundary representation and Chiyokura's . . . . 10 2.2 Re-categorizing overlapped surface regions for the union of A and B . . . 28 4.1 Locations on edges to sample surface normals 63 5.1 Robustness tests using test polyhedron A 69 5.2 Robustness tests using test polyhedron B 69 5.3 Robustness tests using test polyhedron C 70 5.4 Robustness tests using test polyhedron D 70 5.5 Varying the cost thresholds for skinny triangle removal 72 5.6 Performance of skinny-triangle removal 75 5.7 Blend time for junctions with different numbers of edges 76 v i Lis t of Figures 2.1 Topological operations used in our system 12 2.2 edge-swap and its effect on vertex normals 15 2.3 edge-collapse and the affected vertices and triangles 16 2.4 Set-theoretical intersection vs. regularized intersection 17 2.5 Computing the union of two solids 18 2.6 Classifications of different triangle-triangle intersections 24 2.7 Face-Face intersection 25 2.8 Face-Edge intersection 26 2.9 Edge-Edge intersection 27 2.10 Inserting a constrained edge 32 2.11 Removing the unwanted faces and merging the remaining ones 34 3.1 Modification to a narrow triangle under perturbation 43 3.2 Skinny triangle removed using edge-collapse and edge-swap 45 4.1 Simulating surface blending by surface normal interpolation 53 4.2 Constraining a path to lie on a sphere S and a plane P 55 5.1 Polyhedra used during the robustness test 68 5.2 Skinny triangle removal 73 v i i 5.3 Skinny triangle removal with different cost thresholds 74 5.4 Blending smooth base surfaces 77 5.5 Blending base surfaces with creases 78 5.6 3-headed cat model 80 5.7 Constructing a skull model, steps 1-2 83 5.8 Constructing a skull model, steps 3-5 84 5.9 Constructing a skull model, steps 6-8 85 5.10 Constructing a skull model, steps 9-10 86 5.11 Constructing a kid's head model, steps 1-3 89 5.12 Constructing a kid's head model, steps 4-6 90 5.13 Constructing a kid's head model, steps 7-9 91 5.14 Constructing a kid's head model, steps 10-11 92 v m Acknowledgements First and foremost, I would like to thank my supervisor, the late A l a i n Fournier, for giving me the freedom to explore different research ideas, the guidance I needed to define the scope of my thesis, and the insightful comments and suggestions that helped me understand the problems I have chosen to tackle. I would also like to thank Kellogg Booth for being my first reader and for reviewing my thesis during Alain ' s illness, and David Kirkpat r ick for being my second reader despite his leave on sabbatical. Special thanks go to Lisa Streit, Roger Tarn, Rob Walker, Dave Bullock and Rob Scharein of the Imager lab for their support and helpful comments during my degree. This research was funded by a Post Graduate Scholarship from the Natural Sciences and Engineering Research Council . Finally, I would like to thank my parents, my aunt and especially my wife Christ ina for their understanding, support and encouragement. CEDRIC L E E The University of British Columbia September 2000 i x Chapter 1 Introduction Interactive design of 3D vir tual objects is a non-trivial task that requires computer artists to master the use of 3D modeling techniques and work with their strengths and weak-nesses. The ease of mastering a modeling technique depends on its simplici ty and pre-dictability. One technique that excels in both of these is the use of Boolean operations for combining solid models. Boolean operations are often used in the design of mechanical parts and machineries. Disjoint parts are often fused together using the union operator and holes and grooves in objects are often carved out using the subtraction operator. Despite their popularity in engineering applications, Boolean operations are rarely used in the interactive design of free-form 3D sculptures. This thesis explores three problems that need to be addressed in order for Boolean operations to be more widely used in interactive sculpting: the interactive display of objects, the robust application of Boolean operations, and the creation of smooth surface transitions between objects that are combined with Boolean operations. The rapid display of solid models is essential to interactive sculpting as it is important for users to visualize the relative positions of solid models before they apply Boolean 1 Chapter 1. Introduction 2 operations to them. Many representations for solid models exist but only a few of them may be displayed at interactive rates. One of them is the boundary representation (Brep). Boundary represented solids, or Brep solids, are defined by the surfaces that enclose their volume. The explicit ly defined surfaces allow Brep solids to be displayed rapidly. Other advantages of using Brep solids include the ease of associating surface attributes to Brep solids and the ability to manipulate Brep solids using surface modeling techniques. Despite al l of their advantages, Brep solids are well known for having numerical prob-lems under Boolean operations. Like most geometric algorithms, the computation of Boolean combinations is often based on algorithms that assume the use of exact arith-metic. In practice, exact arithmetic is often too expensive and is substituted wi th floating-point arithmetic. As a result Boolean operations may fail due to numerical inaccuracies and the user must adjust the input by trial-and-error to prevent such failures from hap-pening. This is often a difficult and frustrating process, especially when the models are closely aligned or have complex geometries. We address this problem by using a mix of exact and floating-point arithmetic when computing the Boolean combinations of solids. Another problem with using Boolean operations is the creation of sharp surface transi-tions at the junctions where the input solids meet. These sharp transitions are sometimes undesirable and need to be smoothed out for aesthetic reasons. Whi le surface blending schemes may be used to smooth out these transitions, most blending schemes are either designed for implic i t and parametric surfaces or are computationally expensive. We sug-gest a scheme for simulating the effect of blending by smoothing the surface normals across the surface junctions. The rest of this thesis is organized in the following manner. Firs t , previous work is surveyed in Section 1.1. The application of Boolean operations is then described in Chapter 2 followed by our solution to the robustness problem in Chapter 3. Chapter 4 Chapter 1. Introduction 3 explains how we blend the junctions between solids and Chapter 5 describes our imple-mentation of these features in a simple solid modeler and some results generated using this application. Final ly, Chapter 6 provides conclusions from our work and directions for future work. 1.1 Previous Work The related work that we survey may be divided into two categories: volume based modeling techniques and surface based modeling techniques. 1.1.1 V o l u m e - B a s e d M o d e l i n g Volume-based models are models that have clearly defined boundaries between the vol-ume inside and the volume outside the models. Topological changes to the boundary of volume-based models occur naturally as the volumes within the models are added and subtracted. The most popular volume-based models are solid models and "blobby" objects. S o l i d M o d e l i n g The modeling of solids has been mainly the focus of engineering, computer-aided design and computer-aided manufacturing. Solids, in these contexts, must enclose a finite but non-zero volume, must contain no "dangling" lower-dimensional components and must not self intersect. Complex objects can be designed by combining different solids using Boolean operations. The most common representations of solids are constructive solid geometry ( C S G ) , boundary representation (Brep), binary space partitioning trees ( B S P trees), and cell decomposition. Chapter 1. Introduction 4 C S G solids are represented as binary trees [36]. The leaf nodes of the trees contain solid primitives and the non-leaf nodes of the trees contain Boolean operations and rigid motion transformations to be applied to their subtrees. The exterior surfaces of C S G models are impl ic i t ly defined and are often determined at render time through raytracing. Solid primitives with piecewise linear or quadric surfaces are often used so that they may be intersected easily with rays. One of the main advantages of modeling with C S G is that every C S G solid is valid as long as the primit ive solids are valid. The rendering of C S G solids through raytracing, however, is computationally expensive and cannot be done at interactive rates without serious restrictions to the location of viewpoints. This makes C S G solids unsuitable for interactive modeling. Unlike C S G solids, the bounding surfaces of Brep solids are explici t ly defined and can be rendered efficiently. Boolean combinations of Brep solids are computed by intersecting their surfaces, stitching together the surface regions that belong to the final solids and discarding the regions that do not. Low degree surfaces are usually used so that surface intersections may be computed efficiently. Polygonal surfaces are particularly popular due to the ease of computing their intersections. Many schemes for applying Boolean operations to polyhedral Brep solids have been proposed [26] [8] [23] [17]. These schemes assume the use of exact arithmetic and can fail when surface intersections are classified inconsistently due to numerical errors. Hoff-mann [17] discusses this problem in detail and surveys some of the related work. One solution to the robustness problem is the use of exact arithmetic but this is often too expensive for interactive use. Fortune [12] introduces the use of floating-point filters which combines the efficiency of floating-point arithmetic and the robustness of exact arithmetic. We are unaware of any literature that describes the use of Fortune's floating point filter in interactive free-form sculpting. Chapter 1. Introduction 5 Naylor [31][32] proposes yet another solid representation that uses B S P trees. The volumes enclosed in solids are bounded by sets of space parti t ioning planes. Boolean operations on these solids are applied by merging their B S P trees [30]. The exterior surfaces of solids may be stored as polygonal faces with their associated space partitioning planes and may be rendered efficiently. Unlike Brep, B S P trees do not use any topological information. As a result, the algorithms for combining B S P trees do not need to keep the topology of bounding surfaces consistent and are less sensitive to numerical inaccuracies. This , however, also prevents topology-dependent algorithms from being applied to B S P trees efficiently. Another way to represent solids is to decompose their volumes into axis-aligned cells. This type of representation may be divided into two categories: the use of regular grids of volume elements and the use of octrees. In [15], Galyean and Hughes propose a sculpting system that is based on axis-aligned volume elements, or voxels. This system allows the user to fill and clear voxels using metaphors similar to the "paintbrush" and "eraser" metaphors used in 2D paint programs. Boolean combinations of solids may be computed by applying Boolean operators to their voxels. Like C S G , the boundaries of voxel-based solids are not explicit ly defined and are expensive to render. The regular subdivision of space also makes voxel-based models expensive to store as the storage cost is proportional to the volume enclosed in the models. The storage cost is reduced in octrees where the regular subdivision of space is replaced by a hierarchical one. The cost of performing Boolean operation on octrees and the cost of rendering octrees are also lower than the same operations for regular voxel grids. Brunet and Navazo [4] review some of the octree-based solid modeling schemes and describe the use of extended octree nodes to reduce the cost of storing non-axis-aligned faces. One major drawback of voxel and octree-based models is that they are cumbersome to combine once they are scaled Chapter 1. Introduction 6 and rotated independently. Blending is a process that is closely related to the application of Boolean operations to solid models. When solids are combined using Boolean operations, the surfaces of the resulting solids often include sharp transitions at the junctions between the input solids. Surface blending schemes may be used to t r im away these sharp surface transitions and replace them by surfaces that smoothly interpolate the remaining surfaces. Most blending algorithms are based on implici t and parametric surfaces [44]. Blending of polyhedral surfaces is described in [45] and [35]. These techniques, however, compute blend surfaces using energy minimizat ion schemes that are too expensive for interactive modeling. Blobby Object Modeling Blobby objects [48][47][10] are objects represented by scalar fields and their surfaces are iso-surfaces at a predefined field value, s&. A point is considered to be inside a blobby object if its field value is above Sb and outside a blobby object if its field value is below Sb- Smoothly varying field functions that decay over distance are used for blobby objects so that their field functions and iso-surfaces may be smoothly merged to create new blobby objects. The shape of blobby objects, however, is difficult to control as it is often hard to predict the effect of overlapping scalar fields. In particular, it is difficult to create sharp features on blobby objects. Blobby objects, like C S G solids, have impl ic i t ly defined surfaces and are expensive to render. 1.1.2 Surface-Based Modeling Unlike volume modeling schemes, surface modeling schemes do not require objects to have clearly defined boundaries between the volume that is inside and the volume that is outside of objects. Self-intersections are allowed in surface-based models and topological Chapter 1. Introduction 7 changes to these models are often carried out through the explicit use of surface split-ting and surface merging operations. Our work is most related to the work in surface deformation schemes and the work on surface pasting. Surface deformation is the most popular interaction technique in surface modeling. It allows the user to add and remove volume from surface-based models by stretching and shrinking their rubber-sheet-like surfaces. This is often carried out either by directly moving groups of surface control points or by deforming the space in which surface control points are embedded [37] [38] [9]. Other surface deformation schemes assign physical prop-erties to surfaces so that the surfaces may be deformed by external forces [34] [42] [5]. The behavior of the aforementioned surface deformation schemes al l depends on the density and connectivity of surface control points. The user, as a result, must actively maintain the density and connectivity of the surface control points in order to obtain the desir-able surface deformations. The behavior of Boolean operations, on the other hand, does not depend on the structures of the input surfaces and are therefore simpler and more intuitive to use. The problem of pasting one surface to another involves the merging of disjoint surfaces and the smoothing of the junctions where the surfaces intersect. Some of the approaches used in surface pasting include: pasting one surface to another by treating the first surface as an offset surface of the second one [1][7], and merging two surfaces by morphing a section of one surface into the shape of another [21]. The first approach is based on the use of hierarchical B-spline surfaces proposed by Forsey and Bartels [14]. The use of a hierarchy of offset surfaces requires the user to distinguish between the coarse and detailed parts of an object. This can sometimes be a great inconvenience because the distinction between coarse and detailed features is not aways clear during the interactive sculpting of free-form objects. The second is based on the mesh metamorphosis scheme Chapter 1. Introduction 8 proposed by Kana i et al. [22]. This scheme allows one surface to gradually "morph" into another, thus pasting the first surface onto the second one. The rate at which the first surface morphs into the second one may be varied to create both smooth and sharp surface transitions. This scheme, however, only applies to surfaces that are topologically equivalent to spheres or discs. 1.2 Our Approach Solids in our solid modeler are represented by boundary-represented and triangulated sur-faces. Boolean combinations of solids are computed based on Chiyokura's algorithm [8]. Our implementation of this algorithm is described in Chapter 2. Chiyokura's algorithm is prone to robustness problems because it assumes the use of exact arithmetic. Our implementation addresses this problem by using a mix of floating-point and exact arithmetic as suggested by Fortune [12]. This is described in Chapter 3. Sharp junctions between solids are smoothed in our system through the modification of surface normals. This approach takes advantage of the topological information en-coded in boundary-represented solids and is computationally less expensive than energy minimizat ion schemes. Our blending scheme is described in Chapter 4. Chapter 2 Boolean Operations Our solid modeler computes Boolean combinations of boundary-represented polyhedral solids based on Chiyokura's algorithm [8]. This chapter describes the boundary repre-sentation we use and how Boolean combinations of solids are computed. 2.1 Boundary Representation The polyhedral boundary representation we use is made up of three parts: a topological part which describes the connections between vertices, edges and faces, a geometric part which describes how vertices are embedded in space, and a scalar part which describes the attributes that are associated with vertices. The polyhedral surfaces used in our system are restricted to closed and oriented 2-dimensional manifolds. The neighborhood of each point on the surface must then be homeomorphic to a disc and each point must also have a unique surface orientation. The surfaces should also be embedded in 3-space with no self-intersection. A l l input solids to Chiyokura's algorithm are assumed to follow these restrictions. There are a few differences between the representation we use and the representation 9 Chapter 2. Boolean Operations 10 described by Chiyokura. These are listed in Table 2.1. Our representation Chiyokura's representation Uses Halfedge data structure for encoding surface topology Uses Winged-edge data structure for encoding surface topology Uses oriented triangles for surface tessellation Uses polygons for surface tessellation Uses multiple vertex normals Does not use vertex normals Table 2.1: Differences between our boundary representation and Chiyokura's These differences are described in detail in the following sections. 2.1.1 Halfedge Data Structure vs. Winged-edge Data Structure Instead of using Winged-edge data structures [2], our system uses Halfedge data struc-tures to encode the topology of manifold surfaces. This data structure is functionally equivalent to the Winged-edge data structure and is described in the Reference Manual of the Computational Geometry Algor i thm Library ( C G A L ) [6]. A n excerpt from this manual is included in Appendix A . The following are the operations we use for modifying surface topologies. make-triangle, which creates an oriented triangular face wi th three border edges. The orientation of the triangle is determined by the order of the vertices. The vertices are in counter-clockwise order when the triangle is viewed from the outside (see Figure 2.1(a) for an example). a d d - v e r t e x - t o - f ace, which inserts a new vertex into a triangular face by splitting it into three smaller faces (see Figure 2.1(b) for an example). edge-merge, which merges two border edges into an interior edge. A l l duplicated ver-tices are removed during edge-merge (see Figure 2.1(c) for an example with two Chapter 2. Boolean Operations 11 duplicated vertices and Figure 2.1(d) for an example with only one duplicated ver-tex). e d g e - s p l i c e , which splices an interior edge into two border edges. Vertices are repli-cated i f they are shared by more than two border edges (see Figure 2.1(c) and (d)). This is the inverse operation for edge-merge. e d g e - s p l i t , which splits an edge into two edges by inserting a new vertex at the split point, and splits each of the triangles adjacent to the original edge into two smaller triangles (see Figure 2.1(e) for an example). edge-swap, which removes an interior edge e and its two incident triangles, ti and tr, and fills the four-sided hole with another pair of triangles separated by a new edge e'. e' is defined by the two vertices that are originally contained in t\ and tr but not in e. (see Figure 2.1(f) for an example). edge-co l lapse , which collapses an edge into a vertex and collapses the triangles adja-cent to it into edges (see Figure 2.1(g) for an example). 2.1.2 Surface Tessellation Instead of tessellating surfaces with polygons, surfaces in our system are strictly tessel-lated with triangular faces. This allows our algorithm to safely assume the use of planar faces regardless of the numerical accuracy of the face vertices. 2.1.3 Vertex Normals Like most algorithms for computing the Boolean combinations of solids, Chiyokura's algorithm assumes that the surface representation is exact and the orientation of a surface Chapter 2. Boolean Operations 12 (g) Figure 2.1: Topological operations used in our system: (a) make-triangle, (b) add-vertex-to-face, (c) and (d) edge-merge and edge-splice, (e) edge-split, (f) edge-swap, and (g) edge-collapse is impl ic i t ly denned by its geometry. Our system, on the other hand, uses normal vectors to describe the orientation of polygonal surfaces at their vertices. The surface normal everywhere else on the surface is estimated by interpolating vertex normals. These normal vectors are used to determine the surface shading at rendering time. Our system allows a vertex to have multiple normals, one for each triangle that incidents upon it. Each Chapter 2. Boolean Operations 13 vertex normal is represented as a unit vector stored at a face corner. The manipulation of vertex normals is particularly important in our simulated surface blending scheme and is described in more detail in Chapter 3. During topological operations, new vertices may be created and existing vertices may be translated or removed. The normal vectors stored at vertices may need to be computed or adjusted in order to minimize the visual change to the surface. The following is a brief description of how vertex normals may be affected by topological operations. make-triangle: The normal vectors at the three vertices, vp, vq, and vr, are set to the surface normal of the oriented triangle (see Figure 2.1(a)): . _ (Vq ~ Vp) X (Vr - Vp) I K - vp) x (vr - vp)\ add-vertex-to-f ace: A new vertex is introduced into the surface. A common normal vector at this vertex is computed by linearly interpolating the normal vectors stored at the original triangle's vertices. It is shared by all the triangles that are created. The Barycentric coordinates of the new vertex are used as weights in computing the weighted sum of the triangle's vertex normals. The computed vector is then normalized before it is assigned to the new vertex. edge-merge: Vertex normals are not modified in this operation because edge-mergedoes not modify the geometry of the surface and it does not create or destroy any triangle. edge-splice: Vertex normals are not modified in this operation because edge-splicedoes not modify the geometry of the surface and it does not create or destroy any t r i -angle. edge-split: A new vertex v is introduced into the surface. This vertex may take on two different vertex normals: one from the triangle on one side of the edge and one Chapter 2. Boolean Operations 14 from the triangle on the other side. These two vertex normals may be computed by linearly interpolating the vertex normals stored at the end-vertices of the edge. The computed normal vectors are then normalized before they are assigned to the new vertex. edge-swap: Let the input edge be e, the triangles on both sides of e be Â£/ and tr, and the vertices that are contained in t\ and tr be V\ .. .v4 (see Figure 2.2). If the vertex normals on one side of e are the same as the vertex normals on the other side, then the normal vectors at Vi ... v4 may be left unchanged (Figure 2.2(a)). On the other hand, i f e is a crease and the vertex normals at v\ and -y 2 are different on t\ and t r , then the vertex normals at Vi and v2 may need to be approximated after e is swapped (Figure 2.2(b) and (c)). Our system approximates the new vertex normals by weighted sums of the vertex normals stored at the affected vertices. The angles spanned by the triangles at the vertices are used as weights. The computed vectors are then normalized before they are assigned to the new vertices. edge-collapse: Let the input edge be e and the vertices at its end points be v0 and vj. Let the triangles on both sides of e be t\ and t r , and the other triangles that are incident on v0 and Vd be t0 .. .tk-i (see Figure 2.3). During the edge-collapse operation, e is collapsed into its mid-point and ti and tr are collapsed into edges. t0 ... tk-i are stretched as vQ and vj, are translated to a common position and merged into one. The following is how the vertex normals at v0 and vj, are modified in order to preserve smooth surface transitions and surface creases around e. 1. Compute the averaged vertex normal at v0 and the averaged vertex normal at Vd- We shall refer to them as h0 and hd, respectively. Chapter 2. Boolean Operations 15 Figure 2.2: edge-swap and its effect on vertex normals: (a) continuous vertex normal change at e, (b) discontinuous vertex normal change at one of e's end-vertices, (c) discontinuous vertex normal change at both of e's end-vertices 2. Compute the averaged vertex normal at the mid-point of e by linearly inter-polating between n0 and fid- Let this normal vector be hm. 3. Compute the rotation matrix R0 that rotates h0 into nm and compute the Chapter 2. Boolean Operations 16 Figure 2.3: edge-collapse and the affected vertices and triangles rotation matrix Rd that rotates hd into hm. 4. Rotate all vertex normals at v0, wi th the exception of the ones that are to be removed when e is collapsed, by R0. 5. Rotate all vertex normals at Vd, wi th the exception of the ones that are to be removed when e is collapsed, by Rd-The averaged surface normal at a given vertex v is computed based on the weighted average of the vertex normals stored at v. This is described in more detail in Section 4.1.2. 2.2 Computing Boolean Combinations Boolean combinations of polyhedral Brep solids are computed using regularized Boolean operations. Regularized Boolean operations compute the closure of the interior of set-theoretical operations so that lower-dimensional structures such as "dangling" faces, edges and vertices are eliminated [17]. Our solid modeler supports regularized union (U*)J regularized intersection (f)*) and regularized subtraction (â€”*) operations. Our sys-tem also computes the complement of solids. Figure 2.4 illustrates the difference between Chapter 2. Boolean Operations 17 regularized intersection and its set theoretical counterpart. A A n B A n * B Figure 2.4: Set-theoretical intersection vs. regularized intersection [17] Boolean combinations of pairs of solids are computed as follows: union( S o l i d A, S o l i d B ) { 1. Ca l l locateJuncPtsAndLines (A, B) to compute the points and lines for the junction between A and B. 2. C a l l genJuncVerticesAndEdges (A) and genJuncVerticesAndEdges (B) to gen-erate new vertices and edges for the junction points and lines. 3. Ca l l removeUnwantedFaces(A, true) and removeUnwantedFaces(B, false) to splice open each solid along the junction edges and remove the faces that are not included in the final solid. Chapter 2. Boolean Operations 18 4. Ca l l merge ( A , B) to store the remaining faces of B in A and merge the faces along the junction edges. } Figure 2.5 illustrates how the union of two solids is computed using these steps. Each step is described in detail in the subsections that follow. Figure 2.5: Computing the union of two solids The complement of a solid is computed by reversing the orientation of the faces as well as the direction of the vertex normals. The orientation of the faces are reversed by reversing the cyclic order of their vertices. The direction of the vertex normals are reversed through vector negation. The intersection and subtraction of solids may be computed using the union and complement operators according to de Morgan's law: An* B = AU*B A-* B = AXFB Chapter 2. Boolean Operations 19 2.2.1 Computing Junction Points and Lines Junction lines are intersection lines between the two input solids. These lines separate the surface regions to be included in the final solid from the regions to be excluded. The input solids wi l l also be merged into the final solid along these lines. Each junction line is an oriented line segment that connects two points. These points are referred to as junction points. The orientation of each junction line is chosen such that it is counter-clockwise around the surface region to be included in solid A and clockwise around the surface region to be discarded. The opposite classification is true for the surface regions in solid B . The orientations of junction lines are used to help distinguish between surface regions to include and the surface regions to exclude from the final solid. The following information is generated during the computation of junction points and lines: For each junction point: â€¢ its location in 3-space, (x,y,z), â€¢ its associated edges if the junction point falls wi thin the interior of edges in the solids, and â€¢ its associated faces if the junction point falls within the interior of faces in the solids. For each junction line: â€¢ a pointer to the "start" junction point, â€¢ a pointer to the "end" junction point, and â€¢ its associated faces Chapter 2. Boolean Operations 20 This information is obtained by computing the location of junct ion lines followed by classifying the surface regions adjacent to the junct ion lines. Junct ion points and lines are stored in separate tables and are used in subsequent stages for the splitt ing and merging of the input solids. Locating Junction Points and Lines Junction points and lines are computed by intersecting the triangles from solid A with the triangles from solid B. Axis-al igned bounding boxes are used to quickly identify non-intersecting solids and triangles. The bounding box of an object is defined as: 66oa;(object) = [min{x Â£ object}, max{x Â£ object}] x [min{y Â£ object}, max{y Â£ object}]x [min{z Â£ object}, max{z Â£ object}] Bounding boxes are only used to improve the performance of Boolean operations and are not essential to the computation of junct ion lines. Our solid modeler identifies junct ion points and lines using the following algorithm. locateJuncPtsAndLines( S o l i d A, So l i d B ) { 1. If bbox(A) f l bbox(B) then do the following steps. 2. For each pair of triangles, ( t^ , !^) , where IA Â£ A and ts Â£ B: 2.1 If bbox{t,A) F l bbox(tB) then do the following steps. 2.2 Ca l l f i n d JuncLine( t&, ts> I ) to find the junct ion l i ne , / , between and tB-Chapter 2. Boolean Operations 21 2.3 If f indJuncLineO returns true, then insert f s end-points as junction points and / as a junction line into the junction-point and junction-line tables asso-ciated with A and B . } Our system, like the one described by Chiyokura [8], does not handle the case where the volume enclosed in one solid is completely enclosed by another solid. The detection and handling of this case, however, is described in [17]. Junction lines are computed as follows: Bool findJuncLine( Face tA, Face tB, JuncLine 1 ) { 1. Let tA â€” t A and = t B . 2. For each vertex v in t^, test its orientation against the oriented plane, ps, defined by tB- The orientation of v wi th respect to ps can be determined by entering the coordinate of v into the plane equation of ps'-fpi}(xi Vi z) ~ AVBx + BPBy + CPBz + DPB The vertex v is "above" ps i f the result of the plane equation is positive, "below" if the result is negative and "within the plane" i f the result is zero. The coefficients APB,BPB and CPB are the x, y and z components of the outward normal of ts- Dp is computed by setting fPB to zero and substituting the coordinates of one of tfi's vertices into the plane equation. Chapter 2. Boolean Operations 22 3. If all vertices of are "above" or all "below" ps, then t& does not intersect ps s o return false. 4. If al l of the vertices of are within the plane PB, then treat this as a no-intersection case and return false. 5. Repeat steps 2 to 4 but with the role of tA and tg reversed. 6. Let I A be the line where tA intersects ps- The end-points of I A may be computed by intersecting the edges of with ps-7. Let IB be the line where intersects PA-8. Let lint be IA H IB-9. If / int is not empty, then call i s J u n c t i o n L i n e ( l{nt ) to determine if lint is a junction line for 2^ and ts- Otherwise return false. 10. If/, n t is a junction line, then set / to Unt and return true. Otherwise, return false. } Intersections between coplanar triangles are ignored in step 3 because they wi l l ei-ther be eliminated because of the regularity of our Boolean operations, or they wi l l be discovered when other non-coplanar triangles are intersected. Classifying Surface Regions Adjacent to Intersection Lines Intersection lines identified in the previous section are identified as junction lines as follows: Bool i s J u n c L i n e ( J u n c L i n e 1 ) { Chapter 2. Boolean Operations 23 1. Classify the surface regions of solid A adjacent to / as "inside", "outside", or "on the boundary" of solid B. 2. Classify the surface regions of solid B adjacent to / as "inside", "outside", or "on the boundary" of solid A. 3. If / separates two regions of solid A such that one is inside B and one is outside, and if / separates two regions of solid B such that one is inside A and one is outside, then / is a junction line so return true. Otherwise, return false. } Not all intersection lines between IA and ts are junction lines. A n intersection line, lint is only considered a junction line if it separates a surface region to be included in the final solid from a region to be excluded. This can be determined by classifying the surface regions adjacent to / , n t as either "included" or "excluded" from the final solid. Such classification depends on the Boolean operation, the orientations of and tg and how they intersect. The intersection of and i g may be classified into six categories (see Figure 2.6): 1. Face-Face intersection 2. Face-Edge intersection 3. Face-Vertex intersection 4. Edge-Edge intersection 5. Edge-Vertex intersection 6. Vertex-Vertex intersection Chapter 2. Boolean Operations 24 Face-Vertex Vertex-Vertex Figure 2.6: Classifications of different triangle-triangle intersections We are not concerned with the Face-Vertex, Edge-Vertex and Vertex-Vertex intersec-tions as they do not generate any junction line thus no surface classification is necessary. Surface regions adjacent to junction lines may be divided into three types: Chapter 2. Boolean Operations 25 1. Outside the other solid. 2. Inside the other solid. 3. Lying on the boundary of the other solid. We denote these types using the symbols "+", "â€”" and "0", respectively. A surface region adjacent to a junction line, /, may be categorized into one of these types by comparing its orientation with the orientation of the intersecting surface regions from the other solid. Figure 2.7, 2.8 and 2.9 illustrate the different Face-Face, Face-Edge and Edge-Edge intersection scenarios and how the face regions in these scenarios are categorized. These figures are drawn with the viewer looking along the line of intersection, /,- n i. The interiors of the faces are shown with a cross-hatch pattern. Intersections of coplanar faces which do not generate any junction lines are not illustrated. Figure 2.7: Face-Face intersection Surface regions marked with "0" are re-categorized to either "+" or depending on the local relationship between the surfaces. Table 2.2 describes how the regions marked with "0" are re-categorized for the union of solids A and B . The first input case in Table 2.2 corresponds to the scenarios shown in Figure 2.9(i) and (j). The scenario in Figure 2.9(i) contains two pairs of overlapping faces, both of Chapter 2. Boolean Operations Figure 2.8: Face-Edge intersection Chapter 2. Boolean Operations 28 In] Dut Output Solid A Solid B Solid A Solid B (0, 0) (0, 0) ( + , +) (- ,- ) ( + , o ) ( + , o) (+, -) ( + , o ) ( - , o ) (+, +) (-, -) ( - , o ) ( - , o ) ( - -) Table 2.2: Re-categorizing overlapped surface regions for the union of A and B [8] which have the same orientation. This case is resolved by marking the faces from solid A wi th "+" and the faces from the solid B wi th "â€”". This way, the overlap region wi l l only be included in the final solid once. The scenario in Figure 2.9(j) contains two pairs of overlapping faces that have opposite orientations. Because this overlap region is in the interior of the union of solids, it is marked with "â€”" on both solids so that it wi l l not be included in the final solid. The other input cases in Table 2.2 are self-explanatory. A n intersection line l{ni is considered to be a junction line i f it separates a region marked with "+" from an adjoining region marked with "â€”" in both solids. A l l surface regions marked with "+" are included in the union of solids and al l surface regions marked with "â€”" are discarded. 2.2.2 G e n e r a t i n g J u n c t i o n V e r t i c e s a n d E d g e s Junction points and lines are inserted into the operand solids using the topological opera-tions described in 2.1.1. The following is the order in which junction points and junction lines are inserted into a solid. genJuncVerticesAndEdges( S o l i d S ) { 1. For each junction point p in S, call gen JuncVertex( p, S ) to generate a junction Chapter 2. Boolean Operations 29 vertex (see subsection below). 2. For each junction line / in S, call genJuncEdge( /, S ) to generate a junction edge (see subsection below). } Generating Junction Vertices Each junction point in the junction-point table is inserted as a junction vertex for solid A and a different junction vertex for solid B. The following pseudo-code describes how a junction point p is inserted into a solid 5". genJuncVertex( JuncPt p, S o l i d S ) { 1. If a vertex v already exists in S for the junction point, then skip the following steps. 2. If p is located on an edge in 5, then use e d g e - s p l i t to create a vertex for p. 3. If p is located within a face in S, then use a d d - v e r t e x - t o - f ace to create a vertex for p. } Generating Junction Edges Each junction line in the junction-line table is inserted as a junction edge for solid A and a different junction edge for solid B . Junction edges are inserted using a scheme based on Sloan's incremental constrained Delaunay triangulation algorithm [39] which Chapter 2. Boolean Operations 30 forces junction edges to be present in the triangulation. The main difference between our scheme and Sloan's is that our scheme does not require the surface triangulation to be Delaunay and does not enforce the Delaunay condition on unconstrained triangles after constrained edges are inserted. A triangulation is Delaunay if all its triangles meet the Delaunay condition. A triangle meets the Delaunay condition if its circumcircle does not contain any vertex from other triangles. Each junction line is inserted as a constrained edge into a surface region that is locally planar. Note that the planar surface assumption is valid because junction lines are intersection lines between planar faces and are only inserted into planar regions on the surface. The following are the steps involved in inserting a junction line. See Figure 2.10 for an example that demonstrates these steps. genJuncEdge( JuncLine 1, S o l i d S ) { 1. Let the junction line, /, be defined by the vertices u,- and Vj. 2. Let the surface normal of the planar region be n. This can be determined from one of the faces of solid S that is associated with the junction line, /. 3. Find the edges that intersect with V{ â€” Vj as follows: 3.1 Let the list of edges that intersect u,- â€” v3 be / and initialize it to null. 3.2 If one of the incident edges to V{ has v3 as one of its end-vertices, then V{ â€” Vj already exists and it does not intersect with any edge. Otherwise, continue. 3.3 Let the incident triangles to V{ be t0 ... ifc-i- Search the edges in 10 . . . tk~\ for an edge that intersects with V{ â€” Vj. Call this edge e;nt and add it to / . Chapter 2. Boolean Operations 31 3.4 Let the current vertex, v, be one of the end vertices of e,-n< and v' be the other end-vertex such that v, Vi, v' are connected in a counter-clockwise orientation when viewed from the outside. 3.5 Let the triangle with v â€” v' oriented counter-clockwise around its face be ti. If the remaining vertex of ti is Vj, then al l intersecting edges are found. Otherwise continue. 3.6 Examine the remaining two edges of 2/. Let e j n i be the edge that intersects Vi â€” Vj. A d d eint to / . Goto step 3.4. 4. If / is empty, then the constrained edge V{ â€” Vj is already present and we are done. Otherwise, continue. 5. Whi le some unexamined edges sti l l intersect the constrained edge Vi â€” Vj, do the following steps. 5.1 Remove an edge from the front of / . Let this edge be defined by Vk and v\. 5.2 If the two triangles that are incident at edge Vk â€” V[ do not form a strictly convex quadrilateral, then re-insert edge Vk â€” vi at the end of / . Otherwise, apply edge-swap to Vk â€” vi. If the swapped edge st i l l intersects u,- â€” Vj, then the swapped edge is inserted at the end of / . 5.3 Report a runtime error if none of the edges in / may be removed. > Figure 2.10 illustrates the insertion of a constrained edge. The junction edges from solid A and B are paired up and stored in a junction-edge table. Pointers to their Chapter 2. Boolean Operations 32 corresponding junction lines and junction vertices are also stored wi th each junction-edge pair. This table is used during the removal of unwanted faces and the merging of the remaining ones. (c) Figure 2.10: Inserting a constrained edge, u,- - Vj. (a) before edge insertion, (b) search for edges that intersect u,- â€” Vj, (c) steps involved in inserting â€” Vj Chapter 2. Boolean Operations 33 A constraint edge, e, can also be inserted by removing al l the triangles that intersect wi th e and retriangulating the hole with e as one of the edges. This approach, however, is not used in our implementation. 2.2.3 Removing E x t r a Faces Faces that are to be excluded from the final solid are spliced apart from the faces that are to be included as follows. removeUnwantedFaces( S o l i d S, 1. Ca l l s p l i c e ( S, isSolidA, L ) to splice open S along the junction edges and retrieve the list of faces, L, that are adjacent to the junction edges that are to be discarded. 2. Ca l l removeFaces( L ) to remove the faces retrieved by s p l i c e ( ) as well as all the faces that are connected to them. Figures 2.11(c), (d) and (e) illustrate the removal of the unwanted faces. Topological connections between the faces to be included and the faces to be excluded from the final solid are severed as follows. Bool i s S o l i d A ) { } s p l i c e ( S o l i d Bool S, i s S o l i d A , L i s t O f F a c e s L ) { Chapter 2. Boolean Operations :$1 (f) Figure 2.11: Removing the unwanted faces and merging the remaining ones, (a) intersection of faces from the original solids, (b) the affected faces shown with junction lines and the in-clude/exclude classification, (c) retriangulated faces, (d) unwanted faces splice apart from the faces to keep for the final solid, (e) unwanted faces removed, (f) remaining faces merged Chapter 2. Boolean Operations 35 1. Set L to nul l . 2. For each junction edge e in S, do the following steps. 2.1 Let / be the junction line that corresponds to e. 2.2 Let the triangles on both sides of e be t\ and t2. 2.3 Use the orientation of / to identify which of ti and t2 is to be discarded from the final solid. If isSolidA is true, then the triangle with / oriented in the clockwise direction is to be discarded. Otherwise, the triangle with / oriented in the counter-clockwise direction is to be discarded. Insert the triangle to be discarded in L. 2.4 App ly edge-splice to e to separate the triangles on both sides of it. } The faces to be excluded from the final solid are the faces that are connected to the triangles in the list L . They are identified and removed as follows. removeFaces( ListOfFaces L ) { 1. Let L r e m o v e be the list of faces that are to be removed. Initialize L r e m o v e to null . 2. For each triangle t in L, do the following steps. 2.1 If t is marked for removal, then skip the following steps. 2.2 Insert t into L r e m o v e . 2.3 Mark t for removal. Chapter 2. Boolean Operations 36 2.4 Repeat steps 2.1 to 2.4 for each of i 's neighboring faces. 3. Remove al l faces in L r e m o v e . } 2.2.4 Merging Faces Along Junction Edges The remaining faces in solid A and B are merged as follows. merge( S o l i d A, S o l i d B ) { 1. Insert all the faces of B into A. 2. For each pair of junction edges, (e^, eg), in the junction-edge table do the following. 3. App ly edge-merge to merge and eg. } The Boolean operation is complete when solids A and B are merged into one along the junction edges. Our algorithm for computing Boolean combinations of boundary represented solids is the same as Chiyokura's, wi th the exception that al l faces are strictly triangular. 2.3 Numerical Problems The algorithm described in the previous section computes the Boolean combinations of solids through a sequence of steps, many of which assume the use of exact arithmetic. These steps can fail if finite-precision floating arithmetic is used instead. The numerically sensitive computations are: Chapter 2. Boolean Operations 37 â€¢ Testing the orientation of points with respect to planes during the computation of junction lines. â€¢ Determining the intersection between collinear line segments during the computa-tion of junction lines. â€¢ Determining the relative orientation of surfaces during the classification of surface regions adjacent to junction lines. â€¢ Determining if two coplanar line segments intersect during the generation of junc-tion edges. â€¢ Determining if four coplanar points form a strictly convex quadrilateral during the generation of junction edges. The following chapter addresses the problem of using finite-precision floating point arithmetic in the computation of Boolean operations. Chapter 3 Robustness One of the main problems with combining Brep solids is robustness. Like many geomet-ric algorithms, the algorithms for combining Brep solids often assume the use of exact arithmetic. In practice, exact arithmetic is often considered to be too expensive and is substituted with finite precision floating-point arithmetic. As a result, Boolean opera-tions on valid inputs can fail due to numerical imprecisions. This chapter reviews the problem with using floating-point arithmetic and describes how Boolean operations are carried out robustly in our system using a mix of floating-point and exact arithmetic. 3.1 Problem with Floating-Point Arithmetic During the Boolean combinations of Brep solids, the intersections between input solids are computed and are used to derive the topology for the resulting solids. These intersections, when computed using floating-point arithmetic, are inexact and may generate ambiguous or inconsistent topology. This is sometimes the cause for Boolean operations to fail. One way to deal with the inexactness of floating-point arithmetic is to treat numbers that are sufficiently close to zero as equal to zero. The equality of two numbers, for 38 Chapter 3. Robustness 39 instance, can be tested by taking the difference of the two numbers and checking to see if it is less than some predefined tolerance, e. This approach, however, is not robust because this relational operation is not transitive. For instance, given three numbers, a, b and c with the following relationships: 6 = c + 0.75e, c = 6 + 0.75e Then, \b â€” a\ = 0.75e < e â€”> b â€” a, and |c - 6| = 0.75e < e -Â» c = b, but \c â€” a\ = 1.5e > e â€”Â» c ^ a. A more robust way to compute surface intersections is therefore required. 3.2 Making Numerical Computations Robust Our system ensures the unambiguous and consistent derivation of surface topology by using the real package of the Library of Efficient Datatypes and Algori thms ( L E D A ) [24]. This package provides a C- f - f class of algebraic real numbers which we shall refer to as " L E D A - r e a l " . L E D A - r e a l guarantees that relationships between arithmetic expressions are computed exactly using the =, ^ , <, >, < and > operators. Intersections computed using L E D A - r e a l can then be used to derive topology reliably. Computing with L E D A - r e a l numbers, however, is more expensive than computing with floating-point numbers and this cost accumulates wi th the number of arithmetic operations. In the interest of efficiency, our system approximates all L E D A - r e a l numbers by floating-point numbers after pairs of solids are successfully combined. Approximat ing L E D A - r e a l numbers by floating-point numbers can introduce small perturbations to the geometry of solids. Triangles that are extremely narrow may fold onto their neighbours under such perturbation, thus invalidating the representation of Chapter 3. Robustness 40 the solid. Our system provides a scheme to identify and reduce the number of extremely narrow triangles. The rest of this chapter is organized as follows. First , the structure of L E D A - r e a l and the cost of using it is discussed. This is followed by a description of how L E D A -real is incorporated in our solid modeler. The conversion from L E D A - r e a l numbers to floating-point numbers and the identification and removal of narrow triangles are then described. 3.2.1 Structure of LEDA-real and the Cost of Using It Each L E D A - r e a l number, x, contains three components: â€¢ a double precision floating-point (double for short) approximation x' â€¢ a relative error bound on the double approximation e x, and â€¢ an expression tree which describes the L E D A - r e a l numbers from which x is com-puted and the arithmetic operations that are used to combine them. The double approximation and the relative error bound are used as floating-point filters to filter out cases where expensive computations using arbitrary-precision arithmetic are not necessary. The expression tree, on the other hand, is used when floating-point arithmetic fails to guarantee the correct answer and arbitrary-precision arithmetic must be used. Apply ing an arithmetic operation to a pair of L E D A - r e a l numbers, x and y, involves: 1. computing the double approximation of the result using x' and y', 2. computing the relative error bound for the result using x', y', ex and ey, and Chapter 3. Robustness 41 3. storing the operands and the operation in the result's expression tree. The following steps are used when two L E D A - r e a l numbers, x and y, are compared using the =, <, >, < and > operations. 1. Let z â€” x â€” y. 2. If ez < 1 then the sign of z' is the same as the sign of z and it can be used to determined the relationship between x and y. Otherwise continue. 3. Evaluate the expression tree using arbitrary precision arithmetic. Increase the precision of the computation incrementally unt i l e2 is small enough to determine the sign of z. Computing with L E D A - r e a l requires significantly more computational overhead than computing with floating-point numbers. The overhead for arithmetic operations includes computing the relative error bound and allocating new tree nodes for the operands. This overhead is fixed for each arithmetic operation and does not depend on the the size of the expression trees in the operands. Evaluating relational operations for L E D A - r e a l , on the other hand, can have a variable amount of computational overhead. Relational operations are relatively cheap to compute if the intervals spanned by the operands, [(1 - ex)x,(l + ex)x] and [(1 - ey)y, (1 + ey)y], are sufficiently far apart. If the intervals overlap, then the cost of evaluating the relational operation wi l l depend on the double approximation of the operands, the size of their relative error bounds, and the depth of their expression trees. In general, the relative Chapter 3. Robustness 42 error bound of a number and the depth of its expression tree increase as the number of arithmetic operations used in generating it increases. As a result, L E D A - r e a l should only be used for short computations so that the increase in computational overhead may be justified by the increase in robustness. 3.2.2 Computing with LEDA-real The numerically sensitive computations described in Section 2.3 are al l based on geo-metric information stored in the vertices of the input solids. The coordinates of these vertices are ini t ia l ly stored as double precision floating-point numbers. These coordinates are assumed to be exactly represented and may be compared exactly. The construction of bounding boxes and the test for overlaps between bounding boxes are al l computed using floating-point arithmetic. These computations only involve comparing exactly rep-resented numbers and may be done exactly without the use of L E D A - r e a l . The coordinates of face vertices are converted from floating-point to L E D A - r e a l when bounding box tests fail to classify pairs of faces as non-intersecting. The intersection of triangles and the insertion of junction edges can then be computed reliably using geometric data stored in L E D A - r e a l numbers. The coordinates of vertices are converted from L E D A - r e a l back to floating-point once the Boolean combination is computed. This prevents the metadata stored in vertex coordinates from accumulating exponentially and limits the computational overhead of using L E D A - r e a l . Chapter 3. Robustness 43 3.2.3 Problem with LEDA-real to Floating-point Conversion Approximat ing L E D A - r e a l coordinates with floating-point numbers usually reduces the precision of the numbers. This can introduce small perturbations to the geometry of the solids and turn extremely narrow triangles into triangles that overlap with their neigh-bours. The following is a description of how extremely narrow triangles are generated and how numerical perturbations may affect these triangles. One of the steps in computing the Boolean combinations of solids is the insertion of junction points and junction lines into the surfaces of solids. During this step, triangles that are split by junction lines are subdivided into smaller triangles. Some of these triangles may contain vertices that are nearly collinear. The vertices of these triangles may be perturbed by the numerical approximation and may cause the triangles to overlap with one or more neighboring triangles (see Figure 3.1). Figure 3.1: Modification to a narrow triangle under perturbation: the triangle "folds over" neighboring triangles. Overlapping triangles are undesirable because our Boolean combination algorithm requires the surfaces of solids to be free of self-intersections. Boolean operations may fail if overlapping triangles are not removed from solid models. Our system provides a scheme to identify and reduce the number of extremely narrow, Chapter 3. Robustness 44 or "skinny", triangles. This is described in the sections below. 3.2.4 Skinny Triangle Identification Skinny triangles are detected by comparing their aspect ratios against a user defined threshold, a m a x . The aspect ratio, a , of a triangle is the ratio between the square of its perimeter and its area: perimeter2 a = area A triangle is considered skinny if its aspect ratio, a, is greater than a m a x . The skinny triangles in a solid model S are identified and stored in a list Ls as follows. i d e n t i f y S k i n n y T r i a n g l e s ( S o l i d S, double a lphaMax, L i s t O f F a c e s Ls ) { 1. Let Ls = Ls and initialize it to an empty list. 2. Let alphaMax be a m a x . 3. For each triangle, t, in S do the following. 4. Compute the aspect ratio of t. Ca l l it a. 5. If a > a m a x , then add t to Ls. } The skinny triangles identified can then be removed using r educeNumSkinnyTr i ang l e sO described below. Chapter 3. Robustness 45 3.2.5 Skinny Triangle Reduction Our system uses edge-collapse and edge-swap to remove skinny triangles. Figure 3.2 shows examples of how this may be carried out. (b) Figure 3.2: Skinny triangle (shown in gray) removed using (a) edge-collapse and (b) edge-swap A cost minimizat ion scheme is used to choose the operators for removing skinny triangles. The removal of triangles based on cost minimizat ion is a technique that is used in mesh decimation schemes [19] [20] [25]. Unlike general mesh decimation schemes, our scheme removes only skinny triangles. The cost of applying a topological operation is measured by a set of cost attributes. Chapter 3. Robustness 46 These attributes reflect the amount of structural and visual change an operation may introduce to a model. The cost attributes we have selected are: aspect ratio cost which measures the total increase in the aspect ratio of al l the tr i-angles that are affected by an operation. This is computed by: 1. Identify the k triangles that are affected by the operation, t0 .. .tk-i-2. Measure the aspect ratios of t0 â€¢ â€¢ â€¢ tk-\ before the operation, a 0 . . . ccfc-i-3. Measure the aspect ratios of t0 ... tk-i after the operation, a'0 ... cÂ»4-i-4. Compute the aspect ratio cost as: fc-i aspect ratio cost = J^(o: '- â€” ctj) t=0 volume cost which measures the change in volume caused by an operation. For edge-collapse, the affected triangles, t0.. .tk-i, may sweep out a volume as the end-vertices of the input edge are collapsed into the mid-point of the edge. This volume may be computed by summing the tetrahedra swept out by t0 â€¢ â€¢ â€¢ tk-i as the input edge is collapsed. For edge-swap, the volume cost is measured by the volume enclosed in the tetra-hedron defined by the four vertices contained in the two affected triangles. face orientation cost which measures the maximum change in face orientation amongst all the triangles that are affected by an operation. This is computed by: 1. Identify the k triangles that are affected by the operation. Chapter 3. Robustness 47 2. Compute the change in unit normals for each triangle, ti, by taking the dot product of the unit normals before and after the operation. Let us call this dot product, hi â€¢ h^. 3. Compute the face orientation change, Ah by rescaling the dot product: A n , = ( 1 ~ h i â€¢ ^ 2 4. Compute the face orientation cost as: face orientation cost = max{Ah0, . . . , A n n } surface normal cost which measures the max imum change in surface normal amongst all the triangles that are affected by an operation. This cost is computed with the assumption that the surface normal at any point on the surface may be determined by interpolating the surface normals defined at the vertices. The estimation of surface normal is described in more detail in Section 4.1.2. For edge-swap, the surface normal cost is zero if the vertex normals are the same on both sides of the edge. Otherwise, the cost is one. For edge-collapse, the surface normal cost is measured by the change in surface normal at the mid-point of the input edge after the edge-collapse operation. This is computed as follows: 1. Let the mid-point of the edge be m. 2. Identify the k triangles that are affected by the operation, to â€¢ â€¢ - tk-i-3. Compute the averaged surface normal at the middle of the to-be-collapsed edge. Ca l l this h. Chapter 3. Robustness 48 4. For each of the affected triangles, tf. 4.1 Project ra onto the plane in which Â£; is embedded. Let's call this projected point ra;. 4.2 Compute the Barycentric coordinates of m; wi th respect to the vertices in t{. 4.3 Interpolate the normal vectors at the vertices of using the Barycentric coordinates of m,- as weights. Let's call this interpolated surface normal hi. 4.4 Compute the difference between h and n,- by taking their dot product. 4.5 Compute the change in surface normal by rescaling the dot product: self-intersection cost which is zero if the operation does not cause the surface to self-intersect and one if it does so. This is determined by examining the topology of the neighborhood affected by the operation. The cost attributes of each operation are compared against a set of user-defined cost thresholds. These thresholds ensure that the amount of structural and appearance change caused by an operation is not exceedingly high. A n operation is only carried out if all of its cost attributes are below the thresholds. The number of skinny triangles is reduced as follows: 2 5. Compute the surface normal cost as: surface normal cost = max{Aho, . . . , A ^ - i } Chapter 3. Robustness 49 reduceNumSkinnyTr iang les ( L i s t O f F a c e s L s , Cos tThre sho lds T ) { 1. Let Ls = Ls. 2. Let NS: the number of skinny triangles removed in the previous iteration, to a non-zero number (1). 3. Do steps 3.1 to 3.7 for each triangle, t, in Ls, unt i l Ls is empty or Ns = 0: 3.1 Remove t from Ls. 3.2 Compute the costs of collapsing each of the edges of t. 3.3 Compute the costs of swapping each of the edges of t. 3.4 If none of the costs is below T then put t back at the end of Ls. Otherwise continue. 3.5 Amongst all the edge-operator combinations that cost less than T , pick the combination with the lowest volume cost. 3.6 A p p l y the selected operator to the associated edge. 3.7 Increment Ns by one. } Skinny triangles that cannot be removed without significant degradation to the model's structure and appearance may not be removed by r educeNumSkinnyTr i ang l e sO . This is a l imitat ion of our proposed algorithm. Chapter 4 Blending Surface Junctions This section describes how smooth surface transitions are generated at the junctions between solids. It begins with an introduction to some of the terminology commonly used in the surface blending literature. This is followed by a description of how blending is carried out through the interpolation of surface normals. Blending is an operation that creates smooth transitions between adjacent surfaces. It is often used to smooth out sharp edges and corners at the junctions where surfaces intersect. The original surfaces that are to be blended are referred to as the base surfaces. These surfaces are typically blended by cutting away a region around the surface junction and replacing it wi th a smooth interpolating blend surface. The boundary curves which connect the base surfaces to the blend surface are referred to as trimlines. One way to obtain trimlines is to treat the junction curve between the base surfaces as a spine and offset it along the base surfaces by a fixed distance. Most blending literature is concerned with computing blend surfaces once the trimlines are found and the region between them is removed [16] [44] [45] [35] [46]. 50 Chapter 4. Blending Surface Junctions 51 Unlike most work in surface blending, our blending scheme does not modify the surface geometry during the blending process. Instead, our blending scheme gives the illusion of modified surface shape by changing the surface normals. This approach relies on our ability to extract shape information from the way objects reflect light. The same principle is used in bump mapping [3], where the il lusion of bumps and dents are created using texture maps whose values are used to modify the surface normal. In the case of polyhedral models, the surface normal that is perturbed by bump maps is often computed by linearly interpolating vertex normals. B u m p mapped surfaces, unfortunately, are relatively expensive to render and are difficult to display at interactive rates. Advances in hardware accelerated bump mapping [33][11], however, should make the interactive display of bump mapped surfaces possible in the near future. Instead of using bump maps, our solid modeler modifies the surface normal by directly manipulating the normal vectors stored at mesh vertices. Our surface blending algorithm is designed to simulate smooth surface transition at the junction between pairs of solids. This is achieved by locating the trimlines on both sides of the junction and modifying the surface normals within the region between them. The user may interactively specify the extend of the blend region before blending occurs by varying the distance between the trimlines and the junction. We refer to this as the range of the blend, dmax. The surface region less than dmax from the junction is referred to as the blend region. Before blending can be applied, the junction between two solids must first be com-puted through one of the binary Boolean operations. The surface normals within the blend region are then modified as follows (see Figure 4.1): blend( ListOfJuncEdges L ) Chapter 4. Blending Surface Junctions 52 1. C a l l average JuncVert ( L ) to average the normal vectors stored at the junction vertices. 2. Ca l l assocJuncSampC L , dmax, Vuend ) to identify the list of vertices within the blend region, Vbiend, a n d associate each vertex v wi th a point on the junction, Pj(v). 3. C a l l assocTrimlineSamp( Vbiend> dmax ) to associate each vertex v in Vbiend wi th a point, pt(v) on the closest tr imline. 4. Ca l l interpNormal ( Vbiend ) to compute the new normal vector for every vertex v in Vbiend by linearly interpolating between the normal vectors at pj(v) and pt(v). 5. Ca l l improveSamp( L , dmax ) to create new vertices i f the surface normals are not sufficiently sampled by the existing ones. } Chapter 4. Blending Surface Junctions Figure 4.1: Simulating surface blending by surface normal interpolation Chapter 4. Blending Surface Junctions 54 The rest of this section starts by describing some of the basic operations that are used during the surface blending process. The averaging of surface normals at junct ion vertices is then described, followed by the association of vertices with points on the junct ion and tr imlines, and the averaging of vertex normals within the blend region. Final ly, the creation of new vertices within and on the boundary of the blend region is described. 4.1 Basic Operations Our blending scheme relies heavily on two sets of operation: â€¢ the measure and traversal of distances along surface paths, and â€¢ the estimation of surface normals at vertices, on edges and in faces. 4.1.1 Measuring and Traversing Distances Along Constrained Surface Paths During the blending process, distances measured along the surface are used as weights for interpolating surface normals. Samples of surface normals at specific distances away from given surface points also need to be computed. As a result, it is necessary to have a way to measure and traverse distances along the surface. Our blending scheme measures distances along the surface by measuring the length of piecewise linear paths that are constrained to lie on the surface. The following is a description of how these paths are defined and how they may be measured and traversed. Given two points u and v on a closed and connected surface S, one may travel from u to v along some path T that lies entirely on S. The length of V depends on its trajectory. One way to specify this trajectory is to require T to be the shortest path between u and v. F ind ing a path that meets this requirement is non-tr ivial as it involves solving the Chapter 4. Blending Surface Junctions 55 discrete geodesic problem [28]. A simpler approach is to constrain V to lie on a plane P that contains u, t>, and an extra point un which is u translated by its unit normal vector hu (see Figure 4.2). Figure 4.2: Constraining a path to lie on a sphere S and a plane P Assuming that S and P intersect in a single closed loop, then one may travel from u to v through two different paths that start off in opposite directions. A unique path between u and v can then be specified by indicating the in i t ia l direction of the constrained path. If S and P intersect in more than one closed loop and u and v lie on disjoint loops, then the scheme just described would fail to find a constrained path between u and v. In practice, we rarely observe this problem especially when the surface region between u and v is free of surface creases. Our surface blending scheme measures the distance between surface points by mea-suring the length of constrained surface paths between them. The starting direction for the path from point u to point v is selected by choosing the direction that is more collinear with uv. If uv is parallel to n u , then both paths are traversed and the length of Chapter 4. Blending Surface Junctions 56 the shortest path is used as the distance. Besides measuring the distance between surface points, constrained surface paths can also be traversed in order to sample surface points at known distances away from a given surface point, u. In this case, the plane P may be specified by Â« , t i n and the point ut which is u translated by the unit tangent vector t which specifies the in i t ia l heading of the surface path. 4.1.2 Estimating Surface Normals During the blending process, each vertex v wi thin the blend region is associated with two points: one point on the junction curve, Pj(v), and another point on the closest tr imline, Pt(v). The new normal vector for v is then computed by interpolating between the surface normal at pj(v) and pt(v). The surface normal at pj(v) and pt(v), however, may not be explicit ly defined and may need to be computed using the geometry and vertex normals stored in their neighborhoods. The following is a description of how the surface normals at Pj(v) and pt(v) may be estimated i f they lie at vertices, on edges or in faces. Surface Normal at a Vertex Depending on the local surface shape, the surface normal at a given vertex v may or may not be uniquely defined. If the neighborhood of v is smooth, then the surface normal at v is uniquely defined and all faces incident on v would share the same surface normal at v. On the other hand, if v lies on a crease or a corner of the surface, then multiple surface normals wi l l be defined at v because the surface orientation varies discontinuously at v. If the surface normal is uniquely defined at v, then it does not need to be estimated and can be returned immediately. If multiple normals are defined at v, then the surface Chapter 4. Blending Surface Junctions 57 normal at v is computed as the weighted average of the normals that are defined at v. We utilize the weighting scheme suggested by Thurmer and Wi i th r ich [43]. This scheme uses the angles of the incident face corners as weights. Instead of estimating the normal at v by weighting the normals of the incident faces, we compute the estimate by weighting the vertex normals that are associated with the incident faces. k-l navg{v) = ~2)20i(v)hi(v) i=0 A / \ riaVg(y^j \navg(v)\ where: â€¢ Oi(v) is the angle of one of k face corners incident at u, and â€¢ hi(v) is the vertex normal stored at the corresponding face corner at v. Surface Normal on an Edge Depending on the local surface shape, the surface normal at a point p within an edge e may or may not be uniquely defined. If e is a crease in the model, then the surface normals would be different on different sides of the edge and two different normals are defined at p. O n the other hand, if the surface normal is the same on the faces adjacent to e, then a unique normal is defined at p. The surface normal at p is computed as follows: 1. Let the faces on both sides of e be t\ and tr. 2. Estimate the normal at p on ti by linearly interpolating between the normals stored at the end-vertices of e. Ca l l this normal hi. Chapter 4. Blending Surface Junctions 58 3. Estimate the normal at p on tr by linearly interpolating between the normals stored at the end-vertices of e. C a l l this normal nr. 4. Compute the final normal estimate as: hi + hr np \ht + hr\ Surface Normal in a Face The surface normal at a point p within a face / is computed as follows: 1. Compute the Barycentric coordinates, (a,b,c), of p wi thin / and label the corre-sponding vertices as va, vb and vc. 2. Use the Barycentric coordinates as weights to weight the vertex normals stored at the corners of / , ( n a , hb and hc)\ aha + bhb + chc \aha + bhb + chc\ 4.2 Averaging the Surface Normals at Junction Vertices The surface normal stored in junction vertices are averaged as follows: averageJuncVert( ListOfJuncEdges L ) { 1. For every vertex v contained in L, do the following. 2. Use the vertex normal estimation scheme described above to compute the averaged vertex normal for v. Chapter 4. Blending Surface Junctions 59 The averaged surface normal along the junction wi l l then be computed based on these averaged vertex normals. 4.3 Associating Vertices with Points on Junction and Trimlines The vertices within the blend region must first be identified before their associated vertex normals may be modified. Vertices are considered to be wi thin the blend region if they are less than a distance dmax away from the surface junction. They are discovered by walking the surface around the junction and measuring the shortest distance between the vertices and the junction itself. The following scheme is used to both discover the vertices in the blend region as well as associate them with their closest junction points. assocJuncSamp( Lis tOfJuncEdges L , double d_max, L i s t O f V e r t i c e s Vblend ) { 1. Let Vbiend = Vblend and initialize it to an empty list. Let dmax â€” d_max. 2. Do the following steps for every junction edge e in L. 3. Let Ve be the set of vertices that we have examined around e. Ve is ini t ia l ly empty. 4. Start at one of the vertices of e. Ca l l the current vertex v. 5. If v is not on the junction, then do steps 5.1 to 5.3. Otherwise, set d to zero and continue with step 6. 5.1 F i n d the point on e with the shortest Euclidean distance to v. Let this point be p. Chapter 4. Blending Surface Junctions 60 5.2- Measure the surface constrained distance between v and p. Let this distance be d. 5.3 Set u's associated junction point, Pj(v), to p if d is the shortest distance between v and the junction edges visited so far. 6. A d d v to Ve. 7. If d < dmax then: 7.1 A d d v to Vbiend i f v is not a junction vertex. 7.2 For each of u's neighboring vertices, ut-, repeat steps 5 to 7 for if it is not already in Ve. } The vertices in the blend region are associated with points on the trimlines as follows: assocTrimlineSamp( L i s t O f V e r t i c e s Vb iend , double d_max ) { 1. Let Vbiend = Vbiend . Let dmax = d_max. 2. Do the following steps for each vertex v in K / e n d -2.1 Let pj(v) be the junction point that is associated with v. 2.2 Traverse the surface from pj(v) to a point p on the tr imline by walking a distance dmax from p in the direction towards v. Set u's associated trimline point, pt(v) to p. Chapter 4. Blending Surface Junctions 61 4.4 Modifying Vertex Normals The normal vectors for the vertices within the blend region may be computed once their associated points on the junction and trimlines are found. The modified surface normals are computed by linearly interpolating the surface normals at the junction and those at the trimlines. This is described in the following pseudo-code. interpNormal( Vbiend ) { 1. Let Vbiend = Vbiend. 2. Do the following for every vertex, v, in Vbiend-2.1 Let the distance between v and its associated junction point Pj(v) be dj and the distance between v and its associated tr imline point pt(v) be dt. Then, the new normal vector for v may be computed as: â€ž _ dtfij{v) + djht(v) \dthj(v) + d3ht(v)\ where: â€¢ hv is the new normal for u, â€¢ fij(v) is the normal vector estimated at Pj(v), and â€¢ ht(v) is the normal vector estimated at pt(v). } The original normal vectors stored at the vertices within the blend region are lost during interpNormal(). Chapter 4. Blending Surface Junctions 62 4.5 Improving The Sampling of Surface Normal W i t h our polyhedral surface representation, surface normals are only explici t ly defined at mesh vertices. In order for the surface normal to vary continuously inside the blend region and remain unchanged outside of it, the surface normal must be sufficiently sampled by vertices within the blend region and on its boundary. Failure to do so would result in surface artifacts caused by unsmooth changes in surface normals wi thin the blend region as well as unexpected modifications to surface normals outside the blend region. Our algorithm considers the blend region to be sufficiently sampled i f the normal vector at every sampling point p within the blend region may be computed using two different computations with l i t t le discrepancy. These two different computations are: the normal estimation scheme that is based on averaging the normal vectors stored at the vertices, and the normal computation scheme that is based on interpolating the surface normal sampled at the trimlines with the surface normal sampled at the junction. New vertices are introduced at sampling points if the two normal vector estimates differ by more than a threshold, Ahmax. This algorithm is summarized by the following pseudo-code. improveSampC ListOfJuncEdges L, double d_max ) { 1. Let dmax â€” d_max. 2. For every junction edge e in L, do the following. 3. Walk the neighborhood within dmax around e (see assocJuncSampO ). 4. For every edge enei9h wi thin this neighborhood, do steps 3.1 to 3.6. Chapter 4. Blending Surface Junctions 63 3.1 Select a sampling point p on eneiah-3.2 Estimate the surface normal at p by linearly interpolating the vertex normals at the end-vertices of eneiah- Ca l l this ha. 3.3 Associate p wi th its closest point on the junction, Pj(p), and its closest point on the closest tr imline, pt(p). 3.4 Estimate the surface normal at p by linearly interpolating the surface normals at pj(p) and pt(p)- Ca l l this hb. 3.5 Compute the normalized difference between ha and hb as: A . (l-ha-hb) A n = 2 3.6 Insert a sampling point at p using edge-split if A n > Ahmax. } Edges are sampled at different points, depending on where their end-points and mid-points are located wi th respect to the blend region. Table 4.1 describes how different edges are sampled differently. Edge end-points Edge mid-point Edge sampled at In In In mid-point In In Out mid-point In Out In /Out intersection point where the edge intersects the boundary of the blend region Table 4.1: Locations on edges to sample surface normals. A point is "In" if it is within the blend region and "Out" if it is outside. Chapter 4. Blending Surface Junctions 64 Edge sampling points are associated with points on the junction curve and the t r im-lines using the scheme described in assocJuncSampO . The distance measuring and normal interpolating schemes used for vertices are also applicable for the edge sampling points. New vertices may then be introduced at sampling points that have large discrep-ancies between their surface normal estimates. These vertices are inserted into the mesh using the edge-sp l i t operation. The surface normals computed from samples at the junction and trimlines are then stored at these new vertices. Chapter 5 Implementation and Results 5.1 Implementation A prototype solid modeler was written in C + + on a s ing le -CPU Sun U l t r a 80 ( U l t r a S P A R C -II 450 M H z C P U ) . This application allows the user to: â€¢ load and save polyhedral solid models to Wavefront O B J files, â€¢ apply affine transforms (translation, rotation and scaling) to solid models, â€¢ apply Boolean operations to pairs of models, and â€¢ blend the junctions betweens solids combined with Boolean operations. In addition, our prototype system provides l imited support for the generation of new models by sweeping existing models along piecewise linear paths. This feature is provided to demonstrate the usefulness of sweeping in interactive sculpting. A user may define sweep paths as curves that are drawn on top of selected models. The silhouette curves of tool models can then be swept along the sweep paths to create generalized cylinders that 65 Chapter 5. Implementation and Results 66 may be used as solid models. These models may then be combined with other models using Boolean operations. The sweeping algorithm used i n our system assumes that the sweep surfaces are free from self-intersections. The removal of self-intersections in sweep surfaces is beyond the scope of our system. Our prototype system makes extensive use of data structures from the L E D A library, the Computational Geometry Algor i thm Library ( C G A L ) [6] and the Standard Template Library ( S T L ) . These data structures are used for storing the geometry and topology of polyhedral models as well as for keeping track of intermediate data during Boolean operations and surface blending. The display of polyhedral models is implemented using O p e n G L and G L U T and the user interface is constructed using the Mic ro User Interface ( M U I ) [29]. 5.2 Results We performed three types of tests on our solid modeling system: tests for the robustness of Boolean operations, tests for the effectiveness of our surface blending algorithm, and tests for the usefulness of these features. 5.2.1 Robustness Our system ensures robustness by using L E D A - r e a l for computing geometric relation-ships and a skinny-triangle removal scheme for removing numerically unstable triangles. We conducted two sets of tests to demonstrate the usefulness of these two methods: the intersection of convex polyhedra for testing the usefulness of L E D A - r e a l , and the inter-section of models before and after skinny-triangle removal for testing the usefulness of our skinny-triangle removal scheme. Chapter 5. Implementation and Results 67 Intersection Test One test often used in testing the robust combination of boundary-represented polyhedral solids is the intersection test [12] [17]. This test is conducted by intersecting convex polyhedra wi th slightly rotated versions of themselves. These polyhedra are generated by intersecting randomly rotated unit cubes. We conducted this test using four convex polyhedra each with about 800 faces (see Figure 5.1). The rotation applied to each test polyhedron was between 10~ 8 degrees to 1 degree. We intersected each polyhedron with a rotated version of itself in our prototype system and compared it wi th results obtained using M a y a version 2.5 (running on a s ingle-CPU R10000 SGI Impact 10000) and 3D Studio M a x version 2.5 (running on a s ingle-CPU Pentium-II 400 M H z P C ) . Our system was successful in computing all the intersection cases. Maya , on the other hand, failed in all of these tests. 3D Studio M a x was successful in some but not all these tests. In the case of Maya , the failure resulted with the return of the empty set. In the case of 3D Studio M a x , the failure resulted in the unexpected termination of the application. Tables 5.1, 5.2, 5.3 and 5.4 show the results from our robustness tests using the four test polyhedra. Chapter 5. Implementation and Results 68 Test Polyhedron C Test Polyhedron D Figure 5.1: Polyhedra used during the robustness test Chapter 5. Implementation and Results 69 Rot. Angle (degrees) Our system Maya 3DSM i o - 8 Succeeded, 34 s Failed, < 1 s Succeeded, 4 s i o - 7 Succeeded, 34 s Failed, < 1 s Succeeded, 4 s l f r 6 Succeeded, 36 s Failed, < 1 s Succeeded, 4 s i r r 5 Succeeded, 32 s Failed, < 1 s Succeeded, 4 s 10" 4 Succeeded, 30 s Failed, < 1 s Failed, 14 s i o - 3 Succeeded, 28 s Failed, < 1 s Failed, 14 s IO" 2 Succeeded, 24 s Failed, < 1 s Failed, 10 s 10-1 Succeeded, 20 s Failed, < 1 s Failed, 4 s 1 Succeeded, 15 s Failed, < 1 s Succeeded, 3 s Table 5.1: Robustness tests using test polyhedron A Rot. Angle Our system Maya 3DSM (degrees) 10-8 Succeeded, 35 s Failed, < 1 s Succeeded, 6 s IO" 7 Succeeded, 38 s Failed, < 1 s Succeeded, 6 s 10-6 Succeeded, 41 s Failed, < 1 s Succeeded, 6 s IO" 5 Succeeded, 36 s Failed, < 1 s Succeeded, 6 s IO" 4 Succeeded, 37 s Failed, < 1 s Failed, 16 s IO" 3 Succeeded, 34 s Failed, < 1 s Failed, 19 s 10-2 Succeeded, 26 s Failed, < 1 s Failed, 11 s 10-1 Succeeded, 26 s Failed, < 1 s Succeeded, 4 s 1 Succeeded, 20 s Failed, < 1 s Succeeded, 4 s Table 5.2: Robustness tests using test polyhedron B Chapter 5. Implementation and Results 70 Rot. Angle Our system Maya 3DSM (degrees) i o - 8 Succeeded, 40 s Failed, < 1 s Succeeded, 7 s i o - 7 Succeeded, 38 s Failed, < 1 s Succeeded, 7 s i o - 6 Succeeded, 38 s Failed, < 1 s Succeeded, 7 s 10-5 Succeeded, 35 s Failed, < 1 s Succeeded, 7 s 10-4 Succeeded, 34 s Failed, < 1 s Failed, 22 s 10-3 Succeeded, 31 s Failed, < 1 s Failed, 24 s IO" 2 Succeeded, 26 s Failed, < 1 s Failed, 10 s IO" 1 Succeeded, 23 s Failed, < 1 s Failed, 4 s 1 Succeeded, 17 s Failed, < 1 s Failed, 4 s Table 5.3: Robustness tests using test polyhedron C Rot. Angle (degrees) Our system Maya 3DSM 10" -8 Succeeded, 39 s Failed, < 1 s Failed, 11 s i o--7 Succeeded, 42 s Failed, < 1 s Failed, 11 s 10" -6 Succeeded, 44 s Failed, < 1 s Failed, 11 s i o--5 Succeeded, 39 s Failed, < 1 s Succeeded, 10 s 10" -4 Succeeded, 38 s Failed, < 1 s Failed, 29 s io--3 Succeeded, 36 s Failed, < 1 s Failed, 35 s 10" -2 Succeeded, 38 s Failed, < 1 s Failed, 14 s 10" -1 Succeeded, 27 s Failed, < 1 s Failed, 5 s 1 Succeeded, 20 s Failed, < 1 s Failed, 4 s Table 5.4: Robustness tests using test polyhedron D Chapter 5. Implementation and Results 71 To evaluate the performance of our system, we compare the execution times for Boolean operations in our system versus the execution times in 3D Studio M a x . We are aware of the difference between the platform used by these two programs. The S P E C (Standard Performance Evaluation Corporation) ratings for the U l t r a 80 and the P C we used are reasonably similar [41]: C P U SPECint_base95 SPECfp.base 95 450 M H z U l t r a S P A R C - I I (in the U l t r a 80) 400 M H z Pentium-II (in the P C ) 19.7 15.8 16.2 15.8 W i t h the higher S P E C ratings on the Ul t r a 80 but the poorer performance, our system is at least 3 to 9 times slower than 3D Studio M a x running on the P C (refer to Tables 5.1, 5.2, 5.3 and 5.4). Skinny-Triangle Removal Test We tested the usefulness of skinny-triangle removal by carrying out sequences of Boolean operations with and without this feature. Skinny triangles are identified by comparing their aspect ratios against the aspect ratio threshold, a m a x . We set a m a x to 200 which is approximately the aspect ratio of a triangle with its longest edge about 25 times longer than its shortest one. These tests were conducted using the following cost thresholds: aspect ratio cost = 0 face orientation cost = 0.02 surface normal cost = 0.02 self-intersection cost = 0 The aspect ratio cost threshold was set to zero to prevent the aspect ratio of the trian-gles from worsening. The self-intersection cost threshold was set to prevent the creation Chapter 5. Implementation and Results 72 of self-intersecting surfaces. The face orientation and surface normal cost thresholds were chosen to keep the change in surface orientation small. Figure 5.2 illustrates how skinny triangles are removed from a model while preserving its appearance. The skinny triangle removal algorithm was successful in removing most skinny trian-gles but not necessarily al l of them. The number of skinny triangles can often be further reduced by lowering the face orientation and surface normal cost thresholds. Doing so allows the surface appearance to degrade more in exchange for a reduction of numerically unstable triangles. Table 5.5 provides an example of how the reduction of skinny trian-gles depends on the cost thresholds. The original model contains 6958 triangles, 527 of which are skinny triangles. The skinniest triangle has an aspect ratio of 2 x 10 1 2 . Figure 5.3 illustrates the original model as well as two modified models with 29 and zero skinny triangles, respectively. In this example, the appearance of the model does not change noticeably after skinny triangle removal. Face orientation Surface normal N u m . skinny N u m . Worst aspect T ime (s) threshold threshold triangles triangles ratio 0.02 0.02 29 6396 1578 5 0.08 0.08 6 6394 305.82 4 0.15 0.15 4 6394 305.82 4 0.45 0.45 0 6392 < 200 3 Table 5.5: Varying the cost thresholds for skinny triangle removal Apply ing Boolean operations to combined-solids occasionally fails due to the existence of skinny triangles. Without skinny-triangle removal, the user would need to re-position the input models and re-execute the failed operation and repeat the process unti l the operation succeeds. This was at times very difficult even when the tessellation of the Chapter 5. Implementation and Results 73 Figure 5.2: Skinny triangles removal: (a) a sphere about to be subtracted from a cylinder, (b) after subtraction with 970 triangles in total and 85 skinny triangles, (c) after skinny triangle removal with 852 triangles in total and 1 skinny triangle Chapter 5. Implementation and Results 74 Figure 5.3: Skinny triangles removal with different cost thresholds: (a) original model with 527 skinny triangles, (b) modified model with 29 skinny triangles, (c) modified model with 0 skinny triangle Chapter 5. Implementation and Results 75 surface is shown and the position and orientation of the input solids are changed sig-nificantly from their original positions. We were able to recover from most of these failures by applying skinny-triangle removal to the input models and re-executing the failed operations. Table 5.6 provides sample execution time for the removal of skinny-triangles from a variety of models. Num. triangles Num. skinny- Num. skinny- Time in model triangles before triangles after (0 5654 543 0 2 6958 527 6 3 8994 692 0 3 10832 357 0 2 11740 734 0 4 12032 532 0 3 14352 924 25 8 16648 998 35 8 21132 872 53 8 23340 2207 76 16 Table 5.6: Performance of skinny-triangle removal 5.2.2 Surface Blending We tested our surface blending scheme by applying it to the junctions between various combinations of solids. The surface-normal sampling threshold, A n , was set to 0.02 during our tests. Our surface blending scheme can consistently simulate smooth looking surface transitions when the base surfaces are free from surface creases. Creases on the base surfaces can introduce surface normal samples that do not smoothly interpolate between the junction and the trimlines. This is caused by discontinuous changes in surface normals along the trimlines. Chapter 5. Implementation and Results 76 Figure 5.4 illustrates the blending of a pair of smooth base surfaces. Two different blend ranges are shown in this example. Figure 5.5 shows how unsmooth surface normals, which lead to unsmooth surface shading, may be generated when one of the base surfaces is creased. Note the unsmooth surface shading near the edges of the cube. Table 5.7 shows the relationship between the number of edges in a few junctions and the time required for blending them. Num. junction Num. triangles Blend time (s) edges in model 83 1060 2 124 380 2 256 2730 7 267 6350 5 390 1284 8 547 12186 12 750 5022 25 1176 5468 23 Table 5.7: Blend time for junctions with different numbers of edges. Table entries are sorted by the number of junction edges. Chapter 5. Implementation and Results Figure 5.4: Blending smooth base surfaces: (a) before blending, (b) after blending with d. 0.049, and (c) after blending with dmax = 0.127. Chapter 5. Implementation and Results 78 Chapter 5. Implementation and Results 79 5.2.3 Sculpting The following are some of the sculptures created using our prototype solid modeler. Three-headed Cat Model The model of the three-headed cat was created from a Viewpoint domestic cat model by: 1. Getting a copy of the cat's head by intersecting it with a sphere. 2. Sweeping spheres along 3D paths to generate necks for the extra heads. 3. Taking the union of the original cat model with the extra necks and the extra heads, and smoothing the junction between all the merged surfaces. Figure 5.6 shows different views of the three-headed cat model. Figure 5.6: 3-headed cat model Chapter 5. Implementation and Results 81 Skull Model The model of a skull was created using the following steps: 1. Form the bulk of the skull by taking the union of two elongated spheres. Add the rim of the eye sockets by taking the union of the head bulk with small scaled spheres and carve out the sockets using subtraction. Apply surface blending to smooth out unwanted sharp surface junctions (refer to Figure 5.7). 2. Sweep a sphere along a path drawn along the head bulk to create the brow ridge and add it to the head bulk using union. Blend the surface junctions (refer to Figure 5.7). 3. Add an elongated sphere to the head bulk to form the rim of the nasal opening. Blend the surface junctions (refer to Figure 5.8). 4. Carve out the nasal opening using subtraction (refer to Figure 5.8). 5. Sweep a cylinder along a path drawn on a planar surface. Use the swept sheet to separate the crown from the jaw (refer to Figure 5.8). 6. Remove the jaw section, then hollow out the skull by subtraction (refer to Figure 5.9). 7. Further reduce the skull thickness by subtracting elongated spheres from the inside of the skull (refer to Figure 5.9). 8. Elongate a sphere to form the separator for the nasal cavity. Fuse it with the skull using union and apply surface blending (refer to Figure 5.9). Chapter 5. Implementation and Results 82 9. Smooth out the nose-to-lip region by subtraction and surface blending (refer to Figure 5.10). 10. Carve out depressions behind the eye sockets by sweeping spheres along curves drawn on a planar surface, subtracting the swept solid from the sides of the skull and apply surface blending (refer to Figure 5.10). Figure 5.7: Constructing a skull model, steps 1-2 Chapter 5. Implementation and Results Figure 5.8: Constructing a skull model, steps 3-5 Chapter 5. Implementation and Results Figure 5.9: Constructing a skull model, steps 6-8 Chapter 5. Implementation and Results 86 Figure 5.10: Constructing a skull model, steps 9-10 Chapter 5. Implementation and Results 87 Kid's Head M o d e l The model of a kid's head was created using the following steps: 1. Create the bulk of the head by merging two elongated spheres and blending the junction between them (see Figure 5.11). 2. Raise the cheeks by merging the head bulk with scaled spheres and blending the junctions between them (see Figure 5.11). 3. Create the sunken features around the eyes by subtracting squashed spheres at the eye socket area. Raise the area where the eyeballs sit by adding small spheres back into the eye socket regions. A d d the nose stem by merging elongated spheres. Use blending to smooth out al l surface transitions (see Figure 5.11). 4. Create the tip of the nose by adding spheres and blending the surface junctions (see Figure 5.12). 5. Create the eyeballs by cutting away ellipsoids and adding them back but at a lowered depth (see Figure 5.12). 6. Create the pupils by cutting away spheres from the eyeballs (see Figure 5.12). 7. Create the eyebrows by sweeping spheres along paths drawn on the head surface, and merging the swept solids with the head (see Figure 5.13). 8. Create the creases around the mouth by sweeping spheres along paths drawn on the face, merging the swept solids with the head, and blending the junctions between the crease cutting solids and the face. Create the lips similarly by sweeping spheres along paths drawn on the face, merging the upper and lower lips together, merging Chapter 5. Implementation and Results 88 the lips with the head and blending the junctions where they meet (see Figure 5.13). 9. Create the ears by squashing spheres into discs, elongating them, cutting grooves out of them by subtracting away swept solids, and blending the surface junctions (see Figure 5.13). 10. Create the chin by adding an elongated sphere and blending (see Figure 5.14). 11. Create the bulk of the hair by intersecting a sphere wi th a cylinder. Describe the front hairline by intersecting another sphere wi th another cylinder. Cut away the front hairline by subtracting the second solid from the first. Subtract tetrahedra from the front to cut out wedges at the bang. A d d tetrahedra to the top of the hair to create the upward pointing hair. Merge the hair-piece wi th the head (see Figure 5.14). Chapter 5. Implementation and Results Figure 5.11: Constructing a kid's head model, steps 1-3 Figure 5.12: Constructing a kid's head model, steps 4-6 Chapter 5. Implementation and Results Figure 5.13: Constructing a kid's head model, steps 7-9 Chapter 5. Implementation and Results 92 Chapter 6 Conclusions and Future Work We have developed a simple solid modeler which allows the user to create solid sculptures using a set of Boolean operations, a skinny-triangle removal operation and a simulated surface blending operation. This modeler computes the Boolean combinations of triangu-lated boundary-represented solids more robustly than Maya 2.5 and 3D Studio Max 2.5. It also identifies and removes skinny triangles to help maintain the validity of solids. Our system can also simulate smooth surface transitions between non-trivial surface junctions with hundreds of junction edges at near-interactive speed. Achieving the robustness of our Boolean operations has its cost; our solid modeler that relies on LEDA-real for numerical stability is between three to nine times slower than 3D Studio Max running on a slightly slower platform. One way to improve the performance of our algorithm is to replace the use of LEDA-real with finite precision integer arithmetic as suggested by Fortune and Van Wyk [13]. This, however, would increase the programming effort and the complexity of the algorithm. The removal of skinny triangles is currently a function that is manually invoked by the 93 Chapter 6. Conclusions and Future Work 94 user to turn invalid solids with line-degenerate and overlapping faces into valid ones. This is currently used as a means to recover from failed Boolean operations. The usability of the system can be improved by making the identification and removal of skinny triangles automatic. Some of the main drawbacks of our simulated surface blending scheme include the generation of surface artifacts within blend regions that are surrounded by creased base surfaces, and the introduction of a large number of triangles during the process. The generation of surface artifacts is due to the discontinuous change in surface normals along the trimlines. This may be alleviated by averaging the surface normals along the trimlines. Instead of introducing vertices into the mesh to improve the sampling of surface normals, normal maps may be used to specify surface normals without affecting the surface tessellation. One useful feature of our solid modeler that requires much improvement is the ability to generate new solids by sweeping existing solids along 3D paths. This operation allows the user to define volume intuitively and expressively using a painting metaphor. One of the main difficulties of this operation is the removal of self-intersections that are often created during the sweep operation. Self-intersections are undesirable because they invalidate the solids and cause problems during Boolean operations. One solution is to utilize volume-based sweeping schemes for determining the volume enclosed by the swept solid [40]. Appendix A Halfedge Data Structure The following is an introduction to the Halfedge data structure defined in the Compu-tational Geometry Algor i thm Library ( C G A L ) . The introduction is then followed by the interface specification of the "Halfedge" C++ class. This information is extracted from the C G A L Reference Manual [6]. 95 Appendix A. Halfedge Data Structure 9 6 Navigation: Up, Table of Contents, Bibliography, Index, Title Page Halfedge Data Structures Introduction A halfedge data structure is an edge-centered data structure capable of maintaining incidence informations of vertices, edges and facets, for example for planar maps or polyhedrons. Each edge is decomposed into two halfedges with opposite orientations. One incident facet and one incident vertex are stored in each halfedge. For each facet and each vertex one incident halfedge is stored. Reduced variants of the halfedge data structure can omit some of these informations, for example the halfedge pointers in vertices or the storage of vertices at all. The data structure provided here is known as the FE-structure [Wei85], as halfedges [Man88, BFH95] or as the doubly connected edge list (DCEL) [dBvKOS97], although the original reference for the D C E L [MP78] describes a different data structure. We continue naming it halfedge data structure (HDS). This data structure can also be seen as one of the variants of the quad-edge data structure [GS85], reduced to support only orientable surfaces. In general, the quad-edge data structure has a richer modeling space and can represent non-orientable 2-manifolds. The dual and the primal graph are symmetrically represented; the same algorithms can be applied to the dual graph as well as to the primal graph. This implies a lack of static type checking to distinguish between facets and vertices. Even though halfedges are similar to the winged edge data structure [Bau75] or the original reference for the D C E L [MP78], they are not equivalent, since the traversal algorithms are forced to search for certain incidences where the information is directly available in the halfedge data structure. An overview and comparison of these different data structures together with a thorough description of the design implemented here can be found in [Ket98]. Design Overview The design strictly separates topology and geometry. Vertices, halfedges and facets carry both kinds of information. The Halfedge_data_structure acts as a container class and stores all items and manages Appendix A. Halfedge Data Structure Navigation: Up, Table of Contents, Bibliography, Index, Title Page 97 Requirements for a Halfedge Definition A halfedge must store a pointer to the next halfedge and a pointer to its opposite halfedge. It optionally stores pointers to its incident vertex and incident facet. Type tags indicate whether these member functions are supported. Figure S depicts the relationship between a halfedge and its incident halfedges, vertices, and facets. The is_border{) predicate is mandatory, but may return always false. A halfedge is an oriented edge between two vertices. It is always paired with its counterpart that has the opposite direction. They are mutually linked with the opposite() member function. Types Halfedge:: Vertex corresponding vertex type. Halfedge: .-Halfedge self. Halfedge:: Facet corresponding facet type. Operations Halfedge* h.opposite () the opposite halfedge. const Halfedge* h. opposite () const Halfedge* h.next () the next halfedge around the facet. const Halfedge* h.next () const Halfedge* h.prev () the previous halfedge around the facet. const Halfedge* h.prev () const Vertex* h.vertex () the incident vertex. const Vertex* h.vertex () const Facet* hfacet() the incident facet. If h is a border halfedge the result might be NULL or a unique facet representing this hole or a unique facet representing all holes. const Facet* h facet () const bool h.is_border () const is true if h is a border halfedge. void h.set_next( Halfedge* next) void h.set_prev ( Halfedge* prev) void h.set_vertex ( Vertex* v) void h.set_facet ( Facet* f) if f == NULL h becomes a border edge. References [1] Banghiel, C , Bartels, R. , and Forsey, D . , "Pasting Spline Surfaces", Technical Re-port, Department of Computer Science, University of Br i t i sh Columbia , TR-95-32 (December 1995). [2] Baumgart, B . , "Geometric modeling for computer vision", P h . D . dissertation, Com-puter Science Dept., Stanford University (1974). [3] B l i n n , J .F . , "Simulation of wrinkled surfaces", Proceedings of SIGGRAPH '78, pp. 286-292 (1978). [4] Brunet, P. and Navazo, I., "Solid Representation and Operation Using Extended Octrees", ACM Transactions on Graphics, 9(2), pp.170-197 ( A p r i l 1990). [5] Celniker, G . , and Gossard, D , "Deformable curve and surface finite-elements for free-form shape design", Proceedings of SIGGRAPH '91, pp. 257-266 (1991). [6] "The C G A L Basic Library Reference Manual" , 2000. h t tp : / /www.cs .uu.nl /CGAL/Informat ion/doc_html/f rameset / fsBasic .html [7] Chan, L . K . Y . , Mann , S., and Bartels, R. , "World space surface pasting", Proceedings of Graphics Interface '97, pp. 146-154 (May 1997). 98 References 99 [8] Chiyokura, H . , Solid Modeling with Designbase, Theory and Implementation, Addison-Wesley , Reading, Massachusetts, (1988). [9] Decaudin, P., "Geometric Deformation by Merging a 3D-Object with a Simple Shape", Proceedings of Graphics Interface '96, pp. 55-60 (1996). [10] Desbrun, M . and Gascuel, M . - P . , "Animat ing Soft Substances wi th Implicit Sur-faces", Proceedings of SIGGRAPH '95, pp. 287-290 (1995). [11] Ernst, I., Russeler, H . , Schultz, H . , and W i t t i g , 0 . , "Gouraud B u m p Mapping" , Proceedings of Eurographics '98, pp. 47-54 (1998). [12] Fortune, S., "Polyhedral modeling with exact arithmetic", ACM Solid Modeling '95, pp. 225-233 (1995). [13] Fortune, S, and Van W y k , C . J . , "Static Analysis Yields Efficient Exact Integer Ar i thmet ic for Computational Geometry", ACM transactions on Graphics, 15(3), pp. 223-248 (July 1996). [14] Forsey, D . and Bartels, R. , "Hierarchical B-spline Refinement", Proceedings of SIG-GRAPH '88, pp. 205-212 (1988). [15] Galyean, T . and Hughes, J . , "Sculpting: A n Interactive Volumetric Modeling Tech-nique", Proceedings of SIGGRAPH '91, pp. 267-274 (1991). [16] Greiner, G . , "Blending technique based on variational principles", Curves and Sur-faces in Computer Vision and Graphics III, S P I E , pp. 174-183 (1992). [17] Hoffmann, C , Geometric & Solid Modeling, An Introduction, Morgan Kaufmann Publishers, Inc., San Mateo (1989). References 100 [18] Hoffmann, C. and Rossignac, J . , " A Road M a p To Solid Model ing" , IEEE Transac-tions on Visualization and Computer Graphics, 2(1), pp. 3-10 (March 1996). [19] Hoppe, H . , DeRose, T . , and Duchamp, T . , "Mesh Opt imiza t ion" , Proceedings of SIGGRAPH '93, pp. 19-26 (1993). [20] Hoppe, H . , "Progressive Meshes", Proceedings of SIGGRAPH '96, pp. 99-108 (1996). [21] Kana i , T . , Suzuki, H . , Mi t an i , J . , and K imura , F . , "Interactive Mesh Fusion Based on Local 3D Metamorphosis", Proceedings of Graphics Interface '99, pp. 148-156 (1999). [22] Kana i , T . , Suzuki, H . , and K imura , F . , "Three-dimensional geometric metamorpho-sis based on harmonic maps", The Visual Computer, pp. 166-176 (1998). [23] Laidiaw, D . and Hughes, J . , "Constructive Solid Geometry for Polyhedral Objects", Proceedings of SIGGRAPH '86, pp. 161-170 (1986). [24] Mehlhorn, K . , and Naher, S., The LEDA Platform of Combinatorial and Geometric Computing, Cambridge University Press (2000). h t t p : / / w w w . m p i - s b . m p g . d e / L E D A / M A N U A L / M A N U A L . h t m l [25] Lindstrom, P. and Turk, G . , "Fast and Memory Efficient Polygonal Simplification", Proceedings of IEEE Visualization '98, pp. 279-286, (1998). [26] Manty la , M . , "Boolean Operations of 2-Manifolds through Vertex Neighborhood Classification", ACM Transactions on Graphics, 5(1), pp. 1-29 (January 1986). [27] M a x , N . , "Weights for Computing Vertex Normals from Facet Normals", Journal of Graphics Tools, pp. 1-6 (1999). References 101 [28] Mi tche l l , J .S .B . , Mount , D . M . , and Papadimitr iou, C . H . , "The Discrete Geodesic Problem", SI AM Journal of Computing, pp. 647-668 (1987). [29] Baker, S., " A Brief M U I User Guide" http: / / reality, sgi .com / opengl/ t ips/mui / mui .html [30] Naylor, B . , Amanatides, J . , and Thibault , W . , "Merging B S P Trees Yields Polyhe-dral Set Operations", Proceedings of SIGGRAPH '90, pp. 115-124 (1990). [31] Naylor, B . , " S C U L P T : A n Interactive Solid Model ing Tool" , Proceedings of Graphics Interface '90, pp. 138-148 (1990). [32] Naylor, B . , "Interactive Solid Geometry V i a Part i t ioning Trees", Proceedings of Graphics Interface '92, pp. 11-18 (1992). [33] Peercy, M . , Airey J . , and Cabral , B . , "Efficient B u m p Mapping Hardware", Pro-ceedings of SIGGRAPH '97, 303-306 (1997). [34] Pentland, A . , Essa, I., Friedmann, M . , Horowitz, B . , and Sclaroff, S .E. , "The Thing-World Model ing System: V i r t ua l Sculpting by Moda l Forces", Proceedings of the Symposium on Interactive 3D Graphics, pp. 143-144 (March 1990). [35] Pfeifle, R. and Seidel, H .P . , "Triangular B-Splines for Blending and F i l l i ng of Polyg-onal Holes", Proceedings of Graphics Interface '96, pp. 186-193 (1996). [36] Requicha, A . , "Representations for Rig id Solids: Theory, Methods, and Systems", ACM Computing Surveys, 12(4), pp. 437-464 (December 1980). [37] Sederberg, T . and Parry, S., "Free-form deformations of solid geometric models", Proceedings of SIGGRAPH '86, pp. 151-160 (1986). References 102 [38] Singh, K . and Fiume, E. , "Wires: A Geometric Deformation Technique", Proceedings of SIGGRAPH '98, pp. 405-414 (July 1998). [39] Sloan, S., "A Fast Algorithm for Generating Constrained Delaunay Triangulations", Computers & Structures, 47(3), pp. 441-450 (1993). [40] Sourin, A . , and Pasko, A . , "Function representation for sweeping by a moving solid", Proceedings of SMA '95, pp. 383-391 (May 1995). [41] Home page of SPEC (Standard Performance Evaluation Corporation); under "Benchmark Results", 2000. http://www. specbench.org [42] Terzopoulos, D., Piatt, J . , Barr, A . , and Fleischer, K . , "Elastically Deformable Models", Proceedings of SIGGRAPH '87, pp. 205-214 (1987). [43] Thiirmer, G. and Wiithrich, C.A. , "Computing Vertex Normals from Polygonal Facets", Journal of Graphics Tools, 3(1), pp. 43-46 (1998). [44] Vida, J . , Martin, R., and Varady, T., "A survey of blending methods that use parametric surfaces", Computer-Aided Design, 26(5), pp.341-365 (1994). [45] Wang, X . , Cheng, F., and Barsky, B. , "Blending, Smoothing and Interpolation of Irregular Meshes Using N-sided Varady Patches", ACM Solid Modeling, pp. 212-222 (1999). [46] Warren, J . , "Blending algebraic surfaces", ACM Transactions on Graphics, 8(4), pp. 263-278 (October 1989). References 103 [47] Witkin, A . and Heckbert, P., "Using Particles to Sample and Control Implicit Sur-faces", Proceedings of SIGGRAPH '94, pp. 269-278 (July 1994). [48] Wyvi l l , G. , McPheeters, C , and Wyvil l , B . , "Data structure for soft objects", Visual Computer, pp. 227-234 (1986).
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Robust sculpting using boundary represented solids
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Robust sculpting using boundary represented solids Lee, Cedric C. 2000
pdf
Page Metadata
Item Metadata
Title | Robust sculpting using boundary represented solids |
Creator |
Lee, Cedric C. |
Date Issued | 2000 |
Description | Boolean operations are often used in the computer modeling of 3-D mechanical parts and machineries and are known for their predictable behavior and ease of use. The use of Boolean operations in the interactive modeling of free-form models, however, has been rather limited. Some of the difficulties in realizing this include: selecting a model representation that may be displayed at interactive speed, applying Boolean operations robustly, and creating smooth surface transitions at the junctions between models. This thesis explores the use of the real number package of the Library of Efficient Datatypes and Algorithms (LEDA) for computing the Boolean combination of triangulated and boundary-represented solids robustly. This thesis also suggests a scheme for removing numerically unstable triangles which are detrimental to the validity of solids, and a surface blending scheme that simulates the smoothing of sharp surface junctions by modifying surface normals. Our scheme for computing Boolean operations is more robust than those used in two popular modeling applications but at the expense of longer computation time. Our scheme for removing numerically unstable triangles is effective in removing invalid surface triangulations while preserving the appearances of models and our simulated surface blending scheme is capable of smoothing non-trivial surface junctions at near-interactive rates. These features were implemented in a simple solid modeler and a set of models was created interactively using this system. |
Extent | 5401041 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-07-13 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0051706 |
URI | http://hdl.handle.net/2429/10705 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2000-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2000-0460.pdf [ 5.15MB ]
- Metadata
- JSON: 831-1.0051706.json
- JSON-LD: 831-1.0051706-ld.json
- RDF/XML (Pretty): 831-1.0051706-rdf.xml
- RDF/JSON: 831-1.0051706-rdf.json
- Turtle: 831-1.0051706-turtle.txt
- N-Triples: 831-1.0051706-rdf-ntriples.txt
- Original Record: 831-1.0051706-source.json
- Full Text
- 831-1.0051706-fulltext.txt
- Citation
- 831-1.0051706.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051706/manifest