Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Burla, Silver Luciano
Master of Science - MSc
University of British Columbia
Concept sketches are common in the early stages of production design, as they require little time to produce and are effective at communicating both shape and volume information via carefully placed strokes. However, they are limited in their ability to convey material properties, and they do not help to envision a fully shaded product. Affording artists and designers the ability for fast sketching of shapes with rich visual shading can save a significant amount of time during the design refinement process, where shading is often done manually across multiple variations of lighting and material properties per iteration of ideas. To meet this need, CrossShade is an existing tool designed by Shao et al. for automatically shading line drawings. By leveraging specialized curves, in particular cross-section curves and the intersections between them, surface information of the curve-described geometry can be solved for via optimization of cross-section curve plane normals. Cross-section curves enforce a set of geometric constraints that aid viewers in lifting and interpreting concept sketches into 3D space, and so readily supplement regularity cues and perceptual constraints in a 3D reconstruction framework. We adopt the same regularity cues employed by CrossShade to estimate normals along cross-section curves in a new optimization routine, individually target curve networks constituting the whole of a line drawing sketch, and include a simple solution selection heuristic yielding more efficient, and robust results than previously reported. Accompanying our work is an updated sketch interface to make the drawing process more enjoyable for artists and designers.
Improved Normal Estimation from Cross-Section DrawingsbySilver Luciano BurlaB.F.A., The University of British Columbia, 2018A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)The University of British Columbia(Vancouver)December 2020© Silver Luciano Burla, 2020The following individuals certify that they have read, and recommend to the Faculty of Graduateand Postdoctoral Studies for acceptance, the thesis entitled:Improved Normal Estimation from Cross-Section Drawingssubmitted by Silver Luciano Burla in partial fulfillment of the requirements for the degree ofMaster of Science in Computer Science.Examining Committee:Alla Sheffer, Professor, Computer Science, UBCSupervisorMichiel van de Panne, Professor, Computer Science, UBCSupervisory Committee MemberiiAbstractConcept sketches are common in the early stages of production design, as they require little time toproduce and are effective at communicating both shape and volume information via carefully placedstrokes. However, they are limited in their ability to convey material properties, and they do not helpto envision a fully shaded product. Affording artists and designers the ability for fast sketching ofshapes with rich visual shading can save a significant amount of time during the design refinementprocess, where shading is often done manually across multiple variations of lighting and materialproperties per iteration of ideas. To meet this need, CrossShade [55] is an existing tool designed byShao et al. for automatically shading line drawings. By leveraging specialized curves, in particularcross-section curves and the intersections between them, surface information of the curve-describedgeometry can be solved for via optimization of cross-section curve plane normals. Cross-sectioncurves enforce a set of geometric constraints that aid viewers in lifting and interpreting conceptsketches into 3D space, and so readily supplement regularity cues and perceptual constraints ina 3D reconstruction framework. We adopt the same regularity cues employed by CrossShade toestimate normals along cross-section curves in a new optimization routine, individually target curvenetworks constituting the whole of a line drawing sketch, and include a simple solution selectionheuristic yielding more efficient, and robust results than previously reported. Accompanying ourwork is an updated sketch interface to make the drawing process more enjoyable for artists anddesigners.iiiLay SummaryThe production design tool CrossShade [55] can quickly shade design sketches constructed fromspecialized curves. This permits production designers and artists to ideate and envision fully shadedproducts quickly with little time spent on manual drawing labor. We leverage a similar approachto that of CrossShade in a new curve network processing and optimization routine, yielding moreefficient and robust results.ivPrefaceThis thesis is original, unpublished, work by the author S. Burla, and builds on the original CrossShadeimplementation by C. Shao.vContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vContents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Objective and Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Survey of Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Image Binarization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Sketch Vectorization & Consolidation . . . . . . . . . . . . . . . . . . . . . . . . 62.2.1 Thinning Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.2 Non-Thinning Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.3 Junction Detection and Disambiguation . . . . . . . . . . . . . . . . . . . 72.2.4 Sketch Simplification and Stroke Consolidation . . . . . . . . . . . . . . . 82.3 Sketch Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3.1 Silhouette and Contour-Based Methods . . . . . . . . . . . . . . . . . . . 102.3.2 Extrusion-Based Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3.3 Constraint-Based Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3.4 Data Driven and Learning-Based Methods . . . . . . . . . . . . . . . . . . 162.4 Interactive Sketch Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.4.1 Dedicated-Sketch Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . 20vi3 Perceptual Properties of Cross-Sections at Cross-Hairs . . . . . . . . . . . . . . . . 243.1 Intersecting Cross-Sections as Orthogonal Planes . . . . . . . . . . . . . . . . . . 243.2 Intersecting Cross-Sections as Lines of Principle Curvature . . . . . . . . . . . . . 253.3 Intersecting Cross-Sections as Surface Geodesics . . . . . . . . . . . . . . . . . . 253.4 Cross-Hairs and Minimal Foreshortening . . . . . . . . . . . . . . . . . . . . . . 273.5 Cross-Hair Orientations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Normal Estimation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.1 Curve-Network Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.2 Local Analytic Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.3 Energy Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.3.1 Geodesic Energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.3.2 Foreshortening Energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.4 Constraint Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.4.1 Plane Orthogonality Constraint . . . . . . . . . . . . . . . . . . . . . . . 334.4.2 Tangent Orthogonality Constraint . . . . . . . . . . . . . . . . . . . . . . 334.4.3 Plane Offset Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 Optimization Routine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.2 Numerical Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.3 Cross-Patch Solve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.4 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.4.1 Single Guess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.4.2 Quad Guess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416.1 Comparison to Prior Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416.1.1 Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426.1.2 Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436.1.3 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547.1 Sketching Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547.2 Curve-Network Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557.2.1 Primary Graph Representation . . . . . . . . . . . . . . . . . . . . . . . . 557.2.2 Secondary Graph Representation . . . . . . . . . . . . . . . . . . . . . . . 568 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57viiBibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59viiiList of TablesTable 6.1 The number of cross-section curves, cross-hairs, and cross-patches for each inputare listed above. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Table 6.2 Our method consistently outperforms CrossShade [55] with respect to optimiza-tion speed. Optimization runtimes are measured to 5 significant figures, andcalculated speed-up factors are reported to 5 significant figures as well. . . . . . 44ixList of FiguresFigure 1.1 Concept sketches depict objects using sparse sets of construction lines, of whichcross-section curves and the interconnected networks they form with each otherstrongly suggest 3D surface variations. Cross-section curves (highlighted or-ange, right) are a special class of construction lines, the intersections betweenthem are called cross-hairs (highlighted blue, right). ©[20] . . . . . . . . . . . 2Figure 1.2 Overview of our normal estimation pipeline under the quad guessing initial-ization strategy. Users first create their desired concept sketch using annotatedvector curves in our dedicated interface. Then, connected components of cross-section curves are extracted (highlighted red) and cross-hairs with the great-est graph geodesic distance are selected for each extracted connected compo-nent (highlighted red). Four optimization initializations are created for eachextracted connected component using combinations of normal orientations atthe two selected cross-hairs. Each initialization is solved, the best solution isselected, and estimated normals are interpolated for the selected solution acrosscross-section curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Figure 2.1 Example input (left) and output (right) pair from the binarization method pro-posed by Almeida et al. ©[4] . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Figure 2.2 Example input with highlighted junction points (left) and final output (right)from the thinning vectorization method proposed by Hilaire and Tombre ©[25] 6Figure 2.3 Example input (left) and final output (right) with vector output in black and orig-inal non-processed raster in gray from the non-thinning vectorization methodproposed by Song et al. ©[59] . . . . . . . . . . . . . . . . . . . . . . . . . . 7Figure 2.4 Example input and output pairs for the vectorization and junction detectionmethods of Noris et al. [45] (left), Favreau et al. [23] (middle), and Bessmeltsevet al. [9] (right). ©[9] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Figure 2.5 Example input (left), stroke clustering (middle), and final output (right) of thestroke consolidation method proposed by Liu et al. [39]. ©[39] . . . . . . . . . 10Figure 2.6 Example of a silhouette (middle) and contours (right) from the same referenceimage (left). ©[2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11xFigure 2.7 Example of contour inflation from the contour-based method proposed by Igarashiet al. [28], with input contour (left), inflated 3D output (middle), and a rotatedview of the output (right). ©[28] . . . . . . . . . . . . . . . . . . . . . . . . . 11Figure 2.8 Example input and output pairs without a provided silhouette (left) and with aprovided silhouette (right) from the extrusion-based method presented by Andreand Saito [5]. ©[5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12Figure 2.9 Optimization overview of the selective regularity constraints used in the constraint-based method proposed by Xu et al. [66]: (a) initial input, (b - e) resultantintermediate reconstructions as each regularity cue is applied. ©[66] . . . . . . 13Figure 2.10 Modelling pipeline for the constraint-based method proposed by Li et al. [37].From left to right: (a) input strokes coloured by convexity (red/blue for convex/-concave), (b) triangulated planar mesh, (c) direction field modelling curvaturedirections, (d) solved 2D curvature field with curvature and magnitudes usingthe same convexity color labellings from prior steps, (e) final output. ©[37] . . 15Figure 2.11 Example input (left) and rotated output (right) from the constraint-based sketchmodelling method presented by Gryaditskaya et al. [24]. ©[24] . . . . . . . . . 16Figure 2.12 Example input (left) and outputs (right) from the data driven sketch modellingmethod presented by Huang et al. [26]. ©[26] . . . . . . . . . . . . . . . . . . 17Figure 2.13 Three example input (left) and output (right) pairs demonstrating different re-sults from similar sketches using the data driven sketch modelling method pre-sented by Li et al. [38]. ©[38] . . . . . . . . . . . . . . . . . . . . . . . . . . 19Figure 2.14 The Teddy [28] interface on a display-integrated tablet. ©[28] . . . . . . . . . . 21Figure 2.15 The SymbiosisSketch [6] tablet interface (left) and HoloLens output feed (right).©[3] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Figure 2.16 An overview of the Nested Explorative Maps [46] tool: (a) a user first drawsfootprints onto the ground plane canvas, (b) a new 3D canvas is constructed, (c)visual details and maps can be drawn onto the new 3D canvas, (d-e) the canvasmay be deformed by dragging it onto a different footprint. ©[46] . . . . . . . . 23Figure 3.1 Cross-section curves are interpreted as planar and orthogonal to each otherat cross-hairs. Shown above, cross-section curve i (orange) and cross-sectioncurve j (red). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25Figure 3.2 Cross-section curves are interpreted as lines of principle curvature at cross-hairs. Shown above, cross-section curve i (orange) and cross-section curve j(red). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26Figure 3.3 Cross-section curves are interpreted as geodesics at cross-hairs. Shown above,cross-section curve i (orange) and cross-section curve j (red). . . . . . . . . . 27Figure 3.4 Cross-hairs are minimally foreshortened. . . . . . . . . . . . . . . . . . . . . 28xiFigure 3.5 There are two possible interpretations regarding surface normal orientation foreach cross-hair, where viewers have an inherent preference for convex surfacesviewed from above (b) as opposed to concave surfaces (a), and (bottom) orien-tations at cross-hairs connected to silhouette curves (orange) are readily disam-biguated. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Figure 4.1 Two layers of the cooker 1 input showing curve annotation colors used in ourdedicated sketching interface: orange curves denote cross-section curves, bluecurves denote smooth silhouette curves, and green curves denote boundary curves. 30Figure 5.1 We automatically detect curve-network patches across a given layer, providingusers with the option to see them visualized on-screen as they draw per layer,or across all layers simultaneously. In the example shown above, individuallayers of the sewing input are shown alongside a view of curve-network patchesvisualized across all input layers simultaneously (curve network patches shownin colored highlights). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Figure 5.2 Cross-patches are computed from the connected components of cross-sectioncurve and cross-hair filtered curve-network patches, (a) in the example abovewe can see that there is a single curve-network patch, (b) but four cross-patches(colored highlights). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Figure 5.3 It is always the case that when the quad guessing strategy is used, two pairs oforientation-flipped solutions are produced (horizontal pairs, above). . . . . . . 40Figure 6.1 Comparison input-output pairs for each layer of the ashtray and bending planeinputs, optimized with CrossShade [55] and our method. We find more accu-rately foreshortened solutions in the case of bending plane, most notably alongthe vertical stroke segments. . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Figure 6.2 Comparison input-output pairs for each layer of the cooker1 and cooker2 inputs,optimized with CrossShade [55] and our method. We consistently produce re-sults as good as the prior method. . . . . . . . . . . . . . . . . . . . . . . . . 47Figure 6.3 Comparison input-output pairs for each layer of the ellipsoid, stapler, and mouseinputs, optimized with CrossShade [55] and our method. We find more accu-rately foreshortened solutions in the case of ellipsoid, most notably along thevertical curved stroke segments. We find better oriented normal estimations inthe case of stapler, however normal estimations are over-foreshortened alonghorizontal stroke segments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Figure 6.4 Comparison input-output pairs for each layer of the sewing input, optimizedwith CrossShade [55] and our method. We find better oriented normal esti-mations, visible in L0, L3, and L4 where we can see properly aligned outwardfacing normals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49xiiFigure 6.5 Comparison input-output pairs for each layer of the sportbag input, optimizedwith CrossShade [55] and our method. We find better oriented normal estima-tions, visible in L1 where we can see properly aligned inward facing normals,as well as the omission of hanging ends of cross curves overdrawn beyond in-tersections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50Figure 6.6 Comparison input-output pairs for each layer of the camera input, optimizedwith CrossShade [55] and our method. We consistently find optimal solutionsfor cross-patches where the prior method fails or selects sub-optimal solutions,visible in L1 across the front facing body. We also find better aligned orienta-tions of normal orientations, seen in L4. . . . . . . . . . . . . . . . . . . . . . 51Figure 6.7 Comparison input-output pairs for layers 0 to 3 of the robot input, optimizedwith CrossShade [55] and our method. We consistently find optimal solutionsfor cross-patches where the prior method fails or selects sub-optimal solutions,visible in L0 on the legs and left arm, L2 on both arms and the left side of thehead, and L3 on the right eye. . . . . . . . . . . . . . . . . . . . . . . . . . . 52Figure 6.8 Comparison input-output pairs for layers 4 and 5 the robot input, optimizedwith CrossShade [55] and our method. We consistently find optimal solutionsfor cross-patches where the prior method fails or selects sub-optimal solutions,visible in L4 on the right hand. . . . . . . . . . . . . . . . . . . . . . . . . . . 53Figure 7.1 The updated sketching interface includes an inspection tool alongside basicsketching operations and visualizations. . . . . . . . . . . . . . . . . . . . . . 55xiiiAcknowledgmentsI would like to first thank my supervisor Alla Sheffer, for her professional mentorship and guidance.My sincerest gratitude to Tamara Munzner and Michiel van de Panne for their encouragement,support, and direction during difficult times. A heartfelt thank you to my labmates for welcomingme and making my time in the program truly special - the laughs we shared helped sustain me upto the very end. A special thank you to Derek White who always made an effort to adapt my workschedule to school and lab constraints. Finally, to my mom and sister for their unconditional loveand support.xivChapter 1Introduction1.1 MotivationConcept sketches provide a means for artists and production designers to iterate quickly and ef-ficiently over different design ideas. They are typically inexpensive to produce and discard, yetconvey sufficient spatial geometric information to allow viewers to lift depicted objects into 3Dspace. As such, concept sketches are an important mode of communication during the early phasesof design when low-cost ideation and testing is necessary. However, they typically omit richer visualdetails like shading and material properties, and so require a significant effort on the viewers part toenvision the next step of the design. These shaded concept sketches, referred to as production draw-ings, require substantially more time and skill to produce manually, and are often redrawn acrossdifferent materials and lighting conditions during the ideation process. Designers then, require afast and efficient way to produce production drawings in order to streamline the early stages of thedesign process.A typical concept sketch will employ a sparse set of varying kinds of strokes, strategically posi-tioned in such a manner as to communicate maximal 3D geometric information about the drawnobject. Of these strokes, construction lines act as intermediary sketching artefacts used to guide andstructure the sketching process in three-dimensional space [20] (see Figure 1.2), and are often omit-ted in final production drawings. Cross-section curves are a special class of construction lines thatconvey a great deal of 3-dimensional geometric information through viewer perceptual constraintsat cross-hairs: their points of intersection with each other [20]. Shao et al. exploit the predomi-nance of cross-section curves in concept sketches in their sketch-based modeling tool CrossShade[55], which creates production drawings from concept sketches interpreted as networks of intercon-nected curves. They posit five properties of cross-section curves and concept sketches that relate2-dimensional curve-networks to the 3D geometry they convey:11. Cross-hairs are typically induced by two incident cross-section curves which lie in orthogonalplanes to each other [41, 61].2. Intersecting cross-section curves suggest lines of principal curvatures [41, 61].3. Intersecting cross-section curves are perceived as geodesics [35].4. Cross-section curve tangents at cross-hairs are minimally foreshortened to maximize surfacevisibilities [21].5. Orientations at cross-hairs are inherently ambiguous.They leverage these properties of planar cross-section curves at their cross-hairs in a constrainedoptimization routine that estimates cross-section curve plane normals, which are propagated acrossinferred curve-network surfaces in order to create production drawings. In a similar fashion, view-ers interpret concept sketches as interconnected networks of curves as well, and consolidate theproperties of cross-section curves locally at their cross-hairs allowing them to lift two-dimensionalconcept sketches into 3D by seeking the most likely global interpretation.Figure 1.1: Concept sketches depict objects using sparse sets of construction lines, of whichcross-section curves and the interconnected networks they form with each other stronglysuggest 3D surface variations. Cross-section curves (highlighted orange, right) are aspecial class of construction lines, the intersections between them are called cross-hairs(highlighted blue, right). ©[20]1.2 Objective and OutlineOur goal is to improve on and extend the prior sketch-based modelling algorithm from CrossShade[55]. We improve on the prior reconstruction framework by combining the same properties of planarcross-section curves at cross-hairs (see Chapter 3) into an updated constrained minimization, andsolve it using a new optimization routine that uses an updated non-linear optimization library NLopt[31], as well as a new cross-section curve patch targeting optimization subroutine, surface-aware2initialization, and post-processing solution selection strategy. Using our updated reconstructionframework, normal estimations are more efficient, robuster, and higher-quality (see Chapter 6). Wecomplement our work with an updated sketching interface using the Qt framework version 5.14 [43],define curve-network data structures using the Boost Graph Library version 1.74.0 [29], and struc-ture our new codebase with modularity in mind to make the process of incorporating new features,extensions, and code alterations as straightforward and simple as possible for future contributors.(user input)(cross-section curve patch)(quad initialization) (individual optimizations)(solution selection)(maximal graph geodesic)Figure 1.2: Overview of our normal estimation pipeline under the quad guessing initializationstrategy. Users first create their desired concept sketch using annotated vector curvesin our dedicated interface. Then, connected components of cross-section curves are ex-tracted (highlighted red) and cross-hairs with the greatest graph geodesic distance areselected for each extracted connected component (highlighted red). Four optimizationinitializations are created for each extracted connected component using combinationsof normal orientations at the two selected cross-hairs. Each initialization is solved, thebest solution is selected, and estimated normals are interpolated for the selected solutionacross cross-section curves.The thesis therein begins with a detailed survey of related works outlining the progress of tech-niques and sketch-based modelling algorithms over the past two decades in Chapter 2. Followingthis, Chapter 3 outlines and describes the mathematical formulations of the perceptual properties ofcross-section curves, which are subsequently used in our normal estimation algorithm described inChapter 4. Chapter 5 describes our optimization routine, including a brief description of the non-linear optimization library used, our cross-section curve patch targeting subroutine, optimizationinitialization, and solution post-processing strategy. Our results are then presented in Chapter 6 as a3comparison to the prior work of Shao et al. [55]. Afterwards the technical implementation goals anddetails of our codebase are described in Chapter 7. Lastly, our conclusion, limitations, and futurework are presented in Chapter 8.In brief, our technical contributions are summarized as follows;• Improved efficiency of normal estimations from using the NLopt library in our optimizationroutine (see Section 6.1.3).• More robust and accurate normal estimations from individually optimizing patches of con-nected cross-section curves (see Section 6.1.2).• Improved quality of normal estimations by employing a surface-aware optimization initial-ization and post-processing solution selection strategy (see Section 6.1.1).• General implementation efforts including an updated sketching interface, adaptable data struc-tures using the Boost Graph Library, and a modular codebase for ease of extension (see Chap-ter 7).4Chapter 2Survey of Related WorksSketch-based modelling is a fast growing area of multi-disciplinary research, with diverse ap-proaches and strategies rooted in computer vision, digital geometry processing, and machine learn-ing [11, 16, 34].2.1 Image BinarizationPrior to any subsequent digital computations like vectorization, shading, or modelling, sketchesrequire foreground/background separation when drawn on and scanned from paper. Well knownimage binarization algorithms like Chow and Kaneko’s [14] use grayscale information from neigh-boring pixels to threshold locally, while Otsu’s algorithm [47] uses a single threshold value for aglobal image binarization. These methods are suitable for clean scans of sketches, however vari-ability in lighting, paper, and pencil graphite or pen ink can lead to artefacts. To address theselimitations, advances in binarization algorithms targeted for historic documents have led to alter-nate, more robust and effective methods (see Figure 2.1) [4].Figure 2.1: Example input (left) and output (right) pair from the binarization method proposedby Almeida et al. ©[4]52.2 Sketch Vectorization & ConsolidationOnce a sketch is digitized, drawn strokes may be represented in either raster or vector formats.Typically, vector representations of drawn strokes provide more information and flexibility for sub-sequent computations, in addition to providing artists with more editing capabilities.2.2.1 Thinning MethodsThinning, or skeletonization methods are one such approach to transforming sketched raster strokesto vector format, by extracting only those pixels which contribute to the topological skeleton of theentire stroke [10]. The (3,4)-chamfer distance thinning method proposed by G. Baja [7] is widelyused as it is independent of width and robust to noise, where curves of the same nature but varyingwidths will yield very similar skeletons, the computation of the distance transform allows for theestimation of the thickness of extracted shapes. Hilaire and Tombre [25] use the thinning methodproposed by G. Baja to skeletonize separated layers from input binary images prior to fuzzy seg-mentation of each skeleton into line segments and subsequent simplification. The main advantageof thinning based methods lies in their ability to maintain line connectivities. However as a conse-quence they generally suffer from extraneous line segments and so rely heavily on beautification. Incontrast, the main disadvantage of thinning methods is in their inability to faithfully vectorize thepoints at which curves cross or meet with each other, also called junctions (see Figure 2.2).Figure 2.2: Example input with highlighted junction points (left) and final output (right) fromthe thinning vectorization method proposed by Hilaire and Tombre ©[25]2.2.2 Non-Thinning MethodsAmong non-thinning based methods, Ramel et al. [50] avoid some of the problems of thinning meth-ods by representing drawings as vectors and quadrilateral primitives, prior to calculating medial-axes via contour pair matching and their refinements through a number of experts (i.e. “curve” ex-perts). Dori et al. [19] propose an extension of the sparse pixel Orthogonal Zig-Zag (OZZ) method6[18], the Sparse Pixel Vectorization (SPV) algorithm which sparsely visits medial axis points alongconsecutive horizontal or vertical pixel runs, rather than all medial axis points. The resulting crudepolyline is then refined via polygonal approximation by removing redundant points to extract lineand circular arc segments. Song et al. [60] propose the Object-Oriented Progressive-Simplification-based Vectorization (OOPSV) model that identifies graphic objects at the pixel level through naturalcharacteristic object features used by human perception, like direction and thickness. Given that theOOPSV model is designed for engineering drawings, graphics objects are expected to be encodedwithin a hierarchy of lines, symbols, and texts, further including bars, arcs, and curves as a sub-set of lines. Graphics objects are identified from the simplest and most easily detectable (bars) tomost complex (text), and the raster images are then progressively simplified by erasing recognizedgraphic objects to eliminate interference with subsequent recognitions (see Figure 2.3). Identifiedgraphics line objects are vectorized using a variant of the Global Line Vectorization (GLV) algo-rithm from the Line Network Oriented Vectorization (LNOV) method described by Song et al. [59],where rectangular segments are propagated for lines and three rectangular segments are propagatedfor circular arcs. Identified symbol graphics objects are vectorized using template-based domain-specific recognition, and text graphics objects are extracted as text boxes for input into externalomnifont open-vocabulary Optical Character Recognition (OCR) systems for vectorization.Figure 2.3: Example input (left) and final output (right) with vector output in black and orig-inal non-processed raster in gray from the non-thinning vectorization method proposedby Song et al. ©[59]2.2.3 Junction Detection and DisambiguationThe majority of vectorization approaches listed so far target technical documents and so rely heavilyon regular straight line segments and circular arcs, which largely limits their use for sketches whichtypically contain a broad variety of complex curves. These complex curves make it difficult to accu-rately identify junctions which are important elements in determining both curve connectivities andsubsequent topologies of line drawings. In Document Image Analysis (DIA) the junction detectionproblem has mostly been considered a post-processing step of vectorization [18, 25, 60]. Junctions7play crucial roles as both perceptual and occlusion cues in the sketch interpretation problem as wellas in the disambiguation of curve depths [32, 52]. For this reason, there is a broad scope of vector-ization work that targets the detection, preservation, and disambiguation of these junction points.Noris et al. [45] extract sketch topologies using a gradient-based pixel clustering technique, whichare then subsequently leveraged during centerline extraction in their reverse drawing procedure.They generate all possible drawing states prior to identification of a junction and select the mostlikely configuration of strokes. Pham et al. [49] first extract the skeleton using the (3,4)-chamferdistance method described by G. Baja [7] prior to detection of candidate junction points in areasof high curvature using a variation of the method proposed by Teh et al. [63]. Distorted zonesare then defined at each candidate junction point as inscribing circles with diameters of local linethicknesses, where multiple intersecting distorted zones form a connected component distorted zone(CCDZ) inside of which skeleton line segments are discarded, and outside of which skeleton linesegments are tagged reliable. The skeleton topologies around these zones are then used to optimizefor the positions of junctions by finding the optimal meeting points of reliable line segments. Chenet al. [12] propose a line drawing vectorization method based on junction point analysis. They firstdetect line junction encounters through a combination of central line tracking and contour tracking.Following that, luminance polar mapping is used to compute the center positions of junctions as wellas their branch numbers, prior to calculating the smoothness between junction branches in order toproduce topologically consistent structures. Favreau et al. [23] propose a method to disambiguatejunctions by casting line drawing vectorization as a global optimization problem balancing outputsimplicity with sketch fidelity. They first extract the skeleton of a rough input sketch by employ-ing a region-based skeletonization method for closed curves, as this method is robust against roughclusters of correlated strokes, followed by morphological thinning for open curves. The extractedskeleton is over-segmented into Be´zier curves as an initial solution and represented as a hypergraph.The complexity of the initial solution is reduced by merging curves according to simplicity and fi-delity, in addition to curve and tangential continuity constraints, in order to locate junctions. Whileeffective for sketches with overdrawn strokes, their method may produce oversimplified results foralready cleaned sketches. Bessmeltsev et al. [9] employ frame fields [65] to disambiguate junctions.They begin by finding a smooth frame field in the image plane aligned with nearby contours of aline drawing, then extract the topology by tracing curves over the resulting frame field, groupingthese curves into strokes, and finally aligning the frame field with the extracted topology in theirvectorization. Their method is shown to produce more topologically accurate results than priorapproaches (see Figure 2.4).2.2.4 Sketch Simplification and Stroke ConsolidationVectorization methods typically, and explicitly, require clean line drawings as inputs, free fromrough sketching techniques employed by artists and designers. However, with the ubiquity of pen-8Figure 2.4: Example input and output pairs for the vectorization and junction detection meth-ods of Noris et al. [45] (left), Favreau et al. [23] (middle), and Bessmeltsev et al. [9](right). ©[9]sensitive digital drawing tablets, artists can create sketches in any number of commercially availableprograms that readily store strokes in vector format. This allows artists to directly draw in vectorformats while also making full use of rough overdrawing techniques to convey a number of visualcommunicative effects. Overdrawing is the use of numerous strokes in aggregate to communicate asingle consolidated stroke or emphasize a specific stroke. Overdrawn strokes also act as guidelinesfor the motion of the artists hand in subsequent strokes, and they assist in breaking up the motion ofa long smooth stroke into multiple easier to draw strokes. This important technique has spurred anumber of researchers to investigate efficient methods of consolidating overdrawn curves into theirintended depictions.Barla et al. [8] split their stroke consolidation method into two stages; an initial clustering stagewhich uses a greedy algorithm to iteratively group strokes, followed by a geometric stage whichcreates a single stroke per cluster, based on the intended target application of density reduction,level-of-detail representation, or progressive editing. During the clustering stage, ε-lines, lines thatdo not self-intersect within an offset of ε along their normals, are grouped into ε-groups if theyare within ε of each other at either, or both extremities, and do not form a fork. Both a spatialerror and an optional attribute error for ε-groups guide the greedy iterative clustering algorithm,where the spatial error is defined relative to the hull of the representative ε-line for that group.Noris et al. [44] present an interactive system that takes as input a rough digitally drawn sketchcomposed of piecewise linear strokes, along with colored scribbles input by users that convey theirsketch segmentation intent. The problem of sketch segmentation is then cast as a graph multi-waycut optimization. The smoothing term encodes the energy of assigning different scribble labels toneighboring stroke segments based on spatial and temporal similarities, while the data term thenencodes the energy of a given stroke labeling as a function of its spatial similarities with all scribblesegments associated with that label. Simo-Serra et al. [57] present a deep learning model consistingof a fully convolutional neural network (CNN) that operates directly on raster images for sketch sim-9plification, which uses only convolutional layers based on sparse connections, and thus is agnosticto both image dimensions and aspect ratios. However, due to the nature of training on artist-drawndata, there are admitted issues in using these trained models on sketches drawn by different artistswho may employ different sketching strategies. Following this work, Simo-Serra et al. [58] fur-ther propose an adversarial machine learning framework for sketch simplification to address priorlimitations and allow for unsupervised learning. Liu et al. [39] present StrokeAggregator, a novelstroke consolidation method based on human perception research and artistic practices, in whichangular compatibility between strokes, their relative proximity to each other, and their local intra-cluster stroke spacing, are leveraged in a coarse-to-fine stroke clustering framework. Once clustersare identified, a variant of the moving least squares (MLS) fitting algorithm is used to find optimalinitial positions and tangents separately, then an aggregate polyline is subsequently computed andits edges are aligned with desired tangent directions (see Figure 2.5).Figure 2.5: Example input (left), stroke clustering (middle), and final output (right) of thestroke consolidation method proposed by Liu et al. [39]. ©[39]2.3 Sketch InterpretationWhether a sketch is obtained from vectorization of a raster sketch, a dedicated digital drawingprogram, or via artist tools like pen-sensitive tablets, intra- and inter-information cues expressed byartists’ strokes can be leveraged to interpret 3D information from the sketches they compose.2.3.1 Silhouette and Contour-Based MethodsSilhouette-based methods and contour-based methods are generally well related. We use the com-monly accepted definition that silhouettes represent the outlines of shapes, while contours includeall visible divisions of shapes (see Figure 2.6). Therefore, while not all contours are silhouettes,all silhouettes can be regarded as contours. Generally, both inflation and deformation techniquesare paired with silhouette and contour-based methods, where initial blob-like 3D shapes are inflated10from contour lines prior to subsequent deformations and other topological operations. Becauseof this, contour-based methods are well-suited for modeling natural shapes like the body parts ofhumans and animals [22]. Notably the most famous contour-based method, Igarashi et al. [28]present the interactive interface Teddy in which a number of techniques are employed to convert 2Dsketched strokes to 3D polygonal meshes. The first stroke drawn by users is a closed, or near-closed,loop that does not self-intersect. Then, a closed planar polygon is created from this initial loopedstroke, from which the spine of the polygon is computed using the chordal axis. Vertices along thespine are elevated proportional to their distance from the polygon and finally a polygonal mesh isconstructed by wrapping the spine and the polygon in such a way that their sections form ovals (seeFigure 2.7).Figure 2.6: Example of a silhouette (middle) and contours (right) from the same referenceimage (left). ©[2]Figure 2.7: Example of contour inflation from the contour-based method proposed by Igarashiet al. [28], with input contour (left), inflated 3D output (middle), and a rotated view ofthe output (right). ©[28]2.3.2 Extrusion-Based MethodsIn recent years extrusion-based methods are more commonly utilized as components or steps oflarger modeling pipelines. However, sketch modeling systems that do make extensive, or exclusiveuse of extrusion-based methods typically position themselves within modeling domains that expecthighly structured geometries which extrusion operations can faithfully reproduce [46].Igarashi et al. [28] employ extrusion in their Teddy interface once an initial polygonal mesh iscreated. Their extrusion algorithm is activated by drawing a closed loop base ring on the already11created polygonal mesh, followed by an extruding stroke. The base ring is defined as a closed 3Dpolyline on the surface of the polygonal mesh, with a normal calculated from its best fit plane, andfrom which a projection plane is calculated. The extruding stroke is projected onto this projectionplane perpendicular to the base ring, producing a 3D extruding stroke the base ring is swept along.Andre and Saito [5] propose a single fixed-view sketch based modelling method, borrowing thedrawing strategy of splitting complex models into simple geometric primitives from cartoonists. Aprimitive is defined by two construction lines, along with an optional silhouette, where both con-struction lines are planar and orthogonal to each other. Users specify true intersections from thefour possible intersections between a pair of construction lines. Tangents and normals at theseintersections form cubic corners [48], of which their reverse projection is known with respect toNecker’s inversion, and from which construction line plane orientations are computed such that andusers must select either the corner or reverse projection orientations. The geometry is obtained viasweeping the larger diameter construction line along the other, scaling according to the intersectionline in the corresponding plane when a silhouette is not provided, and along both the intersectionline and its perpendicular line in the corresponding plane when a silhouette is provided, such thatresulting silhouette matches user input silhouette and the second construction line intersects sweptlines (see Figure 2.8). While appropriate for simple geometric objects, their algorithm cannot handleholes or complex construction line profiles like forks.Figure 2.8: Example input and output pairs without a provided silhouette (left) and with aprovided silhouette (right) from the extrusion-based method presented by Andre andSaito [5]. ©[5]2.3.3 Constraint-Based MethodsMethods that employ various constrained optimization routines are generally referred to as constraint-based. Literature suggests that these methods typically employ highly correlated rule sets, derivedfrom perception literature and observational studies of artists and designers workflows. These rulesets then, are distilled into mathematical relationships that confer 3D information to 2D sketches,which are reformulated into modeling constraints and optimization energies. Constraint-based12methods are also employed as post-processing steps in larger machine learning pipelines, wheredisjoint solutions are fused together via a blend of standard minimization algorithms and perceptionrule sets.Xu et al. [66] propose a 3D reconstruction framework that takes as input vectorized line drawings ofdepicted shapes represented as curve-networks. In their work, they leverage a number of regularitycues that relate designer drawn lines to intended 3D curvatures and local symmetries of shapes, insimilar fashion to that of the method proposed by Shao et al. [55]: smooth crossings of curves arestrongly perceived as orthogonal, adjacent intersecting curves along a given curve are often locallyparallel, intersecting curves are typically perceived as geodesics and locally symmetrical, and pla-nar curves are often used as strong cues for other regularities. These regularity cues are combinedinto a constrained optimization that optimizes sketch fidelity subject to shape regularity, where theformer enforces both minimal 2D to 3D variation between sketch inputs and resultant 3D outputs,as well as their minimal foreshortening, while the latter combines the regularity cues discussed toretrieve global 3D shape information. The optimization is initialized by optimizing shape regularitysubject to the smooth-crossing orthogonality cue, which lifts the curve-network into a baseline re-construction. Subsequent regularity cues are applied selectively (see Figure 2.9), and the detectionof which regularities to apply is cast as a rounding problem that drives likelihoods of individualcues applicability to binary values. Each iteration of rounding optimizes the curve-network subjectto previously resolved applicable regularity cues as hard constraints, and unresolved regularity cuesas soft constraints weighted by their likelihood as a function of their constraint satisfaction. Thoseregularity cues which are sufficiently satisfied have weightings approaching one, and eventually areresolved as applicable, while those that are poorly satisfied have weightings approaching zero, andeventually are resolved as inapplicable. This process is repeated until all regularity cues are resolvedand sketch fidelity subsequently minimized.Figure 2.9: Optimization overview of the selective regularity constraints used in theconstraint-based method proposed by Xu et al. [66]: (a) initial input, (b - e) resultantintermediate reconstructions as each regularity cue is applied. ©[66]Li et al. [37] present BendSketch, a method for modeling freeform surfaces, represented as height-field surfaces, with controlled curvature variation patterns from sparse 2D strokes. Their methodtakes as input a sparse set of specialized 2D polyline strokes, which characterize curvatures, bound-13aries, sharp features, ridges, valleys, and flat segments on freeform surfaces. Their primary com-municators of surface curvatures are bending strokes, which identify the projection of principlecurvature lines on the sketched surface and represent either concave or convex surface segments.In order to disambiguate convexities denoted by bending strokes, they are first separated into sim-ple strokes which bend in only one direction in the 2D plane. A graph is constructed from thesesimple strokes, with edges connecting those simple strokes which are either sequential, or parallel,to each other. Then, a standard graph labelling problem correlating surface convexity properties oflocally proximate simple strokes is solved, with a preference for convex simple strokes, the same,or opposite, convexity properties for pairs of sequential simple strokes, and the same convexityproperties for parallel simple strokes. Following this, a planar mesh defined by boundary strokesis triangulated using the Delaunay refinement algorithm from the Computational Geometry Algo-rithms Library (CGAL), and a height field is generated and discretized over the mesh with variablesencoded by z-coordinates of the mesh vertices. A dense curvature field parameterized over thebounded 2D region is recovered using a formulation of the BendField energy described by Iarussiet al. [27], in conjunction with a curvature value diffusion energy, and under directional constraintsof the simple bending strokes. An initial guess of the height field surface z for their subsequentjoint optimization of the height field surface and curvature magnitudes is computed over the densecurvature field by minimizing, for one iteration, an energy summation solving for the height field.This energy is a summation over curvature tensor matching penalties across the surface, positionaland smoothness penalties induced by boundary strokes, normal vector matching penalties inducedby contour strokes and boundary triangles, normal vector parallelism matching penalties inducedby triangles along flat strokes, and height field gradient matching penalties on triangle pairs crossedby sharp feature strokes. The joint optimization process proceeds iteratively through three consecu-tive, repeating steps. First, principle curvatures are estimated by circle fitting to fitted strokes, thencurvature values are diffused across the surface by minimizing the curvature value diffusion energy,and finally one iteration of minimizing the height field energy summation to update the height fieldsurface z. An overview of the single-view BendSketch pipeline is shown in Figure 2.10. Li et al.include as well a multi-view modelling system that compliments their single-view system to modelcomplex 3D objects which cannot be sketched from a single view due to occlusions. In their multi-view modelling system, users create, position, and orient drawing planes as needed to sketch sur-face patches. Then, neighboring patches with established correspondence points are tightly mergedthrough a shape preserving deformation by minimizing the sum of a Laplacian surface deformationenergy and correspondence energy.In the ShapeMVD architecture proposed by Lun et al. [40], once depth, normal, and foregroundprobability maps are output from their multi-view decoder, both depth and normal maps are fusedtogether from each canonical view into a single dense point cloud via optimization. Their first stepmaps all foreground pixels to 3D points by considering only foreground pixels given by the previ-ously constructed binary masks, in combination with depths, image-space coordinates, and knownextrinsic camera parameters. This first step generates point sets per viewpoint, which subsequently14Figure 2.10: Modelling pipeline for the constraint-based method proposed by Li et al. [37].From left to right: (a) input strokes coloured by convexity (red/blue for convex/con-cave), (b) triangulated planar mesh, (c) direction field modelling curvature directions,(d) solved 2D curvature field with curvature and magnitudes using the same convexitycolor labellings from prior steps, (e) final output. ©[37]go through a variation of the iterative closest point (ICP) algorithm presented by Rusinkiewicz andLevoy [53] to rigidly align pairs of point sets and handle depth map inconsistencies. Following this,aligned point sets are fused by optimizing for the depths of pixels to handle any remaining depthinconsistencies not handled by the ICP algorithm. Pixel depths are optimized such that given aviewpoint and their 3D point they are close to the predicted depths, their first-order derivatives yieldsurface tangents orthogonal to predicted normals, and they are consistent with depths and normalsof corresponding 3D points generated in other viewpoints from corresponding pixels. The resultingenergy is quadratic and iteratively solved using a sparse linear system, where at each step 3D pointpositions are updated as pixel depths are estimated for. Finally, Kazhdan and Hoppe’s screenedPoisson Surface Reconstruction algorithm [33] is applied to convert the fused point cloud and nor-mals into a surface mesh, which may be subsequently refined further through matching input linedrawing contours and viewpoints to deformations in the mesh.Gryaditskaya et al. [24] present an algorithm that accurately lifts 2D industrial design sketchesinto 3D, by leveraging observations about designer drawing preferences in combination with scaf-folding lines, a commonly employed marking technique by industrial designers. Scaffolding linesare typically always drawn as straight supporting lines for subsequent curved, or straight, strokes,helping position the whole of a sketch in 3D space. Preliminary 2D analysis of raw input sketchesis a crucial step in their pipeline that classifies strokes into axis-aligned scaffolding lines, otherstraight lines, and general curves, and consolidates overdrawn strokes using a conservative versionof StrokeAggregator [39]. Once classified, scaffolding lines are lifted to 3D by considering all pos-sible binary intersection-occlusion labellings between them, in their drawing order. Labelling con-figurations inconsistent with axis-alignment, orthogonality, tangentiality, planarity, and intersectioncoverage regularity cues are discarded, candidate 3D scaffolding lines from remaining configura-tions are generated, and the ones that best satisfy prior cues are selected and propagated. Ambiguousintermediate assignments are delayed until dominant 3D interpretations emerge by considering con-current interpretations in parallel during this stage. Once scaffolding lines are lifted to 3D, a similar15approach is used to lift the remaining planar 3D curves by considering their intersections with thealready lifted scaffold, selecting ones that best satisfy orthogonality, tangentiality, foreshortening,and intersection coverage regularity cues (see Figure 2.11).Figure 2.11: Example input (left) and rotated output (right) from the constraint-based sketchmodelling method presented by Gryaditskaya et al. [24]. ©[24]2.3.4 Data Driven and Learning-Based MethodsMachine learning has successfully intersected the sketch-based modeling problem, with an increaseof new data driven and learning-based methods appearing over recent years. Approaches to sketch-based modeling typically employ feed-forward sub-networks that process inputs with respect todifferent divergent processing steps, the outputs of which are jointly fused later or combined intoan optimization problem. Shape retrieval [30] and multi-view synthesis [26, 38, 40] are commondata driven, learning-based methods. While these methods produce reasonably accurate viewer-expectation aligned outputs, they generally employ post-processing optimizations or smoothing asminimally varied, bumpy surface topologies are a common artefact from methods that aim to re-construct geometries from computed 3D surface information. One common characteristic of datadriven approaches is their utilization of synthetic data produced from non-photorealistic render-ing algorithms, which take as input ground-truth 3D models and render their contours, suggestivecontours, and silhouettes from varying viewpoints and under varying distortions. A substantial ad-vantage of data driven and learning-based methods is in their ability to process pure raster sketches,thus removing the need for input vectorization as a pre-processing step, allowing artists and design-ers more freedom to sketch in their desired digital or physical formats.Huang et al. [26] present a data driven approach based on procedural modeling (PM), in whichusers provide an approximate hand-drawn 2D sketch from which a set of PM parameters of a givenobject classification rule set are mapped, that in turn yield detailed output shape suggestions (seeFigure 2.12). In their approach, rule sets are derived from object classifications of trees, containers,and jewelry, with discrete parameters specifying classification sub-types, for example the genus of16the depicted tree, and continuous parameters specifying characteristics, for example trunk widths,height, and leaf size. The core of their method is a deep convolutional neural network with two-subnetworks of similar structure to that of AlexNet from by Krizhevsky et al. [36], a widely usedCNN architecture in computer vision for object recognition. The structure of AlexNet is such thatinitial convolutional layers feed feature maps into pooling layers for maximal feature sub-sampling,which are then non-linearly transformed through fully connected layers and finally concatenated asinput into either regression or classification layers. Of the two sub-networks, one predicts continu-ous PM parameters via a final regression layer, while the other predicts discrete PM parameters via afinal classification layer. Transfer learning is applied to both CNN sub-networks by first pre-trainingthem for generic object detection on the large, publicly available dataset ImageNet [54], then furtherrefining them on a synthetic dataset with pre-trained parameters. The synthetic dataset is generatedby first sampling the PM continuous parameter space for each combination of discrete PM parame-ter values, reconstructing the associated shapes from different viewpoints using these ground-truthPM parameters, removing redundant shapes via a nearest neighbors threshold on extracted featuresfrom their CNN, then through non-photorealistic rendering algorithms sketches are extracted foreach viewpoint. This dataset is further constricted by removing all but one sketched viewpoint forrotationally symmetric shapes, then subsequently expanded by decimating large portions of sym-metrical groups from shapes and performing mesh contractions through skeleton extractions, thusproducing multiple object and sketch data pairs. Given the PM parameters of a rule set, there aretwo distinct sets of trainable weights; first the weights for the sub-network used for regressing con-tinuous parameters, and second the weights for the sub-network used in classification, per eachdiscrete parameter value. The cost function used to train the first sub-network predicting continuousPM parameters regularizes large weights from pre-training, and penalizes deviation of referenceparameters from those predicted, while the classification sub-network uses logistic loss to penal-ize deviation of predicted probabilities from reference parameters in addition to regularizing largeweights from pre-training as well. The output from the proposed method is a number of outputshapes, from which the user selects their most preferred, or iterates on the input sketch to producemore outputs better aligned with their expectations. However, as the CNN was trained for PM pa-rameters targeting rule sets for trees, containers, and jewelry, the method does not generalize wellfor vastly different objects.Figure 2.12: Example input (left) and outputs (right) from the data driven sketch modellingmethod presented by Huang et al. [26]. ©[26]17Lun et al. [40] propose a multi-view architecture based on a feed-forward convolutional network,ShapeMVD, that takes as input any number of line drawings from different viewpoints, and out-puts multi-view depth and normal maps. These are then consolidated into a dense 3D point cloudby solving an optimization problem, which is subsequently converted into a polygonal mesh thatis optionally further optimized to better match the input line drawings. The core of ShapeMVD’sarchitecture follows a deep encoder-decoder network, where the encoder takes as input 256× 256intensity images representing line drawings, with a total dimensional input of 256×256×C when Cviewpoints are available. Viewpoints are constrained to any of the 12 equidistant vertices of a regularicosahedron, producing a total of 12! trained networks each representing a different configurationof non-repeating viewpoints. The decoder consists of 12 branches, each corresponding to one ofthe canonical viewpoints, and following the structure of U-Net [51] each of its convolutional layerstakes as input the concatenation of the previous layers output in the decoder with the correspondinglayers output in the encoder. 5-channel 256× 256 images consisting of a 1-channel depth map, 3-channel normal map, and 1-channel foreground probability map are output for each correspondingviewpoint. Both the depth and normal maps are masked for subsequent point cloud constructionusing a binary mask constructed from the foreground probability map, using only those pixels witha probability of more than 50%. To train the network, approximations of human line drawingsdepicting 3D shapes from the canonical viewpoints are automatically generated using well-knowndrawing principles, and combinations of non-photorealistic rendering algorithms. The networkstarget loss function consists of four terms penalizing: distance differences between training andpredicted depth maps, angle cosine differences between training and predicted normal maps, dif-ferences between ground-truth and predicted foreground masks using cross-entropy functions, andlarge-scale structural differences between predicted and training maps penalized through an adver-sarial network.Delanoy et al. [15] propose a data driven deep-learning approach to sketch-based modelling basedon voxel representation. A primary single-view CNN is complemented by a downstream updaterCNN that refines initial voxel grid occupancy predictions, given bitmap line drawings from newviewpoints, in addition to fusing new voxel information to existing predictions when supplied byusers. The input to the single-view CNN is a bitmap line drawing, while the updater CNN takes asinput both prior predictions and new bitmap line drawings. Both networks follow the U-Net encoder-decoder architecture described by Ronneberger et al. [51], where input drawings are processed byconvolution and rectified linear units to extract high-dimensional features at low resolutions, whichare then decoded through deconvolutions and rectified linear units to generate a multi-channel imagerepresentative of a voxel grid. The single-view CNN is first trained on rendered synthetic contourdrawings from hand-modeled shape collections as well as from procedurally generated abstractshapes, followed by training the updater CNN on predictions from different viewpoints. While ef-fective at reconstructing simple, low-detail shapes, due to limitations of voxel grids thin structuresas well as fine details cannot be reconstructed.18Li et al. [38] incorporate a convolutional neural network into the sketch processing workflow, allow-ing for inferences of depth and normal maps representative of generic freeform 3D surfaces fromsparse stroke, expressive 2D sketches. The input to their single-view model is 6-channel input mapconsisting of: 1-channel grayscale raster sketch, 1-channel binary mask computed from both sketchcontours and occluding contours, 1-channel optional user input depth samples, and 3-channel op-tional curvature hints for sharp features and target curvatures. The 6-channel input map first goesthrough an intermediate sub-network DFNet based on the encoder-decoder structure of U-Net [51],which regresses the flow field of the surface, followed by the sub-network GeomNet which takesboth the regressed flow field output from the DFNet, and the input map, to predict depth and normalmaps as well as a confidence map. In order to model complete 3D shapes, multiple surfaces fromdifferent views are modelled and fused together weighted by their confidence maps in a quadraticoptimization, which solves for the positions of 3D points (see Figure 2.13). As well, the modellingprocess is assisted when overlapping with existing surfaces, where prior computed information canbe leveraged and may be modified by re-sketching contours. The CNN is trained on a large gen-erated dataset of varying 3D shapes and sketches, which are rendered using non-photorealistic ren-dering algorithms that correspond to general drawing techniques. Training samples then, are inputsketches, their masks, depth samples and curvature hints, paired with corresponding output depthmaps, normal maps, and projected curvature direction fields. The DFNet sub-network is first trainedminimizing a loss function which sums over the absolute differences of regressed flow fields fromthe projected curvature direction fields of rendered 3D shapes, with the total variation of regressedflow fields augmented by signal filtering masks that account for occluding contours, contours, andsharp features. Following this, the GeomNet is trained minimizing a loss function summing the dif-ferences between predicted depths and normals from ground truths taken from 3D shapes, weightedby confidence maps to relax fitting losses over highly ambiguous regions.Figure 2.13: Three example input (left) and output (right) pairs demonstrating different resultsfrom similar sketches using the data driven sketch modelling method presented by Li etal. [38]. ©[38]Jin et al. [30] propose a sketch-based shape retrieval machine learning approach by jointly embed-ding both 2D occluding contours and 3D shapes in the same space via a variational autoencoder(VAE) and a volumetric autoencoder. Their VAE is trained on occluding contours extracted viarandom view projections of the 1165 3D models collected between Chen et al. [13] and Shilane et19al. [56], producing a continuous embedding space where each point represents an occluding con-tour. The volumetric autoencoder is then trained to map the 3D shapes onto the same embeddingspace through a supervised learning process, and subsequently trained to decode merged groups ofthree occluding contours of a 3D shape from the joint embedding space to its 3D voxel representa-tion.2.4 Interactive Sketch InterfacesA number of sketch-based modeling methods are accompanied by interactive sketch interfaces thatintegrate their core reconstruction algorithms and strategies, but are not essential themselves for themethods to work. Instead, these supporting-sketch interfaces aid general, non-specialized artists anddesigners in engaging with the sketch-based modelling methods being put forward. Andre et al. [5]supply an interactive interface for their algorithm, in which users can draw and smoothly overdrawconstruction lines, drag object shadows to set their depths in the screen, and specify junction linesto establish connectivity between objects. Delanoy et al. [15] pair their approach with an interactivedrawing interface that provides users with standard drawing operations. The drawing area acts asboth a canvas for drawing strokes, and a 3D viewer to visualize reconstructed predictions fromdifferent viewpoints. By enforcing the 3/4 view favored by designers for the first drawing, andsnapping the camera to pre-determined viewpoints available to the updater for subsequent drawings,the interface guides users to produce line drawings that match training data viewpoints. Li et al. [38]provide an interactive user interface for sketching 3D shapes from multiple views, where surfacesfrom previous views project to a user’s current view. Xu et al. [66] include a sketching interface withtheir work that provides users with standard drawing and curve manipulation operations, rendersboth drawn 2D curves and optimized 3D curve-networks in an overlaid fashion, and affords usersthe option of mirroring optimized 3D curve-networks such that they are only required to draw halfof a symmetrical object for optimization.2.4.1 Dedicated-Sketch InterfacesSketch-based modeling systems typically integrate modeling methods into dedicated-sketch inter-faces that constrain users to adhere to specific styles, shapes, strokes, and rules that strictly corre-spond to their methods inputs and limitations. While these systems are more readily incorporatedinto the sketch workflow, artists and designers must learn to use these sketch interfaces which areoften more complex than the alternative, simpler, supporting-sketch interfaces.The sketch interface Teddy presented by Igarashi et al. (see Figure 2.14) [28] provides users with anumber of operations necessary for the transition from 2D strokes to 3D polygonal meshes. Typicaloperations like camera manipulation, saving, and loading are available to users via widgets, as wellas previously discussed inflation and extrusion operations accessed through stroke gestures. Ad-20ditional stroke gestures include painting, cutting, and smoothing. Painting is activated by drawinga non-closed loop stroke, which creates surface lines on a polygonal mesh by sequentially pro-jecting each line segment of the painting stroke onto the object’s surface polygons, and does notaffect object geometries. Cutting is activated by drawing a non-closed stroke across and through thepolygonal mesh silhouette, which removes polygons to the left of the cutting stroke. This operationprojects each line segment from drawn cutting stroke onto the front and backfacing polygons, con-nects both projections to construct a planar polygon, and splices all cutting planar polygons togetherprior to their triangulation and subsequent removal of targeted polygons. Smoothing is activated bydrawing a closed loop base ring, deleting polygons surrounding the smoothing ring and creatingnew polygons to cover the hole smoothly using a constrained Delaunay triangulation, prior to aapplying a final surface-fairing algorithm.Figure 2.14: The Teddy [28] interface on a display-integrated tablet. ©[28]Arora et al. [6] present SymbiosisSketch, a hybrid sketching system that integrates augmented reality(AR) HoloLens technology into the sketching workflow, by combining 3D mid-air drawing with aspatially tracked stylus, and 2D surface drawing on a pen-sensitive tablet. Users of the systemdraw strokes interchangeably between the 2D tablet and in 3D mid-air, where the 2D tablet rendersthe 3D world, and any stroke drawn in 2D is mirrored in 3D world and vice-versa. While mid-air 3D strokes are heavily smoothed prior to arc length reparameterization and further bi-Laplaciansmoothing, 2D strokes drawn from the tablet require less smoothing prior to their reparameterizationdue to the motion-stability of drawing on a physical surface. Strokes are output to a collection ofsurface patches and 3D curves, where surfaces in SymbiosisSketch map to the physical tablet aseither planar or curved drawing canvases (see Figure 2.15). Users can create, position, rotate, andswitch between any number of drawing canvases in 3D space, allowing drawn strokes on the tabletto be projected orthographically onto the currently active drawing canvas in 3D. Scaling operationshowever are only available for planar drawing canvases. Curved drawing canvases are created froma combination of canvas-defining 3D curves that specify the intended surface in 3D space, eitherfully from drawn mid-air strokes in 3D, or in combination with prior canvas-constrained strokesfrom the tablet. The surface fitting function for curved drawing canvases is split into two stages.21The first stage consists of finding the best-fit plane for the set of strokes by uniformly samplinga fixed number of points from each input stroke, and solving for the best-fit plane using least-squares. The second stage fits a smooth height field from the best-fit plane to the input strokes byminimizing the fields thin plate spline energy, using the method proposed by Donato and Belongie[17]. Canvas-constrained curves are exactly fit using this method, while curves drawn mid-air areapproximately fitted. Solid surfaces are created with the Fill tool, which connects the start andend points of a stroke drawn on the tablet, computes a constrained Delaunay triangulation with allsegments of the input stroke, and finally projects the vertices of the triangulation onto the activecanvas. The SymbiosisSketch interface allows for typical sketch program operations: users canscale the canonical 1:1 workspace to zoom in, draw visibility-toggled strokes using the Pencil tool,create linearly transformable symmetry planes to mirror strokes, and change stroke colors.Figure 2.15: The SymbiosisSketch [6] tablet interface (left) and HoloLens output feed (right).©[3]Olivier et al. [46] present a new 3D sketch concept Nested Explorative Maps (NEM), with an accom-panying sketching system, targeted towards the needs of architects for interactive design. A NEMis represented by a hierarchical tree-like structure defined by canvases, maps, and footprints. Atthe root of a NEM tree is an initial canvas and map pair, with subsequent children as footprints thatconstruct, and are parent to, new canvas-map pairs. Canvases are represented by semi-transparent,free-form surfaces and generalized cylindrical volumes in 3D space, and are stored as meshes withtexture coordinates associated to their respective maps onto which users direct their strokes. Drawnstrokes are projected along the camera viewing direction to the first encountered canvas, allowingusers to target any visible canvas from a single viewpoint by toggling canvas visibilities on or off.In order to build up a NEM users enter Nested Footprint Mode and draw a single, continuous openor closed stroke that defines a footprint, from which a new child canvas is extruded along verti-cally, horizontally, or in the averaged normal direction of its support canvas. Footprints are storedas smooth cubic interpolating Catmull-Rom splines, and are further smoothed, or sharpened, as afunction of drawing speed and distances between control points on the original stroke. NEM af-fords users the ability to deform and evolve a canvas, along with its children, via drag-and-drop22operations of its parent footprint to different stroke groups on the map associated directly to itsparent canvas. Maps, which guide these deformations, are layers defined over canvases that consistof the set of raw polyline strokes drawn over their associated canvas, accompanied by 2D textureimages onto which the density of these polylines model a continuous field. During interactive can-vas manipulations these texture images, called confidence fields, guide and attract footprint controlpoints, modelled as mass-particles connected by plastic springs, where high density stroke areasindicate a strong likelihood that an element should be placed there. Confidence fields are contin-uously updated as new strokes are projected onto their associated canvas in Map Sketching Mode,allowing for refinement of a single footprint alongside explorative drag-and-drop operations to al-ternate high-confidence mapped stroke groups (see Figure 2.16). Users also have the option to fixthe position of a footprint control point or apply a global rigid translation to the entire footprint. Inaddition to the modes described, the NEM system includes both a Floor Mode and Cutting Mode.In the former, applicable only to generalized cylindrical canvases, drawn strokes are projected andexpanded along the contours of targeted canvas and interpreted as separating surfaces that allow forthe creation of new floors, which are in turn recognized as specialized footprints. In the latter mode,users sketch free-form cutting strokes across any number of visible canvases such that any canvaswith its cross-section spanned by these cutting lines are subsequently trimmed, matching the borderof their projection on screen to the cutting stroke.Figure 2.16: An overview of the Nested Explorative Maps [46] tool: (a) a user first drawsfootprints onto the ground plane canvas, (b) a new 3D canvas is constructed, (c) vi-sual details and maps can be drawn onto the new 3D canvas, (d-e) the canvas may bedeformed by dragging it onto a different footprint. ©[46]23Chapter 3Perceptual Properties of Cross-Sectionsat Cross-HairsThrough conversations with designers, observational studies of sketching sessions, and literaturereviews of design texts and image collections, Shao et al. found that “viewer perception must,consciously or not, influence designers who ultimately aim to maximize the sketch clarity” [55]. Theimplications of this observation for designers then guides their placement of cross-section curvesalong optimized locations in relation to the sketch as a whole, such that networks of cross-sectioncurves allow users to find globally 3D consistent solutions by leveraging local solutions at cross-hairs against one another. We summarize the findings of Shao et al. as they relate to the perceptualproperties of designer drawn cross-sections below.3.1 Intersecting Cross-Sections as Orthogonal PlanesProduct design literature [20] and perception studies [61] suggest that designers consistently usepairs of planar orthogonal cross-section curves at cross-hairs (Figure 3.1). Given two intersectingcross-section curves i and j, let ni be the normal to the supporting plane of cross-section curve iand n j the normal to the supporting plane of cross-section curve j. This property can then be statedmathematically as follows:ni ·n j = 0 (3.1)24Figure 3.1: Cross-section curves are interpreted as planar and orthogonal to each other atcross-hairs. Shown above, cross-section curve i (orange) and cross-section curve j (red).3.2 Intersecting Cross-Sections as Lines of Principle CurvatureDesign literature strongly suggests that observers interpret smooth intersecting curves as lines ofprinciple curvature [41, 61], and that cross-hairs exhibit local reflective symmetries across theirprinciple directions [20]. These suggestions implicate cross-section curve tangents at cross-hairs asorthogonal to each other (Figure 3.2). Given two intersecting cross-section curves i and j, let ti j bethe 3D tangent along cross-section curve i at its cross-hair with cross-section curve j, and t ji the 3Dtangent along cross-section curve j at its cross-hair with cross-section curve i. This property canthen be stated mathematically as follows:ti j · t ji = 0 (3.2)3.3 Intersecting Cross-Sections as Surface GeodesicsA geodesic is a curve that defines the shortest distance between two points on a surface, such that theosculating plane of the curve is normal to the tangent plane of the surface. Therefore, if a geodesic isa planar curve then the normal of the surface that it inscribes must lie in its plane as well. Perceptualstudies suggest that humans “typically perceive intersecting cross-section curves as geodesics” [55]when perceptual cues allow for such an interpretation [35].25Figure 3.2: Cross-section curves are interpreted as lines of principle curvature at cross-hairs.Shown above, cross-section curve i (orange) and cross-section curve j (red).Collinearity Proof. We show that given the plane orthogonality property (Equation 3.1) and tangentorthogonality property (Equation 3.2) at a cross-hair between two intersecting cross-section curves,the plane normal of one cross-section curve must be collinear with the others’ tangent (the cross-section curve geodesicity property). We have, ni ·n j = 0, n j ·ni = 0, ti j · t ji = 0, and t ji · ti j = 0 underorthogonality and tangent constraints. Then assuming ti j×n j 6= 0, ti j and n j must define a plane Psuch that both t ji and ni are orthogonal to it given previous constraints. However, we cannot havefour mutually orthogonal vectors in R3 as a plane can only have one absolute valued normal, and sot ji and ni must be collinear. QEDFurthermore, while cross-hair plane orthogonality and cross-section tangent constraints at a cross-hair together force one of the intersecting cross-section curves to be a geodesic, even if the othercross-section curve is non-geodesic viewers still favor its geodesic interpretation [55] (Figure 3.3).When both cross-section curves are geodesics, this property can be stated mathematically as fol-lows:ti j×n j = 0t ji×ni = 0(3.3)26Figure 3.3: Cross-section curves are interpreted as geodesics at cross-hairs. Shown above,cross-section curve i (orange) and cross-section curve j (red).3.4 Cross-Hairs and Minimal ForeshorteningGiven that the purpose of single-view concept sketches is to convey meaningful product informa-tion, designers often choose the most informative viewpoints that maximally convey 3D surfaceinformation while minimizing perspective distortion. Viewpoints with minimal foreshortening un-der orthographic projection are suggested by design literature as the most informative (Figure 3.4)[21]. Our method adopts a spatial axis with z orthogonal to the view plane, where a single cross-hair is minimally foreshortened when both its tangents are contained in this view plane. Minimalforeshortening then can be cast as a minimization of cross-hair tangent depths, over all cross-hairs.We have corrected a prior error in the foreshortening minimization equation from Shao et al. [55];our corrected mathematical formulation for minimal foreshortening is stated as follows:∑i j(tzi j + tzji)2 (3.4)For a single cross-hair, the minimal foreshortening condition satisfies the normal alignment pref-erence posited by Stevens who suggests that viewers perceive cross-hair normals as orthogonal totheir tangent bisector in 2D [61].Minimal Foreshortening Bisector Condition Equivalence Proof. Foreshortening is optimally min-imized locally at a cross-hair when tzi j = −tzji. Given the tangent orthogonality property (Equa-tion 3.2), the normal n to the surface at a cross-hair is defined as ti j × t ji. Expanding this cross-product and extracting the 2D normal give us n = (tyi jtzji− tyjitzi j, tzi jtxji− tzjitxi j), substituting in opti-27mal foreshortening tzi j = −tzji, gives us n = (tyi jtzji + tyjitzji,−tzjitxji− tzjitxi j), and after collecting termsn = (tzji(tyi j + tyji),−tzji(txi j + txji)). This 2D normal is orthogonal to the 2D bisector b of ti j and t ji,b = ((txi j+ txji)/2,(tyi j+ tyji)/2), proving equivalence to Steven’s bisector condition [61]. QEDFigure 3.4: Cross-hairs are minimally foreshortened.3.5 Cross-Hair OrientationsSurface shape perception induced by intersecting cross-section curves suffers from an inherent,well-documented ambiguity, between convex or concave shapes viewed from different positions.The implication of this ambiguity is that normals at cross-hairs may be oriented in two differentdirections opposite to each other. Generally, viewers have an implicit preference for convex shapesviewed from above instead of concave shapes [41] (Figure 3.5 a, b). However, while we can regulatethis preference in the post-processing of resultant outputs to some degree, the preference itself isnot strict across viewers and therefore cannot be fully automated into the modeling pipeline.Orientations at cross-hairs can be disambiguated in the presence of smooth silhouette curves how-ever, along which surface normals are perpendicular to the view direction. The visible surfacesin the immediate vicinity of silhouettes then must have, by definition, closer depth to the viewerthan the silhouette itself. The implication of this is that cross-section curves must have tangentsoriented with positive depth at their crossing points with silhouettes, and therefore subsequently attheir cross-hairs as well. These cross-hair normal orientations can then be accurately disambiguatedand aligned with a convex interpretation (Figure 3.5 bottom).28Figure 3.5: There are two possible interpretations regarding surface normal orientation foreach cross-hair, where viewers have an inherent preference for convex surfaces viewedfrom above (b) as opposed to concave surfaces (a), and (bottom) orientations at cross-hairs connected to silhouette curves (orange) are readily disambiguated.29Chapter 4Normal Estimation AlgorithmWe combine the cross-section curve properties described in Chapter 3 into a constrained minimiza-tion problem in a similar fashion to Shao et al. [55], which we optimize in order to estimate the sup-port planes of cross-section curves, in addition to their relative offsets. We then project cross-sectioncurve tangents at each cross-hair onto their respective support planes to recover depth information,and take their cross-product for subsequent surface normal estimation computations.4.1 Curve-Network RepresentationWe represent concept sketches as curve-networks, which we define as interconnected networks of2D C2 continuous composite cubic Be´zier curves. We adopt the same curve annotations as Shao etal. [55]; cross-section curves, smooth silhouette curves, and boundary curves. As we have previ-ously covered, cross-section curves supply perceptual constraints to sketch 3D interpretations (seeChapter 3), smooth silhouettes disambiguate cross-hair orientations (see Section 3.5), and boundarycurves are interpreted as standard patch boundaries that do not supply perceptual constraints, nordisambiguation cues (see Figure 4.1).Figure 4.1: Two layers of the cooker 1 input showing curve annotation colors used in ourdedicated sketching interface: orange curves denote cross-section curves, blue curvesdenote smooth silhouette curves, and green curves denote boundary curves.304.2 Local Analytic SolutionGiven two intersecting cross-section curves i and j, let ni be the normal to the supporting plane ofcross-section curve i and n j the normal to the supporting plane of cross-section curve j. We locallysolve for cross-section curve plane normals at cross-hairs by first computing 2D cross-section curvetangents using first order derivatives of Be´zier curves at those points of intersection. Then, we solvefor the tangent depths, assuming symmetry about the view plane, by optimally minimizing fore-shortening locally (Equation 3.4) under the tangent orthogonality property (Equation 3.2), giving usthe quadratic problem:(tzi j)2− (txi j ∗ txji+ tyi j ∗ tyji) = 0 (4.1)We directly solve for tzi j using the quadratic formula:tzi j =−b±√b2−4ac2awhere a = 1, b = 0, and c =−(txi j ∗ txji+ tyi j ∗ tyji), giving us:tzi j =±√txi j ∗ txji+ tyi j ∗ tyji (4.2)We calculate the discriminant to test if the quadratic is solvable, and if it is found to be negative weflip ti j and resume solving for its depth prior to normalizing it to unit length, then compute the depthof t ji as well:tzji =−tzi j (4.3)Once cross-section curve 3D tangents are calculated locally at cross-hairs, we compute their cross-section curves plane normals locally under the geodesicity property (see Section 3.3):ni = t jin j = ti j(4.4)A subset of local cross-section curve plane normals are subsequently used as an initial guess in ouroptimization routine, along with the estimated tangents at each cross-hair.314.3 Energy FunctionGiven initial local estimations of cross-section curve plane normals at a subset of cross-hairs, wecast the search for optimal cross-section curve plane normals aligned with the cross-section curveproperties described in Chapter 3 over all cross-hairs in a given curve-network:Enormal alignment = Egeodesic+E f oreshortening (4.5)We make the assumption that all cross-section curve plane normals have nz = 1, given that in conceptsketches cross-section curves are never depicted as orthogonal to the view plane, nor do we expectdesigners to depict backfacing surfaces in production drawings. This reduces the dimension of ourenergy by making Enormal alignment quadratic, which is far simpler to solve.4.3.1 Geodesic EnergyThe geodesic cross-section curve property (see Section 3.3) serves as a weak cue that is not alwayssatisfied, and hence we cast it as an energy, Egeodesic, that the objective aims to satisfy across allcross-hairs:Egeodesic =∑i j(∥∥t ji×ni∥∥2+∥∥ti j×n j∥∥2) (4.6)4.3.2 Foreshortening EnergyCross-section curve tangent depths at cross-hairs are unknown during optimization. However, underthe cross-section curve properties described in Chapter 3 these tangents are necessarily orthogonalto their cross-section curves plane normal. This allows us to instead reformulate the minimal fore-shortening property (see Section 3.4) under the assumption nz = 1 as a function of cross-sectioncurve tangents and their plane normals at cross-hairs:E f oreshortening =∑i j((−txi j ∗nxi − tyi j ∗nyi )+(−txji ∗nxj− tyji ∗nyj))2 (4.7)4.4 Constraint FunctionsWe enforce inequality constraints for those cross-section curve properties described in Chapter 3that serve as strong cues, and solve for the relative offsets of cross-section curve planes purely32through constraint satisfaction.4.4.1 Plane Orthogonality ConstraintThe cross-section curve plane orthogonality property at cross-hairs (see Section 3.1) is a strict de-signer imposed perceptual constraint on concept sketches, and as such serves as a strong shaperegularity cue:Cplane orthogonality = ni ·n j (4.8)However, due to drawing inaccuracies we formulate this property as an inequality constraint to allowfor a 5◦ deviation from absolute orthogonality:−0.1≤Cplane orthogonality ≤ 0.1 (4.9)4.4.2 Tangent Orthogonality ConstraintThe cross-section curve tangent orthogonality property at cross-hairs (see Section 3.2) is a strictdesigner imposed perceptual constraint on concept sketches as well, given that it is closely tiedto the cross-section curve plane orthogonality property, and as such also serves as a strong shaperegularity cue:Ctangent orthogonality = ti j · t ji (4.10)In similar fashion to the cross-section curve plane orthogonality property, due to drawing inaccura-cies we formulate this property as well as an inequality constraint to allow for a 5◦ deviation fromabsolute orthogonality:−0.1≤Ctangent orthogonality ≤ 0.1 (4.11)4.4.3 Plane Offset ConstraintWe can expect that at each cross-hair the intersecting 3D cross-section curves share the same depthz, and therefore associate a plane offset value ci to each cross-section curve i. At each cross-hairwe then formulate this observation as a standard vector plane equation for each of the intersecting33cross-section curve planes, setting p to the cross-hairs position:p ·ni+ ci = 0p ·n j + c j = 0(4.12)Then, under the assumption that all cross-section curve plane normals have nz = 1, we expand andsubtract both plane equations at a given cross-hair to reformulate our plane offset constraint as twoinequality constraints in terms of the cross-section curve plane normals and known 2D cross-hairsposition:Cplane o f f set pos = (nxi −nxj)px+(nyi −nyj)py+(ci− c j)≤ 0Cplane o f f set neg =−(nxi −nxj)px− (nyi −nyj)py− (ci− c j)≤ 0(4.13)In order to anchor cross-section curve plane offsets, we pick a single cross-hair arbitrarily and setits position to (0,0,0). We formulate this anchor as two inequality constraints on the plane offsetsof the two intersecting cross-section curves k and l incident to the chosen cross-hair:Crelative plane pos = ck− cl ≤ 0Crelative plane neg = cl− ck ≤ 0(4.14)We construct our optimization problem using the normal alignment energy (Equation 4.5) as ourminimization objective over ni, subject to the above inequality constraints (Equation 4.9, Equa-tion 4.11, Equation 4.13, Equation 4.14), and use optimized plane offsets to interpolate estimatednormals post-optimization across cross-section curves. Further details of our optimization routineincluding the non-linear optimization library used, targeting of connected components of cross-section curves for optimization, initialization strategies, and solution post-processing heuristics arecovered in the following Chapter 5.34Chapter 5Optimization RoutineOur new optimization routine uses the non-linear optimization library NLopt to solve our con-strained minimization problem outlined in Chapter 4, in addition to using a surface orientationsensitive initialization, a post-optimization solution selection heuristic, and individually targetedoptimizations on patches of connected cross-section curves. The effects of these decisions on nor-mal estimations are covered in detail in Chapter 6.5.1 OverviewOur optimization problem aims to minimize the normal alignment objective (Equation 4.5) by find-ing optimal cross-section curve plane normals ni, with equal weights of 1.0 for both the geodesicenergy (Equation 4.6) and foreshortening energy (Equation 4.7):minni∑i j(∥∥t ji×ni∥∥2+∥∥ti j×n j∥∥2)+((−txi j ∗nxi − tyi j ∗nyi )+(−txji ∗nxj− tyji ∗nyj))2 (5.1)We use only inequality constraints in our optimization problem given their requirement over equal-ity constraints by the non-linear optimization library we use [31]. All of our inequality constraintsare treated as hard constraints, they consist of plane orthogonality constraints (Equation 4.9), tan-gent orthogonality constraints (Equation 4.11), plane offset constraints (Equation 4.13), and relativeplane offset constraints (Equation 4.14). We select an initialization strategy from two separatestrategies given the presence or absence of silhouette curves in a given curve network being opti-mized (see Section 5.4). When silhoutte curves are present, we use the local analytic solutions ofcross-section curve plane normals at all cross-hairs along cross-section curves incident to silhouettecurves to construct a single initial guess (see Section 5.4.1). However, when silhouette curves arenot present, we find the pair of cross-hairs with the greatest geodesic distance and calculate fourpossible orientation pairs between them to construct four intitial guesses using their cross-section35curves local analytic plane normal solutions (see Section 5.4.2). We then solve four instances of ouroptimization problem using each of the four initializations, and select the best fit solution.5.2 Numerical OptimizationIn our optimization routine, we employ the open-source non-linear optimization library NLopt [31],as it provides a multitude of optimization algorithms and customizable optimization parameters,as well as being readily integrated into our sketching interface. We use the local, gradient-basedalgorithm Method of Moving Asymptotes (MMA) [62], which is popular for topology optimization.MMA forms a local approximation that is both convex and separable at each point x using the gra-dient of the objective function and the constraint functions. In addition, a quadratic penalty termas a function of the upper bounds of x is included to push the approximations to a conservativedirection. The resultant approximated optimization is solved by a dual method, leading to a newcandidate point x on which both the objective and constraints are evaluated. If the approximationsare indeed found to be conservative, the whole process is started from the new candidate point x;otherwise the penalty term on the upper bound is increased and the approximations are re-optimized.Given that the typical concept sketch seldom has more than 20 cross-hairs in total, which are dis-tributed across its curve-network patches, the class of local optimization algorithms are sufficientlycapable of accurately, and efficiently, solving our constrained minimization problem. Since MMAis also a gradient-based optimization algorithm, and we specifically target subnetworks of curvesin our routine, we achieve interactive optimization speeds for most inputs, and near-interactive op-timization speeds for a few (see Section 6.1.3). We found that the best results on our inputs wereproduced with MMA using maximum function evaluations set to 100000, and a relaxed range ofnormal vectors with both upper and lower bounds on the optimized variables set to 20.0 and −20.0respectively.5.3 Cross-Patch SolveDrawn sketches are not necessarily always fully connected when represented as curve-networks.Often users will layer separate curve-networks on top of one another to construct more complex de-signs. While it is trivial to target these layers separately using the sketching interface accompanyingour work, curve-networks additionally may be disjoint themselves across multiple subdivisions ofcurve-network patches in a given layer. We cannot expect users to actively isolate curve-networkpatches onto separate layers, and in fact, enforcing such an expectation does not lend well to theworkflow of designers, where one can imagine that it would be perfectly reasonable to isolate com-ponents with similar topological contexts onto a single layer of design. For example, the knobs onthe side of a sewing machine may be grouped together onto a single layer, even though they may36Figure 5.1: We automatically detect curve-network patches across a given layer, providingusers with the option to see them visualized on-screen as they draw per layer, or acrossall layers simultaneously. In the example shown above, individual layers of the sewinginput are shown alongside a view of curve-network patches visualized across all inputlayers simultaneously (curve network patches shown in colored highlights).not necessarily be directly connected on the layer they share (see Figure 5.1).Consequently, if we optimize a curve-network that consists of multiple curve-network patches eachpatch in turn exerts an influence on the optimal solution of other patches in the same network, andas a result a sub-optimal solution is compromised overall. In our implementation, we representcurve-networks as undirected graphs (see Section 7.2), which allows us to detect connected com-ponents as curve-network patches. Furthermore, we filter curve-network patches to only includecross-section curves and cross-hairs prior to an additional level of subdivision into cross-patches,which are curve-network sub-patches computed from the connected components of these filteredcurve-network patch representations (see Figure 5.2). Generally, the omission of boundary curvesmay disconnect patches of cross-section curves, where boundary curves signify edges along whichnormals may sharply change. Therefore, we cannot jointly estimate the normals of cross-sectioncurves separated onto two patches which are connected only by boundary curves, and so cross-patches are optimized individually.37Figure 5.2: Cross-patches are computed from the connected components of cross-sectioncurve and cross-hair filtered curve-network patches, (a) in the example above we cansee that there is a single curve-network patch, (b) but four cross-patches (colored high-lights).5.4 InitializationResultant surface orientations at cross-hairs are very sensitive to the initial guesses we supply to ouroptimizer, as these guesses locate the optimizations search efforts in the space of possible solutions.Given that the MMA algorithm is a local optimization, the choice of initialization is substantiallymore important as exponential regions, infeasible zones, or function asymptotes can cause a local al-gorithm to converge very poorly or fail all-together. In the context of our inputs, these poorly formedinitializations reference cross-section curves perpendicular to the view-plane, with no nearby cross-section curve information to lead the optimization in the correct direction. In addition, we must alsoaccount for varying surface orientations at cross-hairs in our initializations in any given cross-patch.While it is incredibly difficult, if not infeasible to fully automate the computation of consistent op-timal surface orientations at cross-hairs across a given cross-patch (see Section 3.5), we resolve thisissue by selecting from two possible initialization strategies just prior to minimizing our constrainedobjective energy.5.4.1 Single GuessSimilar to CrossShade [55], the single guess strategy is selected when the target curve-networkpatch contains at least one smooth silhouette curve that touches at least one single cross-sectioncurve. In this curve-network configuration, we can reasonably estimate the intended surface orien-tations at cross-hairs connected to smooth silhouette curves (see Section 3.5). We can then initializethe optimization of the cross-patch with a single guess that includes all local, analytic solutions38for cross-section curve plane normals at those cross-hairs, oriented with respect to the silhouettecurves they touch in the curve-network patch, and set all other cross-section curve plane normals to[0.0,0.0,1.0].5.4.2 Quad GuessThe quad guess strategy is selected when there are no smooth silhouette curves in a given curve-network patch from which to extract orientation cues. In such a scenario, we are faced with anexhaustive search over all possible surface orientation configurations followed by a post-processingselection criterion. We begin by converting target cross-patches into our secondary graph represen-tation, the intersection graph (see Section 7.2). From this, we compute the graph geodesic of eachpair of cross-hairs across each cross-patch intersection graph, selecting the pair with the greatestgeodesic distance, or graph diameter. When there are two such possible pairs, the last computed isselected.Following this, we construct four guesses that we initialize our cross-patch optimization with bycalculating four possible orientation pairs between the graph diameter cross-hairs, and setting allother cross-section curve plane normals to [0.0,0.0,1.0]. From these four initializations, four pos-sible solutions are produced, which we must select from. We found that from these four solutions,it is always the case that there are two pairs of orientation-flipped solutions (see Figure 5.3), asour perceptual constraints can only solve for the surface information of a cross-patch up to, but notincluding, orientations. Therefore, we first remove the worst fitted pair from consideration. Fromthe remaining two solutions, we enforce viewer preferences for surfaces viewed from above (seeSection 3.5) by propagating cross-hair normals along cross-section curves using minimal rotations,integrating propagated normals across cross-patches, and selecting the solution with the greatestoverall y-measure.Taking into consideration the use of the non-linear optimization library NLopt to solve our opti-mization problem, as well as our cross-patch targeting, initialization strategies, and solution post-processing selection heuristics, the most impactful decision of these on the efficiency, robustness,and quality of solutions is cross-patch targeting. The effects of all of our optimization routine deci-sions are presented in detail in the following Chapter 6.39Figure 5.3: It is always the case that when the quad guessing strategy is used, two pairs oforientation-flipped solutions are produced (horizontal pairs, above).40Chapter 6ResultsWe tested our method on a subset of the original curve-network dataset employed by Shao et al.in developing CrossShade [55], in addition to a working subset of the dataset employed by Xu etal. [66]. In total we tested our method across 11 diverse inputs, ranging from simple to complexcurve-networks, and present our findings in detail below.6.1 Comparison to Prior WorkOn the following pages we present a comparison of results produced with our method against thoseproduced with CrossShade [55]; they are presented and delineated as input-output pairs across everylayer of each input. It is worth noting that our interface renders inactive layers on multi-layer inputsat a lower opacity than the prior implementation does, to reduce visual clutter of a users canvas workspace, and so this difference will be noticeable as well in our presentation of results. We do not haveground truths available, and instead rely on visual inspection as well as concrete measurable metricssuch as optimization times and clear failure cases. We leave the development of ground truth datasets as future work, described in further detail in Section 8.2.We use the exact same inputs for both our method and CrossShade; both the exact same curve-network inputs as well as their local analytic solutions of cross-section curve plane normals. Bothour method and the prior method solve the same problem, with minimal foreshortening, reformu-lated equality constraints as inequality constraints, and constraints on both cross-section curve planeoffsets at a single cross-hair set to 0 as the key differences. However, as initialization strategies differin key aspects between our method and the prior method, initial guesses supplied to the optimiza-tions used by both methods differ as well. This difference among others further described in thischapter have a clear effect on results.41input cross-sections cross-hairs cross-patchesashtray 4 3 1cooker1 6 4 2cooker2 6 4 2bending plane 9 14 1camera 24 17 9ellipsoid 6 9 1mouse 7 4 3robot 80 42 39sewing 28 21 10sportbag 21 18 7stapler 11 8 3Table 6.1: The number of cross-section curves, cross-hairs, and cross-patches for each inputare listed above.6.1.1 QualityOn visual inspection, the normal estimations produced by our method are at minimum as good asCrossShade’s [55] on the same inputs, and we can directly see the positive effects of our cross-patch targeting, solution post-processing selection heuristics, and foreshortening correction acrossa number of solutions.Cross-Patch TargetingOur method directly targets connected components of cross-section curves for separate optimiza-tions, while the prior method optimizes over entire input layers regardless of the absence of curveconnectivities. Because disjoint patches of cross-section curves are optimized individually, we avoidthe issue of erroneous influences by patches of cross-section curves that do not supply any surfacenormal information or constraints to a given cross-patch optimization (see Figure 6.4: L0, L3,L4).Solution Post-Processing Selection HeuristicsQuad guessing strategies are used in both our method (see Section 5.4.2) and CrossShade’s. There-for, under either quad guessing strategy four possible solutions are always produced. In the priormethod, y-components of cross-hair normals are integrated across cross-section curves for each so-lution, and the solution with the largest sum of these integrated components is selected. However,it is sometimes the case that a poorly fitted solution has a greater y-summation over a given cross-patch, and so the wrong choice is made when selecting which possible solution to propagate to thewhole curve-network. Our approach handles this issue by directly removing from consideration theworst fitted pair of solutions prior to taking the summation over the integrated y-components and42making a selection. In addition, our method does not integrate across hanging ends of curves (seeFigure 6.5: L1), which typically are drawing artefacts from designers who over estimate lengths ofdrawn strokes beyond intersections. Therefor, we do not erroneously include segments of curvesthat do not contribute to a shapes overall surface variation when selecting a soution. The effects ofthis added heuristic to the selection process can be seen across three of our results when comparedto CrossShade [55] (see Figure 6.5: L1; 6.3b: L0; Figure 6.6: L4).Foreshortening CorrectionWithout a ground truth to establish measurable differences against our results, and those of CrossShade’s[55], it is difficult to properly quantify the quality of normal estimations with respect to optimal fore-shortening. In fact, there are inputs where our method appears to produce better optimally foreshort-ened resuls than the prior method (see 6.1b; 6.3a), as well as one input with over-foreshortenedresults when compared to the prior method (see 6.3b: L0, L1). There are a number of possiblereasons for our over-foreshortened result: it may be the case that neither our method nor the priormethods mathematical formulation for minimal foreshortening is correct, the input itself may bepoorly formed for our updated optimization routine, more optimal cross-section curve plane nor-mals are overwritten by the single guess initialization logic for the case of L1, or our optimizationitself may require further parameter adjustments to better tune it for this specific problem. However,our method produces optimally foreshortened results across the remaining inputs that are, at leaston visual inspection, as good as the prior methods foreshortened results.6.1.2 RobustnessThere are a number of inputs where CrossShade [55] clearly fails to produce an optimal answer,where our method consistently finds optimality. While our solver never fails completely on any ofthe inputs we tested, if a designer creates an ill-formed input NLopt will attempt to optimize it andterminate on a generic failure code when the maximum function evaluations are exceeded. Howeverthe output from the solver may still be used as values are still returned rather than the initial guess,and it is left to the discretion of the designer to inspect the results and resolve issues in their drawncurve-network.Cross-Patch TargetingBecause the prior method optimizes per layer across inputs, there are often cases where their solverfails and returns the initial guess provided to the optimization. When optimizing across layers blindto the presence of disconnected patches of cross-section curves, their initialization strategy suppliesinitial guesses for at most two cross-section curves, so when there are more than two cross-patcheson a given layer for an input their initializations insufficiently capture the necessary topology to43reach optimality, as their optimizations search in the wrong space of potential solutions. However,in our optimization routine we first cast a search for all curve-network patches then further refinethese patches to cross-patches, and as a result produce substantially more robust normal estimationsfor those cases that previously failed (see Figure 6.6: L1; Figure 6.7: L0, L2, L3; Figure 6.8:L4).6.1.3 EfficiencyWe measured the total time in seconds required to solve an entire input, across all of its layers, forboth our optimization method and CrossShade’s optimization method (see Table 6.2). The times aremeasured on a 3rd Generation Intel Core i7 CPU at 3.20GHz. Our updated optimization methodis faster than CrossShade’s by a factor of at least 15.691 for the ellipsoid, and a factor of at most31301 for the robot. For every input tested our method was faster in finding an optimal solution,by a substantial factor, which can be primarily attributed to our cross-patch targeting, as well as ourinitialization strategies and the optimization library we used.input CrossShade Ours speed-up factorashtray 0.51029s 0.011860s 43.026cooker1 0.20386s 0.0039970s 51.003cooker2 0.22143s 0.0058657s 37.750bending plane 35.381s 0.093167s 379.76camera 318.86s 0.054476s 5,853.2ellipsoid 0.22754s 0.014501s 15.691mouse 0.16238s 0.0070768s 22.945robot 121.83s 0.0038921s 31,301sewing 24.359s 0.024797s 982.33sportbag 1.2299s 0.022870s 53.778stapler 140.07s 0.024760s 5,657.1Table 6.2: Our method consistently outperforms CrossShade [55] with respect to optimizationspeed. Optimization runtimes are measured to 5 significant figures, and calculated speed-up factors are reported to 5 significant figures as well.Cross-Patch TargetingIt is evident from the input statistics on cross-patch numbers (Table 6.1), that those inputs with agreater number of cross-patches experienced the most significant optimization speed improvements.By detecting connected components across varying granularities of curve-network subdivisions, weminimize the computational effort required to optimize largely disconnected inputs by initializingour optimization per cross-patch. Our initial guesses accurately capture a range of possible sur-face orientations even in cross-patch dominant inputs, where the prior method instead initializes44per layer, blind to the presence of cross-patches that should not influence each other’s solutions.Therefore, their initialization strategy orients their optimizations search efforts in the wrong spaceof potential solutions, increasing computation times substantially. In contrast, our method positionsour optimizations search efforts closer to feasible areas and so improves optimization runtimessubstantially, and also directly solves cross-patches that contain only one cross-hair which savescomputation time by skipping trivial optimizations.Initialization StrategiesWhile both our method and CrossShade’s [55] employ quad guessing strategies when solving un-der cross-hair orientation uncertainties, our approach is markedly different. We are able to morebroadly capture cross-patch orientation variations, given that we actually permute flipped cross-hairorientations at cross-hairs located at the greatest geodesic distance on a given cross-patch when con-structing our four initial guesses. In contrast, the prior method selects a single cross-hair arbitrarilyand flips individual x and y components of its two incident cross-section curve plane normals topermute orientations, which violates the cross-hair orientation ambiguity perceptual property (seeSection 3.5) for half of the initial guesses this approach constructs. Optimization runtimes are im-proved under our more accurate initializations, which supply initial guesses for four cross-sectioncurve plane normals instead of two that the prior method supplies to its solver.Optimization LibraryWe can also attribute our improved optimization runtimes to our use of the non-linear optimiza-tion library NLopt with the MMA algorithm. Because the MMA algorithm is both local andgradient-based, it is far faster than the alternative derivative-free class of optimization algorithmsthat may approximate derivatives using finite-differences. In contrast, CrossShade [55] uses thefmincon interior-point algorithm from the Matlab Optimization Toolbox [42] fmincon. While a lo-cal optimization algorithm, both the constraint and function gradients are turned off in their imple-mentation, forcing approximal derivatives using finite-differences which can lengthen computationtimes.45(a) ashtray input(b) bending plane inputFigure 6.1: Comparison input-output pairs for each layer of the ashtray and bending planeinputs, optimized with CrossShade [55] and our method. We find more accurately fore-shortened solutions in the case of bending plane, most notably along the vertical strokesegments.46(a) cooker1 input(b) cooker2 inputFigure 6.2: Comparison input-output pairs for each layer of the cooker1 and cooker2 inputs,optimized with CrossShade [55] and our method. We consistently produce results asgood as the prior method.47(a) ellipsoid input(b) stapler input(c) mouse inputFigure 6.3: Comparison input-output pairs for each layer of the ellipsoid, stapler, and mouseinputs, optimized with CrossShade [55] and our method. We find more accurately fore-shortened solutions in the case of ellipsoid, most notably along the vertical curved strokesegments. We find better oriented normal estimations in the case of stapler, howevernormal estimations are over-foreshortened along horizontal stroke segments.48Figure 6.4: Comparison input-output pairs for each layer of the sewing input, optimized withCrossShade [55] and our method. We find better oriented normal estimations, visible inL0, L3, and L4 where we can see properly aligned outward facing normals.49Figure 6.5: Comparison input-output pairs for each layer of the sportbag input, optimized withCrossShade [55] and our method. We find better oriented normal estimations, visible inL1 where we can see properly aligned inward facing normals, as well as the omission ofhanging ends of cross curves overdrawn beyond intersections.50Figure 6.6: Comparison input-output pairs for each layer of the camera input, optimized withCrossShade [55] and our method. We consistently find optimal solutions for cross-patches where the prior method fails or selects sub-optimal solutions, visible in L1 acrossthe front facing body. We also find better aligned orientations of normal orientations,seen in L4.51Figure 6.7: Comparison input-output pairs for layers 0 to 3 of the robot input, optimized withCrossShade [55] and our method. We consistently find optimal solutions for cross-patches where the prior method fails or selects sub-optimal solutions, visible in L0 onthe legs and left arm, L2 on both arms and the left side of the head, and L3 on the righteye.52Figure 6.8: Comparison input-output pairs for layers 4 and 5 the robot input, optimized withCrossShade [55] and our method. We consistently find optimal solutions for cross-patches where the prior method fails or selects sub-optimal solutions, visible in L4 onthe right hand.53Chapter 7ImplementationWe have made a number of careful implementation decisions, motivated with the goal of developinga modular and easy to extend codebase. Our accompanying sketching interface follows strict designguidelines, cleanly separating the front-end of the program from the back-end, and with both endsbuilt up with modular components. We also designed our data structures on top of the Boost GraphLibrary (BGL) [29] using custom vertex and edge properties, along with associated filters and maps,to make our internal curve-network representations adaptable to change, and to broaden the rangeof curve-network operations available.7.1 Sketching InterfaceOur work is accompanied by an updated sketching interface written in the latest Qt framework [43],while the optimization library NLopt [31] is integrated into the back-end of our interface archi-tecture in order to centralize operations into a single user program. With the goal of producing amodular codebase that may be readily extended by future collaborators, we closely followed thedesign principle of Separation of Concerns (SoC) in combination with the Model-View-Controller(MVC) design architecture. We segmented the front-end of our program into three sub-systems asper the MVC design architecture, and subdivided the back-end into multiple submodular compo-nents. Our code is available upon request on the GitHub platform, we make the git informationavailable here [1].Included in the front-end of the sketching interface are basic stroke editing operations accessiblefrom the toolbox widget on the left of the interface, a sketching area in the center of the interfacewhere users can generate new blank canvases on which to draw in a layered manner, a number ofvisualization utilities enabled from the checkbox list on the middle-right that can be visually lay-ered sequentially, and an inspection widget on the right side of the interface that is activated by theinspection tool, and displays select data (see Figure 7.1).54Figure 7.1: The updated sketching interface includes an inspection tool alongside basic sketch-ing operations and visualizations.7.2 Curve-Network Data StructuresThe basic types of data in our implementation are compound Be´zier curves, or polybe´ziers, and theintersections between them. Both of these data types are the building blocks of curve-networks, andare leveraged both separately and jointly across different curve-network processing needs. In orderto expand the number of available operations we can use, we represent curve-networks as undirectedgraphs in our implementation, and leverage two different graph representations based on curve andintersection connectivities. Both are built on top of the newest version of the Boost Graph Library(BGL) [29] for improved adaptability and customization of graph properties.One common feature across both graph representations is our adherence to strict data constancy,which we guarantee with the Boost UUID Library [64] by associating each polybe´zier and inter-section data instance with their own Universally Unique Identifier (UUID). This additional layer ofidentification allows us to traverse our graphs securely, as we both employ a number of data UUIDchecks throughout our code to guarantee data constancy, as well as leverage a number of searchfunctions capable of extracting and cross-checking information from graph representations usingeither vertex or edge descriptors, or data UUIDs.7.2.1 Primary Graph RepresentationOur primary graph representation of a curve-network is a curve graph. In a curve graph, curves arerepresented as graph vertices, and intersections between curves are represented as edges between55vertices. This allows for curve self-intersections, and for two curves to intersect each other multipletimes along their lengths. Each vertex has encoded a custom data pointer property, formatted asa shared pointer to an instance of a polybezier curve, while each edge similarly has encoded acustom data pointer property, formatted as a shared pointer to an instance of an intersection. Wedo not store any graph-specific data, such as descriptors, in our curve or intersection data instances.Instead, UUIDs create a correspondence between descriptors and data instances via UUID-targetedsearch functions. We directly store curve-networks as curve graphs, and use this representation forthe majority of our computations.7.2.2 Secondary Graph RepresentationThe secondary graph representation we use is the intersection graph. This representation is usedon-the-fly, primarily for computing graph geodesics during optimization with the quad guessingstrategy (see Section 5.4.2). Each vertex has encoded a custom curve graph edge descriptor prop-erty, and each edge similarly has encoded a custom curve graph vertex property, creating a directcorrespondence to the curve graph it is derived from.56Chapter 8ConclusionWe presented our work on improved normal estimation from cross-section drawings, and demon-strated that our method makes substantial improvements on optimization efficiencies, robustness,and quality of normal estimations over the prior work of Shao et al. [55]. In addition to improvednormal estimations, we have included an updated sketching interface and re-designed our code im-plementations with extensibility in mind.8.1 LimitationsOur method is unable to handle viewpoints aligned with canonical directions parallel to the viewplane (front, back, left, right, top, and bottom), and relies on the assumption that all input curve-networks are drawn under a relaxed orthographic projection. As well, we assume all input sketchesto be drawn in the general concept sketch setup, where cross-hair plane normals are never parallel tothe view plane. We also do not involve a finer granularity selection strategy when constructing ini-tializations in the presence of smooth silhouette curves, and as a consequence cross-hairs along thesame cross-section curve may overwrite previous, more optimal, cross-section plane normals.8.2 Future WorkWe believe normal estimations can be further improved by including a selection heuristic duringthe optimization routines initialization phase under smooth silhouette curves. The absence of thisheuristic in our method is noticeable in our stapler input, where foreshortening may have beenover-optimized as a result of a sub-optimal initial guess. Conversely, our minimal foreshorteningformulation may not be fully correct either given the same stapler input, requiring further testing toresolve for the correct formulation. Developing ground truths for further testing is also necessary,and may be done by generating curve networks from 3D shapes that have known surface normals.57Making the upper and lower bounds of the optimization dynamic as a function of inputs would alsosee improved results, as solvers are typically sensitive to the range of permissible value bounds.While our selection heuristics are quite simple, they have a clear and positive effect on results.However, it would be interesting to see more dynamic heuristics as a function of shape topolo-gies as we suspect that the y-metric may not be appropriate across future unseen inputs. Furthercurve type annotations with accompanying heuristics and perceptual rules would extend the rangeof possible concept sketch complexities as well. Regarding the interface and user workflows, com-bining sketch vectorization, simplification and stroke consolidation pre-processing steps to scannedconcept sketches would improve user adoptability of our method, as would further developing oursketching interface.58Bibliography[1] Public code available upon request. git@github.com:silv3rburl4/msc thesis.git. → page 54[2] Contour line drawings.https://www.learn-how-to-draw-and-paint-great.com/contour-line.html. Accessed:2020-12-07. → pages x, 11[3] Symbiosissketch: Combining 2d & 3d sketching for designing detailed 3d objects in situ.https://www.youtube.com/watch?v=BoAjGlIOkl0. Accessed: 2020-12-07. → pages xi, 22[4] M. Almeida, R. Lins, R. Bernardino, D. Jesus, and B. Lima. A new binarization algorithm forhistorical documents. Journal of Imaging, 4(2):27, Jan 2018. ISSN 2313-433X.doi:10.3390/jimaging4020027. URL http://dx.doi.org/10.3390/jimaging4020027. → pagesx, 5[5] A. Andre and S. Saito. Single-view sketch based modeling. In SBIM ’11, 2011. → pagesxi, 12, 20[6] R. Arora, R. Kazi, T. Grossman, G. W. Fitzmaurice, and K. Singh. Symbiosissketch :Combining 2d & 3d sketching for designing detailed 3d objects in situ. 2018. → pagesxi, 21, 22[7] G. Baja. Well-shaped, stable, and reversible skeletons from the (3, 4)-distance transform. J.Vis. Commun. Image Represent., 5:107–115, 1994. → pages 6, 8[8] P. Barla, J. Thollot, and F. Sillion. Geometric clustering for line drawing simplification. InProceedings of the Eurographics Symposium on Rendering, 2005. URLhttp://maverick.inria.fr/Publications/2005/BTS05a. → page 9[9] M. Bessmeltsev and J. Solomon. Vectorization of line drawings via polyvector fields. ACMTrans. Graph., 38(1), Jan. 2019. ISSN 0730-0301. doi:10.1145/3202661. URLhttps://doi.org/10.1145/3202661. → pages x, 8, 9[10] H. F. Blum. A transformation for extracting new descriptors of shape. 1964. → page 6[11] A. Bonnici, A. Akman, G. Calleja, K. Camilleri, P. Fehling, A. Ferreira, F. Hermuth, J. Israel,T. Landwehr, J. Liu, N. Padfield, T. Sezgin, and P. Rosin. Sketch-based interaction andmodeling: where do we stand? Artificial Intelligence for Engineering Design, Analysis andManufacturing, 33:1–19, 11 2019. doi:10.1017/S0890060419000349. → page 559[12] J. Chen, Q. Lei, Y. Miao, and Q. Peng. Vectorization of line drawing image based on junctionanalysis. Science China Information Sciences, 58(7):1–14, 2015.doi:10.1007/s11432-014-5246-x. URL https://doi.org/10.1007/s11432-014-5246-x. → page8[13] X. Chen, A. Golovinskiy, and T. Funkhouser. A benchmark for 3d mesh segmentation. ACMTrans. Graph., 28(3), July 2009. ISSN 0730-0301. doi:10.1145/1531326.1531379. URLhttps://doi.org/10.1145/1531326.1531379. → page 19[14] C. Chow and T. Kaneko. Automatic boundary detection of the left ventricle fromcineangiograms. Computers and Biomedical Research, 5(4):388 – 410, 1972. ISSN0010-4809. doi:https://doi.org/10.1016/0010-4809(72)90070-5. URLhttp://www.sciencedirect.com/science/article/pii/0010480972900705. → page 5[15] J. Delanoy, M. Aubry, P. Isola, A. A. Efros, and A. Bousseau. 3d sketching using multi-viewdeep volumetric prediction. Proceedings of the ACM on Computer Graphics and InteractiveTechniques, 1(1):1–22, Jul 2018. ISSN 2577-6193. doi:10.1145/3203197. URLhttp://dx.doi.org/10.1145/3203197. → pages 18, 20[16] C. Ding and L. Liu. A survey of sketch based modeling systems. Frontiers of ComputerScience, 10:985–999, 2016. → page 5[17] G. Donato and S. Belongie. Approximate thin plate spline mappings. In A. Heyden, G. Sparr,M. Nielsen, and P. Johansen, editors, Computer Vision — ECCV 2002, pages 21–31, Berlin,Heidelberg, 2002. Springer Berlin Heidelberg. ISBN 978-3-540-47977-2. → page 22[18] D. Dori. Orthogonal zig-zag: An algorithm for vectorizing engineering drawings comparedwith hough transform. Advances in Engineering Software, 28(1):11 – 24, 1997. ISSN0965-9978. doi:https://doi.org/10.1016/S0965-9978(96)00035-X. URLhttp://www.sciencedirect.com/science/article/pii/S096599789600035X. → page 7[19] D. Dori and L. Wenyin. Sparse pixel vectorization, an algorithm and its performanceevaluation. ieee trans pattern anal mach intell. Pattern Analysis and Machine Intelligence,IEEE Transactions on, 21(3):202 – 215, 04 1999. doi:10.1109/34.754586. → page 6[20] K. Eissen and R. Steur. Sketching: Drawing Techniques for Product Designers. BisPublishers, 2008. → pages x, 1, 2, 24, 25[21] K. Eissen and R. Steur. Sketching: The Basics. Bis Publishers, 2011. → pages 2, 27[22] E. Entem, L. Barthe, M.-P. Cani, F. Cordier, and M. van de Panne. Modeling 3d animals froma side-view sketch. 46(C):221–230, Feb. 2015. ISSN 0097-8493.doi:10.1016/j.cag.2014.09.037. URL https://doi.org/10.1016/j.cag.2014.09.037. → page 11[23] J.-D. Favreau, F. Lafarge, and A. Bousseau. Fidelity vs. simplicity: a global approach to linedrawing vectorization. ACM Transactions on Graphics (SIGGRAPH ConferenceProceedings), 2016. URL http://www-sop.inria.fr/reves/Basilic/2016/FLB16. → pages x, 8, 9[24] Y. Gryaditskaya, F. Ha´hnlein, C. Liu, A. Sheffer, and A. Bousseau. Lifting freehand conceptsketches into 3d. ACM Transactions on Graphics (Proc. SIGGRAPH Asia), 39, 12 2020. →pages xi, 15, 1660[25] X. Hilaire and K. Tombre. Robust and Accurate Vectorization of Line Drawings. IEEETransactions on Pattern Analysis and Machine Intelligence, 28(6):890–904, 2006. URLhttps://hal.inria.fr/inria-00000394. → pages x, 6, 7[26] H. Huang, E. Kalogerakis, E. Yumer, and R. Mech. Shape synthesis from sketches viaprocedural models and convolutional networks. IEEE Transactions on Visualization andComputer Graphics, 23(8):2003–2013, 2017. → pages xi, 16, 17[27] E. Iarussi, D. Bommes, and A. Bousseau. Bendfields: Regularized curvature fields fromrough concept sketches. 34(3), May 2015. ISSN 0730-0301. doi:10.1145/2710026. URLhttps://doi.org/10.1145/2710026. → page 14[28] T. Igarashi, S. Matsuoka, and H. Tanaka. Teddy: A sketching interface for 3d freeformdesign. volume 99, pages 409–416, 01 1999. doi:10.1145/311535.311602. → pagesxi, 11, 20, 21[29] A. L. Jeremy Siek, Lie-Quan Lee. The boost graph library, 2020.https://sourceforge.net/projects/boost/files/. → pages 3, 54, 55[30] A. Jin, Q. Fu, and Z. Deng. Contour-based 3d modeling through joint embedding of shapesand contours. Symposium on Interactive 3D Graphics and Games, 2020. → pages 16, 19[31] S. G. Johnson. The nlopt nonlinear-optimization package, 2020.http://github.com/stevengj/nlopt. → pages 2, 35, 36, 54[32] G. Kanizsa. Organization in Vision: Essays on Gestalt Perception. Praeger Publishers, 1979.→ page 8[33] M. Kazhdan and H. Hoppe. Screened poisson surface reconstruction. ACM Trans. Graph., 32(3), July 2013. ISSN 0730-0301. doi:10.1145/2487228.2487237. URLhttps://doi.org/10.1145/2487228.2487237. → page 15[34] I. K. Kazmi, L. You, and J. Zhang. A survey of sketch based modeling systems. 2014 11thInternational Conference on Computer Graphics, Imaging and Visualization, pages 27–36,2014. → page 5[35] D. C. Knill. Perception of surface contours and surface shape: from computation topsychophysics. J. Opt. Soc. Am. A, 9(9):1449–1464, Sep 1992.doi:10.1364/JOSAA.9.001449. URL http://josaa.osa.org/abstract.cfm?URI=josaa-9-9-1449.→ pages 2, 25[36] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deepconvolutional neural networks. In P. L. Bartlett, F. C. N. Pereira, C. J. C. Burges, L. Bottou,and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26thAnnual Conference on Neural Information Processing Systems 2012. Proceedings of ameeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages 1106–1114,2012. URL http://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks. → page 17[37] C. Li, H. Pan, Y. Liu, X. Tong, A. Sheffer, and W. Wang. Bendsketch: Modeling freeformsurfaces through 2d sketching. ACM Trans. Graph., 36(4), July 2017. ISSN 0730-0301.doi:10.1145/3072959.3073632. URL https://doi.org/10.1145/3072959.3073632. → pagesxi, 13, 1561[38] C. Li, H. Pan, Y. Liu, A. Sheffer, and W. Wang. Robust flow-guided neural prediction forsketch-based freeform surface modeling. ACM Trans. Graph. (SIGGRAPH ASIA), 37(6):238:1–238:12, 2018. doi:https://doi.org/10.1145/3272127.3275051. → pages xi, 16, 19, 20[39] C. Liu, E. Rosales, and A. Sheffer. Strokeaggregator: Consolidating raw sketches intoartist-intended curve drawings. ACM Transaction on Graphics, 37(4), 2018.doi:10.1145/3197517.3201314. → pages x, 10, 15[40] Z. Lun, M. Gadelha, E. Kalogerakis, S. Maji, and R. Wang. 3d shape reconstruction fromsketches via multi-view convolutional networks. In 2017 International Conference on 3DVision (3DV), 2017. → pages 14, 16, 18[41] P. Mamassian and M. S. Landy. Observer biases in the 3d interpretation of line drawings.Vision Research, 38(18):2817 – 2832, 1998. ISSN 0042-6989.doi:https://doi.org/10.1016/S0042-6989(97)00438-0. URLhttp://www.sciencedirect.com/science/article/pii/S0042698997004380. → pages 2, 25, 28[42] MATLAB Optimization Toolbox. Matlab optimization toolbox, R2018b. The MathWorks,Natick, MA, USA. → page 45[43] H. Nord and E. Chambe-Eng. Qt: cross-platform application and ui framework, 2020.https://www.qt.io/. → pages 3, 54[44] G. Noris, D. Sy´kora, A. Shamir, S. Coros, B. Whited, M. Simmons, A. Sorkine-Hornung,M. Gross, and R. Sumner. Smart scribbles for sketch segmentation. Computer GraphicsForum, 31, 12 2012. doi:10.1111/j.1467-8659.2012.03224.x. → page 9[45] G. Noris, A. Hornung, R. W. Sumner, M. Simmons, and M. Gross. Topology-drivenvectorization of clean line drawings. ACM Trans. Graph., 32(1), Feb. 2013. ISSN0730-0301. doi:10.1145/2421636.2421640. URL https://doi.org/10.1145/2421636.2421640.→ pages x, 8, 9[46] P. Olivier, R. Chabrier, D. Rohmer, E. Thoisy, and M.-P. Cani. Nested explorative maps: Anew 3d canvas for conceptual design in architecture. Computers & Graphics, 82, 05 2019.doi:10.1016/j.cag.2019.05.027. → pages xi, 11, 22, 23[47] N. Otsu. A threshold selection method from gray-level histograms. IEEE Transactions onSystems, Man, and Cybernetics, 9(1):62–66, 1979. → page 5[48] D. Perkins. Cubic corners, oblique views of pictures, the perception of line drawings ofsimple space forms. geometry and the perception of pictures: Three studies. technical reportno. 5. 1971. → page 12[49] T.-A. Pham, M. Delalandre, S. Barrat, and J.-Y. Ramel. Accurate junction detection andcharacterization in line-drawing images. Pattern Recognition, 47(1):282 – 295, 2014. ISSN0031-3203. doi:https://doi.org/10.1016/j.patcog.2013.06.027. URLhttp://www.sciencedirect.com/science/article/pii/S0031320313002793. → page 8[50] J.-Y. Ramel, N. Vincent, and H. Emptoz. A coarse vectorization as an initial representationfor the understanding of line drawing images. pages 48–57, 08 1997.doi:10.1007/3-540-64381-8 38. → page 662[51] O. Ronneberger, P. Fischer, and T. Brox. U-net: Convolutional networks for biomedicalimage segmentation. In N. Navab, J. Hornegger, W. M. Wells, and A. F. Frangi, editors,Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015, pages234–241, Cham, 2015. Springer International Publishing. ISBN 978-3-319-24574-4. →pages 18, 19[52] N. Rubin. The role of junctions in surface completion and contour matching. Perception, 30(3):339–366, 2001. doi:10.1068/p3173. URL https://doi.org/10.1068/p3173. PMID:11374204. → page 8[53] S. Rusinkiewicz and M. Levoy. Efficient variants of the icp algorithm. In Proceedings ThirdInternational Conference on 3-D Digital Imaging and Modeling, pages 145–152, 2001. →page 15[54] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy,A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei. Imagenet large scale visual recognitionchallenge. Int. J. Comput. Vision, 115(3):211–252, Dec. 2015. ISSN 0920-5691.doi:10.1007/s11263-015-0816-y. URL https://doi.org/10.1007/s11263-015-0816-y. → page17[55] C. Shao, A. Bousseau, A. Sheffer, and K. Singh. Crossshade: Shading concept sketches usingcross-section curves. ACM Trans. Graph., 31(4), July 2012. ISSN 0730-0301.doi:10.1145/2185520.2185541. URL https://doi.org/10.1145/2185520.2185541. → pagesiii, iv, ix, xii, xiii, 1, 2, 4, 13, 24, 25, 26, 27, 30, 38, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 57[56] P. Shilane, P. Min, M. Kazhdan, and T. Funkhouser. The Princeton shape benchmark. InShape Modeling International, June 2004. → page 20[57] E. Simo-Serra, S. Iizuka, K. Sasaki, and H. Ishikawa. Learning to simplify: Fullyconvolutional networks for rough sketch cleanup. ACM Trans. Graph., 35(4), July 2016.ISSN 0730-0301. doi:10.1145/2897824.2925972. URLhttps://doi.org/10.1145/2897824.2925972. → page 9[58] E. Simo-Serra, S. Iizuka, and H. Ishikawa. Mastering sketching: Adversarial augmentationfor structured prediction. 37(1), Jan. 2018. ISSN 0730-0301. doi:10.1145/3132703. URLhttps://doi.org/10.1145/3132703. → page 10[59] J. Song, F. Su, J. Chen, and S. Cai. A knowledge-aided line network oriented vectorisationmethod for engineering drawings. Pattern Anal. Appl., 3:142–152, 06 2000.doi:10.1007/s100440070019. → pages x, 7[60] J. Song, F. Su, C.-L. Tai, and S. Cai. An object-oriented progressive-simplification-basedvectorization system for engineering drawings: Model, algorithm, and performance. PatternAnalysis and Machine Intelligence, IEEE Transactions on, 24:1048– 1060, 09 2002.doi:10.1109/TPAMI.2002.1023802. → page 7[61] K. A. Stevens. The visual interpretation of surface contours. Artif. Intell., 17(1–3):47–73,Aug. 1981. ISSN 0004-3702. doi:10.1016/0004-3702(81)90020-5. URLhttps://doi.org/10.1016/0004-3702(81)90020-5. → pages 2, 24, 25, 27, 28[62] K. Svanberg. A class of globally convergent optimization methods based on conservativeconvex separable approximations. SIAM Journal on Optimization, 12:555–573, 01 2002.doi:10.1137/S1052623499362822. → page 3663[63] C.-H. Teh and R. T. Chin. On the detection of dominant points on digital curve. PatternAnalysis and Machine Intelligence, IEEE Transactions on, 11:859 – 872, 09 1989.doi:10.1109/34.31447. → page 8[64] A. Tompkins. The boost uuid library, 2006. https://sourceforge.net/projects/boost/files/. →page 55[65] A. Vaxman, M. Campen, O. Diamanti, D. Panozzo, D. Bommes, K. Hildebrandt, andM. Ben-Chen. Directional field synthesis, design, and processing. Computer GraphicsForum, 35(2):545–572, May 2016. ISSN 0167-7055. doi:10.1111/cgf.12864. → page 8[66] B. Xu, W. Chang, A. Sheffer, A. Bousseau, J. McCrae, and K. Singh. True2form: 3d curvenetworks from 2d sketches via selective regularization. Transactions on Graphics (Proc.SIGGRAPH 2014), 33(4), 2014. doi:2601097.2601128. → pages xi, 13, 20, 4164
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Improved normal estimation from cross-section drawings
Text