@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix dc: . @prefix skos: . vivo:departmentOrSchool "Science, Faculty of"@en, "Computer Science, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Chang, Xianglong"@en ; dcterms:issued "2008-05-01T20:11:59Z"@en, "2008"@en ; vivo:relatedDegree "Master of Science - MSc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description "We present a novel method for building 3D models from a user sketch. Given a 2D sketch as input, the approach aligns and deforms a chosen 3D template model to match the sketch. This is guided by a set of user-specified correspondences and an algorithm that deforms the 3D model to match the sketched profile. Our primary contribution is related to fitting the 3D deformable geometry to the 2D user sketch. We demonstrate our technique on several examples."@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/797?expand=metadata"@en ; dcterms:extent "5915960 bytes"@en ; dc:format "application/pdf"@en ; skos:note "Semi-Automatic fitting of deformable 3D models to 2D sketches by Xianglong Chang B.Eng., Huazhong University of Science and Technology, 1994 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Computer Science) The University of British Columbia (Vancouver) April 2008 c© Xianglong Chang, 2008 Abstract We present a novel method for building 3D models from a user sketch. Given a 2D sketch as input, the approach aligns and deforms a chosen 3D template model to match the sketch. This is guided by a set of user-specified correspondences and an algorithm that deforms the 3D model to match the sketched profile. Our primary contribution is related to fitting the 3D deformable geometry to the 2D user sketch. We demonstrate our technique on several examples. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 User Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Alignment and Deformation . . . . . . . . . . . . . . . . . . . 4 1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Sketch-based Modeling and Reconstruction . . . . . . . . . . . . . . 6 2.1.1 Freeform-based Modeling . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Template-based Modeling . . . . . . . . . . . . . . . . . . . . 7 2.2 Registration and Alignment . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Shape Deformations . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 iii 2.3.1 Deformations Based on Gradients . . . . . . . . . . . . . . . 9 2.3.2 Deformations Based on Differential Coordinates . . . . . . . . 10 3 3D to 2D Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1 2D Sketch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1.1 Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Correspondence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3.1 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3.2 Rotation and Translation . . . . . . . . . . . . . . . . . . . . 17 3.4 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4.1 Penalty Method . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4.2 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4 Mesh Deformations . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.1 Method Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.1.1 Optimization Scheme . . . . . . . . . . . . . . . . . . . . . . 25 4.1.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Deformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3 Numerical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.1 Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.2 Deformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . 40 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 iv List of Figures 1.1 The example of input and output of the system . . . . . . . . . . . . 2 1.2 System workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 System user interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Sketch-based modeling of parameterized objects [33] . . . . . . . . . 8 2.2 Material-aware mesh deformations [22] . . . . . . . . . . . . . . . . . 10 2.3 Pyramid coordinates for morphing and deformation [25] . . . . . . . 11 3.1 Smoothing of the sketch . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Assuming that p1 and p2 are two adjacent sketch points, p0 is the point that user clicked on the screen, then the system will locate point p on the stroke and return it as a corresponding 2D point. . . 15 4.1 Expansion of linear system . . . . . . . . . . . . . . . . . . . . . . . 31 5.1 Cat head example - The model has 3,748 triangles and 1,893 vertices, and is aligned n 0.5 second with 4 correspondences on forehead, face, nose and nose tip. The alignment . . . . . . . . . . . . . . . . . . . 34 5.2 Cat example - The model has 14,410 triangles and 7,207 vertices, and is aligned 0.7 second with 5 correspondences. 2 on head, 1 on neck, 1 on back and 1 on rear . . . . . . . . . . . . . . . . . . . . . . . . . 35 v 5.3 Horse head example - The model has 5,123 triangles and 2,589 ver- tices, and is aligned 0.5 second with 4 correspondence on forehead, face, nose and nose tip . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.4 Simple deformation test with a bar - 4 correspondences for alignment at the horizontal part of the bar, see right part of the bar in (a). For deformation, based on existing 4 correspondences from alignment, we add one more on the left end of the bar (please refer to (a)), so use 5 correspondences to deform the model. We pick α = 0.2 and β = 1.0. Please note that we highlight the anchor facets with red color. . . . 37 5.5 Cat head deformation test with 4 correspondences after alignment. α = 0.2 and β = 1.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.6 Cat head alignment and deformation example . . . . . . . . . . . . . 39 vi Acknowledgements First of all, I’d like to acknowledge the invaluable supervision from my supervisors Dr. Alla Sheffer and Dr. Michiel van de Panne. Without you, this would have never been possible. I also would like to thank Sahar Sajadieh for her work on this project during her summer study with Dr. Alla Sheffer. Thanks also to the people from imager lab and my friends in Computer Science Department for the fun, inspiring work and study environment. Most important, my special thanks to my parents and my wife for encour- aging me to complete the study and the greatest support at all time. Xianglong Chang The University of British Columbia April 2008 vii All my work is dedicated to my family. viii Chapter 1 Introduction 1.1 Motivation Geometry processing techniques are widely used in computer-aided design, computer animation, and related areas. One of the central geometry processing tasks is to create models. Users demand tools to be intuitive, robust, and most importantly, to help in conveying their ideas. Sketching with pen and paper is a traditional way of communicating ideas and shapes. A sketch can convey a shape in a few strokes and thus can be an efficient tool in prototyping and preliminary design. The desire for efficiency and convenience has driven researchers to study sketching as a form of interaction graphical software and develop tools capable of interpreting sketches. Today, a small but increasing number of applications in design, modeling and animation support some form of sketching. Sketch-based applications in geometry processing area have been around since late 1990’s. Creating simple freeform shapes from scratch has been demon- strated in limited form by [11] and [13]. The systems are not able to create complex shapes, because these include a multitude of geometric features, many of which are difficult to infer from a sketch. An alternative is to modify existing templates using sketched feature lines, such as suggestive contours [7]. However, this is by no means trivial. Nealen et al. [20] developed a sketch-based interface to tackle this problem. 1 The resulting shapes can be realistic and complex, but the approach requires the user to be experienced in manipulating the models. If we could work with existing models while using a sketch as input as in [11] and [13], then the system would be accessible to a wide range of users. Creating a model from a photograph may also become possible. 1.2 System Overview This thesis presents a method to create new geometric models by fitting 3D de- formable templates to 2D sketches. In our system, a user creates a sketch by draw- ing contour strokes either on a blank canvas or on top of a background image of the object to be modeled. The user also needs to specify a small number of correspon- dences between the 3D template model and the user drawing. Each correspondence pairs a 2D sketch point with a 3D vertex on the template model. The system uses these correspondences and the associated 2D and 3D normal to align and deform the 3D template so that the resulting model matches the 2D sketch. An example of input and output of the system is shown in Figure 1.1. The corresponding workflow is shown in Figure 1.2. (a) User sketch (b) Template (c) Align and de- form (d) Final result Figure 1.1: The example of input and output of the system 2 2D sketch curves  Preprocessing: - Smooth sketch curves - Establish correspondences  Alignment: Using at least 4 correspondences, solve for the rotations and scaling needed to best align the user-specified correspon- dences.  Deformation: Iteratively establish additional corre- spondences between the sketch and 3D model and then deform the model based on all correspondences  New 3D Model as output Figure 1.2: System workflow 1.2.1 User Interfaces The system has two separate user interfaces: a 2D sketch interface, and a 3D tem- plate editing interface, as shown in Figure 1.3. The sketch consists of strokes, which can be either open or closed. We do require that a unique normal can be inferred 3 for each point on a stroke, this is obtained from knowing the direction of the stroke as it is drawn, as described in more detail in Chapter 3. The user draws with the mouse by holding the left button pressed while dragging the cursor in the sketch area. The user uses both 2D and 3D interfaces in order to specify correspondences between the sketch and the 3D template, one pair a time. Lastly, the 3D interface is used to display the result of the alignment and deformation. (a) 2D user sketch interface (b) 3D editing interface Figure 1.3: System user interfaces 1.2.2 Alignment and Deformation The alignment process transforms the template in order to align the user-specified correspondences as closely as possible. During this step, the shape of the template is preserved and the template only undergoes a similarity transformation. The alignment consists of two steps. First, the system scales the model to the same size as the sketch. Second, it rigidly transforms and translates the model to best achieve the specified correspondences. The output of the alignment is then used as the input to the deformation process. Once the template is approximately aligned with the sketch, we further de- form it so that the deformed model better fits the sketch. Correspondences are first established between the template and the sketch. Then we use both the normal 4 vectors and spatial positions of the corresponding points to determine the appropri- ate deformations that deform the 3D model towards matching the 2D sketch. Our deformation method is based on Popa et al. [22] where they compute the transfor- mation for each triangle of the mesh by propagating and blending transformations from anchor triangles, and use vertex positions before and after the deformation to represent the transformation gradients. The optimal vertex positions can then be obtained by minimizing the difference between the transformation gradients and the previously computed transformations. The original method uses only normal constraints. In our application, we also consider positional constraints in order to obtain a better match. Therefore, we modify the optimization scheme of the origi- nal method by introducing an extra term in the optimization metric to account for the positional constraints. We further introduce additional constants that balance the relative contributions of the desire to maintain the original template shape and positional constraints. The modified method is described in Chapter 4. 1.3 Organization The rest of this thesis is organized as follows. Relevant literature is discussed in Chapter 2. The 3D to 2D alignment is described in Chapter 3. Mesh deformations is discussed in Chapter 4, and Chapter 5 demonstrates and explains the results. Lastly Chapter 6 discusses possible improvements and as well as future research. 5 Chapter 2 Related Work Our proposed modeling method involves aspects of sketch-based modeling and re- construction, registration, alignment, and shape deformation. In this chapter we review previous work in these areas. 2.1 Sketch-based Modeling and Reconstruction Sketch-based modeling potentially provides users with a convenient way to interac- tively create new objects on a computer either from scratch or by deforming existing templates. It combines a user interface with mesh editing methods. 2.1.1 Freeform-based Modeling Igarashi et al. [11] designed a sketch-based interface called Teddy to generate 3D freeform models. The user draws several 2D freeform strokes representing a desired geometry, and the system automatically generates a plausible 3D model by inflating [30] the region surrounded by the user sketch. The creation process requires silhou- ettes to be simple and closed curves and the geometries it creates are topologically equivalent to a sphere. Karpenko and Hughes [13] present a method which can be incorporated into a sketch-based freeform modeling interface, such as Teddy [11], to extend the ability 6 of creating more complex freeform geometries. The algorithm is based on the work of [24] and [31] to infer a plausible shape from its visible contours. The sketch is no longer required to be a simple closed curve, but can have cusps and T-junctions. To create a desired 3D geometry, they use a mass-spring system to connect the topo- logical embedding and smoothen the raw solid shape to obtain the final geometry. 2.1.2 Template-based Modeling Nealen et al. [20] present a view-dependent sketch-based interface for mesh editing. They adopted the Laplacian framework to deform the shape of the template to get a desired model. They suggest that building a model from sketch can be seen as an inverse Non-Photorealistic-Rendering problem, and therefore their interface uses silhouettes and suggestive contours as input for the editing mode. Users sketch a curve within a user specified region of influence on the model and the system adapts the template so that the curve becomes a feature line on the model. Kho and Garland [14] present a system that allows users to interactively modify a template via direct sketching on the model. They treat the user sketch as a reference skeleton of the region of the interest(ROI). Users first draw a reference curve to define a skeleton of the ROI, then draw another target reference curve as the skeleton of the desired shape. The deformation of the template is determined by the deformation of the reference curves. Yang et al. [33] developed a sketch-based system for modeling of param- eterized objects. Their system creates 3D geometries of particular object classes from 2D user sketches. It interprets the strokes as a sketch graph and uses the 2D template to label the parts of the sketch. Once a best-fit template is found, the system constructs a new model by extracting measurements from the resulting la- beled sketch. These measurements are fed to a pre-existing parameterized 3D model generator for each object class. They demonstrate results using planes, cups, and fish (Figure 2.1). The method can be extended to work with other parameterizable 7 3D objects. Figure 2.1: Sketch-based modeling of parameterized objects [33] 2.2 Registration and Alignment Registration and alignment are required in our work to find the relationship between the template model and the sketch. Many applications of surface matching or shape recognition also have similar requirements. Normally, registrations can be used to align scanned point-based surfaces to 3D models [17], align 2D textures to a 3D model [16], align 3D models with respect to one another, etc. Besl and McKay [5] present an iterative closest point (ICP) algorithm for registration of 3D shapes. The method is independent of the representations of the geometric data and iteratively solves the registration problem of 3D shapes. During each iteration, it finds the closest point on a geometric model to a given point; then a rigid transformation is computed by minimizing the distances between the transformed points of the given points and their corresponding points on the model. The iteration is repeated using the updated points from previous iteration steps and stops once the error metric falls below a threshold. The convergence of the 8 algorithm depends on a good initial estimate of the registration. Li et al. [17] present a feature-based algorithm for approximate scan-to-model alignment. Their method estimates the transformation that matches two surfaces from a single pair of corresponding points with their surface positions, normals and principle curvature directions. However, they need to do an exhaustive search over all possible correspondences from scan data and the model data to find an optimal pair of corresponding points. The result can then be used as the input to an ICP algorithm to refine the registration between the surface and the model. 2.3 Shape Deformations 2.3.1 Deformations Based on Gradients Mesh editing and deformation are key topics in geometric modeling. Yu et al. [34] use a Poisson equation to edit meshes through gradient field manipulation. The method relies on both the guidance vector field, i.e. gradient fields, and boundary conditions. They used geodesic distance between every free vertex and constrained vertices to evaluate the guidance vector field. Manipulations to the guidance field yield local transformations defined on a per triangle basis, the system then propa- gates the local transformations to create a smooth transition. Sumner et al. [29] propose a deformation gradient based method for transfer- ring large deformations from source to target models. They use the correspondences between the source and target triangles to define how the deformation of the source mesh should be transferred to the target. Once the correspondences are found, the system evaluates the transformations induced by the deformation of the source model and then maps the transformations through the correspondences from the source to the target. Finally, the system solves an optimization problem to enforce the continuous shape requirements of the target mesh. Popa et al. [22] also use deformation gradients in their method. They add material properties to the model 9 to allow for non-uniform transformations as shown in Figure 2.2. Figure 2.2: Material-aware mesh deformations [22] The reconstruction of meshes with desired gradients is an overdetermined problem, and is thus solved in a weighted least-squares sense. These methods work well for rotations but not for translations, as the gradient field is not sensitive to translation. Deformations containing both rotation and translations therefore remain problematic. 2.3.2 Deformations Based on Differential Coordinates Another class of methods modifies the differential coordinates of the surface vertices. Alexa [1] demonstrates that using Laplacian coordinates as a mesh representation in morphing is better than using traditional Cartesian coordinates, and proposes to use varying weights during linear interpolation to obtain more natural, gradual blending. The Laplacian coordinate of a vertex vi is represented by the difference between vi and the average of its neighbors: δi = vi − 1 ni ∑ j∈Nbr(vi) vj (2.1) where Nbr(vi) is the set of the immediate neighboring vertices of the vertex vi and ni = |Nbr(vi)| or the valence of vertex vi. There are a number of methods that use variations of the Laplacians coordi- nates for mesh deformation [18, 19, 28, 27]. Sorkine [27] provides a review of current 10 research in geometric processing that is related to Laplacian processing framework and differential representations. Lipman et al. [18] use Laplacian Coordinates to preserve the high frequency of mesh surfaces where they solve the rotation invariant problem by first estimating rotations of a local frame and then rotating original Lalacians with these estimated rotations. Sorkine et al. [28] develop a method to implicitly solve for rotations of Laplacians by finding optimal transformations for each vertex. They linearize the local frame transformations to make computations more efficient, but at the cost of unavoidable artifacts for large rotations. Sheffer and Kraevoy [25] present a method that uses pyramid coordinates for 3D mesh morphing and deformation. Pyramid coordinates are a local shape representation based on a set of angles and the edge lengths relating a vertex to its adjacent neighbors. They are invariant under rigid transformations. For mesh de- formation, their method uses a number of user-specified control vertices to evaluate deformations consisting of scaling, bending and rotation. The method is robust and capable of generating natural looking deformations and morphing sequences (see Figure 2.3). For reconstruction, they project the vertex v and its neighboring ver- tices vi onto v’s projection plane. Given v′, the projection of v, and the information of the offsets of all vi’s, the new position of the vertex v can be reconstructed. Figure 2.3: Pyramid coordinates for morphing and deformation [25] The above methods do not take the volume change into consideration when deforming a mesh surface. Zhou et al. [35] present a method to process large de- formations using the volumetric graph Laplacian to avoid unnatural volume change and local self-intersection by building two lattices wrapping around the mesh from 11 both inside and outside. The internal graph fills the interior volume to prevent large volume change, and the external graph prevents local self-intersection. This hier- archy can better preserve both the local details and volumes, but also significantly increases the complexity of the operations. 12 Chapter 3 3D to 2D Alignment 3.1 2D Sketch In our system, we use the 2D sketch to infer an intended 3D shape. To serve our purpose, the points on any sketched curve are required to have unique 2D normals. We infer the normal direction from the direction of the stroke using the counter- clockwise convection. The resulting normal vector of each sample point will be assumed to point outwards with respect to the contour direction. 3.1.1 Smoothing The hand drawn sketch is prone to noise. Smoothness is important to our system because the normal vectors of sketch points are used as the input for mesh defor- mation. As a result, we apply the following Laplacian smoothing formula to all the sketch points p′i = λ  1 n n∑ j=1 qj + (1− λ) pi (3.1) where p′i is the smoothed position of pi, λ is the coefficient to balance the contribu- tions between pi and its neighbors, n is the number of points in the neighborhood of pi denoted as Nbr(pi), and qj ∈ Nbr(pi). 13 (a) Before smoothing (b) Before smoothing with points highlighted (c) After smoothing (d) After smoothing with points highlighted Figure 3.1: Smoothing of the sketch 3.2 Correspondence Correspondences between the sketch and the model are supplied by the user. The user selects a point from the sketch and a corresponding vertex from the model establishing a corresponding pair. When selecting the 3D corresponding vertex, we also determine one of its surrounding facets as the anchor facet. We use the same definition of the anchor facet as in [22]. The anchor facets are needed to determine 14 the deformation gradients for mesh deformations, as will be explained in detail in Chapter 4. The user repeats the selection process, one pair a time, until there are enough correspondences for our operations. We require a minimum set of four correspondences for alignment. Additional correspondences can serve to help with mesh deformations. In our implementation, we use Graphite’s [8] built-in function to select the vertices of the 3D model as the 3D points for correspondences. For the 2D sketch, we use the mouse to select a point on the 2D strokes and the system then locates the point closest to the selected location as illustrated in Figure 3.2. Figure 3.2: Assuming that p1 and p2 are two adjacent sketch points, p0 is the point that user clicked on the screen, then the system will locate point p on the stroke and return it as a corresponding 2D point. Once the correspondences are established, the spatial coordinates of the sketch points are then used as position constraints for both alignment and mesh deformation. 3.3 Alignment We wish to find a similarity transformation that aligns the template and the sketch. For a generic rigid transformation matrix M as shown in a homogeneous form in equation 3.2, there are 12 unknowns of which 9 unknowns, rij , i, j ∈ [0, 2], are for the rotation or reflection, and 3 unknowns, tx, ty, tz, are for the translation. In our 15 system we have to deal with uniform scaling, rotations and translations. M =  r00 r01 r02 tx r10 r11 r12 ty r20 r21 r22 tz 0 0 0 1  (3.2) However, we are not able to unambiguously determine the 3D transformation matrix required for alignment in one step. Therefore, we developed a procedure to do alignment in three steps. Given a set of 2D correspondences supplied by the user as described in Section 3.2, we model the transformation matrixM by separating the overall transformation into three groups of transformations. Each of the three successive transformations contains scaling, rotation and translation. However, the rotation is fixed to rotate around a specific axis of the Cartesian coordinate system, i.e. the rotation axis is either X, Y , or Z. It can be defined mathematically as: v′i =M(vi) =Mx(My(Mz(vi))) (3.3) where vi is the ith vertex of the original 3D template, v′i is the ith vertex of the aligned model, and for each set of transformations: Mk(v) = Rk(skv) + Tk (3.4) Mk is a group of transformations and k = x, y, or z. Rk is a rotation matrix, sk is a scale factor, and Tk is a translation vector. The alignment problem can then be factored into the subproblems of scaling, rotation and translation. 3.3.1 Scaling Given a set of correspondences, we can estimate a scale factor s by solving the following optimization problem (3.5) min s ∑ ∀(i,j) ( s ‖pi − pj‖22 − ∥∥∥p′i − p′j∥∥∥2 2 )2 (3.5) 16 where pi, pj are 3D vertices, and p′i, p′j are corresponding 2D sketch points. 3.3.2 Rotation and Translation As shown in equation (3.3), we need to find up to three sets of transformations with respect to the rotation axis, and we solve the following optimization metric for a specific rotation matrix R and translation vector T . min n∑ i ‖M(vi)− pi‖22 (3.6) where n is the number of the correspondences and we require n ≥ 4, vi is a vertex of the 3D model and pi is the corresponding 2D sketch point. Our problem is under-constrained in that pi is only a 2D point with which we are not able to fully constrain the position of a 3D vertex during the transformation. Therefore, we make an assumption that a 2D sketch is drawn on a 3D plane. In our implementation, we use the XZ plane, and set the Y-component of the translation vector to zero which means we accept whatever value of y-coordinate of the transformed vertex vi after a transformation. We will then be able to proceed solving the optimization problem (3.6) for a rotation matrix and a translation vector. As shown in equation (3.4), we have to solve for three degrees of freedom for alignment. Transformations with Rotation around X-Axis A 3D model rotation about the X-Axis can be expressed using the rotation matrix : R =  1 0 0 0 C −S 0 S C  17 where C = cos θ, S = sin θ, and θ is the rotation angle. Therefore, the optimization problem (3.6) can be written explicitly as: min C,S,tx,tz n∑ i ∥∥∥∥∥∥∥∥∥∥∥∥∥  1 0 0 tx 0 C −S 0 0 S C tz 0 0 0 1   sx xi sx yi sx zi 1  −  x′i 0 z′i 1  ∥∥∥∥∥∥∥∥∥∥∥∥∥ 2 2 (3.7) where sx is the scale factor computed as described in Section 3.3.1, t = [tx, 0, tz]T , xi, yi, zi are the coordinates of a vertex vi of the 3D model and x′i, z′i are the coordi- nates of the corresponding point pi on the 2D sketch. After algebraic simplifications of (3.7), we obtain min C,S,tx,tz n∑ i [( Sysi + Cz s i + tz − z′i )2 + (xsi + tx − x′i)2] (3.8) Subject to : C2 + S2 = 1 where xsi = sxxi, y s i = sxyi, z s i = sxzi. As each of the two terms in (3.8) must be positive, and involves an independent set of variables, the entire expression is minimized when both of them are minimized. Hence, we can first solve the second term for tx min tx n∑ i ( xsi + tx − x′i )2 (3.9) Taking derivative w.r.t tx, and setting it equal to 0, we obtain the following solution tx = 1 n n∑ i ( x′i − xsi ) (3.10) Now we still need to solve the first term for C, S, tz, namely: min C,S,tz n∑ i ( Sysi + Cz s i + tz − z′i )2 (3.11) Subject to : C2 + S2 = 1 This can be treated as a minimization problem with an equality constraint, and we shall use a penalty method to solve it as will be explained in more detail in section 18 3.4. The optimization steps for the two remaining transformations are determined in an analogous fashion. Transformations with Rotation around Y-Axis The rotation matrix R is as follows: R =  C 0 S 0 1 0 −S 0 C  Equation (3.6) therefore becomes min C,S,tx,ty ,tz n∑ i ∥∥∥∥∥∥∥∥∥∥∥∥∥  C 0 S tx 0 1 0 0 −S 0 C tz 0 0 0 1   sy xi sy yi sy zi 1  −  x′i 0 z′i 1  ∥∥∥∥∥∥∥∥∥∥∥∥∥ 2 2 (3.12) With a similar derivation, we can obtain an equivalent form of the scheme (3.12): min C,S,tx,tz n∑ i [( Cxsi + Sz s i + tx − x′i )2 + (−Sxsi + Czsi + tz − z′i)2] (3.13) Subject to : C2 + S2 = 1 where sy is the scale factor and xsi = syxi, y s i = syyi, z s i = syzi. Transformations with Rotation around Z-Axis The rotation matrix R becomes: R =  C −S 0 S C 0 0 0 1  19 Equation (3.6) is then: min C,S,tx,tz n∑ i ∥∥∥∥∥∥∥∥∥∥∥∥∥  C −S 0 tx S C 0 0 0 0 1 tz 0 0 0 1   sz xi sz yi sz zi 1  −  x′i 0 z′i 1  ∥∥∥∥∥∥∥∥∥∥∥∥∥ 2 2 (3.14) which is equivalent to min C,S,tx,tz n∑ i [( Cxsi − Sysi + tx − x′i )2 + (zsi + tz − z′i)2] (3.15) Subject to : C2 + S2 = 1 We can solve for tz = 1 n n∑ i ( z′i − zsi ) (3.16) and then minimize the following optimization scheme for C, S, and tx. min C,S,tx n∑ i ( Cxsi − Sysi + tx − x′i )2 (3.17) Subject to : C2 + S2 = 1 where sz is the scale factor and xsi = szxi, y s i = szyi, z s i = szzi. 3.4 Optimization In this section, we briefly discuss using penalty method [21] to solve our optimization schemes (3.11), (3.13), and (3.17). 3.4.1 Penalty Method In general, the penalty method can be considered when solving an optimization problem with equality constraints: min f (x) (3.18) s.t. ci (x) = 0, i = 1, 2, . . . ,m 20 The optimization problem is cast as an unconstrained problem by creating a new objective function φ (x;µ) min φ (x;µ) = f (x) + 1 2µ m∑ i=1 c2i (x) (3.19) Similarly, the first order condition requires: ∇φ (x;µ) = ∇f (x) + m∑ i=1 ci (x) µ ∇ci (x) = 0 (3.20) For a sequence of values of µ. We can use the solution x∗ of the (k − 1)’s unconstrained problem (3.19) with µ = µk. This is a continuation technique. The penalty method algorithm is shown in Algorithm (1) and we choose the appropriate µ during iterations by the following criteria µk+1 =  0.7µk if φ(x, µk) was difficult to solve0.1µk if φ(x, µk) was easy to solve Algorithm 1 Quadratic penalty method Input: Given µ0 > 0, x0 and a final tolerance tol Output: x∗k 1: x = x0 2: µ = µ0 3: for k = 0, 1, 2, . . . do 4: if ‖∇φ (x;µ) ‖ ≤ tol then 5: x∗k = x 6: Exit 7: else 8: choose µk+1 ∈ (0, µk) 9: Use Newton’s method with line search to get xk+1, see Algorithm (2). 10: x = xk+1 11: µ = µk+1 12: end if 13: end for 3.4.2 Derivation We have already given three independent optimization schemes for rotation and translation with respect to each coordinate axis. When solving them using penalty 21 Algorithm 2 Newton’s method with line search Input: f (x) ,x0, maxiterations, αmin Output: x∗ 1: Give an initial guess: x = x0 and k = 0 2: while k < maxiterations do 3: First try Newton’s method with xk 4: if The error is within the tolerance then 5: Accept the result from Newton’s method and return xk as x∗ 6: else 7: Try a line search to get a new xk and α 8: if α < αmin then 9: line search fails and if we have not reached the max number of iterations, then try it again. Otherwise, we return the best solution of this search. 10: else 11: return xk as x∗ 12: end if 13: end if 14: end while method, we need to reformulate the original constrained optimization to uncon- strained optimization as explained in section (3.4.1). The remainder of this section shows the derivation of the corresponding gradient vectors and Hessian matrices. Transformations with Rotation around X-Axis The new optimization is obtained from expanding scheme (3.11)as follows: min C,S,tz n∑ i ( Syi + Czi + tz − z′i )2 + 1 2µ ( C2 + S2 − 1 )2 (3.21) let φ(x, µ) = n∑ i ( Syi + Czi + tz − z′i )2 + 1 2µ ( C2 + S2 − 1 )2 (3.22) x = [C, S, tz] T , µ is the penalty coefficient. Hence, the gradient and Hessian of φ(x, µ) are ∇φ(x, µ) =  ∑n i 2zi (Czi + Syi + tz − z′i) + 2C(C2+S2−1) µ∑n i 2yi (Czi + Syi + tz − z′i) + 2S(C2+S2−1) µ∑n i 2 (Czi + Syi + tz − z′i)  (3.23) 22 and Hessianφ =  ∑n i 2z 2 i + 6C2+2S2−2 µ ( ∑n i 2yizi) + 4CS µ ∑n i 2zi ( ∑n i 2yizi) + 4CS µ ∑n i 2y 2 i + 2C2+6S2−2 µ ∑n i 2yi∑n i 2zi ∑n i 2yi ∑n i 2  (3.24) Transformations with Rotation around Y-Axis We expand scheme (3.13) as: min C,S,tx,tz n∑ i [( Cxi + Szi + tx − x′i )2 + (−Sxi + Czi + tz − z′i)2] + ( C2 + S2 − 1)2 2µ (3.25) and similarly, φ(x, µ) = n∑ i [( Cxi + Szi + tx − x′i )2 + (−Sxi + Czi + tz − z′i)2] + ( C2 + S2 − 1)2 2µ (3.26) where x = [C, S, tx, tz] T and µ is the same as before. Hence, the gradient∇φ(x, µ) ∑n i 2xi (Cxi + Szi + tx − x′i) + 2zi (−Sxi + Czi + tz − z′i) + 2C(C2+S2−1) µ∑n i −2zi (Cxi + Szi + tx − x′i) + 2xi (−Sxi + Czi + tz − z′i) + 2S(C2+S2−1) µ∑n i 2 (Cxi + Szi + tx − x′i)∑n i 2 (−Sxi + Czi + tz − z′i)  and the Hessian of φ(x, µ) ∑n i 2 ( x2i + z 2 i ) + 6C 2+2S2−2 µ 4CS µ ∑n i 2xi ∑n i 2zi 4CS µ ∑n i 2 ( x2i + z 2 i ) + 2C 2+6S2−2 µ ∑n i 2zi − ∑n i 2xi∑n i 2xi ∑n i 2zi ∑n i 2 0∑n i 2zi − ∑n i 2xi 0 ∑n i 2  23 Transformations with Rotation around Z-Axis Expand the scheme (3.17): min C,S,tx n∑ i ( Cxi − Syi + tx − x′i )2 + (C2 + S2 − 1)2 2µ (3.27) and φ(x, µ) = n∑ i ( Cxi − Syi + tx − x′i )2 + (C2 + S2 − 1)2 2µ (3.28) where x = [C, S, tz] T and µ is the same as before. Hence, the gradient and Hessian of φ(x, µ) are ∇φ(x, µ) =  ∑n i 2xi (Cxi − Syi + tx − x′i) + 2C(C2+S2−1) µ∑n i −2yi (Cxi − Syi + tx − x′i) + 2S(C2+S2−1) µ∑n i 2 (Cxi − Syi + tx − x′i)  (3.29) and Hessianφ =  ∑n i 2x 2 i + 6C2+2S2−2 µ − ∑n i 2xiyi + 4CS µ ∑n i 2xi −∑ni 2xiyi + 4CSµ ∑ni 2y2i + 2C2+6S2−2µ −∑ni 2yi∑n i 2xi − ∑n i 2yi ∑n i 2  (3.30) 24 Chapter 4 Mesh Deformations After the alignment step, the template will be overlapping the 2D sketch, but the overall shape of the template remains unchanged since the alignment is a rigid transformation. Hence, we now deform the aligned template to better match the sketch. Our mesh deformation method is based on the method given by Popa et al. [22], and we modify it to incorporate the positional constraints. 4.1 Method Overview 4.1.1 Optimization Scheme In [22], a 3D model is deformed by utilizing a set of user specified anchors. First, it computes the anchor transformation matrices using the rotation angle and axis which are given by users when selecting anchors, and then propagates the trans- formations to the entire model by blending them with each facet of the 3D model. Finally, it finds an optimal position for each vertex of the mesh by minimizing the errors between previously computed transformations and the transformations obtained from the transformation gradient. The optimization scheme is formally modeled as: min ṽ n−q∑ i ψi‖ṼiV −1i − Ti‖2F (4.1) 25 where n is the number of faces, q is the number of the anchors, ψi is the shearing stiffness coefficient, Ti is the transformation for ith triangle of the mesh, Vi and Ṽi are the local frames of the ith triangle before and after applying the deformation and defined as follows: Vi = (v4 − v1, v4 − v2, v4 − v3) (4.2) where v1, v2, and v3 are the three vertices of the ith triangle, v4 is the augmented fourth vertex computed by offsetting one of the vertices by the triangle normal, such that three vectors (v4 − v1, v4 − v2, v4 − v3) define a local frame. After applying the deformation, Vi becomes Ṽi Ṽi = (ṽ4 − ṽ1, ṽ4 − ṽ2, ṽ4 − ṽ3) (4.3) We refer readers to [22] for a detailed explanation. The anchor triangles in the system only provide information for the rotations, and therefore the position constraints are not included in the above formulation. In our system, however, a good match between the sketch and model requires the correspondences to be as close as possible after deformation, thus we must enforce the position constraints. We modify the optimization scheme given in (4.1) as follows: min ṽ n∑ i α ( ψi‖ṼiV −1i − Ti‖2F ) + m∑ j β ‖ṽj − cj‖22 (4.4) where α and β are weighting factors to balance the contributions between the trans- formation and position constraints, n is the number of faces and m is the number of correspondences; ṽj is the deformed vertex of vj and cj is the corresponding 2D sketch point of vj . Note that when we compute the error between ṽj and cj , we only consider the X and Z components of ṽj , since our sketch is assumed to be on the XZ plane. We thus change the framework of [22] to accommodate 2D sketch points as position constraints. We do not have restrictions on choosing the values of α and β. In our experiments, we use various values for them, but make β > α 26 so that position constraints are given significant weight. Solving this optimization problem yields new positions of the vertices such that the correspondences are as close as possible. 4.1.2 Constraints As described above, we shall use both the normal vectors and the spatial positions of the correspondences as constraints. The spatial positions are taken from the corresponding points. We use the normal vectors of the anchor facets as the normal vectors of the 3D correspondences. For the sketch, we modify the 2D normal vectors of the sketch points as described below so that we are able to use them to evaluate the deformations. For a correspondence pair (vj , cj), where vj is a vertex of the template, and cj is a 2D sketch point, assume that −→ Nc = [ncx, n c z] T is the normal vector of cj , and −→Nv = [nvx, nvy, nvz ]T is the normal vector of the anchor facet which contains vj . Then we modify −→Nc to obtain −→Nc′ = [ncx, nvy, ncz]T . Note that we do not take 0 as the y-component of −→Nc′, even though we have assumed that the 2D sketch is on XZ coordinate plane. When using a 2D vector to infer a 3D vector, we do not have enough information on what a best fit y-component should be. Therefore, we consider only the differences between −→Nv and −→Nc in the X and Z directions. Experiments have also shown that using 0 valued y-component results in larger errors. 4.2 Deformation In order to evaluate the appropriate deformation of the mesh, we need to estimate the transformation of each triangle on the mesh. As given in [22], the transformations of individual triangles can be obtained by blending the transformations of the anchor facets. The transformations of anchor facets can be evaluated as described below. Assuming that the normal vector of an anchor triangle fa is −→ Nmodel = 27 [xm, ym, zm]T and its corresponding augmented normal vector from the 2D sketch(see section 4.1.2) is −→N sketch = [xs, ys, zs]T . Then θ = arccos (−→ N sketch · −→Nmodel ) −→w = −→N sketch ×−→Nmodel (4.5) where θ is the rotation angle and−→w is the rotation axis, therefore, the transformation matrix is Ta =  txwxw + cos θ txwyw + zw sin θ txwzw − yw sin θ txwyw − zw sin θ tywyw + cos θ tywzw + xw sin θ txwzw + yw sin θ tywzw − xw sin θ tzwzw + cos θ  (4.6) where t = 1 − cos θ and xw, yw, zw are the three components of −→w . We find the transformation for each anchor facet by using (4.6) and then compute Ti as follows: Ti = q⊕ a=1 ωai Ta (4.7) where i = 1, . . . , n, Ta is the transformation of an anchor triangle, a = 1, . . . , q, and ωai represents the relative influence of the anchor transformation Ta to Ti. The details of weights computation for each triangle of the mesh are given in [22]. Finally, we solve the optimization problem (4.4) with {T1, . . . , Tn} to compute the newly deformed shape. 4.3 Numerical Methods The optimization formulation given by (4.1) can be rewritten as a linear system: min ṽ ‖Ψ(Aṽ − t) ‖22 (4.8) where A is a sparse matrix constructed using Ṽi and Vi, t is a vector composed of all the elements in Ti and Ψ is a diagonal matrix composed of all ψi. Similarly, we can reformulate our optimization problem (4.4) in terms of a linear system: min ṽ ∥∥∥Ãṽ − t̃∥∥∥2 2 (4.9) 28 where ṽ is the same as in (4.8), à and t̃ are derived from A and t of (4.8). Below we will show how to get (4.8) and extend it to (4.9). First, recall that Vi = ( vi4 − vi1, vi4 − vi2, vi4 − vi3 ) Ṽi = ( ṽ4 i − ṽ1i, ṽ4i − ṽ2i, ṽ4i − ṽ3i ) Note that only Ṽi is unknown. Now assume: vi1 =  xi1 yi1 zi1  vi2 =  xi2 yi2 zi2  vi3 =  xi3 yi3 zi3  vi4 =  xi4 yi4 zi4  ṽ1 i =  x̃1 i ỹ1 i z̃1 i  ṽ2i =  x̃2 i ỹ2 i z̃2 i  ṽ3i =  x̃3 i ỹ3 i z̃3 i  ṽ4i =  x̃4 i ỹ4 i z̃4 i  then Vi =  xi4 − xi1 xi4 − xi2 xi4 − xi3 yi4 − yi1 yi4 − yi2 yi4 − yi3 zi4 − zi1 zi4 − zi2 zi4 − zi3  Ṽi =  x̃4 i − x̃1i x̃4i − x̃2i x̃4i − x̃3i ỹ4 i − ỹ1i ỹ4i − ỹ2i ỹ4i − ỹ3i z̃4 i − z̃1i z̃4i − z̃2i z̃4i − z̃3i  therefore, we can get V −1i =  a b c d e f g h i  29 where a, b, . . . , i correspond to the entries of the inverse matrix of Vi that can be evaluated from the coordinates of the vi1, v i 2, v i 3 and v i 4. Thus ṼiV −1 i − Ti =  x̃4 i − x̃1i x̃4i − x̃2i x̃4i − x̃3i ỹ4 i − ỹ1i ỹ4i − ỹ2i ỹ4i − ỹ3i z̃4 i − z̃1i z̃4i − z̃2i z̃4i − z̃3i   a b c d e f g h i  −  ti1 t i 2 t i 3 ti4 t i 5 t i 6 ti7 t i 8 t i 9 (4.10) and ‖ṼiV −1i − Ti‖2F is equivalent to∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥  −a 0 0 −d 0 0 −g 0 0 a+ d+ g 0 0 ... . . . ... ... . . . ... 0 0 −c 0 0 −f 0 0 −i 0 0 c+ f + i   x̃1 i ỹ1 i z̃1 i x̃2 i ỹ2 i z̃2 i ... x̃4 i ỹ4 i z̃4 i  −  ti1 ti2 ti3 ti4 ti5 ti6 ti7 ti8 ti9  ∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥∥ 2 2 From left to right we have a 9×12 sparse matrix, a 12×1 column vector containing ṽ1 i, ṽ2i ṽ3i and ṽ4i, and a 9 × 1 column vector containing all elements of the Ti. Similarly, for a model with n faces, q anchors, and k vertices, we can construct a 9n× 3(n+ k) sparse matrix A, a 3(n+ k)× 1 column vector ṽ containing all ṽi and ṽ4 i, ṽ = [ x̃1 ỹ1 z̃1 . . . x̃k ỹk z̃k x̃4 1 ỹ4 1 z̃4 1 . . . x̃4 n ỹ4 n z̃4 n ]T and finally, a 9n× 1 column vector t containing all the elements of T1, T2, . . . , Tn t = [ t11 . . . t 1 9 . . . t n 1 . . . t n 9 ]T Note that for an anchor, ṼiV −1i = Ti, therefore, n−q∑ i ψi ∥∥∥ṼiV −1i − Ti∥∥∥2F 30 is equivalent to ‖Ψ(Aṽ − t)‖22 where Ψ is a diagonal matrix composed of all ψi. Hence (4.1) becomes the linear system (4.8). To get (4.9), we need to expand (4.8) as illustrated in Figure 4.1: where A′ and C are to account for the position constraint term ∑m j β‖ṽj − cj‖22 in Figure 4.1: Expansion of linear system (4.4), and then let à =  Ψ′A A′  and t̃ =  Ψ′T C  where Ψ′ is a 9n × 9n matrix based on Ψ of (4.8), but its diagonal values become √ αψi and each will be repeated 9 times on the diagonal. Ψ′ =  √ αψ1 . . . 0 ... . . . ... 0 . . . √ αψ9n  We then arrived at (4.9) which can be solved using the normal equation to obtain a least-squares solution. 31 Chapter 5 Results We have implemented the system using C++ and Graphite [8]. Graphite is a re- search platform for computer graphics, 3D modeling and numerical geometry. It is a cross-platform toolkit which works under both Windows XP and Linux. 5.1 Alignment We use at least 4 correspondences between the sketch and the model. Additional correspondences do not necessarily better align the model with the sketch, instead that may introduce more errors. The alignment transformation matrices are ob- tained from solving the optimization problems described in Chapter 3, requiring a moderately good initial guess to avoid the local minima. The results are presented in Figure 5.1, 5.2, and 5.3. 5.2 Deformation After the alignment, we may need to manually establish more correspondences other than those we used for the alignment to obtain a better match. Therefore, we use extra correspondences when necessary. Our system handles small deformations better than large deformations. The extent of deformations is determined by the 32 extent of differences between normals and the positions of the correspondences. Large deformations imply a large change in orientation of normals and/or significant distance between corresponding sketch and model points. The results are shown in Figure (5.4, 5.5, 5.6). 33 (a) 2D Sketch (b) 2D sketch and 3D template before alignment (c) After alignment, side view (d) After alignment, front view Figure 5.1: Cat head example - The model has 3,748 triangles and 1,893 vertices, and is aligned n 0.5 second with 4 correspondences on forehead, face, nose and nose tip. The alignment 34 (a) 2D sketch with 3D cat template before alignment (b) After alignment, side view (c) After alignment, top left view (d) After alignment, top right view Figure 5.2: Cat example - The model has 14,410 triangles and 7,207 vertices, and is aligned 0.7 second with 5 correspondences. 2 on head, 1 on neck, 1 on back and 1 on rear 35 (a) 2D sketch with 3D horse head template before alignment (b) After alignment, side view (c) After alignment, front view Figure 5.3: Horse head example - The model has 5,123 triangles and 2,589 vertices, and is aligned 0.5 second with 4 correspondence on forehead, face, nose and nose tip 36 (a) Side view (b) left side and front view (c) Top view (d) Front view Figure 5.4: Simple deformation test with a bar - 4 correspondences for alignment at the horizontal part of the bar, see right part of the bar in (a). For deformation, based on existing 4 correspondences from alignment, we add one more on the left end of the bar (please refer to (a)), so use 5 correspondences to deform the model. We pick α = 0.2 and β = 1.0. Please note that we highlight the anchor facets with red color. 37 (a) 4 correspondences, 2 on ears and 2 on nose. and the positions of ear tips are de- liberately set to one front and one back (b) Top view (c) left side view (d) Right side view Figure 5.5: Cat head deformation test with 4 correspondences after alignment. α = 0.2 and β = 1.0 38 (a) 2D sketch (b) After alignment, use new correspon- dences to deform the model so that the shape match the sketch as closely as pos- sible (c) Final result Figure 5.6: Cat head alignment and deformation example 39 Chapter 6 Conclusions and Future Work The construction of 3D models from sketches is far from trivial. A reliable and capable system needs to interpret user drawings correctly and be able to generate a visually pleasing shape. Currently, our system uses simple sketches, such as the profile of a virtual 3D model; but we aim in the future to be able to use feature lines as well, like in [20] where they modify the features of a model. The alignment of the 3D model to the 2D sketch plays an essential role in our system. It significantly affects the final result. However, in the alignment process, using penalty method with Newton iteration to solve a minimization problem with equality constraints is not guaranteed to give a meaningful result unless the initial guess is good. Our current system is problematic in this respect. Deforming the 3D geometry to obtain a desired shape poses challenge with respect to the efficiency and quality of the results. From our experiments, it shows that the processing time significantly increases when the number of vertices gets large. The system does not work well with large deformations. Therefore, we need to improve from these two aspects. One way to mitigate the influence of large deformations is that we could use the concepts of the region of interests or the mesh material as proposed in [22], such that the deformation would not be propagated through out the entire mesh. 40 Deformation and vertex repositioning can potentially introduce bad shaped triangles in the resulting mesh. Therefore, after deformation step, we may need to remesh the new model. Any easy to use and robust method of remeshing would likely be suitable. 41 Bibliography [1] M. Alexa. 2001. Local Control for Mesh Morphing. In Proceedings of Shape Modeling International, pages 209-215. IEEE Computer Society Press, 2001. [2] M. Alexa. 2003. Differential coordinates for local mesh morphing and defor- mation. In The Visual Computing 19, 2, pp105-114, 2003 [3] M. Alexa, D. Cohen-Or, D. Levin. 2000. As-rigid-as possible shape in- terpolation. In SIGGRAPH ’00: ACM Trans. Graph., ACM Press, pp157-164, 2000. [4] K.S. Arun, T.S. Huang, and S.D.Blostein 1987. Least square fitting of two 3-D point sets. In IEEE Trans. Patt. Anal. Machine Intell.vol. PAMI-9, no.5, pp 698-700, 1987. [5] P. J. Besl, and N. D. McKey 1992. A Method for Registration of 3-D Shapes. In IEEE Transactions on pattern analysis and machine intelligence, Vol, 14, No.2, Feberuary 1992. [6] M. Botsch, M. Pauly, C. Rossl, S. Bischoff, L. Kobbelt 2006. SIG- GRAPH’06 Course on: Geometry modeling based on triangle meshes. [7] D. DeCarlo, A. Finkelstein, S. Rusinkiewicz, A. Santella. 2003. Suggestive Contours for Conveying Shape. In SIGGRAPH ’03: ACM Trans. Graph., ACM Press, pp848-855, 2003. [8] Graphite 2003. http://www.loria.fr/ levy/Graphite/index.html, 2003 [9] B.K.P. Horn 1987. Closed-form solution of absolute orientation using unit quaternions. In J.Opt. Soc. Amer. A, vol. 4, no.4 pp629-642, Apr. 1987. [10] J. Huang, X. Shi, X. Liu, K. Zhou, L. Wei, S. Teng, H. Bao, B. Guo, H. Shum. 2006. Subspace Gradient Domain Mesh Deformation. In SIGGRAPH ’06: ACM Trans. Graph., ACM Press, 2006. 42 [11] T. Igarashi, S. Matsuoka, and H. Tanaka 1999. Teddy: A Sketching Interface for 3D Freeform Design In SIGGRAPH ’99: ACM Trans. Graph., ACM Press, pp 409-416, 1999. [12] T. Igarashi, T. Moscovich, and J. H. Houghes 2005. As-rigid-as possible shape manipulation In SIGGRAPH ’05: ACM Trans. Graph., ACM Press, pp 1134-1141, 2005. [13] O. A. Karpenko, and J. F. Hughes 2006. SmoothSketch: 3D free-form shapes from complex sketches. In SIGGRAPH ’06: ACM Trans. Graph., vol 25, , no. 3, pp 589-598, 2006. [14] Y. Kho and M. Garland 2005. Sketching mesh deformations. In SI3D ’05: Proceedings of the 2005 symposium on Interactive 3D graphics and games., pp 147-154, ACM Press, NY. 2005. [15] J. J. LaViola Jr., R. Davis, and T. Igarashi 2006. SIGGRAPH’06 Course on: An Introduction to Sketch-Based Interfaces. [16] H. Lensch, W. Heidrich, and H.-P. Seidel 2001. A Silhouette-based Algorithm for Texture Registration and Stitching. In Graphical Models, July 2001, pp. 245-262 [17] X. Li and I. Guskov and J. Barhak 2006. Robust Alignment of Multi-view Range Data to CAD Model. In SMI ’06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006 (SMI’06), IEEE Com- puter Society, Washington, DC, USA. [18] Y. Lipman, O. Sorkine, D. Cohen-Or, D. Levin, C. Rossl,and H.- P. Seidel. 2004. Differential coordinates for interactive mesh editing. In Proceedings of Shape Modeling International, pages 181C190. IEEE Computer Society Press, 2004. [19] Y. Lipman, O. Sorkine, D. Levin, and D. Cohen-Or. Linear 2005. Lin- ear rotation-invariant coordinates for meshes. In Proceedings In SIGGRAPH ’05: ACM Trans. Graph., ACM Press, 2005. [20] A. Nealen, O. Sorkine, M. Alexa and D. Cohen-Or 2005. A Sketch- Based Interface for Detail-Preserving Mesh Editing. In SIGGRAPH ’05: ACM Trans. on Computer graphics, vol. 24, no. 3, pp 1142-1147, 2005. [21] J. Nocedal and S. Wright 1999. Numerical Optimization. Springer Verlag, 1999 43 [22] T. Popa, D. Julius, and A. Sheffer 2006. Material Aware Mesh De- formations. In SMI ’06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006 (SMI’06), IEEE Computer Society, Washington, DC, USA. [23] S. Rusinkiewicz, M. Levoy. 2001. Efficient variants of the ICP algorithm. In Third International Conference on 3D Digital Imaging and Modeling(3DIM)., 2001 [24] D. Mumford. 1994. Elastica and computer vision. In Algebraic Geometry and Its Applications., C. L. Bajaj, Ed. Springer-Verlag New York Inc. 1994 [25] A. Sheffer and V. Kraevoy. 2004. Pyramid coordinates for morphing and deformation. In 3DPVT, pages 68C75, 2004. [26] K. Singh, and E. Fiume 1998. Wires: A geometry deformation technique. In SIGGRAPH ’98: ACM Trans. Graph., ACM Press, pp 405-414, 1998. [27] O. Sorkine 2005. Laplacian mesh processing. In Eurographics 2005—State of the Art Reports., The Eurographics Association, Dublin, Ireland, Eurographics, 53–70. [28] O. Sorkine, Y. Lipman, D. Cohen-Or, M. Alexa, C. Rossl, and H.-P. Seidel 2004. Laplacian surface editing. In Proceedings of the Eurograph- ics/ACM SIGGRAPH Symposium on Geometry processing., pp 179-188, 2004 [29] R. W. Sumner and J. Popovic 2004. Deformation transfer for triangle meshes. In SIGGRAPH ’04: ACM Trans. on Computer graphics, vol. 23, no. 3, 2004. [30] L. R. Williams 1991. Shading in Two Dimensions. In Graphics Interface’91, pages 143-151, 1991. [31] L. R. Williams 1994. Perceptual Completion of Occluded Surfaces. PhD thesis, University of Massachusetts. [32] L. R. Williams 1997. Topological reconstruction of a smooth manifold-solid from its occluding contour. In Intl. Journal of Computer Vision 23, 1, 93-C108, 1997. [33] C. Yang, D. Sharon, and M. van de Panne 2005. Sketch-based Modeling of Parameterized Objects. In 2nd Eurographics Workshop on Sketch-Based Interfaces and Modeling, Dublin, August 28-29, 2005. 44 [34] Y. Yu, K. Zhou, D. Xu, X. Shi, H. Bao, B. Guo, H. Shum. 2004. Mesh Editing with Poisson-Based Gradient Field Manipulation. In SIGGRAPH ’04: ACM Trans. Graph., ACM Press, pp644-651, 2004. [35] K. Zhou, J. Huang, J. Snyder, X. Liu, H. Bao, B. Guo, H. Shum. 2005. Large Mesh Deformation Using the Volumetric Graph Laplacian. In SIGGRAPH ’05: ACM Trans. Graph., ACM Press, pp496-503, 2005. 45"@en ; edm:hasType "Thesis/Dissertation"@en ; vivo:dateIssued "2008-11"@en ; edm:isShownAt "10.14288/1.0051370"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Computer Science"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms:rights "Attribution-NonCommercial-NoDerivatives 4.0 International"@en ; ns0:rightsURI "http://creativecommons.org/licenses/by-nc-nd/4.0/"@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Semi-automatic fitting of deformable 3D models to 2D sketches"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/797"@en .