FRENCH SURFACE: A NEW TECHNIQUE FOR SURFACE DESIGN by ZLTA SZE TING C H E N G Bachelor of Science, University of Calgary, 1999 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E DEGREE OF MASTER OF SCIENCE in T H E FACULTY OF G R A D U A T E STUDIES Department of Mathematics We accept this thesis as conforming to the required standard. T H E UNIVERSITY OF BRITISH COLUMBIA July 2001 © Zita Sze Ting Cheng, 2001 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British 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 representa-tives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Mathematics The University of British Columbia Vancouver, Canada Date An^ niT" 3\ j ^° , (>. 1 Abstract We present a new user-friendly paradigm for surface design. The goal is to overcome limita-tions associated with traditional methods: their dependence on freehand controlling and their rigid mathematical structures. Our solution is inspired by the drafter's tool known as French curves, which are used as templates for tracing curves. This project considers its analogue in one higher dimension, namely 3D surfaces. A carefully defined and intuitively arranged set of French surfaces is given to the user to choose from. The selected surfaces are then connected together to form the final model. The potential of this approach is explored with our prototyping system, F R E N C H S U R F A C E , where models are constructed via aggregated blendings of chosen French surfaces. Triangu-lated point-sets are used to engage a structure-free representation, and data structuring algo-rithms are integrated to ensure an efficient blending. The current system supports the creation of objects topologically homeomorphic to a sphere or a plane. Users' experiences demonstrate that the F R E N C H S U R F A C E system is intuitive, robust, and easy to comprehend. ii Table of Contents Abstract ii Table of Contents iii List of Figures v Acknowledgement vii Chapter 1. Introduction 1 Chapter 2. Related Work 5 2.1 Traditional Approaches 5 2.1.1 Techniques 5 2.1.2 Limitations 6 2.2 Direct Manipulation 7 2.2.1 Techniques 7 2.2.2 Discussion 8 2.3 Nontraditional Interactive Systems 9 2.3.1 2D Input Techniques 9 2.3.2 3D Input Techniques 10 2.3.3 Discussion 11 2.4 Motivation of Our Project: French Curves 11 2.4.1 Physical French Curves and their Advantages 11 2.4.2 Digital French Curves and their Implications 12 2.5 Primitive Surfaces 13 2.5.1 Primitive Surfaces in Existing Systems 13 2.5.2 Discussion 14 Chapter 3. The FRENCH SURFACE System: Theory 15 3.1 The Set of French Surfaces and its Navigation 15 3.1.1 The Surfaces in the Set of French Surf aces 16 3.1.2 Navigation Technique 18 3.1.3 Alternative Approach 21 3.2 General Scheme 22 3.2.1 Logical Framework of the Scheme 22 3.2.2 Pragmatic Framework of the Scheme 23 3.2.3 Alternative Approach 25 Chapter 4. The FRENCH SURFACE System: Implementation and Evaluation 27 4.1 Representation and Local Approximation 27 4.1.1 Triangulated Point Set 27 4.1.2 Alternative Approaches 29 4.2 Positioning 31 iii Table of Contents 4.3 Blending 32 4.3.1 Step 1: Establishing Correspondence 32 4.3.2 Step 2: Finding Boundary Triangles and Boundary Vertices 36 4.3.3 Step 3: Removing Enclosed Triangles 41 4.3.4 Step 4: Forming the Blending Surface 44 4.3.5 Discussion and Implications of the Blending Algorithm 46 4.4 Evaluation of the F R E N C H S U R F A C E System 48 Chapter 5. Conclusion 53 5.1 Contributions 53 5.1.1 The French Surface Concept 53 5.1.2 Blending of Triangle Meshes 54 . 5.2 Limitations 54 5.3 What's next? 55 5.3.1 Future Work on the F R E N C H S U R F A C E System 56 5.3.2 Future Research on the French Surface Concept 57 5.4 Conclusion 58 Bibliography 59 iv List of Figures 1.1 Some models created using the FRENCH SURFACE system 2 1.2 Examples of French curves 2 1.3 The French surface library is created based on the theory described in this thesis and is the main focus of the project. The FRENCH SURFACE system is a prototype application based on the French surface concept and it gives some indications of the usability of the approach 3 3.1 Some examples of French surfaces from the infinitely large set 17 3.2 Continuum of transitional surfaces from the ellipsoid to the drop 17 3.3 The control panel 20 3.4 The spiral for capturing surfaces with orthogonal principal directions 21 3.5 Stages in drawing Piggy in Figure 1.1 24 3.6 The creation cycle in the FRENCH SURFACE System 24 3.7 The bottom-up approach 26 4.1 Triangulation of a sphere, (a) The preferred uniform triangulation. (b) Nonuniform sampling and triangulation 28 4.2 The rim of a French surface is represented by a counter-clockwise sequence of equally spaced vertices {ao, ai, . . . , ai<}- Directional tangent at each rim vertex ai is required in the blending algorithm 29 4.3 The blending algorithm. Step 1: establishing correspondence; step 2: finding boundary triangles and boundary vertices; step 3: removing enclosed triangles; step 4: forming the blending surface 32 4.4 The correspondence between the rim vertex ai of the French surface and the model. Ci denotes the correspondence (or intersection) point and Ti the triangle containing it. 33 4.5 The planar cross section for determining the correspondence point C i . For smooth blending, Ci occurs at an angle deviation from ti 34 4.6 (a) If n intersects the model more than once, choose the closest intersection as C i . (b) Test 1 restricts the triangle candidates to those with centroids inside a ^-cylinder around n 34 4.7 Joining Ti and Ti+i (shaded) by finding the intermediate triangles (dotted), and recording their outside vertices which will become the boundary vertices 36 4.8 Finding intermediate triangles between Ti and Ti+i. (a) Two examples explaining the algorithm, (b) The end result. Here, Ii represents the intermediate triangles, and S, = {Ti , lo, Ii, . . . , Ti+i} represents the boundary triangles. Their outside vertices become the boundary vertices, (c) A n example showing the boundary triangles may not follow a one-up-one-down pattern 38 List of Figures 4.9 Possible scenarios at the joints of consecutive sequences of boundary vertices. Black, light grey, and dark grey denote Si, Si+i, and S,-i respectively. The dot diagrams show the concatenated sequence in each case. "?" represents a missing vertex, "u" an identical vertex, and "x" a vertex to be removed. See Figure 4.10 for a case study. 40 4.10 Case study of case 3 in Figure 4.9. See text for explanation 41 4.11 Removing boundary and inside triangles. In the mesh, only boundary triangles are labelled, but inside and outside ones are not distinguished from each other 41 4.12 Possible scenarios when we arrive at a triangle T during the recursive marking of toBeRemoved triangles. The number of boundary vertices of T ( M T ) induces which neighbour triangles of T we should apply recursion to. The thin black line indicates the boundary between outside and inside 43 4.13 The use of the "Enclose" checkbox to choose what side to keep, (a) Blend on top and keep outside, flb) Blend on top and keep inside, (c) Blend underneath and keep outside, (d) Blend underneath and keep inside. Figure 4.19 shows the 3D version of these diagrams 44 4.14 The use of Bezier curves to create the blending surface and various degree of blending. 45 4.15 Merging 2 sequences of vertices to create an even triangle mesh 45 4.16 Rays from the rim as a positioning guide. They also give the user an idea of what to expect in the blending result 46 4.17 Two interpretations of the power of blending, (a) varying the tightness of the blend; and (b) varying the extent of the blend 47 4.18 Varying the extent of a blend, (i) When the angle is large, it is likely that the rim ray misses the model, (ii) This problem can be solved by adaptively adjusting the rim ray. 48 4.19 Different combinations of blending on top/bottom and keeping inside/outside. This is the 3D version of Figure 4.13 49 4.20 Multiple blending showing the robustness of the system 50 4.21 Models created using the FRENCH SURFACE system. Piggy, Castle, Industrial-Part, and Snake 51 vi Acknowledgement I would like to thank my supervisor Dr. Sidney Fels. Thanks to Dr. Wolfgang Heidrich and Dr. Michiel van der Panne for their valuable suggestions and comments on an earlier draft of this thesis. I would also like to express my appreciation to the people at the Human Commu-nications Technology Lab for their support. It is my pleasure to thank the Institute of Applied Mathematics (IAM) for giving me the op-portunity to pursue this research and combine my interests in mathematics and art. I am grateful for the financial support given to me by the Natural Sciences and Engineering Research Council of Canada (NSERC) and the University of British Columbia. Finally I would like to thank my parents for all their years of support and encouragement. vii Chapter 1 Introduction The state of the art in 3D surface1 design is capable of representing complex surfaces with satisfactory results. There are, however, several restrictions associated with these methods. Parametric surface modelling depends on a priori patch layout and manipulation of control points external to the surface. To master such systems, users inevitably have to understand the mathematics behind them. Freeform deformation and direct manipulation of surface points are developed to give users an illusion of independence from mathematics. Yet, tedious free-hand manipulation and complicated global changes distract the user from the artwork being modeled. Approaches aimed at a user-friendly interface are often only brought to the point of rough conceptual prototyping. The objective of this work is to develop a surface modeling methodology capable of interac-tively generating shapes with maximum tractability and minimum user input. Ideally, the only input from users should be direct artistic expression. Our inspiration comes from the French curve, a tool used by drafters (Figure 1.2). The key to its usability is that it serves as a visual basis for selection, and provides a template for tracing curves. Choosing from a display in front of your eyes and then copying something is easier than creating it from scratch and out of imagination [36]. In [44], Singh suggests the use of digital French curves in planar curve modelling. This work extends the French curve metaphor to 3D surface design. In short, we create a set 1In strict mathematical terms, surfaces are actually 2D embedded in R 3 . It is, however, common in computer graphics literature to call them "3D" to signify they are non-planar objects. 1 Chapter 1. Introduction Chapter 1. Introduction F R E N C H S U R F A C E System French Surfaces Library Application Layer - Other 3D modelling applications Drawing Layer Figure 1.3: The French surface library is created based on the theory described in this thesis and is the main focus of the project. The F R E N C H S U R F A C E system is a prototype application based on the French surface concept and it gives some indications of the usability of the approach. of surfaces for users and they simply select and combine. Our task includes consideration of (1) what surface features should be included and (2) how they should be arranged on the templates. We want to provoke a discussion about the extent to which selection from a given library of surface templates can relieve the cognitive burden of the designer. Naturally, we call the predefined library a set of French surfaces. The realization of the concept of French surfaces is the main focus of the system as illustrated in Figure 1.3. The French surface idea can be used in conjunction with many 3D modelling system (Fig-ure 1.3). In this project, we test the French surface concept with a simple modelling system, which we called F R E N C H S U R F A C E , where surfaces are combined incrementally through a blending operation. Some models created using the F R E N C H S U R F A C E system are shown in Figure 1.1. Since our goal is to overcome the limitations of current methods discussed above, the following is a list of criteria which informed the design of our system. CI. Simple Modelling Tasks: The cognitive overhead of the system must be kept at a minimum level. The behaviour of the system should not rely on direct in-teraction with the mathematical structure. Also, tedious tasks such as freehand controlling, modelling with a large toolkit, and low-level editing and revision, are unwanted. Our goal is to allocate difficult tasks to the computer, freeing up re-sources for artistic creation and contemplation of the model. This is motivated by 3 Chapter 1. Introduction the principles of user interface design discussed in [31]. C2. Functions with Predictable Results: The effect of each action should agree with the user's intuitive prediction. Otherwise modelling is reduced to experi-mentation based on trial and error. This is inspired by the features of a what-you-see-is-what-you-get system [43]. We only consider direct operations that do not have a wide range of possible interpretations, so that the system can unmistakably infer what the user expects. C3. Minimal Math Structure: Not only must the mathematics be intrinsic to the system, the mathematical representation of the models must be as simple as possi-ble - just enough to represent the topology. We want to avoid complex parametric structures because the behaviour of the system would then be limited to some fixed number of degrees of freedom. In Chapter 2, we will take an in-depth look at related work in surface design; we will discuss various approaches, advantages, and shortcomings. Chapter 3 presents the French surface invention, detailing what the templates are, and how the surface elements are arranged. The implementation details of the F R E N C H S U R F A C E system are depicted in Chapter 4, including interesting use of data structures and algorthims. We will also report on users' experiences with the system. Chapter 5 presents a discussion of the contributions and limitations of the French surface concept. This report concludes with a list of avenues for future research. 4 Chapter 2 Related Work 2.1 Traditional Approaches 2.1 .1 Techniques The state of the art in 3D geometric modelling systems uses a number of techniques to cre-ate and edit curved surfaces. These range from manipulation of control vertices, revolution, and extrusion in conventional approaches, to more sophisticated direct manipulation strate-gies with tangency or curvature constraints. Some researchers also propose various interface for surface design, such as sketching, sculpting, and gestural-based input mechanisms. A n overview of these approaches, their pros and cons will be discussed, and a comparison with our method is given at the end of each section. The simplest surface construction methods include revolution, extrusion, and birailing. These methods essentially reduce the task of creating surfaces to that of drawing curves. Surface revolution creates a symmetric surface by rotating a given curve about an axis. The extrusion method generates a ruled surface by sliding a profile curve along a trajectory curve, while birailing constructs a surface by following a profile curve along two trajectory curves. Another traditional surface formation is performed by manipulating the control mesh of a B-spline or other tensor product surface [15]. The typical procedure begins with a simple shape with an imaginative lattice of controls points around it. By repositioning control points or changing their multiplicity, the initial shape can be modified to give a more complex shape. The new object points will be re-determined according to a weighted sum of the control pa-5 Chapter 2. Related Work rameters [27]: S(u,v) = ^2VijBitj{u,v), where S(u,v) denotes new object points, Vij the control points, and Bitj the B-spline basis function. Traditional shape deformation interface is thus tightly tied to the underlying math-ematics architecture. 2.1.2 Limitations Despite the powerful capacity of control point manipulation, its limitations have been ad-dressed by many authors [25] [51] [45] [26] [39]. There are, in summary, three problems. 1. Exact shapes are difficult to achieve, largely because of the underlying rigid mathemat-ical structure. Designers must be familiar with splines in order to manipulate control point properties. Even so, the procedure is often cumbersome because a slight change may require repositioning of many control points. 2. Placement of control points relies on freehand movement or pure coordinate entries. Either way, the manipulation of control mesh can be a tedious and frustrating experience. 3. The designer usually has to face an overwhelmingly dense clutter of control points. The problem is further complicated because the control points are often occluded by the ob-jects that need to be deformed. To allow for easy shape control, some systems have the option of moving control points in groups [9]. Also, freeform deformation techniques allow deformation of the space in which the object lies, which has fewer control points than the object itself [2] [10] [42]. Yet manip-ulation is indirect, as control points are extraneous to the object. To address this issue, direct manipulation of surface points and features has been proposed in the literature. 6 Chapter 2. Related Work 2.2 Direct Manipulation 2.2.1 Techniques A straight-forward solution for direct manipulation is presented by Hsu et. al. [25]. When the user moves a selected object point to a target position, the control points are automatically reconfigured so that the deformed object point matches with its intended destination. The shape of the surface is fully determined by the extra constraint of minimum combined control point movement. B-spline tensor product deformation functions are used in their system. Fowler [18] similarly considers direct manipulation of B-spline surfaces by introducing ge-ometric constraints. In addition to positional manipulation, Fowler proposes the control of higher order properties such as tangency and partial derivatives. Rotating the pair of partial derivative vectors Su(u, v) and Sv(u, v) changes the orientation of the tangent plane. Scaling the directional derivative creates a tension effect. Rotating the mixed partial Suv(u,v) cor-responds to a twisting result. Extra degrees of freedom are incorporated in the parameters to prevent asymmetric effects. VPL Data Gloves are used as the input device for the direct manipulation interface. More powerful direct manipulation techniques permit user-defined curves or surface regions as handles for free-form surface modelling [45] [51] [52]. In particular, Welch and Witkin in [51] use a summation of tensor-product B-splines and smaller parametric patches to repre-sent the original model and refinement details respectively. Computation of the control pa-rameters is cast as a variational optimization problem. The objective function is a quadratic shape-fairness measure and the constraints are geometric descriptions of surface shape at dis-crete points, curves, or subregions. Later in [52], these authors implement the same methodology, but relaxing the parametric representation to a simple set of triangle mesh with no intrinsic structure. Surface proper-ties like tangents and normals are approximated, and mesh refinement tactics ensures well-conditioned triangulation. Users are free to embed control curves, define surface regions, split surfaces, and merge surfaces. 7 Chapter2. Related Work Another direct manipulation system is proposed by Kobbelt et. al. [28]. The goal of their paper is to propose a new multi-resolution modelling technique that avoids restriction by subdivi-sion connectivity. In order to demonstrate the functionality of such an approach, they design a multi-resolution modelling system based on direct manipulation of polygonal mesh. The user first defines a region on the mesh as the region to be modified. Next a sequence of surface points inside this region is specified to represent the control handle. Finally, by manipulat-ing the control handle, the mesh inside the bounded region is modified accordingly based on a constrained energy minimization. The multi-resolution techniques allow the modelling system to support direct manipulation of polygonal mesh in realtime. Other researchers use the machinery from 3D curve design as an input substratum for surface modelling. ShapeWright by Celniker and Gossard [7] creates a C\ skinned surface around character lines defining edges and creases. The surface can then be modified by varying inter-nal pressure, bending-resistance, or other stress elements. Moreton and Sequin [34] minimize the variation of curvature to construct a skinned surface on a network of curves. Although their technique is quite computationally intensive, it allows the creation of surfaces with a wide range of topologies. 2.2.2 Discussion The above approaches have taken great strides toward direct and precise surface modelling by manipulating surface points, surface curves, or other surface features. However hiding the control points cannot totally get rid of mathematical analysis. Tangency and curvature for surfaces are not trivial concepts, and the behaviour of the system is still controlled by the mathematical representation. High-level manipulation and definition of surface curves for use as control handles are potentially tedious operations and may create unexpected results. The French surface scheme in this paper attempts to reduce user input as much as possible. Our aim is to escape manipulation and to provide users with a collection of predrawn sur-faces for selection. The key is an adequate collection of templates with a good organization. If we must describe our system in surface manipulation terms, F R E N C H S U R F A C E performs 8 Chapter2. Related Work manipulation for users and categorizes the results for selection. 2.3 Nontraditional Interactive Systems There has recently been more attention paid to the problems of interactive 3D surface mod-elling, not from the view of algorithm or mathematical representations, but in terms of the intuitiveness of the interface and the support for artistic expressions. These systems do not engage in meeting analytic criteria such as curvature continuity, but in creating a user-friendly interface. As our project shares a similar goal, this section is devoted to an overview of these innovative methods. 2.3.1 2D Input Techniques A n input technique using shading as a proxy for height is introduced by Overveld [48]. Shading patterns are painted directly on the surface, and they are translated into image processing operations on pixels' depth buffer. The user can also choose from a hemispherical menu of shades to directly control the rendered view of shading. Finally, the result is converted to a tessellated wireframe. Zeleznik et. al. [54] implement an interactive system S K E T C H which automatically infers hand gestures from mouse strokes to generate adaptive 3D models. Different gestures are associated with different visual tasks like creating, transforming, resizing, grouping, and copying geo-metric objects. Complex objects can be created using smaller and simpler pieces. This closely resembles our system. The merit of 2D sketching as an input device becomes the motivation of other interactive systems, such as Teddy. Teddy [26] supports surface drawing using 2D freeform strokes on a display-integrated tablet as the input control. Examples of operations include inflating a 3D surface from a 2D silhou-ette, extruding a base ring on the surface along an extension stroke, digging a cavity on the surface, cutting away sections of the form, and smoothing a highlighted region. The triangu-lated surfaces determined from these 2D input strokes take a spherical topology. The system 9 Chapter 2. Related Work is particularly praised for its usefulness in conceptual design of stuffed animals and round objects. Some systems take on the metaphor of sculpting 3D objects from an initial solid volume [19] [37] [49]. Volume sculpting presented by Galyean and Hughes [19] suggests the sub-traction and addition of material with a virtual "heatgun" and a virtual "toothpaste". In [49], Wang and Kaufman propose some highly precise geometric sawing and carving tools. The solids in both systems are represented by voxels; these systems work through a direct manip-ulation of voxel elements. 2.3.2 3D Input Techniques The prototype system presented by Schkolne et. al. [39] is based on the versatility of hand motion and its ability to communicate 3D shapes. Surfaces are built according to the user's hand gesture, which is captured in a semi-immersive 3D display. The user can switch between various modes (e.g. drawing, erasing, and detailing) through the use of different finger con-figurations sensed by a special glove. The surface forms are realized as triangle meshes which are constructed incrementally through the Cookie Cutter algorithm (triangulation in 2D) with Laplacian mesh smoothing. The goal is not an accurate surface modeller, but an expressive device for capturing intricate gestural form. The 3DSketch system described by Han and Medioni allows one to copy an existing object using a digitizing stylus [21]. A rough clay prototype is first built from a few strokes sketched on the objects. Singular features such as corners and edges are then traced to provide a more refined model. Finally, hard-to-trace edges are detected via reconstruction of smooth faces. The above systems have adopted a 3D input device, but they are still restricted to a mono-scopic display. Holosketch [11] implemented by Deering provides a virtual-reality-based 3D input and display environment, using a head-tracked high-resolution stereo coupled with a 3D wand. 3D display system has the advantage over 2D projected display in its accuracy of reflecting the "perceptual stability of the physical world". Deering calls this paradigm an "ab-10 Chapter 2. Related Work solute manipulation", in opposed to the rather "relative" traditional manipulation technique. 2.3.3 Discussion The above innovative interfaces are quite successful in alleviating difficult mathematics and controlling tasks for designers. On the other hand, they are designed with a particular group of target users in mind: For example, Shading Gradient appeals to artists who understand how to represent 3D features with 2D shaded images. Also, the sculpting metaphor uses repeated subtraction steps and is excellent for designers who are familiar with negative space. Finally, sketching and gestural techniques are suitable for prototyping and conceptual design where precision is not necessary. We believe all of these approaches are important and valuable, as no one technique will satisfy all artists' appetites under all occasions. However, there is limited work on composing a user-friendly system that is at the same time accurate. The French surface paradigm tries to seek a balance between the expressive capacity of an interface and the accuracy of the outcome. We hope to demonstrate that user-friendliness does not always lead to a sacrifice in accuracy. Users should have the freedom to choose their desired degree of abstraction and precision. We briefly mention here that many authors have argued on the issue of a 2D interface versus a 3D interface [21] [26] [39] [48] [54]. We pick the more common choice: a 2D interface with a "walk-around" rotation of the 3D model for inspection, as in [26] and [49]. Since the French surface idea proposes a general scheme rather than a particular input mechanism, it can be easily integrated with a 3D input or display system. 2.4 Motivation of Our Project: French Curves 2.4.1 Physical French Curves and their Advantages French curves, ship curves, and flexible curves are used by designers to create rigid and smooth curves. The most common among these tools is the set of French curves(Figure 1.2). The design of the French curve templates and the number in a set differ among different man-11 Chapter 2. Related Work ufacturers. French curve is just a general name for a rigid template providing a guide for curve drawing. The advantages of using French curves in the realm of curve design are twofold. 1. They provide templates for tracing out rigid curves. In contrast, it is difficult to draw accurate and smooth curves by freehand. 2. They offer a visual medium for selection and comparison. Psychologically speaking, choosing a shape from a menu requires less cognitive input than imagining an abstract form with no visual basis [36]. These advantages suggest a solution that can overcome limitations associated with conven-tional surface design systems. They are the motivation behind our surface modeller. 2.4.2 Digital French Curves and their Implications The use of French curves as a metaphor in computer graphics can be seen as early as in 1971 when McConalogue introduced an algorithm for passing tangentially continuous curve through scattered points [33]. More recently, digital French curves are used by researchers from Alias|Wavefront to demonstrate a GUI scheme based on tablet and transparency [29]. The technical details are depicted by Singh [44]. His technique uses French curves approxi-mated by elliptic arcs to create or edit 2D and almost-planar 3D curves. Our system considers the analogue of digital French curves in one higher dimension, namely 3D surfaces. We are curious about how the advantages of French curves can be extended to application in 3D surface design. We aim to initiate an exploration as to what extent a carefully predefined set of surfaces can reduce perceptual constraints of inflexible math structure and tedious freehand adjusting. We, however, are careful not to dictate a strict translation of Singh's method to the 3D scenario, as the geometric situations will be different. Since no physical French surfaces exist, our major effort is on the design of a set of French surfaces that is complete and well-arranged to allow 12 Chapter 2. Rela ted Work easy location for a desired surface feature. While French curves are used in the proof for transparency concept in [29], French surface is the concept that has to be proved here via one of many possible applications. 2.5 Primitive Surfaces When using French curve to draw a 2D curve, the 2D curve is first visualized as composed of short primitive segments, which are going to be approximated by segments of the French curves. The primitive concept is thus the rudiment of exploiting French curves in curve design. When this idea is extended to French surfaces, an important issue is deciding what surface primitives need to be included in the set of French surfaces. This reduces to understanding how primitive features comprise the design of an object. The primitive surfaces we choose to put in our set of French surfaces will be described in the next chapter. But first, this section gives an overview of the different interpretations of primitives in the graphics design litera-ture. 2.5.1 Primitive Surfaces in Existing Systems At one extreme are systems which employ primitive objects of one unified shape. The vision of a tangible 3D modelling medium using a Lego™-\ike computational building blocks is pursued by Anderson et. al. [1]. 3D geometry is recovered from the connectivity between the blocks in a construction, and graphical interpretation automatically augments the coarse structure into a more refined building model. This technology requires the realization of real-life objects as composed of low-level primitives of the same shape. In contrast, many systems provide users with a set of more complicated shapes such as quadrics (spheres, ellipsoids, cylinders) and cubes (e.g. Holosketch [11] and many commercial sys-tems). Here, each primitive is a candidate as a high-level component of the final model, as opposed, to being an elementary particle; the metaphor now is a model car or model airplane kit rather than Lego™. In most systems, each primitive has a list of attributes which can 13 Chapter 2. Related Work be changed numerically. Other systems, such as various direct manipulation modellers and sketching paradigms (e.g. Sketch [54] and Teddy [26]), require more user input to create or edit the primitives before they are combined. Primitives are also the backbone for constructive solid modelling (CSG) and implicit surface modelling. In contrast to parametric surfaces, an implicit surface is defined to be the zero-set of an implicit function f(x, y, z). Literature on implicit surface modelling includes works by Sederberg [41], Blinn [4], Bloomenthal and Wyvill [5], and Wyvill and Guy [53]. On one hand, algebraic-based implicit surface modelling uses polynomial functions, especially quadratics, as the implicit function [41]. On the other hand, the skeleton-based Blobby models (also called Metaballs) determine smooth implicit surfaces as a summation of point potentials created by an imaginative skeleton of electron fields [4] [5]. Common primitives such as quadrics, su-perquadrics, and cylinders can be created as the equipotential surfaces of specific point-fields, spline-fields, or polygonal-fields [5]. The primitives are put together using CSG Boolean op-erators (union, intersection, difference), and the final model is determined by the combined influences of the individual potential fields [30]. High-level operations such as blending, warping, tapering, and twisting are also available [53]. However one drawback is that each additional primitive may affect the global shape of the model [5]. 2.5.2 Discussion The concept of primitive is usually an assistant feature, but not the main focus of the above systems. As a result, the primitives are often too simple to allow casual construction of com-plex models. In this project, we want to explore the full potential of the primitive concept. The set of primitives in the French surfaces is rich and complete with the inclusion of the whole continuum of transitional shapes. But at the same time, it is also concise and well-organized to enable easy search for the right one. Our combining algorithm ensures that there is no unex-pected result. 14 Chapter 3 The F R E N C H SURFACE System: Theory The French surface concept can be a supplemental addition to an existing method or it can be the foundation of a totally independent system (Figure 1.3). The system F R E N C H S U R F A C E implements one of the many possibilities to provide an existence proof of the French surface concept. The bulk of the remaining chapters of this report develops the theory and algorithms needed to support the F R E N C H S U R F A C E system. There are 4 problems in the design tasks: 1. What surfaces are included in the set of French surfaces? 2. How can the user navigate through the space of French surfaces easily and locate the one she wants quickly? 3. What is the general scheme of the system? 4. And finally, how are selected surfaces going to be glued together to form the final model? The following sections reveal the footprints in completing each of these tasks. We will give a full account of the related issues, the different approaches we have tried, the rationale be-hind our final solution, and the supporting technical details. Our research is dictated by the guidelines stated in C1-C3 and the theoretical background in Chapter 2. 3.1 The Set of French Surfaces and its Navigation There must be a sufficient number of surfaces in the set of French surfaces to yield any arbitrary shape. But at the same time, the collection must not be over abundant or too redundant so 15 Chapter 3. The F R E N C H SURFACE System: Theory that searching for the desired surface will not be unduly awkward. This section describes the design of the set of French surfaces with its accompanying navigation technique that satisfies these principles. 3.1.1 The Surfaces in the Set of French Surfaces We first consider our 2D analogue: what shapes of curves are included in the set of French curves (Figure 1.2)? A well-designed set of French curves can include a continuous bounded subset in the set of all possible point curvatures (homeomorphic to the set of real numbers). However it is impossible to include all possible global shapes of curves in the set of French curves. French curves circumvent this difficulty by approximating a desired curve with primi-tive segments. That is, the user divides the desired curve into small segments and approximates each locally with an arc from the templates. This allows the creation of any 2D curve up to any desired degree of accuracy. Hence the primitive concept overcomes the requirement to include all possible curves1. Similarly, in the case of 3D surfaces, one principal difficulty is that there are infinitely many possible surfaces. Consider, for instance, the vast variation of wrinkles on your clothes. Like the French curve, it is impossible to include all imaginable surfaces in the set of French sur-faces. So our solution involves the use of primitive surfaces, analogous to the curve segments in French curves. However, unlike in the French curve, we decide to choose those included primitives carefully. After all, the number of 3D surfaces is incomparable to that of 2D curves; we cannot get away with an arbitrary set. To this end, we create a minimal set of surfaces: a set which is small enough to allow easy search, but sufficient to produce any 3D feature with a simple combining algorithm. Our set consists of ellipsoids, paraboloids, cones, various cylinders (ducts) and wedges, torii, and spirals among others not associated with common names. lWe are unaware of any discussion of why those particular curves were used as the contour of French curve templates. It seems that French curves do not have a standardized design and that each design is based on aesthetics and for compactness. The phrase "French curve" is used as a general term for any predefined curve template. 16 Chapter 3. The F R E N C H SURFACE System: Theory Figure 3.1: Some examples of French surfaces from the irvfinitely large set. Figure 3.2: Continuum of transitional surfaces from the ellipsoid to the drop. Figure 3.1 shows some examples from this infinitely large set of primitive surfaces. For ex-ample, we include the whole continuum of surfaces in the transitions from the ellipsoid to the paraboloid then to the cone (Figure 3.2). This is distinct from conventional approaches which exclude transitional surfaces. Also, all characteristic shapes come with the full spec-trum of spatial measurements such as scale, extent, and tilting angle. A closeness relationship between surfaces is thus established based on these parameters. The primitives paradigm provides a way around the problem caused by the enormity of pos-sible surface features. As many objects are an assembly of several smaller parts like blobs or sticks [21], the set of French surfaces, together with the blending technique described in the next chapter, can yield many complex surfaces. For example, blending several cylindrical wedges onto a flat surface can form wrinkles. In fact, the current system supports the creation of any object topologically homeomorphic to a sphere or a plane. The extension to arbitrary surfaces (e.g. self-intersection surfaces and surfaces with holes) is uncomplicated (e.g. see 17 Chapter 3. The F R E N C H SURFACE System: Theory [52]) and is left for future work. We note in passing that we have also considered the inclusion of hyperbolic surfaces, such as various saddles, in the set of French surfaces. But we were faced with the problems of the enormous variations of saddles. For example, common saddles usually have 2 ridges at 0° and 180° and 2 valleys at 90° and 270°, but in fact ridges and valleys can also occur at any angle. Also, some saddles can have more than 2 ridges and 2 valleys; for instance, the monkey saddle has 3 ridges and 3 valleys. Inclusion of all saddles would result in too many complicated parameters for the user to control. To partly circumvent this, our system supports the approximation of any saddle by blending several wedges to a flat surface. More work is required on the characterization of hyperbolic surfaces before they can be included in the set of French surfaces. We also want to mention that our original plan was to create a set of global surface features, rather than a collection of local primitive surface elements. Some examples of that type of sur-face are surface of waves, terrain, cloth wrinkles, hardware parts, and irregular round shapes. However, this is an endless list. Moreover, different artists will have different needs. We prefer the idea of a personalized library, for instance, a library of petals and leaves for floral artists, or a library of fluffy and rotund free-form shapes for artists designing stuffed toys. This would be the logical next step for future research (Section 5.3). 3.1.2 Navigation Technique Given the set of French surfaces, how can users traverse the set and easily locate the one they want? A strict imitation of the French curve idea would require that all primitive surfaces be incorporated into a few 3D templates. The advantage of compressing the primitive surfaces into a small number of large templates is that one can visualize the relationship between primi-tives in the whole surface space. Unfortunately, there are several practical difficulties in taking such an approach. Imagine, for example, combining some cones, paraboloids, and spheres of various sizes into a few surface templates. First of all, it is difficult to arrange them in such a way that the "closeness" relationship is preserved; that is, two shapes which are related or 18 Chapter 3. The F R E N C H SURFACE System: Theory similar to one and other should be placed close to each other. Second, it is not easy to visualize hidden surfaces in a complex formation. Finally, we would need a mechanism for specifying a desired region from the template. Such a mechanism necessitates the use of active drawing and freehand sketching; this is undesirable, given criterion CI. Given the above difficulties, we decide to treat each primitive surface as an individual French surface, and achieve the visualization of the space by an intuitive arrangement of the surfaces that reflects their closeness properties. We will see later that in effect, we are building a 9 dimensional French surface. We break the navigation design into three levels: On the lowest level (Nl), the parameteriza-tion lets us arrange and relate the French surfaces for easy visualization. On top of that is built the mechanism for traversing the space of French surfaces (N2). Finally, we focus our attention on interface development which resembles the visualization advantage of the French curves (N3). These are now discussed in detail. Let's start with the lowest level (Nl). Having designed the primitive surfaces, we realize that they generally have either a broad base or a narrow one. Then, surfaces within each of these two groups can range over various degrees of "sharpness". This gives the basis for visualizing the set of French surfaces arranged in a 2D array (Figure 3.3). Moving through the array verti-cally, surfaces are arranged from "bumps" to elongated shapes; moving horizontally, surfaces range from those with rounded tops to those with sharp tips or edges. To provide an intuitive searching algorithm in an infinitely large set of abstract objects, a sampling of the set serves as the starting point for search. Figure 3.3 shows how the samples are arranged on the control panel. Each category of shapes in the 2D array comes with a complete range of values in up to 7 parameters (e.g. scale, tilting angle, thickness, extent, etc.) Hence, the whole structure is embedded in a 9D space. In mathematical terms, this gives a topology to the set of surfaces; in data-analysis parlance, a coding system is formulated. 19 Chapter 3. The F R E N C H SURFACE System: Theory Comparison Of Surfaces Starting Point Surfaces Fiench Surface • i i Confirm Load E * F Axes P* Wireframe r QJ Pane Memory; Store | Recai Swap •ear Elliptic Parab, Wed^e Tari Cupped Round Q t _ j £ lb Cylinder C 3 Straight fife- O Torus Range I"" Lock Unbend Sham Blunt Stretch x 1.20 | _ | J Stretch y 1.20 | _L J Stretch z| 1.20 Navigation J Handles Cut rim I 0 Enlaige fcS" Extend flo" Shaip 0.D0 Figure 3.3: The control panel. The second level (N2) of the navigation technique is built on the closeness relationship. For instance, the sphere is related to the ellipsoid by stretching, the round cylinder is related to the triangular cylinder by sharpness, and the spiral is related to the torus by tilting. The French surface space is traversed by adjusting the scale bars (Figure 3.3) with the assistance of buttons like "Bend" and "Unbend". Different French surfaces have a different set of scale bars. Users are virtually cropping the base of a cone, scaling a paraboloid, extending the ring of a torus, bending a cylinder, or tilting the angle of a wedge. The "Range" button allows users to toggle between coarse and fine scaling, and the "Lock" checkbox gives the option of scaling each direction individually or simply scaling the model as a whole. The system is a state machine which accumulates changes performed; in other words, if you tilt and then bend a cylinder, the result will be a spiral, instead of a torus. For the top level of navigation (N3), we have created the buttons "Store", "Recall", and "Swap" (Figure 3.3). The "Store" button is used to save the current surface and configuration before the 20 Chapter 3. The FRENCH SURFACE System: Theory R B C Figure 3.4: The spiral for capturing surfaces with orthogonal principal directions. user adventures more in the neighbourhood. He can "recall" the stored configuration at any time, and when the user arrives at another suitable surface, he can "swap" between the two to compare them. We attempt to display the neighbourhood of each French surface the user goes through for comparisons and visualization purpose. This is to leverage off the visualization advantage of French curve. The buttons are designed to overcome the difficulties of displaying a 9D local neighbourhood. As a bonus, this functionality also allows easy creation of identical surface entries. 3.1.3 Alternative Approach Our original intention was to provide users with a few huge French surface templates, and allow them to select any desired region inside these templates. We had considered the use of a spiral as one of the French surface templates (Figure 3.4). We were motivated by a common class of surface points: those characterized by the 2 orthogonal principal directions [13]. For each radius r (curvature 1/r), the points on the radial cross section have the whole range of orthogonal radii from — (r — a) to +(r + a). Here, "+" denotes positive curvature (bowl) and "—" denotes negative curvature (saddle). In Figure 3.4, we have a saddle at A , a (curved) cylinder at B, and a bowl at C. We hoped that the spiral may be generalized to some tilted spirals to yield surfaces of non-orthogonal princi-21 Chapter 3. The F R E N C H SURFACE System: Theory pal directions. With the addition of some generalized cylinders, we envisioned a powerful set of French surface templates. We rejected this method however, because the selection of regions within a template requires tedious user input, which is a violation of CI. We also realized the incompleteness of the set. Other limitations have been depicted in detail in Section 3.1.2. Yet we can combine the set of spirals and generalized cylinders with our navigation technique to serve as a map showing the "position" of a selected surface in the "big picture". Developing this potential could lead to a fulfilling visualization technique. 3.2 General Scheme There are many avenues we can take to test this set of French surfaces. We can treat it as a selection basis to use in conjunction with an existing paradigm. We can also design a new system that caters particularly for criterion C1-C3 to test the French surface concept. We must decide on the general framework before the implementation details can be constructed. 3.2.1 Logical Framework of the Scheme In terms of the logical structure behind our system, there are two options, the bottom-up and the top-down approach. On one hand, the bottom-up approach allows artists to work on smaller components of the artwork before combining them together to give the final model. On the other hand, designers using the top-down approach first construct a rough shape of the model. Details are then added in a stepwise refinement process. As an example, an artist creating a sculpture of a cow using the bottom-up approach will make the head, the legs, the body, and the tail of the cow separately. These parts are combined together afterwards. In contrast, an artist following the top-down approach will first build a rough model of the body of the cow. Major body components like the head and the legs are added next. Then come smaller parts, such as eyes, ears, nose, toes, and so forth. The sculptor keeps refining the model until the desired level of detail is reached. 22 Chapter 3. The FRENCH SURFACE System: Theory Both of these strategies are seen in artists' practice. The top-down approach is, however, more intuitive and more common to sculptors and 3D artists. It is easier to get the right proportion using this scheme than using the bottom-up approach. Moreover, the stepwise refinement procedure implies the design task is a sequence of many simple steps rather than a few com-plicated ones. The refinement cycle also prevents the psychological burden of having to choose the right surface the first time. A mistake in an earlier step can be amended by blending in another piece or subtracting some volume away at any later time; this resembles exactly what a sculptor would do. Finally, the level of abstraction of the art-piece is comfortably under con-trol. Psychologically speaking, the artist is free in her creation without being hindered by the need to plan ahead. These considerations are important to satisfy C3 in our criteria. 3.2.2 Pragmatic Framework of the Scheme The top-down scheme and the criteria C1-C3 are the foundations for the practical structure and the interface design of F R E N C H S U R F A C E . The interface consists of a drawing screen (canvas) and an independently positionable control panel. The control panel is used for selecting the appropriate French surface and controlling the blending operation, while the screen is used for displaying and positioning the artwork. Since there are infinitely many French surfaces, only a sampling of the full set is displayed on the control panel. As mentioned before, they serve as the starting point of navigation. Figure 3.5 shows some beginning stages in the creation of an artwork using F R E N C H S U R F A C E . The typical steps in each stage begin with the selection of a French surface from the sampling set on the control panel. Then the user navigates for the exact one he wants by adjusting scale-bars and action-buttons, and by using "Store", "Recall" and "Swap". The surfaces will be displayed dynamically on canvas. Positioning of the surface relative to the progressing model can be done at the same time the user traverses the space of French surfaces. Placing the surface above the model corresponds to the addition of volume (adding clay), while placing it under simulates the subtraction of 23 Chapter 3. The F R E N C H SURFACE System: Theory Figure 3.5: Stages in drawing Piggy in Figure 1.1. Select the Starting Point Surface Navigate for the Desired Surface Store and Swap to Compare Choose Blending Power Confirm Blending 1 Position the Surface Inspect the Configuration Figure 3.6: The creation cycle in the F R E N C H S U R F A C E System. volume (carving away clay). Blending are performed to join the surface and the progressing model together. The smoothness of the blending may be adjusted, among other options. The user may also virtually walk-around the artwork to inspect the configuration. Users can freely experiment with different surfaces, positioning, and blending results; no op-eration is finalized until the "Confirm" button is pressed. This procedure is repeated to build the model incrementally (Figure 3.6). The user is free to save the current model or load an old one at any time. In summary, this general scheme provides a setting to incorporate the set of French surface as a tool in a 3D modelling environment. The main features of this system are: 1. the complete and continuous set of predefined French surfaces for selection; 2. the organization of the set reflecting closeness relationship among French surfaces to provide easy navigation; 3. the visualization technique which allows understanding of the "big picture" for easier 24 Chapter 3. The F R E N C H SURFACE System: Theory comparison and search; and 4. the blending algorithm which ensures what-you-see-is-what-you-get. 3.2.3 Alternative Approach We have also considered using the bottom-up scheme as the logical skeleton behind the sys-tem. In that case, a collection of French surfaces placed side-by-side are to be joined together at the seam (Figure 3.7). We prefer, however, the top-down scheme over the bottom-up approach. In addition to its advantages discussed above, the top-down scheme allows tractable control and predictable results implementation-wise. On the other hand, using the bottom-up metaphor, designers are required to define the curve along which two surfaces are to be joined together. Hence, some degree of freehand input is inevitable, against CI. Yet it would be worthwhile in future research to look for a graceful solution for a bottom-up based addition to the system. One possible solution is inspired by the mesh zippering tech-nique used in combining range images representing different perspectives of a single object. In [47], Turk and Levoy describe a method that first zippers range images together, then re-fines the surface geometry through an averaging operation on the contributing range images. In particular, their system is incremental, that is, the surface is reconstructed by combining range images one at a time. This fits nicely with the bottom-up approach, and it suggests an alternative combining method than the blending technique used here. 25 Chapter 3. The F R E N C H SURFACE System: Theory Figure 3.7: The bottom-up approach. 26 Chapter 4 The F R E N C H SURFACE System: Implementation and Evaluation A surface design modeller implementing the methodology described above has been devel-oped. The F R E N C H S U R F A C E system, which runs at interactive speed on a standard P C , is written in C code with the assistance of OpenGL, G L U , and G L U T libraries. The control panel is created with Tcl/Tk. This chapter discloses implementation details, including our nontradi-tional surface representation, and the original blending algorithm. 4.1 Representation and Local Approximation 4.1.1 Triangulated Point Set We require a representation for interactive blendable surfaces, with no a priori limit on their geometry and how two are going to be configured and combined. Because constraints from mathematical architecture are undesirable (C3) , the representation must be as simple as possi-ble. It must also be flexible enough to resolve both smooth surfaces and hard edges. Our choice for surface representation is the triangulated point set. This vision is also shared by [26], [32], and [52]. Our surfaces are tessellated into triangles, and an independent functional induces and updates local connectivity between neighbouring triangles of the models when needed. We use just enough sample points to unambiguously define the surface topology and carefully space them to preserve curvature. For example, we triangulate a sphere by evenly spaced triangles of roughly the same size (Figure 4.1a), rather than the more usual triangulation based on longitude and latitude (Figure 4.1b) resulting in lots of tiny triangles 27 Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation Figure 4.1: Triangulation of a sphere, (a) The preferred uniform triangulation. (b) Nonuniform sampling and triangulation. at the poles. We postulate a good triangle mesh must conform to the rule that the area of a triangle is inversely proportional to the local curvature1. Normals are needed for rendering and blending purposes. A fair amount of machinery goes toward reconstruction of the normals at sample surface points. Given a triangulated point set, each vertex normal is usually calculated as the mean of facet normals of all the triangles containing the vertex. However, averaging normals of all triangles at a hard edge tends to smooth the edge out. With this concern, we adopt Robins' method [38] where a facet normal is included in the averaging if and only if its direction is close to that of the other facet normals within an angular threshold. This tends to capture hard edges. In the view of our implementation, tangent computation is only required to find the tangent (t) perpendicular to the rim of French surfaces where blending occurs(see Figure 4.2). First, the tangent of the rim curve at a rim vertex a, is approximated by fitting a circle to the three con-secutive rim vertices {ai_i, ai, aj +i} in its neighbourhood. As rim vertices are approximately equally spaced, the tangent turns out to be simply ai+i - aj_i. Then the required directional tangent t; is calculated as n; x (a , + i — ai_i), where n, is the normal vector. French surfaces are characterized internally by different parameters and categories of shapes (Chapter 3). The corresponding triangle mesh will be generated on the fly when a certain Consider a small circle and a big circle. If the big circle is approximated by a regular octagon, a smaller circle requires also a regular polygon of 8 sides, but not less, to give the same degree of accuracy. It is the curvature not the size that matters. 28 Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation Figure 4.2: The rim of a French surface is represented by a counter-clockwise sequence of equally spaced vertices {ao, a i , . . . , ax}. Directional tangent at each rim vertex a; is required in the blending algorithm. French surface is requested. On the other hand, the progressing model is saved as a triangle mesh. Despite its intensive memory occupancy, this is preferred over saving just the parame-ters' values and the blending steps. This is to ensure portability even if the modelling routines are later modified. Although triangle mesh fairing is postponed in this short Master's project, we do not lose sight of its importance to maintain a decent shape resolution after each blending operation. Uneven sample distribution and skinny triangles may result from the introduction of new sample points. However, we are surprised to discover with the initial optimization of the mesh, we are seldom troubled by unexpected wiggles; the surfaces behave robustly under blending operations. 4.1.2 Alternative Approaches A n alternative surface representation method is to utilize the tensor product B-splines. These surfaces are suitable for modelling rectilinear topology, but they have artifacts when applied to irregular formations, blends, and fillets [15] [21]. The dependency on an initial planning of the patches layout, and the inflexible mathematical structure make tensor product patches un-29 Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation suitable for intricate design purposes. On the other extreme, point-based range data involves completely no structure at all to explain the topology. For the F R E N C H S U R F A C E system, our triangulated point set uses just enough structure to clearly define the shape; it is a hybrid of the patch-based and point-based systems. Another surface representation scheme we have considered is the hierarchical B-spline method proposed by Forsey and Bartels [17]. Under this approach, a surface is represented using a series of B-spline surfaces with different "levels" of resolution. Each level k consists of a set of B-spline surfaces with twice the resolution of the surfaces in level k - 1. The bases in each level must be decomposable as a linear combination of bases in a smaller level. The main advantage of hierarchical B-spline representation is that it supports local surface refinement, a procedure impossible in traditional tensor product surface representation. Forsey and Bartels also introduce some local editing techniques based on overlays of hierarchically controlled subdivision. Finally, we have also considered subdivision surfaces as an alternative surface representation scheme. In general, subdivision surfaces are represented by an initial polygonal mesh and a mesh refinement procedure. The refinement procedure is based upon the binary subdivision of the uniform B-spline surface to produce a more refined polygonal mesh. Through a sequence of repetitive subdivision steps, the generated meshes converge to a smooth surface that is topologically equivalent to the initial mesh. The most common subdivision surfaces are (i) Doo-Sabin surfaces, which involve subdivision of bi-quadratic uniform B-spline surfaces [14], (ii) Catmull-Clark surfaces, which utilize refinement of bicubic uniform B-spline surfaces [6], and (iii) Loop surfaces, which involve subdivision of quartic uniform B-splines [23]. In par-ticular, Doo-Sabin and Catmul-Clark surfaces are based on meshes built out of quadrilaterals, while Loop surface is based on triangle meshes. Loop surface is thus a nice generalization of the B-spline scheme to non-rectangular base domains, covering the most general case. The major advantage of subdivision surfaces is the flexible patch layout they offer. Although the lack of an exact evaluation scheme has often been cited as a drawback of subdivision sur-30 Chapter 4. The FRENCH SURFACE System: Implementation and Evaluation faces, this problem has recently been overcome [46]. Hence, a wide range of topological types can be represented. Also they do not require an initial planning of resolution, so a more direct control over accuracy can be achieved. Moreover, subdivision rules can be modified to support piecewise smooth surfaces with sharp or semi-sharp creases [12]. This allows explicit control of smoothness properties. For future work, we would like to adapt subdivision surfaces as the surface representation of our system. 4.2 Positioning Techniques for positioning objects in 3D constitute a rich field of research in human computer interaction. The scope of our project does not include an in-depth investigation of the position-ing issue. We support three simple positioning modes: pure translation of the French surface, pure trackball rotation of the French surface, and a trackball rotation of the French surface and model as a single rigid system. The first mode involves translation parallel to the screen while the second controls rotation about the center point in the base of a French surface. They couple together to support placement of the French surface relative to the progressing model with trackball motion. The third mode allows for "walking around" the artwork to examine the geographical relation of the French surface and the model. The wire-frame display mode can be switched on to allow a see-through inspection. These actions are bound to the left mouse button and the keyboard shift and control keys. For a blending operation to be valid, we purposely require that a French surface should be positioned so it does not intersect the model. The motivation for this is to create a what-you-see-is-what-you-get effect. The complete French surface should appear in the blended model exactly as when the user choose it. If, on the other hand, we allow a French surface to intersect the model, then part of the French surface will be cropped to create a margin for blending. This is undesirable as it increases the chance of obtaining an unexpected outcome after blending (C2). We propose in the future research the option of automatic positioning using the iterative closest point (ICP) method. 31 Chapter 4. The FRENCH SURFACE System: Implementation and Evaluation Correspondence Points Step 1 Boundary Vertices Boundary Triangles Step 2 Step 3 Step 4 Figure 4.3: The blending algorithm. Step 1: establishing correspondence; step 2: finding boundary triangles and boundary vertices; step 3: removing enclosed triangles; step 4: form-ing the blending surface. 4.3 Blending Most literature on blending is for parametric [16] [20] or algebraic surfaces [22] [50], not for polygonal modelling. They mainly deal with the construction of a transitional surface between two rail curves or smoothing out of creases or corners, which are not suitable for our purpose. This chapter describes our original technique for blending the French surface along its rim to the model (Figure 4.3). Figure 4.3 gives an overview of the steps. First, step 1 establishes a correspondence from the rim vertices to points on the model. Then, step 2 interpolates the triangles containing the correspondence vertices and finds the continuous loop of vertices (called boundary vertices) im-mediately surrounding the correspondence vertices. Next, step 3 removes all the enclosed triangles. Finally, step 4 creates a C1 smooth blending surface between the boundary and rim vertices. The algorithm seems cumbersome but in fact it runs in real-time. The code for the blending algorithm is in Appendix A. 4.3.1 Step 1: Establishing Correspondence To blend the French surface to the model, vertices along the rim of French surface must first be put into correspondence with points of the model (Figure 4.4). The circular curve at the prede-fined rim of each French surface is stored as a counter-clockwise sequence of geodesically equal-spaced vertices {ao, a i , . . . , ax}. Recall that the normals ni and the tangent perpendicular to 32 Chapter 4. The FRENCH SURFACE System: Implementation and Evaluation Figure 4.4: The correspondence between the rim vertex a; of the French surface and the model, cj denotes the correspondence (or intersection) point and T i the triangle containing it. the rim tj are evaluated at each rim vertex a, using information from the local neighbourhood (Section 4.1). For each rim vertex a;, the goal is to determine the correspondence point c; on the model (Figure 4.4). We consider the 2D planar view containing n\ and tj (Figure 4.5). The simplest case is to use the intersection point of ti with the model as c;. A sharp edge will then result at the base of the blending surface. However, to create a smooth blend between the French surface and the model, we use instead a ray r; which is at an angular deviation 6 from ti. We will discuss later how we determine the value of 8, but let's assume for now 6 = 10°. Then the rim ray r\ equals to cos6t\ + sin6ri\. Once T\ is known, the next step is to find C i , the intersection point of n and the model. Steps la-lc discuss the algorithm in detail. Note that it is possible that the intersection may not be unique (Figure 4.6a); in those cases, we choose C i to be the intersection point closest to a;. Stepla: Build a Trinary Neighbourhood Tree. First, we need the preliminary step of finding the 3 neighbour triangles for each triangle in the model. This is a once-and-f or-all procedure and it has roughly linear complexity O(n) because 33 Chapter 4. The FRENCH SURFACE System: Implementation and Evaluation Figure 4.5: The planar cross section for determining the correspondence point c;. For smooth blending, Cj occurs at an angle deviation from t j . Figure 4.6: (a)If rj intersects the model more than once, choose the closest intersection as c;. (b)Test 1 restricts the triangle candidates to those with centroids inside a s-cylinder around r\. 34 Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation neighbours are close by in the triangle list. Steplb: Search for c o by going through all model triangles. This step focuses on the first rim vertex ao and rim ray ro, and searches over all triangles T of the model for the intersection co- There are 2 qualification tests. Test 1 checks whether the centroid of T is within a perpendicular distance of e to ro (Figure 4.6b). e = 0.1 is a good start. Test 2 involves solving a 3 x 3 constrained linear system2 to see whether ro really passes through T . Since Test 2 is a computationally intensive procedure, Test 1 is designed to filter out most of the disqualified candidates. Let To be the triangle which passes these 2 tests, and is closest to ao- Let Co be the correspond-ing intersection point. Steplc: Use breadth-first-search repeatedly to find all Cj using C j _ i as the starting point. Note that since a i is adjacent to ao, c i and T i must be close to co and To respectively. Hence to search for T i , we build a dynamically updated queue of candidate triangles so that candidates closer to To are tested first. Algo 1 explains the breadth-first-search algorithm. Algo 1: Breadth-First-Search Initially insert To to the empty queue. Then check whether r i passes through T 0 by the 2 tests: (Test 1) the quick £-cylinder test and (Test 2) the constrained linear system test. If yes, we are done. Else, add the 3 neighbours of To to the head of the queue and delete the tail=T 0 from the queue. Repeat the procedure to the new tail of the queue. If it passes the 2 tests, then break from the iteration; else add its neighbours to the head of the queue, remove the failed tail, and repeat the routine on the new tail. If the queue becomes empty before a solution is found, we (Test 2) Let P, Q, and S be the vertices of the triangle candidate T. Solve [ai-P] = [ Q - P | S - P | - r i ] a P t for a, (3, and t with constraints a > 0, (3 > 0, a + fi < 1, t > 0. v 35 Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation Figure 4.7: Joining T ; and T i + 1 (shaded) by finding the intermediate triangles (dotted), and recording their outside vertices which will become the boundary vertices. have reached an edge or a hole, and blending is invalid. The queue is a doubly-linked list that allows examination of candidates in a first-in-first-out fashion. In practice, this algorithm usually terminates in a few iterations. It is repeated for all 1 < i < K to locate T; using T ; _ i as reference. This breadth-first-search exploits known knowledge to enhance efficiency. 4.3.2 Step 2: Finding Boundary Triangles and Boundary Vertices The natural next step is to fill in any possible gaps between the adjacent intersection triangles Tj and T ; + i (Figure 4.7) in order to construct a continuous circle of boundary triangles. The synopsis goes as follow. Let m, denote the midpoint between a; and &\+\. The intermediate triangles between T; and T j + i are determined as those cut by the plane containing mi, Ci, and C i + i . At the same time, the plane separates the vertices of these boundary triangles into 2 categories: outside and inside'. The outside vertices in the boundary triangles are called the boundary vertices (Figure 4.7). They are necessary in the formulation of triangles along the base of the blending surface. Al l triangles bounded within the boundary vertices will eventually be removed. Steps 2a-2b depict the details for carrying out Step 2. 3Define a function / on the model vertices to E to be /(v) = ((ci - m;) x (c; +i - mi)) • (v - c;). Then V is outside if and only if /(v) > 0 and inside if and only if /(v) < 0. 36 Chapter 4. The FRENCH SURFACE System: Implementation and Evaluation Step2a: Finding the intermediate triangles between each pair of T; and T i + i . The trinary neighbourhood tree is utilized again to exploit the local connectivity. Algo 2 de-scribes how to connect T i and T i + 1 . Here, v o u t designates an outside vertex and v i n an inside one. ; Algo 2: Connecting T ; and T i + 1 Initially, begin with triangle T i . T; either has 2 outside vertices and 1 inside vertex, or 2 inside vertices and 1 outside vertex. Assign v o u t to be the more counter-clockwise outside vertex of T i and v i n the less counter-clockwise inside vertex (Fig-ure 4.8a illustrates two examples). v o u t and v j n turn out to be precisely the vertices that T i share with the first intermediate triangle. Hence let Irj be the neighbour triangle which shares v o u t and v j n with T;. Next determine whether the unvisited vertex of l o is outside or inside, and update v o u t or V i n (Figure 4.8a). As before, the neighbour which shares the v o u t and V i „ with I 0 must be the next intermediate triangle Ii . Repeat until we reach T i + i , recording the consecutive list of outside vertices as we progress (Figure 4.8b). In effect, we are walking along adjacent triangles between T i and Tj+i. The procedure is repeatedly applied to all pairs {Ti, Ti+i}0<i</<--i and { T K , T 0 } to form K + 1 sequences of boundary triangles {So, • • • ,SK}- The outside vertices of the boundary triangles become boundary vertices. It is tempting to assume that the triangles are always one-up-one-down since the algorithm would be much simpler. However this is a false assumption. Figure 4.8c shows a counter example where some adjacent triangles do not have alternative orientation. Step2b: Remove repeated and extraneous boundary vertices at the joint of Si and Si+i. Now the K+l sequences {So, . . . , £ # } of boundary vertices have to be concatenated to resolve a cycle of boundary vertices. This is somewhat complicated on account of repeated, extraneous, and/or missing boundary vertices at the joints. Figure 4.9 shows some of the possible scenar-ios at the joint Tj+i of Si and Sj+i, assuming the sequences overlap by at most 2 triangles. (We 37 Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation (a) example 1 example 2 Figure 4.8: Finding intermediate triangles between T i and T [ + i . (a)Two examples explaining the algorithm. (b)The end result. Here, I; represents the intermediate triangles, and Si = {T;, lo, I i , . . . , T i + i } represents the boundary triangles. Their outside vertices become the boundary vertices. (c)An example showing the boundary triangles may not follow a one-up-one-down pattern. 38 Chapter 4. The F R E N C H S U R F A C E System: Implementation and Evaluation omi t situations where it is obv ious no amend ing is required). In the diagrams, the black triangles indicate Si w i t h the black l ine des ignat ing the nijCjCi+i intersection plane. The b lack dots indicate the boundary vertices i n Si. S im i l a r l y the l ight grey triangles, the l ight grey l ines, and the l ight grey dots represent the cor respond ing features for 5j+i. Dots w i t h more than one co lour be long to more than one sequence. Cases 17 to 25 describe special s ituations w h e n Si consists of just 2 tr iangles w i t h 1 boundary vertex. In those cases, Si-i ( in dark grey) also needs to be taken into account. The dot-diagrams (on the r ight i n each case) show the concatenated sequences b y juxtapos it ion. M i s s i n g vertices are represented by "?", ident ica l vertices are jo ined b y and vertices to be removed are ma rked b y "x". To i l lustrate more clearly, consider Case 3 where the second-last vertex of Si coincides w i t h the first vertex of 5,+i at B (see F igure 4.10). A l so , the last vertex of Si at C shou ld not be i n c l uded i n the l ist of bounda r y vertices. W h e n the sequences Si and Sj+i are concatenated to f o r m {••• A B C B D • • •}, the 2 copies of vertex B have to be comb ined and the vertex C has to be removed. The result ing sequence shou ld be {• • • A B D • • • }. Cases 2, 4, and 16 are other examples of repeated vertices. They have one pa i r of repeated vertices that have to be condensed, and 0,1, and 3 extraneous vertices respect ively that have to be removed. Cases 7 and 8 are examples of a mi s s ing bounda ry vertex; the corner vertex is ignored i n both Si and Si+i because i t is inside of the intersection planes for both sequences. Cases 17 and 18 are examples of a vertex repeated three times, wh i l e Cases 24 and 25 are examples where there are more that one pa i r of repeated vertices. Clearly, m i s s ing vertices shou ld be added, repeated vertices shou ld be condensed, and extra-neous vertices in-between shou ld be removed. To retrieve a l l repeated and extraneous vertices, w e real ize that it is enough to compare the 6 consecutive vertices i n the concatenated sequence beg inn ing w i t h the th i rd last boundary vertex of Si for a l l i. These 6 nodes are compared i n pairs i n an outside-in manner to accommodate tr ip le repet it ion (Cases 17 and 18), nested pairs (Case 24), or intersecting pairs (Case 25) of repeated vertices. F inal ly, a mi s s ing boundary vertex occurs at a tr iangle T w h e n and on ly w h e n exactly 1 of T ' s ne ighbours is a b o u n d -39 Chapter 4. The F R E N C H S U R F A C E System: Implementation and Evaluation Figure 4.9: Possible scenarios at the joints of consecutive sequences of boundary vertices. Black, light grey, and dark grey denote Si, S i + i , and S,_i respectively. The dot diagrams show the concatenated sequence in each case. "?" represents a missing vertex, "w" an identical vertex , and "x " a vertex to be removed. See Figure 4.10 for a case study. 40 Chapter 4. The F R E N C H S U R F A C E System: Implementation and Evaluation repeated extraneous Figure 4.10: Case study of case 3 in Figure 4.9. See text for explanation. outside triangles boundary triangles inside triangles enclosed triangles ^ to be swept out by recursion Figure 4.11: Removing boundary and inside triangles. In the mesh, only boundary triangles are labelled, but inside and outside ones are not distinguished from each other. ary triangle and the other 2 vertices of T are already marked as boundary vertices. Missing vertices can be captured easily during the next step (Step 3). 4.3.3 Step 3: Removing Enclosed Triangles Inside and outside triangles are not yet distinguished from each other. Only the loop of bound-ary triangles are marked in the mesh. However the inside triangles together with the boundary triangles have to be removed (Figure 4.11). The identification of covered triangles is imple-mented by a (depth-first) recursion r(T) . Algo 3: Recursive Removal of Enclosed Triangles 41 Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation Initially invoke the recursion r with input T = some boundary triangle. Inside the recursion, if T is not a boundary triangle, then it must be an inside triangle by the construction of the recursion. So mark T as toBeRemoved and apply recursion r on its 3 neighbours. If T is a boundary triangle, we mark T as toBeRemoved. We also want to continue recursion on its non-outside neighbours. The inside-outside property can be deduced from M r , the number of vertices of T which are boundary vertices. Figure 4.12 exhausts all the possible cases: • If M r =0,1 (cases 2,4, and 5), apply recursion to all neighbours of T. • If M T = 2 (cases 1, 6, and 8), apply recursion to all boundary neighbours of T. If in addition, T has only 1 neighbour which is a boundary triangle (case 6), then the last vertex is a missing boundary vertex. Insert it into the correct position in the list of boundary vertices. • If M T = 3 (cases 3 and 7), apply recursion to only the neighbours which are boundary triangles. The terminating condition of recursion is that T is already marked as toBeRe-moved. The toBeRemoved triangles are made temporarily invisible. They are truly purged when the user confirms the blending operation. For the sake of explanation, the previous discussion assumes that the inside portion under-neath the French surface is to be removed and the outside portion is to be kept (Figure 4.13a,c). In fact, the user can also choose the option of removing the outside and keeping the inside (Figure 4.13b,d) by using the checkbox "Enclose". In this case, the rim rays will be set at 10° inward of the tangent rather than outward. This feature allows the creation of the broad class of closed surfaces. Moreover, to simulate both addition and subtraction of clay in sculpting, a French surface can be blended to the back of the model (Figure 4.13c,d). The normal directions are adaptively adjusted to maintain consistency of intrinsic (front-back) orientation. 42 Chapter 4. The F R E N C H S U R F A C E System: Implementation and Evaluation c a s e Number of Boundary Vertices o f T ( M T ) Boundary Triangles o fT Action Examples A = Boundary Triangles • = Boundary Vertices 1 2 2 boundary As, 1 outside A recurs on the 2 boundary As - A A A -2 1 2 boundary As, 1 inside A recurs on all 3 As T V W 3 3 1 boundary A, 2 outside As recurs on the 1 boundary A 4 0 1 boundary A, 2 inside As recurs on all 3 As 5 1 3 boundary As recurs on all 3 boundary As 6 2 — * 3 1 boundary A, 2 outside As recurs on the 1 boundary A missing^^^^^ 7 3 2 boundary As, 1 outside A recurs on the 2 boundary As 8 2 3 boundary As recurs on all 3 As W Figure 4.12: Possible scenarios when we arrive at a triangle T during the recursive marking of toBeRemoved triangles. The number of boundary vertices of T (Mp) induces which neigh-bour triangles of T we should apply recursion to. The thin black line indicates the boundary between outside and inside. 43 Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation Figure 4.13: The use of the "Enclose" checkbox to choose what side to keep, (a) Blend on top and keep outside, (b) Blend on top and keep inside, (c) Blend underneath and keep outside, (d) Blend underneath and keep inside. Figure 4.19 shows the 3D version of these diagrams. 4.3.4 Step 4: Forming the Blending Surface Recall the corresponding pair: aj on the French surface and c; on the model. The blending surface is formed by joining each pair with a smooth curve which has the desired shape, and whose tangents at the end points agree with that of the surfaces. We use a Bezier curve with control points at a;, c;, and Xj the intersection of the tangents at aj and Cj on the cross section plane (Figure 4.14). The power of blending is varied by changing the multiplicity of X J ; more coincident points at x; yields a tighter blend [35]. For instance, the Bezier curve with 1 and 2 coincident points are: 7 l (s) = (1 - S ) 3 C J + 3s(l - s)x; + £ 3aj,0 < t < 1 and 72(s) = (1 - S ) 4 C J + (s2-s + 2)XJ + t 4 a i , 0 < t < 1 respectively. We have also experimented with blending of power zero using a straight connec-tion line, that is, the directional tangent t. This version provides a sharp edge at the base. Taking the view that our surfaces are represented by a discrete triangulation, the connection curves are sampled at 5 locations. Together with the loop of the boundary vertices, these 6 layers of sample points serve as the nodes to weave the triangle mesh. As the number of boundary vertices may be different from the number of vertices of the above layers, a merging 44 Chapter 4. The FRENCH SURFACE System: Implementation and Evaluation Figure 4.14: The use of Bezier curves to create the blending surface and various degree of blending. w i w 2 w 3 w 4 • • • V i v 2 v 3 A/. /vvrv Figure 4.15: Merging 2 sequences of vertices to create an even triangle mesh. algorithm is used to form a well-conditioned mesh: Algo 4: Merging Given 2 layers of vertices {v;} and {WJ} (Figure 4.15). First join v i and wi . If distance(vi,wa) < distance(wi,V2), join v i and W2. Else, join w i and V2. Re-peat the procedure so that in a general iteration, compare distance(vu Wj+i) and distance(wj, v ; + 1 ) , and join the closer pair. The repetition halts when we return to v i (or wi) around the loop. The remaining w/s (or vi's) are joined to v i (or wi). Via this construction, an even triangulation will be woven through all vertices in the 2 layers. 45 Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation Figure 4.16: Rays from the rim as a positioning guide. They also give the user an idea of what to expect in the blending result. 4.3.5 Discussion and Implications of the Blending Algorithm The above procedure is triggered by the press of the "Blend" button. In the current system, the user is responsible for the positioning which in turn affects the smoothness of the blending. To assist the user with positioning, and to give an idea of what the blending result will look like, the rim rays (r;) are displayed to serve as a blending guide (Figure 4.16). A blending surface will be displayed whenever the blending operation is valid. A n invalid blending operation occurs when the user attempts to blend over the edge of the model, or when the loop of boundary triangles passes through a hole. Invalid moves are detected either in the projection of rim rays or during the recovering of boundary triangles. Originally, we had additional tests to ensure all invalid blending attempts are filtered. A n example is the jump-limit threshold which disqualifies sudden jumps between two intersection triangles. Yet we found that they are redundant as the original algorithm already captures all unexpected results. The user can adjust the French surface template or its position anytime during the modelling procedure. As soon as the modification begins, the blending surface vanishes. A new one is formed the next time "Blend" is pressed. It is natural to suggest dynamic blending. We have implemented an initial prototype of dy-namic blending, but we are disappointed with the result. The flickering blending surface (due to sometimes valid and sometimes invalid blending) confuses the canvas environment and the movement trajectory when the user is simply performing coarse positioning. We have tried 46 Chapter 4. The F R E N C H S U R F A C E System: Implementation and Evaluation (a) C i vs. (b) Figure 4.17: Two interpretations of the power of blending: (a) varying the tightness of the blend; and (b) varying the extent of the blend. to overcome this by delaying blending to the end of the move (i.e. when the mouse button is released). So blending is dynamic all the time except during positioning. However we are still troubled by ceaseless replication of the blending algorithm, an intensive computation. Display is delayed tremendously, especially during the later stages of design. Dynamic blending is of-ten confused by the multi-threading execution of the many callback functions. Thus currently, we go back to the static scheme, with the ray-guides suggesting the blending result. We will continue to look into dynamic blending in future research. One issue that arises is whether the power of blending depends on (a) the tightness or (b) the extent of a blend (Figure 4.17). We are unaware of any literature that addresses which inter-pretation, if any, is more intuitive under different geometrical circumstances. In the current system, we have chosen to follow case (a); the tightness of the blending surface depends on the multiplicity of Bezier control points. In fact, we have also experimented with manipulation of the inclination angle 9 of the rim ray which is analogous to case (b). In practice, however, it is likely that some shooting rays miss the model when 6 > 15°, making the blending invalid (Figure 4.18a). This defect may be amended through an iterative adjustment process (Fig-ure 4.18b). This is left as possible future work, and for now we revert to the original scheme (case (a)). 47 Chapter 4. The FRENCH SURFACE System: Implementation and Evaluation Figure 4.18: Varying the extent of a blend, (i) When the angle is large, it is likely that the rim ray misses the model, (ii) This problem can be solved by adaptively adjusting the rim ray. 4.4 Evaluation of the F R E N C H S U R F A C E System Some results are displayed in Figures 4.19-Figure 4.21. Figures 4.19a-d show the 3D version of Figure 4.13, illustrating the difference between blending on top and blending underneath, and the difference between keeping outside and keeping inside. Figure 4.20 shows an example of overlapped blending. It demonstrates that the blending algorithm is quite robust, because it behaves well even in a region of complex triangulation structure. Figures 4.21a-d show some artwork created using the F R E N C H SURFACE system, including some regular industrial objects and some irregular real life objects. They are constructed using 7-10 cycles of the selecting and blending procedure. The F R E N C H SURFACE system has been tested by approximately 10 users, mostly fellow grad-uate students. Also, it has been demonstrated during several events where we obtained some useful feedback. Most users understand how to use the modelling system after one demon-stration of the blending cycle. In terms of the efficiency of the system, it usually takes 5 min-utes up to 30 minutes to construct one model, depending on the desired level of detail and precision. Many users express that the concept of primitive surfaces and the set of French surfaces are very intuitive. We observe that the users like to casually look around the set of surfaces, and display the surfaces as a visual basis for selection, especially when they do not know exactly which surface they want. We believe that the organization of the French surface space is the 48 Chapter 4. The F R E N C H S U R F A C E System: Implementation and Evaluation Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation Figure 4.20: Multiple blending showing the robustness of the system. reason why navigation becomes second nature after a short time. The rim rays are also very popular; all users turn them on as a positioning guide. In addition, "Store" and "Recall" buttons are used frequently to draw repeated components. They are important time-savers. Furthermore, it is interesting to discover that some users like to display the surfaces using wireframe. Some comment that the wireframe provides positioning guide. Other expresses that they like the beauty of complexity. Some users ask for specific features, such as waves, wrinkling cloth, grassy plains, and moun-tain terrain. We think that these features should be included in some specialized or personal-ized libraries (similar to the libraries of clip arts), but not as a member of the set of common primitives. This idea can be pursued in future research. While using an early version of the system, some users asked for the functionalities for subtracting volume, adding colour, and drawing on the surface. We satisfy the first demand by supporting blending on the inside or the back of a model. The later two suggestions are left for future work as they would ordinarily be part of a full 3D modelling application. We are occasionally troubled by an uneven sample distribution and skinny triangles in the 50 Chapter 4. The FRENCH SURFACE System: Implementation and Evaluation Chapter 4. The F R E N C H SURFACE System: Implementation and Evaluation mesh. Also, our initial prototype for dynamic blending runs well only in the early stages of blending, but lagging begins to occur when more French surfaces are added. Both of these problems can be solved by mesh optimization; work is in progress to implement a mesh fairing scheme. We also want to point out that many users prefer static blending to dynamic blending even when lagging does not occur. They feel that they have more control with static blending. We are using static blending for the time being. In the future, we want to incorporate both options. Other typical options in normal 3D modelling packages, such as undo features and mesh manipulation, will be considered in future work. We observe that in the process of constructing a model, the most time is spent on positioning the French surface with respect to the model, rather than on searching for the right French surface. For example, careful adjustment is required to create symmetric features of an animal object. Positioning is outside the scope of this project, but alternative positioning and camera manipulation methods should be investigated in future research. Automatic positioning is our ultimate goal, since our guidelines entail there should be as little user input as possible. 52 Chapter 5 Conclusion 5.1 Contributions The contributions of this project are twofold: the proposal of the French surface concept (Sec-tion 5.1.1), and the blending algorithm (Section 5.1.2). 5.1.1 The French Surface Concept The most important contribution is the invention of the French surface concept and the corre-sponding method of arranging and navigating the set of French surfaces. It is an extension of the common French curve to 3D graphic design. It is also an evolutionary step from the simple surface menu in many existing systems to a more complete and well-organized library with transitional surfaces and non-restricted, continuous navigation. Also, the F R E N C H SURFACE system provides an approach that allows both fine and coarse precision surface modelling to be embedded in a user-friendly interface, in contrast to systems which tradeoff precision and user-friendliness. The difference between F R E N C H SURFACE and existing techniques that ma-nipulate control points is that manipulating or drawing tasks are now allocated to the system. Users only select from the set of surfaces tailored to their needs. In terms of the guidelines in C1-C3, the French surface concept has achieved the following: Simple Modelling Tasks (CI): This is exactly the motivation behind the French surface concept. A predrawn library of French surfaces avoids laborious manipulation, noisy freehand control, and the prerequisite of specialized knowledge. It is easier to assemble existing parts than to 53 Chapter 5. Conclusion generate drawings, given our rich and organized library. The toolset is small but powerful, yielding many surface features (concave, convex, closed, etc). The only input from the users comes from their artistic expression, but not their mathematical skills. Predictable Results (CI): The French surface paradigm provides a what-you-see-is-what-you-get setting. First, the blending method leaves the selected surfaces unchanged in the blended result. Also, ray guides give the user an idea of what to expect in the blending result. Further-more, editing and manipulation are avoided, so there is minimal guess work. Finally, users' needs are considered to make sure all results agree with their expectation. Minimal Math Structure (C3): In addition to making the mathematics hidden from the interface, our system avoids operation dependency on any rigid mathematical structure. We represent our surfaces using triangulated point sets. Its simplicity makes representation of arbitrary topology feasible; its flexibility escapes any restriction to a fixed mathematical layout. Users can interact directly with the object. 5.1.2 Blending of Triangle Meshes The second contribution is our blending algorithm. The triangulated point sets representing the French surface and the ongoing model induce a blending surface which extends from the base rim of the French surface. The blending function adaptively establishes correspondence from the French surface to the model, and constructs a smooth, power-adjustable blend (Chap-ter 4). Aggregated blending results converge to the desired model. The approach is novel in that various data structures and algorithms are combined to give an effective and robust blending implementation. 5.2 Limitations We have created both the French surface concept and the F R E N C H S U R F A C E prototype. Within the F R E N C H S U R F A C E prototype, there are several areas for refinement, such as improving the positioning mechanism and applying a mesh optimization scheme. The prototype is not 54 Chapter 5. Conclusion the main focus of the work, as we expect the French surface concept to be integrated into a modelling tool. Lessons learnt from the prototype provide improvements that could be useful when integrating the French surfaces library into a 3D modeller. These are discussed in the future work section (Section 5.3). In terms of the French surface concept however, we are aware of two limitations that French surfaces inherit from French curves. First, choosing from a library implies the French surface scheme cannot be as expressive as a freehand gestural-based system, but is more suitable for fine-controlled modelling. Second, objects are realized as a composition of primitives using both the French curve and the French surface concept. One could argue that this is an indirect approach to design because users have to build up complex objects from small pieces. However, it is direct in the sense that the user has a set of what-you-see-is-what-you-get prim-itives. Also, in many modelling contexts, designers build models incrementally In addition, we believe both the library and the primitives concept minimize cognitive load on the user. Finally, the allowance of expressive and intricate design is not significantly reduced. Future work should explore these tradeoffs. It is not possible to have a single system that is suitable for all design tasks. In some cases, the characteristics of French surfaces relieve laborious manual overhead and are advantageous. In other cases, where French surfaces may not be directly applicable, they can still be useful as a supplementary tool to enhance the ease of use. 5.3 What's next? We regard our F R E N C H S U R F A C E system as a proof-of-concept application, and the concept to be proved is the French surface metaphor. Future research can proceed in 2 directions: improvements on the F R E N C H S U R F A C E system (Section 5.3.1), and further development of the French surface concept (Section 5.3.2). 55 Chapter 5. Conclusion 5.3.1 Future Work on the FRENCH SURFACE System Positioning: We do not pretend our positioning method is the most efficient choice. Since this is outside the scope of our project, we simply employ trivial translation and trackball rotation with an ordinary mouse. We are looking into other positioning methods, in addition to camera manipulation mechanisms, and various input devices (e.g. a 6 degree-of-freedom spaceball, a 3D pen, and multi-sensor tablets). We are also considering automatic positioning using the iterative closest point (ICP) method [3]. In most cases, the user wants to place a chosen French surface so that its base is evenly close to the model. The ICP algorithm adjusts an initial configuration to achieve an optimal proximity relation. Blending Optimization: The current blending algorithm does not deal with the case when some rim rays from the French surface miss the model; blending is currently invalid under such situation. A possible strategy to solve this problem is the iterative adjustment of rays method proposed in Section 4.3.5. More work is required to further explore this. Also, as described in the same section, our initial prototype for dynamic blending does not provide satisfactory re-sults. We believe that dynamic blending is important in enhancing the what-you-see-is-what-you-get characteristic of the system, and more work is in progress to pursue this direction. Surface Representation and Mesh Optimization: Though we avoid short edges and skinny trian-gles in the primitives' mesh, our system does not yet accommodate dynamic mesh optimiza-tion. Occasionally, topological inconsistencies results from skinny triangles in the mesh. There are two elements to a fair triangle mesh: a sample distribution that reflects curvature, and a quality triangulation. We are studying a variety of efforts on mesh optimization, including adaptive sample refinement by [52], Dalaunay triangulation by [8], Schroeder's triangle deci-mation [40], and Hoppe's minimization of energy function [24]. Also, it would be worthwhile to try out subdivision surfaces as an alternative surface representation scheme. Subdivision surface representation does not depend on an initial decision of the resolution, and allows explicit control of blending parameters. Additional Functionalities: As discussed in Section 4.3.5, a different interpretation of blending 56 Chapter 5. Conclusion power is based on the extent rather than the tightness of a blend (Figure 4.17). It would be interesting to try this out. Also, as inspired by [52], we want to modify our system to allow an intersecting triangle mesh to support more topologies. Moreover, it would be useful to support formation where surfaces are placed side by side and without connection by blending. Finally, some users suggest commercial features such as multiple backtracking, colour and texture painting, drawing on the surfaces, and display of coordinates for more precise construction. 5.3.2 Future Research on the French Surface Concept Set of French Surfaces: We are considering the addition of hyperbolic surfaces, superquadrics, rope-like cylinders, planes, prisms, and cubes to the set of French surfaces. More research on common shapes that appear in art-form and real-life objects is required in that regard. One of the advantages of the French surface approach is that it does not impose any limits on the surface topologies that can be blended. Also, different artists may have different sets of commonly used surfaces. The support for personalized libraries will develop the French surface concept to its full potential. For instance, a floral artist can use a given library of petals. Or she can build up her own library as she creates more petals. These may be automatically arranged based on various curvature properties. It would also be interesting to investigate the use of artificial intelligence (AI) to learn commonly used surfaces for easy access. Visualization To Assist Navigation: The French curve allows one to easily scan the templates for available curves. We try to imitate this visualization advantage by arranging French surfaces through dimensionalization of the surface space, and by allowing neighbourhood inspection (Section 3.1.2). This may not be the most elegant solution; as with navigation of the colour space, analyzing the red, green, blue component may not be as intuitive as inspecting the colour wheel. In our case, one possibility remains as to display all close relatives of the French surface, but the difficulty is how to lay out the enormous 9D neighbourhood. A solution is to display only the linear set of neighbours associated with the parameter currently being adjusted. Another possibility is to utilize animation or transparent rendering to "steal" more dimensions for display. We have also tried to imitate the French curve and visualize some 57 Chapter 5. Conclusion surfaces as part of a big template, such as the spiral (Figure 3.4). These ideas require further investigation. Integration with Other Paradigms: Our system assumes the top-down scheme. It is useful to ex-tend it to support also the bottom-up approach and a combination of both. Also, the blending mechanism assumes part of the underlying model M is to be covered by the chosen French surface F. We propose future research on combining operations which take M into account, for example, super-imposition M + F, editing ^ ± ^ , and weighted combination Wl™+™%F • Fi-nally, it is interesting to apply the French surface concept as a supplementary feature to any existing system. For example, we can create an extensive library of solids for CSG, a library of skeletons for Blobby Model, or a library of rotund body parts for TEDDY. The libraries can be organized based on shape characteristics or curvature properties. 5.4 Conclusion This thesis introduces the French surface concept as an extension of French curves to the realm of surface design. A decision is made regarding the membership and organization of the set of French surfaces based on a list of design principles and the requirement to cover all the surface contours. The use of an extensive and organized library avoids the limitations of conventional systems, and provides a solution to a user-friendly modelling paradigm. We explore the potential of the French surfaces with our prototype, the F R E N C H S U R F A C E system. The French surfaces are represented using triangle meshes, which are combined in-crementally to form the model using the original blending algorithm. The system runs at interactive speed on a 700MHz Pentium 3 with a GeForce II graphics card. Users' experiences with the system demonstrate that the system is robust, intuitive, and easy to comprehend. We look forward to the future development of the French surface paradigm. 58 Bibliography [1] David Anderson, James L. Frankel, Joe Marks, Aseem Agarwala, Paul Beardsley, Jessica Hodgins, Darren Leigh, Kathy Ryall, Eddie Sullivan, and Jonathan S. Yedidia. Tangible interaction + graphical interpretation: A new approach to 3d modeling. Computer Graph-ics (SIGGRAPH 2000 Conference Proceedings), pages 393-402,2000. [2] Alan H . Barr. Global and local deformations of solid primitives. Computer Graphics (SIG-GRAPH '84 Conference Proceedings), 18(3):21-30,1984. [3] Paul J. Besl and Neil D. McKay. A method for registration of 3-d shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2):239-256,1992. [4] James F. Blinn. A generalization of algebraic surface drawing. ACM Transactions on Graph-ics, l(3):235-256,1982. [5] Jules Bloomenthal and Brian Wyvill. Interactive techniques for implicit modeling. Com-puter Graphics, 24(2):109-116,1990. [6] E. Catmull and J. Clark. Recursively generated b-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 10:350-355,1978. [7] George Celniker and Dave Gossard. Deformable curve and surface finite-elements for free-form shape design. Computer Graphics (SIGGRAPH '91 Conference Proceedings), 25(4):257-266,1991. [8] Paul Chew. Guaranteed quality mesh generation for curved surfaces. In Proceedings 1993 ACM Symposium on Computational Geometry, pages 274-280,1993. [9] Elizabeth S. Cobb. Design of sculptured surfaces using the b-spline representation. PhD thesis, University of Utah, June 1984. [10] Sabine Coquillart. Extended free-from deformation: A sculpturing tool for 3d geometric modeling. Computer Graphics (SIGGRAPH '90 Conference Proceedings), 24(4):187-196,1990. [11] Michael F. Deering. Holosketch: A virtual reality sketching/animation tool. ACM Trans-actions on Computer-Human Interaction, 2(3):220-238,1995. [12] Tony DeRose, Michael Kass, and Tien Truong. Subdivision surfaces in character anima-tion. Computer Graphics (SIGGRAPH '98 Conference Proceedings), pages 85-94,1998. [13] Manfredo P. do Carmo. Differential Geometry of Curves and Surfaces. Prentice-Hall, Engle-wood Cliffs, New Jersey, 1976. [14] D. Doo. A subdivision algorithm for smoothing down irregularly shaped polyhedrons. In Proceedings International Conference of Interactive Techniques in Computer Aided Design, pages 157-165,1978. [15] Gerald Farin. Curves and Surfaces for Computer Aided Geometric Design: a Practical Guide. Academic Press, Inc., San Diego, C A , third edition, 1993. 59 Bibliography [16] Daniel J. Filip. Blending parametric surface. ACM Transactions on Graphics, 8(3):164-173, 1989. r [17] D. R. Forsey and R. H . Bartels. Hierarchical b-spline refinement. Computer Graphics (SIG-GRAPH '88 Conference Proceedings), pages 205-212,1988. [18] Barry Fowler. Geometric manipulation of tensor product surfaces. In Proceedings 1992 Symposium on Interactive 3D Graphics, pages 101-108,1992. [19] Tinsley A. Galyean and John F. Hughes. Sculpting: A n interactive volumetric modeling technique. Computer Graphics (SIGGRAPH '91 Conference Proceedings), 25(4):267-274,1991. [20] Gunther Greiner and Hans-Peter Seidel. Curvature continuous blend surfaces. In Model-ing in Computer Graphics, pages 309-318. Springer-Verlag, Berlin, 1993. [21] Song Han and Gerard Medioni. I3dsketch: Modeling by digitizing with a smart 3d pen. In ACM Multimedia 1997, pages 41-49. Addison Wesley, 1997. [22] C. Hoffmann and J. Hopcroft. Quadratic blending surface. Computer-Aided Design, 18:301-306,1986. [23] Hugues Hoppe, Tony DeRose, Tom Duchamp, Mark Halstead, Hubert Jin, John McDon-ald, Jean Schweitzer, and Werner Stuetzle. Piecewise smooth surface reconstruction. Com-puter Graphics (SIGGRAPH '94 Conference Proceedings), pages 295-302,1994. [24] Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. Mesh optimization. Computer Graphics (SIGGRAPH '93 Conference Proceedings), 27:19-26, 1993. [25] William M . Hsu. Direct manipulation of free-form deformations. Computer Graphics (SIG-GRAPH '92 Conference Proceedings), 26(2):177-184,1992. [26] Takeo Igarashi, Satoshi Matsuoka, and Hidehiko Tanaka. Teddy: A sketching interface for 3d freeform design. Computer Graphics (SIGGRAPH '99 Conference Proceedings), pages 409-416,1999. [27] Michael Kallay. Constrained optimization in surface design. In Modeling in Computer Graphics, pages 85-94. Springer-Verlag, Berlin, 1993. [28] Leif Kobbelt, Swen Campagna, Jenz Vorsatz, and Hans-Peter Seidel. Interactive multi-resolution modeling on arbitrary meshes. Computer Graphics (SIGGRAPH '98 Conference Proceedings), pages 105-114,1998. [29] Gordon Kurtenbach, George Fitzmaurice, Thomas Baudel, and Bill Buxton. The design of a graphical user interface paradigm based on tablets, two-hands, and transparency. In ACM CHI 1997 Conference Proceedings, pages 35-42,1997. [30] David H . Laidlaw, W. Benjamin Trumbore, and John F. Hughes. Constructive solid ge-ometry for polyhedral objects. Computer Graphics (SIGGRAPH '86 Conference Proceedings), 20(4):161-168,1986. 60 Bibliography [31] Aaron Marcus. Principles of effective visual communication for graphical user interface design. In Readings in Human-Computer Interaction: Toward the Year 2000, pages 425-441. Morgan Kaufmann Publishers, 1995. [32] Lee Markosian, Jonathan M . Cohen, Thomas Crulli, and John Hughes. Skin: A construc-tive approach to modeling free-form shapes. Computer Graphics (SIGGRAPH '99 Confer-ence Proceedings), pages 393-400,1999. [33] D. J. McConalogue. Algorithm 66 - an automatic french-curve procedure for use with an incremental plotter. Computer Journal, 14:207-209,1971. [34] Henry P. Moreton and Carlo H . Sequin. Functional optimization for fair surface design. Computer Graphics (SIGGRAPH '92 Conference Proceedings), 26(2):167-176,1992. [35] Michael E. Mortenson. Geometric Modelling. John Wiley and Sons, Inc., second edition, 1997. [36] Kent L. Norman. The Psychology of Menu Selection: Designing Cognitive Control at the Hu-man/Computer Interface. Ablex Publishing Corporation, Norwood, New Jersey, 1991. [37] R. Parent. A system for sculpting 3d data. Computer Graphics (SIGGRAPH '77 Conference Proceedings), 11(2):138-147,1977. [38] Nate Robins. Smooth normal generation with preservation of edges. In http://www.xmission.com/ nate/smooth.html#figl. [39] Steven Schkolne, Michael Pruett, and Peter Schroder. Surface drawing: Creating organic 3d shapes with the hand and tangible tools. In ACM CHI 2001 Conference Proceedings, pages 261-268, 2001. [40] William J. Schroeder, Jonathan A. Zarge, and William E. Lorenson. Decimation of triangle meshes. Computer Graphics (SIGGRAPH '92 Conference Proceedings), 26(2):65-70,1992. [41] T. Sederberg. Piecewise algebraic surface patches. Computer Aided Geometric Design, 2:53-59,1985. [42] Thomas W. Sederberg and Scott R. Parry. Free-from deformation of solid geometric mod-els. Computer Graphics (SIGGRAPH '86 Conference Proceedings), 20(4):151-160,1986. [43] Ben Shneiderman. Direct manipulation: a step beyond programming languages. In Sparks of Innovation in Human-Computer Interaction, pages 17-37. Ablex Publishing Corporation, 1993. [44] Karan Singh. Interactive curve design using digital french curves. In Proceedings 1999 Symposium on Interactive 3D Graphics, pages 23-30,1999. [45] Karan Singh and Eugene Fiume. Wires: A geometric deformatino technique. SIGGRAPH 1998 Conference Proceedings, pages 405^414,1998. [46] Jos Stam. Exact evaluation of catmull-clark subdivision surfaces at arbitrary parameter values. Computer Graphics (SIGGRAPH '98 Conference Proceedings), pages 395-404,1998. 61 Bibliography [47] G. Turk and M . Levoy. Zippered polygon meshes from range images. Computer Graphics (SIGGRAPH '94 Conference Proceedings), pages 311-318,1994. [48] C.W.A.M. van Overveld. Painting gradients: free-from surface design using shading pat-terns. In Proceedings Graphics Interface '96, pages 151-158,1996. [49] Sidney W. Wang and Arie E. Kaufman. Volume sculpting. In Proceedings 1995 Symposium on Interactive 3D Graphics, pages 151-214,1995. [50] Joe Warren. Blending algebraic surface. ACM Transactions on Graphics, 8(4):263-278,1989. [51] William Welch and Andrew Witkin. Variational surface modeling. Computer Graphics (SIGGRAPH '92 Conference Proceedings), 26(2):157-166,1992. [52] William Welch and Andrew Witkin. Free-form shape design using triangulated surfaces. Computer Graphics (SIGGRAPH '94 Conference Proceedings), 28(3):247-256,1994. [53] Brian Wyvill, Eric Galin, and Andrew Guy. Extending the constructive solid geometry tree, warping, blending and boolean operations in an implicit surface modeling system. Computer Graphics Forum, 18(2):149-158,1999. [54] Robert C. Zeleznik, Kenneth P. Herndon, and John F. Hughes. Sketch: A n interface for sketching 3d scenes. Computer Graphics (SIGGRAPH '96 Conference Proceedings), 30(4):163-170,1996. 62
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- French surface : a new technique for surface design
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
French surface : a new technique for surface design Cheng, Zita Sze Ting 2001
pdf
Page Metadata
Item Metadata
Title | French surface : a new technique for surface design |
Creator |
Cheng, Zita Sze Ting |
Date Issued | 2001 |
Description | We present a new user-friendly paradigm for surface design. The goal is to overcome limitations associated with traditional methods: their dependence on freehand controlling and their rigid mathematical structures. Our solution is inspired by the drafter's tool known as French curves, which are used as templates for tracing curves. This project considers its analogue in one higher dimension, namely 3D surfaces. A carefully defined and intuitively arranged set of French surfaces is given to the user to choose from. The selected surfaces are then connected together to form the final model. The potential of this approach is explored with our prototyping system, FRENCH SURFACE, where models are constructed via aggregated blendings of chosen French surfaces. Triangulated point-sets are used to engage a structure-free representation, and data structuring algorithms are integrated to ensure an efficient blending. The current system supports the creation of objects topologically homeomorphic to a sphere or a plane. Users' experiences demonstrate that the FRENCH SURFACE system is intuitive, robust, and easy to comprehend. |
Extent | 3272367 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-08-04 |
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.0080043 |
URI | http://hdl.handle.net/2429/11669 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2001-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2001-0354.pdf [ 3.12MB ]
- Metadata
- JSON: 831-1.0080043.json
- JSON-LD: 831-1.0080043-ld.json
- RDF/XML (Pretty): 831-1.0080043-rdf.xml
- RDF/JSON: 831-1.0080043-rdf.json
- Turtle: 831-1.0080043-turtle.txt
- N-Triples: 831-1.0080043-rdf-ntriples.txt
- Original Record: 831-1.0080043-source.json
- Full Text
- 831-1.0080043-fulltext.txt
- Citation
- 831-1.0080043.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-0080043/manifest