UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Semi-automatic fitting of deformable 3D models to 2D sketches Chang, Xianglong 2008-12-31

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
ubc_2008_fall_chang_xianglong.pdf [ 5.64MB ]
Metadata
JSON: 1.0051370.json
JSON-LD: 1.0051370+ld.json
RDF/XML (Pretty): 1.0051370.xml
RDF/JSON: 1.0051370+rdf.json
Turtle: 1.0051370+rdf-turtle.txt
N-Triples: 1.0051370+rdf-ntriples.txt
Original Record: 1.0051370 +original-record.json
Full Text
1.0051370.txt
Citation
1.0051370.ris

Full Text

Semi-Automatic fittingof deformable 3D models to 2D sketchesbyXianglong ChangB.Eng., Huazhong University of Science and Technology, 1994A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE STUDIES(Computer Science)The University of British Columbia(Vancouver)April 2008c Xianglong Chang, 2008AbstractWe present a novel method for building 3D models from a user sketch. Given a 2Dsketch as input, the approach aligns and deforms a chosen 3D template model tomatch the sketch. This is guided by a set of user-specified correspondences and analgorithm that deforms the 3D model to match the sketched profile. Our primarycontribution is related to fitting the 3D deformable geometry to the 2D user sketch.We demonstrate our technique on several examples.iiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.1 User Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.2 Alignment and Deformation . . . . . . . . . . . . . . . . . . . 41.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1 Sketch-based Modeling and Reconstruction . . . . . . . . . . . . . . 62.1.1 Freeform-based Modeling . . . . . . . . . . . . . . . . . . . . 62.1.2 Template-based Modeling . . . . . . . . . . . . . . . . . . . . 72.2 Registration and Alignment . . . . . . . . . . . . . . . . . . . . . . . 82.3 Shape Deformations . . . . . . . . . . . . . . . . . . . . . . . . . . . 9iii2.3.1 Deformations Based on Gradients . . . . . . . . . . . . . . . 92.3.2 Deformations Based on Differential Coordinates . . . . . . . . 103 3D to 2D Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1 2D Sketch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1.1 Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Correspondence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3 Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3.1 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.3.2 Rotation and Translation . . . . . . . . . . . . . . . . . . . . 173.4 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.4.1 Penalty Method . . . . . . . . . . . . . . . . . . . . . . . . . 203.4.2 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 Mesh Deformations . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.1 Method Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.1.1 Optimization Scheme . . . . . . . . . . . . . . . . . . . . . . 254.1.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.2 Deformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.3 Numerical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.1 Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.2 Deformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . 40Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42ivList of Figures1.1 The example of input and output of the system . . . . . . . . . . . . 21.2 System workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 System user interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 Sketch-based modeling of parameterized objects [33] . . . . . . . . . 82.2 Material-aware mesh deformations [22] . . . . . . . . . . . . . . . . . 102.3 Pyramid coordinates for morphing and deformation [25] . . . . . . . 113.1 Smoothing of the sketch . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Assuming that p1 and p2 are two adjacent sketch points, p0 is thepoint that user clicked on the screen, then the system will locatepoint p on the stroke and return it as a corresponding 2D point. . . 154.1 Expansion of linear system . . . . . . . . . . . . . . . . . . . . . . . 315.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 . . . . . . . . . . . . . . . . . . . 345.2 Cat example - The model has 14,410 triangles and 7,207 vertices, andis aligned 0.7 second with 5 correspondences. 2 on head, 1 on neck,1 on back and 1 on rear . . . . . . . . . . . . . . . . . . . . . . . . . 35v5.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 . . . . . . . . . . . . . . . . . . . . . . . . . . 365.4 Simple deformation test with a bar - 4 correspondences for alignmentat the horizontal part of the bar, see right part of the bar in (a). Fordeformation, based on existing 4 correspondences from alignment, weadd one more on the left end of the bar (please refer to (a)), so use 5correspondences to deform the model. We pick alpha = 0.2 and beta = 1.0.Please note that we highlight the anchor facets with red color. . . . 375.5 Cat head deformation test with 4 correspondences after alignment.alpha = 0.2 and beta = 1.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.6 Cat head alignment and deformation example . . . . . . . . . . . . . 39viAcknowledgementsFirst of all, I?d like to acknowledge the invaluable supervision from my supervisorsDr. Alla Sheffer and Dr. Michiel van de Panne. Without you, this would have neverbeen possible.I also would like to thank Sahar Sajadieh for her work on this project duringher summer study with Dr. Alla Sheffer. Thanks also to the people from imagerlab and my friends in Computer Science Department for the fun, inspiring work andstudy 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 ChangThe University of British ColumbiaApril 2008viiAll my work is dedicated to my family.viiiChapter 1Introduction1.1 MotivationGeometry processing techniques are widely used in computer-aided design, computeranimation, and related areas. One of the central geometry processing tasks is tocreate models. Users demand tools to be intuitive, robust, and most importantly,to help in conveying their ideas. Sketching with pen and paper is a traditionalway of communicating ideas and shapes. A sketch can convey a shape in a fewstrokes and thus can be an efficient tool in prototyping and preliminary design. Thedesire for efficiency and convenience has driven researchers to study sketching asa form of interaction graphical software and develop tools capable of interpretingsketches. Today, a small but increasing number of applications in design, modelingand animation support some form of sketching.Sketch-based applications in geometry processing area have been aroundsince 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 complexshapes, because these include a multitude of geometric features, many of which aredifficult to infer from a sketch. An alternative is to modify existing templates usingsketched feature lines, such as suggestive contours [7]. However, this is by no meanstrivial. Nealen et al. [20] developed a sketch-based interface to tackle this problem.1The resulting shapes can be realistic and complex, but the approach requires theuser to be experienced in manipulating the models. If we could work with existingmodels while using a sketch as input as in [11] and [13], then the system would beaccessible to a wide range of users. Creating a model from a photograph may alsobecome possible.1.2 System OverviewThis 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 theobject 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 correspondencepairs a 2D sketch point with a 3D vertex on the template model. The system usesthese correspondences and the associated 2D and 3D normal to align and deformthe 3D template so that the resulting model matches the 2D sketch. An example ofinput and output of the system is shown in Figure 1.1. The corresponding workflowis shown in Figure 1.2.(a) User sketch (b) Template (c) Align and de-form(d) Final resultFigure 1.1: The example of input and output of the system22D sketchcurvesd15d15Preprocessing:- Smooth sketch curves- Establish correspondencesd15d15Alignment:Using at least 4 correspondences, solvefor the rotations and scaling needed tobest align the user-specified correspon-dences.d15d15Deformation:Iteratively establish additional corre-spondences between the sketch and3D model and then deform the modelbased on all correspondencesd15d15New 3D Modelas outputFigure 1.2: System workflow1.2.1 User InterfacesThe 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, whichcan be either open or closed. We do require that a unique normal can be inferred3for each point on a stroke, this is obtained from knowing the direction of the strokeas it is drawn, as described in more detail in Chapter 3. The user draws with themouse by holding the left button pressed while dragging the cursor in the sketcharea. The user uses both 2D and 3D interfaces in order to specify correspondencesbetween the sketch and the 3D template, one pair a time. Lastly, the 3D interfaceis used to display the result of the alignment and deformation.(a) 2D user sketch interface (b) 3D editing interfaceFigure 1.3: System user interfaces1.2.2 Alignment and DeformationThe alignment process transforms the template in order to align the user-specifiedcorrespondences as closely as possible. During this step, the shape of the templateis preserved and the template only undergoes a similarity transformation. Thealignment consists of two steps. First, the system scales the model to the samesize as the sketch. Second, it rigidly transforms and translates the model to bestachieve the specified correspondences. The output of the alignment is then used asthe 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 firstestablished between the template and the sketch. Then we use both the normal4vectors and spatial positions of the corresponding points to determine the appropri-ate deformations that deform the 3D model towards matching the 2D sketch. Ourdeformation method is based on Popa et al. [22] where they compute the transfor-mation for each triangle of the mesh by propagating and blending transformationsfrom anchor triangles, and use vertex positions before and after the deformationto represent the transformation gradients. The optimal vertex positions can thenbe obtained by minimizing the difference between the transformation gradients andthe previously computed transformations. The original method uses only normalconstraints. In our application, we also consider positional constraints in order toobtain 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 forthe positional constraints. We further introduce additional constants that balancethe relative contributions of the desire to maintain the original template shape andpositional constraints. The modified method is described in Chapter 4.1.3 OrganizationThe rest of this thesis is organized as follows. Relevant literature is discussed inChapter 2. The 3D to 2D alignment is described in Chapter 3. Mesh deformationsis discussed in Chapter 4, and Chapter 5 demonstrates and explains the results.Lastly Chapter 6 discusses possible improvements and as well as future research.5Chapter 2Related WorkOur proposed modeling method involves aspects of sketch-based modeling and re-construction, registration, alignment, and shape deformation. In this chapter wereview previous work in these areas.2.1 Sketch-based Modeling and ReconstructionSketch-based modeling potentially provides users with a convenient way to interac-tively create new objects on a computer either from scratch or by deforming existingtemplates. It combines a user interface with mesh editing methods.2.1.1 Freeform-based ModelingIgarashi et al. [11] designed a sketch-based interface called Teddy to generate 3Dfreeform models. The user draws several 2D freeform strokes representing a desiredgeometry, 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 topologicallyequivalent to a sphere.Karpenko and Hughes [13] present a method which can be incorporated intoa sketch-based freeform modeling interface, such as Teddy [11], to extend the ability6of creating more complex freeform geometries. The algorithm is based on the workof [24] and [31] to infer a plausible shape from its visible contours. The sketch is nolonger required to be a simple closed curve, but can have cusps and T-junctions. Tocreate 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 ModelingNealen 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 geta desired model. They suggest that building a model from sketch can be seen asan inverse Non-Photorealistic-Rendering problem, and therefore their interface usessilhouettes and suggestive contours as input for the editing mode. Users sketch acurve within a user specified region of influence on the model and the system adaptsthe template so that the curve becomes a feature line on the model.Kho and Garland [14] present a system that allows users to interactivelymodify a template via direct sketching on the model. They treat the user sketch asa reference skeleton of the region of the interest(ROI). Users first draw a referencecurve to define a skeleton of the ROI, then draw another target reference curve asthe skeleton of the desired shape. The deformation of the template is determinedby 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 classesfrom 2D user sketches. It interprets the strokes as a sketch graph and uses the 2Dtemplate to label the parts of the sketch. Once a best-fit template is found, thesystem constructs a new model by extracting measurements from the resulting la-beled sketch. These measurements are fed to a pre-existing parameterized 3D modelgenerator for each object class. They demonstrate results using planes, cups, andfish (Figure 2.1). The method can be extended to work with other parameterizable73D objects.Figure 2.1: Sketch-based modeling of parameterized objects [33]2.2 Registration and AlignmentRegistration and alignment are required in our work to find the relationship betweenthe template model and the sketch. Many applications of surface matching or shaperecognition also have similar requirements. Normally, registrations can be used toalign scanned point-based surfaces to 3D models [17], align 2D textures to a 3Dmodel [16], align 3D models with respect to one another, etc.Besl and McKay [5] present an iterative closest point (ICP) algorithm forregistration of 3D shapes. The method is independent of the representations of thegeometric data and iteratively solves the registration problem of 3D shapes. Duringeach 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 thetransformed points of the given points and their corresponding points on the model.The iteration is repeated using the updated points from previous iteration stepsand stops once the error metric falls below a threshold. The convergence of the8algorithm depends on a good initial estimate of the registration.Li et al. [17] present a feature-based algorithm for approximate scan-to-modelalignment. Their method estimates the transformation that matches two surfacesfrom a single pair of corresponding points with their surface positions, normals andprinciple curvature directions. However, they need to do an exhaustive search overall possible correspondences from scan data and the model data to find an optimalpair of corresponding points. The result can then be used as the input to an ICPalgorithm to refine the registration between the surface and the model.2.3 Shape Deformations2.3.1 Deformations Based on GradientsMesh editing and deformation are key topics in geometric modeling. Yu et al. [34]use a Poisson equation to edit meshes through gradient field manipulation. Themethod relies on both the guidance vector field, i.e. gradient fields, and boundaryconditions. They used geodesic distance between every free vertex and constrainedvertices to evaluate the guidance vector field. Manipulations to the guidance fieldyield 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 correspondencesbetween the source and target triangles to define how the deformation of the sourcemesh should be transferred to the target. Once the correspondences are found,the system evaluates the transformations induced by the deformation of the sourcemodel and then maps the transformations through the correspondences from thesource to the target. Finally, the system solves an optimization problem to enforcethe continuous shape requirements of the target mesh. Popa et al. [22] also usedeformation gradients in their method. They add material properties to the model9to 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 overdeterminedproblem, and is thus solved in a weighted least-squares sense. These methods workwell for rotations but not for translations, as the gradient field is not sensitiveto translation. Deformations containing both rotation and translations thereforeremain problematic.2.3.2 Deformations Based on Differential CoordinatesAnother class of methods modifies the differential coordinates of the surface vertices.Alexa [1] demonstrates that using Laplacian coordinates as a mesh representationin morphing is better than using traditional Cartesian coordinates, and proposesto use varying weights during linear interpolation to obtain more natural, gradualblending. The Laplacian coordinate of a vertex vi is represented by the differencebetween vi and the average of its neighbors:deltai = vi - 1nisummationdisplayjelementNbr(vi)vj (2.1)where Nbr(vi) is the set of the immediate neighboring vertices of the vertex vi andni = |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 current10research in geometric processing that is related to Laplacian processing frameworkand differential representations. Lipman et al. [18] use Laplacian Coordinates topreserve the high frequency of mesh surfaces where they solve the rotation invariantproblem by first estimating rotations of a local frame and then rotating originalLalacians with these estimated rotations. Sorkine et al. [28] develop a method toimplicitly solve for rotations of Laplacians by finding optimal transformations foreach vertex. They linearize the local frame transformations to make computationsmore efficient, but at the cost of unavoidable artifacts for large rotations.Sheffer and Kraevoy [25] present a method that uses pyramid coordinatesfor 3D mesh morphing and deformation. Pyramid coordinates are a local shaperepresentation based on a set of angles and the edge lengths relating a vertex to itsadjacent neighbors. They are invariant under rigid transformations. For mesh de-formation, their method uses a number of user-specified control vertices to evaluatedeformations consisting of scaling, bending and rotation. The method is robust andcapable of generating natural looking deformations and morphing sequences (seeFigure 2.3). For reconstruction, they project the vertex v and its neighboring ver-tices vi onto v?s projection plane. Given vprime, the projection of v, and the informationof 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 whendeforming a mesh surface. Zhou et al. [35] present a method to process large de-formations using the volumetric graph Laplacian to avoid unnatural volume changeand local self-intersection by building two lattices wrapping around the mesh from11both inside and outside. The internal graph fills the interior volume to prevent largevolume change, and the external graph prevents local self-intersection. This hier-archy can better preserve both the local details and volumes, but also significantlyincreases the complexity of the operations.12Chapter 33D to 2D Alignment3.1 2D SketchIn our system, we use the 2D sketch to infer an intended 3D shape. To serve ourpurpose, 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 beassumed to point outwards with respect to the contour direction.3.1.1 SmoothingThe hand drawn sketch is prone to noise. Smoothness is important to our systembecause 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 thesketch pointspprimei = lambdaparenlefttpparenleftbt1nnsummationdisplayj=1qjparenrighttpparenrightbt+ (1 -lambda)pi (3.1)where pprimei is the smoothed position of pi, lambda is the coefficient to balance the contribu-tions between pi and its neighbors, n is the number of points in the neighborhoodof pi denoted as Nbr(pi), and qj element Nbr(pi).13(a) Before smoothing (b) Before smoothing withpoints highlighted(c) After smoothing (d) After smoothing withpoints highlightedFigure 3.1: Smoothing of the sketch3.2 CorrespondenceCorrespondences between the sketch and the model are supplied by the user. Theuser selects a point from the sketch and a corresponding vertex from the modelestablishing a corresponding pair. When selecting the 3D corresponding vertex, wealso determine one of its surrounding facets as the anchor facet. We use the samedefinition of the anchor facet as in [22]. The anchor facets are needed to determine14the deformation gradients for mesh deformations, as will be explained in detail inChapter 4. The user repeats the selection process, one pair a time, until thereare enough correspondences for our operations. We require a minimum set of fourcorrespondences for alignment. Additional correspondences can serve to help withmesh deformations.In our implementation, we use Graphite?s [8] built-in function to select thevertices 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 locatesthe 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 pointthat user clicked on the screen, then the system will locate point p on the strokeand return it as a corresponding 2D point.Once the correspondences are established, the spatial coordinates of thesketch points are then used as position constraints for both alignment and meshdeformation.3.3 AlignmentWe 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 inequation 3.2, there are 12 unknowns of which 9 unknowns, rij, i,j element [0,2], are forthe rotation or reflection, and 3 unknowns, tx,ty,tz, are for the translation. In our15system we have to deal with uniform scaling, rotations and translations.M =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtr00 r01 r02 txr10 r11 r12 tyr20 r21 r22 tz0 0 0 1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt(3.2)However, we are not able to unambiguously determine the 3D transformation matrixrequired for alignment in one step. Therefore, we developed a procedure to doalignment in three steps.Given a set of 2D correspondences supplied by the user as described in Section3.2, we model the transformation matrix M by separating the overall transformationinto three groups of transformations. Each of the three successive transformationscontains scaling, rotation and translation. However, the rotation is fixed to rotatearound a specific axis of the Cartesian coordinate system, i.e. the rotation axis iseither X, Y , or Z. It can be defined mathematically as:vprimei = M(vi) = Mx(My(Mz(vi))) (3.3)where vi is the ith vertex of the original 3D template, vprimei is the ith vertex of thealigned 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 isa scale factor, and Tk is a translation vector. The alignment problem can then befactored into the subproblems of scaling, rotation and translation.3.3.1 ScalingGiven a set of correspondences, we can estimate a scale factor s by solving thefollowing optimization problem (3.5)mins summationdisplayuniversal(i,j)parenleftbiggsbardblpi -pjbardbl22 -vextenddoublevextenddoublevextenddoublepprimei -pprimejvextenddoublevextenddoublevextenddouble22parenrightbigg2(3.5)16where pi,pj are 3D vertices, and pprimei,pprimej are corresponding 2D sketch points.3.3.2 Rotation and TranslationAs shown in equation (3.3), we need to find up to three sets of transformations withrespect to the rotation axis, and we solve the following optimization metric for aspecific rotation matrix R and translation vector T.minnsummationdisplayibardblM(vi) -pibardbl22 (3.6)where n is the number of the correspondences and we require n greaterequal 4, vi is a vertexof the 3D model and pi is the corresponding 2D sketch point. Our problem isunder-constrained in that pi is only a 2D point with which we are not able to fullyconstrain the position of a 3D vertex during the transformation. Therefore, we makean assumption that a 2D sketch is drawn on a 3D plane. In our implementation, weuse the XZ plane, and set the Y-component of the translation vector to zero whichmeans we accept whatever value of y-coordinate of the transformed vertex vi aftera 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), wehave to solve for three degrees of freedom for alignment.Transformations with Rotation around X-AxisA 3D model rotation about the X-Axis can be expressed using the rotation matrix :R =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt1 0 00 C -S0 S Cbracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt17where C = cos theta, S = sintheta, and theta is the rotation angle. Therefore, the optimizationproblem (3.6) can be written explicitly as:minC,S,tx,tznsummationdisplayivextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublebracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt1 0 0 tx0 C -S 00 S C tz0 0 0 1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtbracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtsx xisx yisx zi1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt-bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtxprimei0zprimei1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtvextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddouble22(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 xprimei, zprimei are the coordi-nates of the corresponding point pi on the 2D sketch. After algebraic simplificationsof (3.7), we obtainminC,S,tx,tznsummationdisplayibracketleftBigparenleftbigSysi + Czsi + tz -zprimeiparenrightbig2 + parenleftbigxsi + tx -xprimeiparenrightbig2bracketrightBig(3.8)Subject to : C2 + S2 = 1where xsi = sxxi, ysi = sxyi, zsi = sxzi. As each of the two terms in (3.8) mustbe positive, and involves an independent set of variables, the entire expression isminimized when both of them are minimized. Hence, we can first solve the secondterm for txmintxnsummationdisplayiparenleftbigxsi + tx -xprimeiparenrightbig2 (3.9)Taking derivative w.r.t tx, and setting it equal to 0, we obtain the following solutiontx = 1nnsummationdisplayiparenleftbigxprimei -xsiparenrightbig (3.10)Now we still need to solve the first term for C, S, tz, namely:minC,S,tznsummationdisplayiparenleftbigSysi + Czsi + tz -zprimeiparenrightbig2 (3.11)Subject to : C2 + S2 = 1This can be treated as a minimization problem with an equality constraint, and weshall use a penalty method to solve it as will be explained in more detail in section183.4. The optimization steps for the two remaining transformations are determinedin an analogous fashion.Transformations with Rotation around Y-AxisThe rotation matrix R is as follows:R =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtC 0 S0 1 0-S 0 CbracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtEquation (3.6) therefore becomesminC,S,tx,ty,tznsummationdisplayivextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublebracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtC 0 S tx0 1 0 0-S 0 C tz0 0 0 1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtbracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtsy xisy yisy zi1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt-bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtxprimei0zprimei1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtvextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddouble22(3.12)With a similar derivation, we can obtain an equivalent form of the scheme (3.12):minC,S,tx,tznsummationdisplayibracketleftBigparenleftbigCxsi + Szsi + tx -xprimeiparenrightbig2 + parenleftbig-Sxsi + Czsi + tz -zprimeiparenrightbig2bracketrightBig(3.13)Subject to : C2 + S2 = 1where sy is the scale factor and xsi = syxi, ysi = syyi, zsi = syzi.Transformations with Rotation around Z-AxisThe rotation matrix R becomes:R =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtC -S 0S C 00 0 1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt19Equation (3.6) is then:minC,S,tx,tznsummationdisplayivextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublebracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtC -S 0 txS C 0 00 0 1 tz0 0 0 1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtbracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtsz xisz yisz zi1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt-bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtxprimei0zprimei1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtvextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddouble22(3.14)which is equivalent tominC,S,tx,tznsummationdisplayibracketleftBigparenleftbigCxsi -Sysi + tx -xprimeiparenrightbig2 + parenleftbigzsi + tz -zprimeiparenrightbig2bracketrightBig(3.15)Subject to : C2 + S2 = 1We can solve fortz = 1nnsummationdisplayiparenleftbigzprimei -zsiparenrightbig (3.16)and then minimize the following optimization scheme for C, S, and tx.minC,S,txnsummationdisplayiparenleftbigCxsi -Sysi + tx -xprimeiparenrightbig2 (3.17)Subject to : C2 + S2 = 1where sz is the scale factor and xsi = szxi, ysi = szyi, zsi = szzi.3.4 OptimizationIn this section, we briefly discuss using penalty method [21] to solve our optimizationschemes (3.11), (3.13), and (3.17).3.4.1 Penalty MethodIn general, the penalty method can be considered when solving an optimizationproblem with equality constraints:min f (x) (3.18)s.t. ci (x) = 0, i = 1,2,...,m20The optimization problem is cast as an unconstrained problem by creating a newobjective function phi(x;?)min phi(x;?) = f (x) + 12?msummationdisplayi=1c2i (x) (3.19)Similarly, the first order condition requires:nablaphi(x;?) = nablaf (x) +msummationdisplayi=1ci (x)? nablaci (x) = 0 (3.20)For a sequence of values of ?. We can use the solution xasteriskmath of the (k - 1)?sunconstrained problem (3.19) with ? = ?k. This is a continuation technique. Thepenalty method algorithm is shown in Algorithm (1) and we choose the appropriate? during iterations by the following criteria?k+1 =bracelefttpbraceexbraceleftmidbraceexbraceleftbt0.7?k if phi(x,?k) was difficult to solve0.1?k if phi(x,?k) was easy to solveAlgorithm 1 Quadratic penalty methodInput: Given ?0 > 0, x0 and a final tolerance tolOutput: xasteriskmathk1: x = x02: ? = ?03: for k = 0,1,2,... do4: if bardblnablaphi(x;?)bardbl <=< tol then5: xasteriskmathk = x6: Exit7: else8: choose ?k+1 element (0,?k)9: Use Newton?s method with line search to get xk+1, see Algorithm (2).10: x = xk+111: ? = ?k+112: end if13: end for3.4.2 DerivationWe have already given three independent optimization schemes for rotation andtranslation with respect to each coordinate axis. When solving them using penalty21Algorithm 2 Newton?s method with line searchInput: f (x),x0, maxiterations, alphaminOutput: xasteriskmath1: Give an initial guess: x = x0 and k = 02: while k < maxiterations do3: First try Newton?s method with xk4: if The error is within the tolerance then5: Accept the result from Newton?s method and return xk as xasteriskmath6: else7: Try a line search to get a new xk and alpha8: if alpha < alphamin then9: 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: else11: return xk as xasteriskmath12: end if13: end if14: end whilemethod, we need to reformulate the original constrained optimization to uncon-strained optimization as explained in section (3.4.1). The remainder of this sectionshows the derivation of the corresponding gradient vectors and Hessian matrices.Transformations with Rotation around X-AxisThe new optimization is obtained from expanding scheme (3.11)as follows:minC,S,tznsummationdisplayiparenleftbigSyi + Czi + tz -zprimeiparenrightbig2 + 12?parenleftBigC2 + S2 -1parenrightBig2(3.21)letphi(x,?) =nsummationdisplayiparenleftbigSyi + Czi + tz -zprimeiparenrightbig2 + 12?parenleftBigC2 + S2 -1parenrightBig2(3.22)x = [C, S, tz]T , ? is the penalty coefficient. Hence, the gradient and Hessian ofphi(x,?) arenablaphi(x,?) =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtsummationtextni 2zi (Czi + Syi + tz -zprime) +2C(C2+S2-1)?summationtextni 2yi (Czi + Syi + tz -zprime) +2S(C2+S2-1)?summationtextni 2 (Czi + Syi + tz -zprime)bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt(3.23)22andHessianphi =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtsummationtextni 2z2 + 6C2+2S2-2? (summationtextni 2yizi) + 4CS?summationtextni 2zi(summationtextni 2yizi) + 4CS? summationtextni 2y2i + 2C2+6S2-2? summationtextni 2yisummationtextni 2zisummationtextni 2yisummationtextni 2bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt(3.24)Transformations with Rotation around Y-AxisWe expand scheme (3.13) as:minC,S,tx,tznsummationdisplayibracketleftBigparenleftbigCxi + Szi + tx -xprimeiparenrightbig2 + parenleftbig-Sxi + Czi + tz -zprimeiparenrightbig2bracketrightBig+parenleftbigC2 + S2 -1parenrightbig22? (3.25)and similarly,phi(x,?) =nsummationdisplayibracketleftBigparenleftbigCxi + Szi + tx -xprimeiparenrightbig2 + parenleftbig-Sxi + Czi + tz -zprimeiparenrightbig2bracketrightBig+parenleftbigC2 + S2 -1parenrightbig22? (3.26)where x = [C, S, tx, tz]T and ? is the same as before. Hence, the gradientnablaphi(x,?)bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtsummationtextni 2xi (Cxi + Szi + tx -xprime ) + 2zi (-Sxi + Czi + tz -zprime) +2C(C2+S2-1)?summationtextni -2zi (Cxi + Szi + tx -xprime ) + 2xi (-Sxi + Czi + tz -zprime) +2S(C2+S2-1)?summationtextni 2 (Cxi + Szi + tx -xprime )summationtextni 2 (-Sxi + Czi + tz -zprime)bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtand the Hessian of phi(x,?)bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtsummationtextni 2parenleftbigx2i + z2parenrightbig + 6C2+2S2-2?4CS?summationtextni 2xisummationtextni 2zi4CS?summationtextni 2parenleftbigx2i + z2parenrightbig + 2C2+6S2-2?summationtextni 2zi -summationtextni 2xisummationtextni 2xisummationtextni 2zisummationtextni 2 0summationtextni 2zi -summationtextni 2xi 0summationtextni 2bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt23Transformations with Rotation around Z-AxisExpand the scheme (3.17):minC,S,txnsummationdisplayiparenleftbigCxi -Syi + tx -xprimeiparenrightbig2 + parenleftbigC2 + S2 -1parenrightbig22? (3.27)andphi(x,?) =nsummationdisplayiparenleftbigCxi -Syi + tx -xprimeiparenrightbig2 + parenleftbigC2 + S2 -1parenrightbig22? (3.28)where x = [C, S, tz]T and ? is the same as before. Hence, the gradient and Hessianof phi(x,?) arenablaphi(x,?) =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtsummationtextni 2xi (Cxi -Syi + tx -xprime ) +2C(C2+S2-1)?summationtextni -2yi (Cxi -Syi + tx -xprime ) +2S(C2+S2-1)?summationtextni 2 (Cxi -Syi + tx -xprime )bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt(3.29)andHessianphi =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtsummationtextni 2x2 + 6C2+2S2-2? -summationtextni 2xiyi + 4CS?summationtextni 2xi-summationtextni 2xiyi + 4CS? summationtextni 2y2i + 2C2+6S2-2? -summationtextni 2yisummationtextni 2xi -summationtextni 2yisummationtextni 2bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt(3.30)24Chapter 4Mesh DeformationsAfter the alignment step, the template will be overlapping the 2D sketch, but theoverall shape of the template remains unchanged since the alignment is a rigidtransformation. Hence, we now deform the aligned template to better match thesketch. 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 Overview4.1.1 Optimization SchemeIn [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 axiswhich 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 minimizingthe errors between previously computed transformations and the transformationsobtained from the transformation gradient. The optimization scheme is formallymodeled as:min?vn-qsummationdisplayipsiibardbl tildewideiV -1i -Tibardbl2F (4.1)25where n is the number of faces, q is the number of the anchors, psii is the shearingstiffness coefficient, Ti is the transformation for ith triangle of the mesh, Vi and tildewideiare the local frames of the ith triangle before and after applying the deformationand 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 augmentedfourth vertex computed by offsetting one of the vertices by the triangle normal, suchthat three vectors (v4 -v1,v4 -v2,v4 -v3) define a local frame. After applying thedeformation, Vi becomes tildewideitildewideVi = ( ?v4 - ?v1, ?v4 - ?v2, ?v4 - ?v3) (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. Inour system, however, a good match between the sketch and model requires thecorrespondences to be as close as possible after deformation, thus we must enforcethe position constraints. We modify the optimization scheme given in (4.1) asfollows:min?vnsummationdisplayialphaparenleftBigpsiibardbl tildewideiV -1i -Tibardbl2FparenrightBig+msummationdisplayjbeta bardbl ?j -cjbardbl22 (4.4)where alpha and beta are weighting factors to balance the contributions between the trans-formation and position constraints, n is the number of faces and m is the numberof correspondences; ?j is the deformed vertex of vj and cj is the corresponding 2Dsketch point of vj. Note that when we compute the error between ?j and cj, weonly consider the X and Z components of ?j, since our sketch is assumed to be onthe XZ plane. We thus change the framework of [22] to accommodate 2D sketchpoints as position constraints. We do not have restrictions on choosing the valuesof alpha and beta. In our experiments, we use various values for them, but make beta > alpha26so that position constraints are given significant weight. Solving this optimizationproblem yields new positions of the vertices such that the correspondences are asclose as possible.4.1.2 ConstraintsAs described above, we shall use both the normal vectors and the spatial positionsof the correspondences as constraints. The spatial positions are taken from thecorresponding points. We use the normal vectors of the anchor facets as the normalvectors of the 3D correspondences. For the sketch, we modify the 2D normal vectorsof the sketch points as described below so that we are able to use them to evaluatethe deformations.For a correspondence pair (vj,cj), where vj is a vertex of the template, andcj is a 2D sketch point, assume that -arrowrightc = [ncx,ncz]T is the normal vector of cj,and -arrowrightv = [nvx,nvy,nvz]T is the normal vector of the anchor facet which contains vj.Then we modify -arrowrightc to obtain -arrowrightcprime = [ncx,nvy,ncz]T . Note that we do not take 0 asthe y-component of -arrowrightcprime, even though we have assumed that the 2D sketch is onXZ coordinate plane. When using a 2D vector to infer a 3D vector, we do nothave enough information on what a best fit y-component should be. Therefore,we consider only the differences between -arrowrightv and -arrowrightc in the X and Z directions.Experiments have also shown that using 0 valued y-component results in largererrors.4.2 DeformationIn order to evaluate the appropriate deformation of the mesh, we need to estimate thetransformation of each triangle on the mesh. As given in [22], the transformations ofindividual triangles can be obtained by blending the transformations of the anchorfacets. The transformations of anchor facets can be evaluated as described below.Assuming that the normal vector of an anchor triangle fa is -arrowrightmodel =27[xm, ym, zm]T and its corresponding augmented normal vector from the 2D sketch(seesection 4.1.2) is -arrowrightsketch = [xs, ys, zs]T . Thentheta = arccosparenleftBig-arrowrightNsketch ? -arrowrightmodelparenrightBig-w = -arrowrightNsketch ?-arrowrightNmodel (4.5)where theta is the rotation angle and -arrowrightis the rotation axis, therefore, the transformationmatrix isTa =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbttxwxw + cos theta txwyw + zw sintheta txwzw -yw sinthetatxwyw -zw sintheta tywyw + cos theta tywzw + xw sinthetatxwzw + yw sintheta tywzw -xw sintheta tzwzw + cos thetabracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt(4.6)where t = 1 - cos theta and xw, yw, zw are the three components of -arrowright. We find thetransformation for each anchor facet by using (4.6) and then compute Ti as follows:Ti =qcircleplusdisplaya=1omegaai circledotTa (4.7)where i = 1,...,n, Ta is the transformation of an anchor triangle, a = 1,...,q,and omegaai represents the relative influence of the anchor transformation Ta to Ti. Thedetails 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 newlydeformed shape.4.3 Numerical MethodsThe optimization formulation given by (4.1) can be rewritten as a linear system:min?v bardblPsi(A? -t)bardbl22 (4.8)where A is a sparse matrix constructed using tildewidei and Vi, t is a vector composed ofall the elements in Ti and Psi is a diagonal matrix composed of all psii. Similarly, wecan reformulate our optimization problem (4.4) in terms of a linear system:min?vvextenddoublevextenddoublevextenddouble tildewide? - ?vextenddoublevextenddoublevextenddouble22 (4.9)28where ? is the same as in (4.8), tildewide and ? are derived from A and t of (4.8). Belowwe will show how to get (4.8) and extend it to (4.9). First, recall thatVi = parenleftbigvi4 -vi1,vi4 -vi2,vi4 -vi3parenrightbigtildewideVi = parenleftBig ?v4i - ?v1i, ?v4i - ?v2i, ?v4i - ?v3iparenrightBigNote that only tildewidei is unknown. Now assume:vi1 =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtxi1yi1zi1bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtvi2 =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtxi2yi2zi2bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtvi3 =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtxi3yi3zi3bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtvi4 =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtxi4yi4zi4bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt?1i =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt?1i?1i?1ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt?2i =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt?2i?2i?2ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt?3i =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt?3i?3i?3ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt?4i =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt?4i?4i?4ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtthenVi =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtxi4 -xi1 xi4 -xi2 xi4 -xi3yi4 -yi1 yi4 -yi2 yi4 -yi3zi4 -zi1 zi4 -zi2 zi4 -zi3bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbttildewideVi =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt?4i - ?1i ?4i - ?2i ?4i - ?3i?4i - ?1i ?4i - ?2i ?4i - ?3i?4i - ?1i ?4i - ?2i ?4i - ?3ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbttherefore, we can getV -1i =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbta b cd e fg h ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt29where a,b,...,i correspond to the entries of the inverse matrix of Vi that can beevaluated from the coordinates of the vi1, vi2, vi3 and vi4. ThustildewideViV -1i -Ti =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt?4i - ?1i ?4i - ?2i ?4i - ?3i?4i - ?1i ?4i - ?2i ?4i - ?3i?4i - ?1i ?4i - ?2i ?4i - ?3ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtbracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbta b cd e fg h ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt-bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtti1 ti2 ti3ti4 ti5 ti6ti7 ti8 ti9bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt(4.10)and bardbl tildewideiV -1i -Tibardbl2F is equivalent tovextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublebracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt-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 + ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtbracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbt?1i?1i?1i?2i?2i?2i...?4i?4i?4ibracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbt-bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtti1ti2ti3ti4ti5ti6ti7ti8ti9bracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtvextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddoublevextenddouble22From left to right we have a 9?12 sparse matrix, a 12?1 column vector containing?1i, ?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 a9n ?3(n + k) sparse matrix A, a 3(n + k) ?1 column vector ? containing all ?i and?4i,? =bracketleftbigg?1 ?1 ?1 ... ?k ?k ?k ?41 ?41 ?41 ... ?4n ?4n ?4nbracketrightbiggTand finally, a 9n ?1 column vector t containing all the elements of T1,T2,...,Tnt =bracketleftbiggt11 ... t19 ... tn1 ... tn9bracketrightbiggTNote that for an anchor, tildewideiV -1i = Ti, therefore,n-qsummationdisplayipsiivextenddoublevextenddoublevextenddouble tildewideiV -1i -Tivextenddoublevextenddoublevextenddouble2F30is equivalent tobardblPsi(A? -t)bardbl22where Psi is a diagonal matrix composed of all psii. Hence (4.1) becomes the linearsystem (4.8). To get (4.9), we need to expand (4.8) as illustrated in Figure 4.1:where Aprime and C are to account for the position constraint term summationtextmj betabardbl ?j - cjbardbl22 inFigure 4.1: Expansion of linear system(4.4), and then lettildewideA =bracketlefttpbracketleftexbracketleftbt PsiprimeAAprimebracketrighttpbracketrightexbracketrightbt and ?t =bracketlefttpbracketleftexbracketleftbt PsiprimeTCbracketrighttpbracketrightexbracketrightbtwhere Psiprime is a 9n ? 9n matrix based on Psi of (4.8), but its diagonal values becomeradicalalphapsii and each will be repeated 9 times on the diagonal.Psiprime =bracketlefttpbracketleftexbracketleftexbracketleftexbracketleftexbracketleftbtradicalalphapsi1 ... 0... ... ...0 ... radicalalphapsi9nbracketrighttpbracketrightexbracketrightexbracketrightexbracketrightexbracketrightbtWe then arrived at (4.9) which can be solved using the normal equation to obtain aleast-squares solution.31Chapter 5ResultsWe have implemented the system using C++ and Graphite [8]. Graphite is a re-search platform for computer graphics, 3D modeling and numerical geometry. It isa cross-platform toolkit which works under both Windows XP and Linux.5.1 AlignmentWe use at least 4 correspondences between the sketch and the model. Additionalcorrespondences do not necessarily better align the model with the sketch, insteadthat may introduce more errors. The alignment transformation matrices are ob-tained from solving the optimization problems described in Chapter 3, requiring amoderately good initial guess to avoid the local minima. The results are presentedin Figure 5.1, 5.2, and 5.3.5.2 DeformationAfter the alignment, we may need to manually establish more correspondences otherthan those we used for the alignment to obtain a better match. Therefore, weuse extra correspondences when necessary. Our system handles small deformationsbetter than large deformations. The extent of deformations is determined by the32extent of differences between normals and the positions of the correspondences.Large deformations imply a large change in orientation of normals and/or significantdistance between corresponding sketch and model points. The results are shown inFigure (5.4, 5.5, 5.6).33(a) 2D Sketch (b) 2D sketch and 3D template beforealignment(c) After alignment, side view (d) After alignment, front viewFigure 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 nosetip. The alignment34(a) 2D sketch with 3D cat template beforealignment(b) After alignment, side view(c) After alignment, top left view (d) After alignment, top right viewFigure 5.2: Cat example - The model has 14,410 triangles and 7,207 vertices, andis aligned 0.7 second with 5 correspondences. 2 on head, 1 on neck, 1 on back and1 on rear35(a) 2D sketch with 3D horse head templatebefore alignment(b) After alignment, side view(c) After alignment, front viewFigure 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 tip36(a) Side view (b) left side and front view(c) Top view (d) Front viewFigure 5.4: Simple deformation test with a bar - 4 correspondences for alignmentat 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 leftend of the bar (please refer to (a)), so use 5 correspondences to deform the model.We pick alpha = 0.2 and beta = 1.0. Please note that we highlight the anchor facets withred color.37(a) 4 correspondences, 2 on ears and 2 onnose. 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 viewFigure 5.5: Cat head deformation test with 4 correspondences after alignment.alpha = 0.2 and beta = 1.038(a) 2D sketch (b) After alignment, use new correspon-dences to deform the model so that theshape match the sketch as closely as pos-sible(c) Final resultFigure 5.6: Cat head alignment and deformation example39Chapter 6Conclusions and Future WorkThe construction of 3D models from sketches is far from trivial. A reliable andcapable system needs to interpret user drawings correctly and be able to generatea visually pleasing shape. Currently, our system uses simple sketches, such as theprofile of a virtual 3D model; but we aim in the future to be able to use feature linesas 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 oursystem. It significantly affects the final result. However, in the alignment process,using penalty method with Newton iteration to solve a minimization problem withequality constraints is not guaranteed to give a meaningful result unless the initialguess is good. Our current system is problematic in this respect.Deforming the 3D geometry to obtain a desired shape poses challenge withrespect to the efficiency and quality of the results. From our experiments, it showsthat the processing time significantly increases when the number of vertices getslarge. The system does not work well with large deformations. Therefore, we needto improve from these two aspects. One way to mitigate the influence of largedeformations is that we could use the concepts of the region of interests or the meshmaterial as proposed in [22], such that the deformation would not be propagatedthrough out the entire mesh.40Deformation and vertex repositioning can potentially introduce bad shapedtriangles in the resulting mesh. Therefore, after deformation step, we may need toremesh the new model. Any easy to use and robust method of remeshing wouldlikely be suitable.41Bibliography[1] M. Alexa. 2001. Local Control for Mesh Morphing. In Proceedings of ShapeModeling 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 oftwo 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-DShapes. 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 unitquaternions. 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 SketchingInterface 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 possibleshape manipulation In SIGGRAPH ?05: ACM Trans. Graph., ACM Press, pp1134-1141, 2005.[13] O. A. Karpenko, and J. F. Hughes 2006. SmoothSketch: 3D free-formshapes from complex sketches. In SIGGRAPH ?06: ACM Trans. Graph., vol25, , 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., pp147-154, ACM Press, NY. 2005.[15] J. J. LaViola Jr., R. Davis, and T. Igarashi 2006. SIGGRAPH?06 Courseon: An Introduction to Sketch-Based Interfaces.[16] H. Lensch, W. Heidrich, and H.-P. Seidel 2001. A Silhouette-basedAlgorithm for Texture Registration and Stitching. In Graphical Models, July2001, pp. 245-262[17] X. Li and I. Guskov and J. Barhak 2006. Robust Alignment of Multi-viewRange Data to CAD Model. In SMI ?06: Proceedings of the IEEE InternationalConference 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. InProceedings of Shape Modeling International, pages 181C190. IEEE ComputerSociety 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: ACMTrans. on Computer graphics, vol. 24, no. 3, pp 1142-1147, 2005.[21] J. Nocedal and S. Wright 1999. Numerical Optimization. Springer Verlag,199943[22] T. Popa, D. Julius, and A. Sheffer 2006. Material Aware Mesh De-formations. In SMI ?06: Proceedings of the IEEE International Conferenceon 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. InThird International Conference on 3D Digital Imaging and Modeling(3DIM).,2001[24] D. Mumford. 1994. Elastica and computer vision. In Algebraic Geometryand Its Applications., C. L. Bajaj, Ed. Springer-Verlag New York Inc. 1994[25] A. Sheffer and V. Kraevoy. 2004. Pyramid coordinates for morphingand 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 ofthe 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 trianglemeshes. 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. PhDthesis, University of Massachusetts.[32] L. R. Williams 1997. Topological reconstruction of a smooth manifold-solidfrom 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 Modelingof Parameterized Objects. In 2nd Eurographics Workshop on Sketch-BasedInterfaces and Modeling, Dublin, August 28-29, 2005.44[34] Y. Yu, K. Zhou, D. Xu, X. Shi, H. Bao, B. Guo, H. Shum. 2004. MeshEditing 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. InSIGGRAPH ?05: ACM Trans. Graph., ACM Press, pp496-503, 2005.45

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Country Views Downloads
United States 107 6
China 17 12
France 11 0
India 1 1
Japan 1 0
City Views Downloads
Unknown 97 2
Shenzhen 11 12
Ashburn 7 0
Beijing 6 0
Los Angeles 3 0
Paris 3 0
Roubaix 2 0
University Park 2 0
Washington 2 0
Bilaspur 1 1
Dallas 1 0
Seattle 1 0
Tokyo 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

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>
                        
                    
IIIF logo 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

Comment

Related Items