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 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Correspondence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3.1 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3.2 Rotation and Translation . . . . . . . . . . . . . . . . . . . . 17 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4.1 Penalty Method . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4.2 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4 Smoothing 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 5.2 . . . . . . . . . . . . . . . . . . . 34 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 . . . . . . . . . . . . . . . . . . . . . . . . . v 35 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 36 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. 5.5 5.6 . . . 37 Cat head deformation test with 4 correspondences after alignment. α = 0.2 and β = 1.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 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 encouraging 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 demonstrated 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 deformable templates to 2D sketches. In our system, a user creates a sketch by drawing 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 correspondences 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 deform (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 correspondences. Deformation: Iteratively establish additional correspondences 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 template 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 deform 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 appropriate 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 transformation 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 original 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 reconstruction, 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 interactively 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 silhouettes 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 topological 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 parameterized 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 labeled 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 2.3.1 Shape Deformations 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 propagates the local transformations to create a smooth transition. Sumner et al. [29] propose a deformation gradient based method for transferring 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 vj (2.1) j∈N br(vi ) where N br(vi ) is the set of the immediate neighboring vertices of the vertex vi and ni = |N br(vi )| or the valence of vertex vi . There are a number of methods that use variations of the Laplacians coordinates 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 deformation, 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 vertices 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 deformations 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 hierarchy 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 counterclockwise 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 deformation. As a result, we apply the following Laplacian smoothing formula to all the sketch points 1 n qj + (1 − λ) pi pi = λ n j=1 (3.1) where pi is the smoothed position of pi , λ is the coefficient to balance the contributions between pi and its neighbors, n is the number of points in the neighborhood of pi denoted as N br(pi ), and qj ∈ N br(pi ). 13 (a) Before smoothing (b) Before smoothing with points highlighted (c) After smoothing (d) After smoothing points highlighted with 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. r00 r01 r02 tx r10 M = r20 0 r11 r12 ty r21 r22 tz 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 matrix M 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: vi = M (vi ) = Mx (My (Mz (vi ))) (3.3) where vi is the ith vertex of the original 3D template, vi is the ith vertex of the aligned model, and for each set of transformations: Mk (v) = Rk (sk v) + 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) s pi − pj min s 2 2 ∀(i,j) 16 − pi − p j 2 2 2 (3.5) where pi , pj are 3D vertices, and pi , pj 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 . n M (vi ) − pi min 2 2 (3.6) i 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 : 0 1 0 R= 0 C −S 0 S 17 C where C = cos θ, S = sin θ, and θ is the rotation angle. Therefore, the optimization problem (3.6) can be written explicitly as: n min C,S,tx ,tz i 1 0 0 0 C 0 S 0 tx sx xi xi 2 0 sx yi 0 − tz sx zi zi −S C 0 0 1 1 1 (3.7) 2 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 xi , zi are the coordinates of the corresponding point pi on the 2D sketch. After algebraic simplifications of (3.7), we obtain n Syis + Czis + tz − zi min C,S,tx ,tz 2 + xsi + tx − xi 2 (3.8) i Subject to : C 2 + S 2 = 1 where xsi = sx xi , yis = sx yi , zis = sx zi . 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 n xsi + tx − xi min tx 2 (3.9) i Taking derivative w.r.t tx , and setting it equal to 0, we obtain the following solution tx = 1 n n xi − xsi (3.10) i Now we still need to solve the first term for C, S, tz , namely: n Syis + Czis + tz − zi min C,S,tz 2 (3.11) i Subject to : C 2 + S 2 = 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: C R= 0 0 S 1 0 −S 0 C Equation (3.6) therefore becomes n min C,S,tx ,ty ,tz i C 0 S 0 −S 0 1 tx sy xi xi 2 0 sy yi 0 − tz sy zi zi 0 0 C 0 0 1 1 1 (3.12) 2 With a similar derivation, we can obtain an equivalent form of the scheme (3.12): n Cxsi + Szis + tx − xi min C,S,tx ,tz 2 + −Sxsi + Czis + tz − zi i Subject to : C 2 + S 2 = 1 where sy is the scale factor and xsi = sy xi , yis = sy yi , zis = sy zi . Transformations with Rotation around Z-Axis The rotation matrix R becomes: C R= S −S 0 C 0 0 0 19 1 2 (3.13) Equation (3.6) is then: n min C,S,tx ,tz i C −S 0 tx S 0 C 0 0 1 0 0 0 sz xi xi 2 0 sz yi 0 − tz sz zi zi 1 1 1 (3.14) 2 which is equivalent to n Cxsi − Syis + tx − xi min C,S,tx ,tz 2 + zis + tz − zi 2 (3.15) i Subject to : C 2 + S 2 = 1 We can solve for 1 n tz = n zi − zis (3.16) i and then minimize the following optimization scheme for C, S, and tx . n Cxsi − Syis + tx − xi min C,S,tx 2 (3.17) i Subject to : C 2 + S 2 = 1 where sz is the scale factor and xsi = sz xi , yis = sz yi , zis = sz zi . 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; µ) 1 min φ (x; µ) = f (x) + 2µ m c2i (x) (3.19) i=1 Similarly, the first order condition requires: m ∇φ (x; µ) = ∇f (x) + 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 solve 0.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 unconstrained 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: n C,S,tz 2 + Syi + Czi + tz − zi 2 Syi + Czi + tz − zi min i 1 C2 + S2 − 1 2µ 2 (3.21) let n φ(x, µ) = i + 1 C2 + S2 − 1 2µ 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 − zi ) + n i 2yi (Czi + Syi + tz − zi ) + n i 2 (Czi 2C (C 2 +S 2 −1) µ 2S (C 2 +S 2 −1) µ + Syi + tz − zi ) 22 (3.23) and n 2 i 2zi Hessianφ = ( + 6C 2 +2S 2 −2 µ n i 2yi zi ) + n i 2yi zi ) ( n 2 i 2yi 4CS µ + n i 2zi + n i 2zi 4CS µ 2C 2 +6S 2 −2 µ n i 2yi n i 2yi n i 2 (3.24) Transformations with Rotation around Y-Axis We expand scheme (3.13) as: n 2 Cxi + Szi + tx − xi min C,S,tx ,tz + −Sxi + Czi + tz − zi 2 i 2 C2 + S2 − 1 + 2µ (3.25) and similarly, n Cxi + Szi + tx − xi φ(x, µ) = 2 + −Sxi + Czi + tz − zi 2 i + 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 2C (C 2 +S 2 −1) µ 2S (C 2 +S 2 −1) zi ) + µ + Szi + tx − xi ) + 2zi (−Sxi + Czi + tz − zi ) + n i −2zi (Cxi + Szi + tx − xi ) + 2xi (−Sxi + Czi + tz − n i 2 (Cxi + Szi + tx − xi ) n i 2 (−Sxi + Czi + tz − zi ) and the Hessian of φ(x, µ) n i 2 x2i + zi2 + 4CS µ 6C 2 +2S 2 −2 µ n i 2 x2i + n i 2xi n i 2zi n i 2xi 4CS µ zi2 + 2C 2 +6S 2 −2 µ n i 2zi − 23 n i 2xi n i 2zi n i 2zi − n i 2xi n i 2 0 0 n i 2 Transformations with Rotation around Z-Axis Expand the scheme (3.17): n C,S,tx 2 + Cxi − Syi + tx − xi 2 Cxi − Syi + tx − xi min C2 + S2 − 1 2µ i 2 (3.27) and n φ(x, µ) = + i 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, µ) = 2C (C 2 +S 2 −1) − Syi + tx − xi ) + µ 2S (C 2 +S 2 −1) n i −2yi (Cxi − Syi + tx − xi ) + µ n i 2xi (Cxi n i 2 (Cxi − Syi + tx − xi ) (3.29) and Hessianφ = n 2 i 2xi − + 6C 2 +2S 2 −2 µ n i 2xi yi + − n i 2xi yi n 2 i 2yi 4CS µ n i 2xi − 24 + + 2C 2 +6S 2 −2 µ n i 2yi n i 2xi 4CS µ − n i 2yi n i 2 (3.30) 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 4.1.1 Method Overview 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 transformations 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: n−q ψi Vi Vi−1 − Ti min v˜ i 25 2 F (4.1) 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 Vi are the local frames of the ith triangle before and after applying the deformation and defined as follows: (4.2) Vi = (v4 − v1 , v4 − v2 , v4 − v3 ) 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 Vi (4.3) Vi = (v˜4 − v˜1 , v˜4 − v˜2 , v˜4 − v˜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: m n α ψi Vi Vi−1 − Ti min v˜ 2 F β v˜j − cj + 2 2 (4.4) j i where α and β are weighting factors to balance the contributions between the transformation and position constraints, n is the number of faces and m is the number of correspondences; v˜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 v˜j and cj , we only consider the X and Z components of v˜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 , ncz ]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 N model = 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 · N model − → → − → − w = N sketch × N model (4.5) → where θ is the rotation angle and − w is the rotation axis, therefore, the transformation matrix is txw yw + zw sin θ txw zw − yw sin θ txw xw + cos θ Ta = tyw yw + cos θ tyw zw + xw sin θ txw yw − zw sin θ txw zw + yw sin θ tyw zw − xw sin θ tzw zw + 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: q ωia Ti = Ta (4.7) a=1 where i = 1, . . . , n, Ta is the transformation of an anchor triangle, a = 1, . . . , q, and ωia 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˜ v − t) v˜ 2 2 (4.8) where A is a sparse matrix constructed using Vi 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 A˜ v − t˜ v˜ 28 2 2 (4.9) where v˜ is the same as in (4.8), A 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 = v4i − v1i , v4i − v2i , v4i − v3i Vi = v˜4 i − v˜1 i , v˜4 i − v˜2 i , v˜4 i − v˜3 i Note that only Vi is unknown. Now assume: i x1 i v1i = y1 z1i z2i z˜1 i z˜2 i z3i i x4 i v4i = y4 z˜3 i i i i i i i x4 − x1 x4 − x2 x4 − x3 i i i i i i Vi = y 4 − y 1 y 4 − y 2 y4 − y3 z4i − z2i z4i − z3i i i i i i i x˜4 − x˜1 x˜4 − x˜2 x˜4 − x˜3 i i Vi = y˜4 i − y˜2 i y˜4 i − y˜3 i y˜4 − y˜1 z˜4 i − z˜1 i z˜4 i − z˜2 i z˜4 i − z˜3 i therefore, we can get Vi−1 a b = d e z4i i i x˜3 x˜4 i i i v˜3 i = y˜3 v˜4 = y˜4 then z4i − z1i i x3 i v3i = y3 i i x˜1 x˜2 i i i v˜1 i = y˜1 v˜2 = y˜2 i x2 i v2i = y2 g h i 29 c f z˜4 i where a, b, . . . , i correspond to the entries of the inverse matrix of Vi that can be evaluated from the coordinates of the v1i , v2i , v3i and v4i . Thus i i i i i i x˜4 − x˜1 x˜4 − x˜2 x˜4 − x˜3 i i Vi Vi−1 − Ti = y˜4 i − y˜2 i y˜4 i − y˜3 i y˜4 − y˜1 z˜4 − z˜1 and Vi Vi−1 − Ti −a 0 0 i 2 F i i z˜4 − z˜2 i z˜4 − z˜3 i −d 0 0 −g 0 0 g h i a+d+g 0 0 .. . ... .. . .. . ... 0 −c 0 i i i c t 1 t2 t3 i i i f − t4 t5 t6 (4.10) ti7 ti8 ti9 is equivalent to .. . 0 i a b d e 0 −f 0 0 −i 0 0 c+f +i i x˜1 y˜ i 1 2 z˜1 i x˜2 i y˜2 i z˜2 .. . i x˜4 i y˜4 i z˜4 i − ti1 ti2 ti3 ti4 ti5 ti6 ti7 ti8 ti9 v˜1 i , v˜2 i v˜3 i and v˜4 i , 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 v˜ containing all v˜i and v˜4 i , T x˜1 y˜1 z˜1 . . . x˜k y˜k z˜k x˜4 1 y˜4 1 z˜4 1 . . . x˜4 n y˜4 n z˜4 n and finally, a 9n × 1 column vector t containing all the elements of T1 , T2 , . . . , Tn T t= t11 . . . t19 . . . tn1 . . . tn9 Note that for an anchor, Vi Vi−1 = Ti , therefore, n−q ψi Vi Vi−1 − Ti i 30 2 F 2 From left to right we have a 9 × 12 sparse matrix, a 12 × 1 column vector containing v˜ = is equivalent to Ψ (A˜ v − t) 2 2 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 β v˜j − cj 2 2 in Figure 4.1: Expansion of linear system (4.4), and then let A= Ψ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 research 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 obtained 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 deliberately 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 correspondences to deform the model so that the shape match the sketch as closely as possible (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 deformation. In The Visual Computing 19, 2, pp105-114, 2003 [3] M. Alexa, D. Cohen-Or, D. Levin. 2000. As-rigid-as possible shape interpolation. 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. SIGGRAPH’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 Computer 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. Linear 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 SketchBased 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 Deformations. 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 Eurographics/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
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Semi-automatic fitting of deformable 3D models to 2D...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Semi-automatic fitting of deformable 3D models to 2D sketches Chang, Xianglong 2008
pdf
Page Metadata
Item Metadata
Title | Semi-automatic fitting of deformable 3D models to 2D sketches |
Creator |
Chang, Xianglong |
Publisher | University of British Columbia |
Date Issued | 2008 |
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. |
Extent | 5915960 bytes |
Subject |
Sketching Sketch-based interface 3D template Correspondences Alignment Deformation gradients |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2008-05-01 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
IsShownAt | 10.14288/1.0051370 |
URI | http://hdl.handle.net/2429/797 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2008-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2008_fall_chang_xianglong.pdf [ 5.64MB ]
- Metadata
- JSON: 24-1.0051370.json
- JSON-LD: 24-1.0051370-ld.json
- RDF/XML (Pretty): 24-1.0051370-rdf.xml
- RDF/JSON: 24-1.0051370-rdf.json
- Turtle: 24-1.0051370-turtle.txt
- N-Triples: 24-1.0051370-rdf-ntriples.txt
- Original Record: 24-1.0051370-source.json
- Full Text
- 24-1.0051370-fulltext.txt
- Citation
- 24-1.0051370.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.24.1-0051370/manifest