FlowShape: 3D Concept Modeling from Single-View Design Sketches by Baoxuan Xu Dual B. S. in Computer Science, Zhejiang University and Simon Fraser University, 2011 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Computer Science) The University Of British Columbia (Vancouver) April 2013 c Baoxuan Xu, 2013 Abstract This work presents an automatic creation of 3D models from single view design sketches. We observe that these sketches typically employ networks of trim curves and cross-sections to convey shape. Combined together these curves define the representative flow-lines of the model, reflecting principal curvature and feature lines across the target surface. Artists design these lines to serve as a visual proxy of the 3D object and to effectively convey all surface details. Cross-sections, in particular, are known to impose a set of geometric constraints on the imagined surface, that help position the surface in 3D. We formulate the problem of reconstructing believable 3D curve geometry from design sketches via an optimization framework that leverages the geometric properties of flow-line networks, the constraints imposed by cross-section curves, and observations on how people perceive and sketch such networks. This algorithm utilizes these criteria to simultaneously construct the 3D curves and correct for inevitable inaccuracies in free-hand sketches, which if retained would hinder constraint satisfaction and may lead to noticeable artifacts in the reconstructed 3D models. We validate our framework by producing believable 3D curve networks and surfaces from design sketches based on cross-section and trim curves, conducting a qualitative comparison to artist-estimated models, and visual validation by designers. ii Preface The interface in Chapter 5 was mainly developed by Dr. Adrien Bousseau, Cloud Shao and James McCrae. The algorithm in this thesis were mostly developed by myself and discussed with Dr. Alla Sheffer, Dr. Karan Singh and Dr. Adrien Bousseau. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Design sketching and sketch interpretation. . . . . . . . . . . . . 5 2.2 3D Sketching based modeling. . . . . . . . . . . . . . . . . . . . 5 2.2.1 Multi-view . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Single-view . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Cross-section curves and flow-lines. . . . . . . . . . . . . . . . . 8 2.4 Constraint based 3D model inference from informative views. . . 10 Properties of Sketched Curve Networks . . . . . . . . . . . . . . . . 12 3.1 Conjugacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Minimal variation . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Input approximation . . . . . . . . . . . . . . . . . . . . . . . . . 14 3 iv 4 Reconstructing 3D Curve Networks . . . . . . . . . . . . . . . . . . 15 4.1 Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1.1 Cross-section characteristics . . . . . . . . . . . . . . . . 16 4.1.2 Local symmetry . . . . . . . . . . . . . . . . . . . . . . 17 4.1.3 Curve conjugacy . . . . . . . . . . . . . . . . . . . . . . 18 4.1.4 Minimal variation . . . . . . . . . . . . . . . . . . . . . . 19 4.1.5 Input approximation . . . . . . . . . . . . . . . . . . . . 21 4.1.6 Combined functional . . . . . . . . . . . . . . . . . . . . 21 Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.1 Step I: cross-section scaffold . . . . . . . . . . . . . . . . 22 4.2.2 Step II: curve details . . . . . . . . . . . . . . . . . . . . 24 4.2.3 Regularization . . . . . . . . . . . . . . . . . . . . . . . 25 4.2.4 Disconnected networks . . . . . . . . . . . . . . . . . . . 26 5 User Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 7.1 Dependency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 7.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 8 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2 v List of Figures Figure 1.1 Designers commonly use visible and hidden cross-section and trim curves to convey shape variations in a sketch. c [ES08] . 3 Figure 2.1 This shows an example produced from Teddy c [IMT99] . . . 6 Figure 2.2 Gingold et al. [GIZ09]’s modeling process . . . . . . . . . . . 7 Figure 2.3 Schmidt et al. [SKSK09]’s tool . . . . . . . . . . . . . . . . . 8 Figure 2.4 Andre et al. [ASN07]’s reconstruction of lines . . . . . . . . 9 Figure 2.5 Andre and Saito [AS11]’s reconstruction algorithm . . . . . . 9 Figure 2.6 Shao et al.[SBSS12]’s algorithm . . . . . . . . . . . . . . . . 10 Figure 3.1 On a typical principal curvature network, quad corners are expected to form near-planar quadrilaterals. . . . . . . . . . . . 13 Figure 3.2 Two different views of a sketch of a saddle. . . . . . . . . . . 14 Figure 4.1 Our algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Figure 4.2 Curve network with corresponding cross-section B´ezier segments and control points (blue) and polygons (dashed lines). . 17 Figure 4.3 Three types of quad configurations we aim to co-planarize . . 18 Figure 4.4 Effect of the conjugacy term on a reconstructed four-sided cycle 19 Figure 4.5 Tracing the curves on a coarse artist sketch . . . . . . . . . . 27 Figure 6.1 User study . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Figure 6.2 Several abstract and real shapes reconstructed with FlowShape 31 Figure 6.3 Reconstructions of the evaluation study models. . . . . . . . . 32 vi Figure 8.1 Result of a guitar sketch . . . . . . . . . . . . . . . . . . . . 37 Figure 8.2 Result of a racecar sketch . . . . . . . . . . . . . . . . . . . . 37 Figure 8.3 Result of a iron sketch . . . . . . . . . . . . . . . . . . . . . 38 Figure 8.4 Result of a quarter of a ring sketch . . . . . . . . . . . . . . . 38 Figure 8.5 Result of a sewing machine sketch . . . . . . . . . . . . . . . 39 Figure 8.6 Result of a spoon, cup and fork sketch . . . . . . . . . . . . . 40 vii Acknowledgments I owe my deepest gratitude to my supervisor, Dr. Alla Sheffer, for her instructive advice and valuable suggestions on my thesis. I am deeply grateful of her guidance on this research project. Special thanks should also go to my second reader, Dr. Wolfgang Heidrich, who has given me valuable feedback on my thesis. I would also like to express my thanks to my colleagues Dr. Adrien Bousseau, James McCrae and Dr. Karan Singh who have been wonderful collaborators. Special thanks go to Mikhail Bessmeltsev, who helped to generate nice 3D surfaced models for my results. This thesis would not have been possible without their help. Last but not least, this thesis is dedicated to my parents for their endless love throughout my life. viii Chapter 1 Introduction Conceptual design, from the inception of a creative vision to a 3D realization of the mental concept, relies on a variety of sketching techniques. Half a century after the ”Sketchpad” seminal drawing program [Sut64], creating 3D curves and surfaces from design sketches remains a grand challenge in computer graphics. Multi-view sketching systems [IMT99, NISA07, BBS08] leverage 3D graphics capabilities in a “sketch-rotate-sketch” workflow, where users build their model incrementally by drawing 3D strokes over the existing surfaces and making heavy use of camera manipulation to select appropriate sketching viewpoints. Instead, the emerging single-view sketching systems build upon traditional drawing techniques like scaffolds [SKSK09] and annotations [GIZ09] to disambiguate the conversion from 2D to 3D and mimic the traditional paper-based sketching workflow. We adopt this second methodology and propose a novel 3D sketching approach based on two families of curves, trim curves and cross-sections, that artists routinely use to depict shape [ES11, BR11, Gah10]. Combined together these curves define the representative flow-lines of the model [BR11, Gah10] and typically reflect principal curvature and feature lines across the target surface [BWSS12]. Artists design these lines to serve as a visual proxy of the 3D object and effectively convey all surface details [Gah10]. Cross-sections can be seen as a special type of planar flow-lines and are known to impose a set of geometric constraints on the imagined surface, helping to position it in 3D [SBSS12]. Our approach leverages the mathematical properties of cross-sections and other flow lines and combines them with 1 observations on designer choices and user perception of sketched curve networks to formulate the relationships between these 2D networks and the 3D models they represent. This formulation enables believable 3D interpretation of 2D designer sketches, addressing simultaneously the creation of 3D curve networks and the specification of curve cycles forming the model faces to be surfaced. We first consider the geometric properties of designer-drawn networks of crosssection and trim curves and define coherent relationships between them (Chapter 3). We observe that principal curvature lines form conjugate networks over a surface [dC76], thus corners of four-sided cycles in these networks (Figure 3.1) are expected to be near co-planar when the network density is fine enough [LPW+ 06, PAHK07]. Since both trim and cross-section curves are strongly correlated with curvature lines we expect the reconstructed networks to often exhibit similar behavior. Shao et al.[SBSS12] observe that cross-sections, and in particular their intersections, impose a number of geometric constraints on the imagined surface. They use these constraints to estimate surface normals over the sketch and enable 3Dlike shading for presentation renderings. Since shading needs to align with the underlying sketch, they account for the inevitable inaccuracies of human sketching by satisfying these constraints approximately. Since we aim to reconstruct a consistent 3D shape from the sketched curves, we strictly enforce the cross-section constraints to prevent distortions visible when viewing the model from all but the view of the design sketch, correcting the sketches as necessary. We complement these geometric characteristics of cross-sections and flowlines with design recommendations of selecting informative views that minimize foreshortening and disambiguate the drawing [ES11], consistent with the perceptual notion of non-accidental or general viewpoints [NS92]. We deduce from these observations that on design sketches foreshortening and perspective should not significantly alter local relationships between drawing elements, i.e. that rotating the recovered model should not generate “surprises”. We refer to this principle as minimal variation. Combined together, the geometric properties of flow-line networks, the constraints imposed by cross-sections, and the minimal variation principle yield a system of constraints and terms suitable for optimization (Section 4.1). To generate geometrically valid models, we correct 2 Figure 1.1: Designers commonly use visible and hidden cross-section and trim curves to convey shape variations in a sketch. c [ES08] for hand-drawing inaccuracies and approximate perspective by allowing the orthographic projection of the reconstructed 3D curves to deviate from the 2D sketch, balancing input approximation against the other optimized terms. We also incorporate regularization terms that favor common properties of the engineered shapes we target [MZL+ 09, LWC+ 11], such as line-straightness and plane parallelism, over 2D input approximation. We tackle the resulting non-linear optimization problem via a tailored solver that first solves for the cross-section planes, which form the overall scaffold of the model, and then for the individual curve control points (Section 4.2). We demonstrate the effectiveness of our formulation with a single-view sketchbased modeling system. Users of our system can draw visible and hidden crosssection, trim, and silhouette curves generating sketches similar to those commonly made by designers (Figure 1.1) and use layers to build objects composed of multiple parts. We accelerate sketching by allowing users to draw half of a symmetric object and automatically generate the other half. Our single-view approach facilitates the identification of curve cycles to be surfaced since those directly correspond to minimal closed regions bounded by network curves within each layer of the sketch. 3 In summary, our chief contribution is enabling reconstruction of 3D curve networks from single view sketches created with a commonly used 2D drawing technique of employing visible and hidden cross-section and trim curves. Contrary to previous methods, e.g. [SKSK09], our approach does not depend on the order in which curves are drawn and can be used to recover 3D shape from pre-existing sketches. The resulting curve networks and cycles can be easily surfaced with exiting tools [BWSS12]. From a technical standpoint, this paper introduces two contributions: • An explicit mathematical formulation of the relationship between networks of designer-drawn cross-section and trim curves and the 3D geometry they aim to convey. • An algorithm for 3D reconstruction of such networks from, possibly inaccurate, design sketches based on the formulation above. We note that since our method leverages a number of conflicting properties and operates on inaccurate, hand-drawn sketches it does not aim to replace full-blown modeling systems designed to create 3D models precisely conforming to user specifications. Instead, like other sketch-based approaches, it provides an approximate prototype of the 3D shape. Designers can use these prototypes to quickly evaluate and iterate on design alternatives and to communicate with decision makers. When a concept is validated to undergo detailed 3D modeling, our outputs will provide an initial scaffold that designers can further refine. 4 Chapter 2 Related Work This work leverages studies on conceptual design and sketch interpretation and builds on research in 3D curve sketching interfaces, cross-section based sketch manipulation and constraint based 3D model inference from non-accidental views. 2.1 Design sketching and sketch interpretation. Well drawn design sketches effectively convey 3D shapes by relying on a variety of strategies for curve placement and view selection [Pip07, ES08, ES11]. While those strategies are likely linked to human perception of line drawings [Ste81, ML98], no clear consensus exists as to what makes well drawn sketches, and particularly those using cross-section and trim curves, so effective. We leverage observations made by experts in both communities to develop a framework for 3D reconstruction from designer sketches. 2.2 3D Sketching based modeling. Sketch-based modeling has matured over the past two decades. Olsen et al. [OSSJ09] discuss a variety of existing methods. In the following paragraphs, we summarize some of the most relevant previous works. We discuss them separately in two categories since sketching interfaces can be roughly described as based on a singleview or a multi-view metaphor. 5 Figure 2.1: This shows an example produced from Teddy c [IMT99] 2.2.1 Multi-view Using multi-view tools, artists sketch strokes from different viewpoints onto existing 3D geometry [IMT99, NISA07]. Teddy [IMT99] is a sketching system that can generate 3D polygonal surface from freeform strokes by users interactively. Users can perform operations such as creation, rotating, painting, and extrusion. It constructs 3D polygonal surface from a silhouette curve by inflating the silhouette. The key idea is that it “ inflates a contour by pushing vertices away from the chordal axis according to their distance from the contour” [OSSJ09]; see Figure 2.1 for a typical result. FiberMesh [NISA07] provides an interface that allows users to draw arbitrary 3D curves and then constructs smooth surface automatically by a real-time nonlinear optimization. Similarly to Teddy [IMT99] the system includes a variety of operations such as add, remove and deform curves to control the geometry. Using multi-view tools, artists can also use strokes from one view to define transient 3D construction surfaces onto which strokes from other views are projected. ILoveSketch [BBS08] is one such 3D curve sketching system that provides professional designers an interface to interact directly on concept 3D curve models and users can rotate the view to improve the sketchability. Multi-view sketching tools thus aim to combine the fluidity of sketching with a typical 3D CAD modeling workflow. 6 Figure 2.2: Gingold et al. [GIZ09]’s modeling process on an image ([Kako 1973]). c [GIZ09] 2.2.2 Single-view Our work is more in line with single-view sketching, which mimics the traditional workflow of sketching on paper [GIZ09, SKSK09]. Gingold et al. [GIZ09] created a system designed for casual users to generate 3D modeling of free-form surfaces from 2D sketches. They use primitives (generalized cylinders and ellipsoids with cross-sections) with dynamic handles to control the shape, placement, and orientation and use annotations to describe geometric relationships between these shapes. Users place primitives and annotations over the image, then tilt the cross-sections to lifts a shape out of the plane. Figure 2.2 shows the process. Since they use the two existing primitives therefore the application is limited in the set of geometries it can create. They cannot model surfaces with sharp features or relatively flat surfaces. In contrast, our algorithm is not limited to predefined primitives and can deal with flat surfaces and sharp features such as edges and corners . Schmidt et al. [SKSK09] describe an approach for inferring 3D curves by using the analytic drawing rules and a linear 3D scaffold. Their method is based on perspective drawings and relies on extensive scaffold construction and incremental top-down sketching order. Figure 2.3 shows an overview of their approach. The drawback is that it requires the user to correctly draw the scaffold first before drawing the actual sketch. Our approach is similar in spirit but is order-independent and 7 Figure 2.3: Schmidt et al. [SKSK09] first construct scaffold (a) from input strokes. Then 3D features lines (b) can be produced from the scaffold constraints. c [SKSK09] requires no scaffold. Users can draw any of the curves in any order without specifying any scaffold. Our system builds upon a families of curves ubiquitous in conceptual design [ES08]. Figure 1.1 illustrates typical sketches that we target, where designers draw visible and hidden cross-sections as well as trim curves that demarcate intersections of adjacent smooth surfaces. We show that these curves provide sufficient information to recover plausible 3D curve networks from a single sketch, with minimal annotation and with tolerance to sketch inaccuracy. 2.3 Cross-section curves and flow-lines. Several sketch-based systems rely on cross-sections as a modeling primitive. Andre et al. [ASN07] use a grid of orthogonal geodesics (a special subset of cross-sections) to generate relief-like 3D surfaces. In their work they infer the depth information from two perpendicular planar curves (backbone strokes) and then propagate the 3D reconstruction of the curves in the same group of backbone by projecting them to the planes orthogonal to the backbone. Figure 2.4 shows the approach. The system can only construct satisfying surfaces that are close to a plane, or a cylinder and is not able to model objects of spherical topology. Our work can construct much more complex model such as the iron (Figure 8.3) and 8 Figure 2.4: Andre et al. [ASN07] reconstruct the object from two groups of 3D hatching lines. Each group is created by projecting the backbone stroke to the orthogonal planes. c [ASN07] Figure 2.5: Andre and Saito [AS11] build a a cubic corner by two construction lines(green and blue) and two possible intersections(black), then sweep one of the construction line along the other one with the restriction of the silhouette line(in red) to construct the 3D object. c [AS11] sewing machine (Figure 8.5). Andre and Saito [AS11] use two major orthogonal cross-sections to construct ellipsoids as basic elements to model 3D models. They use a similar approach to [ASN07] to recover 3D of two construction lines (perpendicular planar curves) from the 2D sketch. Then they reconstruct the 3D volume of the sketch by sweeping one of the construction line along the other one guided by the silhouette line. Figure 2.5 demonstrates the reconstruction algorithm. Our work considers a much more general scenario, using networks of general designer-specified cross-sections and trim curves as modeling input. Shao et al. [SBSS12] outline a set of constraints that intersecting cross-sections are meant to satisfy, and use those to estimate normals at these intersections, and then propagate them across the sketch to generate normal fields suitable for shading 9 Figure 2.6: With an annotated input (a), Shao et al.[SBSS12]’s algorithm first builds the supporting plane of each cross-section (b) and then propagates the normals (c) to obtain the normal map (d) for shading (e). c [SBSS12] sketches. Figure 2.6 shows the overview of their algorithm. However, their goal implies drastically different requirements than ours. First, shading needs to align with the input sketch and its distortions, while 3D reconstruction aims at estimating the consistent shape that the sketch represents. As a result, while CrossShade is designed to tolerate sketch inaccuracies, we design our method to correct for them. Second, our goal is to reconstruct the complete network of curves drawn by designers, while it is sufficient for CrossShade to only recover 3D information at cross-section intersections. For these reasons, our formulation complements the mathematical properties of curve intersections with geometric cues provided by the sketch as a whole, which allows our method to recover plausible 3D models and to correct for inaccuracies inherent to the sketching process. Bessmeltsev et al. [BWSS12] make several valuable observations linking artistdrawn curve networks with surface flow- and curvature- lines and use those to surface input 3D curve networks. As they state “flow-lines are strongly correlated to sharp features and lines of curvature on a surface, but that these flow-lines also allow for artistic license at surface discontinuities over fine details and in umbilic regions.” [BWSS12] Our method adopts some of their observations to perform the necessary, earlier step of converting a 2D sketch into a 3D curve network. 2.4 Constraint based 3D model inference from informative views. Automatic line drawing interpretation aims to reconstruct shapes from silhouette and other feature lines [Coo08], a challenging and often ill-posed task [Mal87]. In10 spired by research in computer vision, e.g. [Low87], Lipson and Shpitalni [LS96] and subsequent work [MKL05, LFG08, LSMI10] use geometric constraints such as orthogonality and parallelism to estimate 3D models from engineering drawings. By interpreting regularity relationships observed in the image such as parallelism, perpendicularity and symmetry, Lipson and Shpitalni [LS96] optimize an energy function to calculate the depths of vertices and reconstruct 3D object from a 2D drawing. Their optimization mainly estimates how well the 3D shape satisfies the 2D image regularity relationships and works well for mechanical drawings. Masry et al. [MKL05] presented a pen-based sketching system for progressively constructing 3D objects from single view freehand sketches. They first extract straight lines from the sketch and use them to determine a 3D coordinate system. They then calculate the depth of each vertex using the sketch connectivity graph. By assuming planarity of curved strokes, they recover the 3D coordinates of these strokes and finally build the faces of the 3D objects. With focus on architectural drawings, Lee et al. [LFG08] improves the approach of [LS96] by constructing planar polygonal models from sketches that do not contain hidden lines. Their algorithm can handle sketches with perspective view. Lau et al. [LSMI10] introduced another extension of Lipson and Shpitalni ’s algorithm [LS96]. They use a two-step optimization process where they first find an estimated solution of depth for each vertex satisfying the annotated geometric constraints and then optimize for geometric and projection constraints to get the 3D positions for all vertices. These methods assume that the 3D models are dominated by straight edges and planar curves, and as such, focus on polygonal models with limited curved surfaces. We draw inspiration from this body of work and incorporate similar concepts into our formulation, such as (1) straight lines in 2D are interpreted as straight lines in 3D, (2) lines parallel in 2D are interpreted as parallel in 3D, (3) coincident lines are interpreted as coincident in 3D. We further refine them to account for specific properties of cross-section and trim curve networks, a priori positioned to best convey shape, and use this formulation to recover the 3D curved shapes common in design sketches. 11 Chapter 3 Properties of Sketched Curve Networks Chapter 1 introduced the three major properties of 3D curve networks reconstructed from design sketches that we propose to leverage to facilitate reconstruction: conjugacy, minimal variation, and input approximation. We now elaborate on each of those identifying the basis for our observations. 3.1 Conjugacy Numerous sources indicate a strong correlation between designer-drawn curves and curvature lines. Perception studies indicate that observers interpret intersecting curves as aligned with the principal lines of curvature [Ste81, ML98], when the global context allows for it. Design books recommend the use of cross-sections to “explain or emphasize curvature” [ES08](p.136). Other design texts similarly emphasize the use of representative surface flow-lines in depicting shape [BR11, Gah10]. While there is no precise mathematical definition of flow-lines, design and modeling references [Gah10, BWSS12] suggest that sketched flow-lines are often aligned with sharp features and lines of curvature. Principal lines of curvature form a conjugate network of curves over the surface [dC76]. As observed by [PAHK07, LPW+ 06] the corners of four-sided regions formed by intersecting conjugate curves are expected to be close to coplanar when the network is sufficiently 12 Figure 3.1: On a typical principal curvature network, quad corners are expected to form near-planar quadrilaterals. dense (see Figure 3.1). These observations lead us to optimize corner co-planarity at several granularity levels as the main tool for communicating 3D information between network curves. To account for global context, we balance conjugacy with other geometric cues. 3.2 Minimal variation Design books recommend to use viewpoints that “optimize shape information” and instruct designers to minimize foreshortening over most faces of the object [ES11, p.56]. This recommendation is consistent with the perceptual notion of general or non-accidental viewpoints [NS92, Mat08] that suggests that observers interpret 2D geometric properties as correlated with 3D properties rather than being due to a particular choice of viewpoint. For example, people interpret the top drawing in the Figure 3.2 as a flat ellipsoid, while a non-accidental viewpoint reveals that it is a saddle. We deduce from these observations a minimal variation principle: since the 2D curves are drawn so as to reveal maximal information, the amount of 3D information not evident from the 2D drawing should be minimal. Following the advice from [ES11] we speculate that the inevitable 2D/3D distortion should be evenly distributed when possible. This principle has two main implications on our algorithm. First, we conclude that the degrees of freedom provided by the control points of the 2D curves should be enough to capture all the complexity of their 3D 13 Accidental Non-accidental Figure 3.2: Two different views of a sketch of a saddle. interpretation. A corollary of this property is that a curve that is continuous in 2D should correspond to a continuous curve in 3D, as relaxing continuity introduces unexpected degrees of freedom. The second implication is that the curvature, or shape, of the 2D curves should as much as possible reflect their curvature in 3D. A corollary of this observation, often used explicitly in scene analysis [LS96, Low87] is that straight line segments in 2D should correspond to straight segments in 3D. We express this property as a shape-preserving term in our 2D to 3D conversion. While shape is unlikely to be fully preserved, we aim to minimize the change and distribute it across the 3D model. 3.3 Input approximation To satisfy the geometric constraints enforced by cross-sections (Chapter 4, [SBSS12]) and improve adherence to the properties discussed above, we must allow the 2D re-projection of the reconstructed curves to deviate from the exact input curves. Following the minimal variation principle we aim to minimize changes in curve shape while allowing for greater drift in absolute curve location. While artists often use perspective in their drawings, it is both subtle and inaccurate [SKKS09]. In our setup we therefore assume near-orthographic projection and expect the reconstructed 3D curves to project near the original ones. 14 Chapter 4 Reconstructing 3D Curve Networks Given a network of 2D curves annotated as cross-sections or trim curves, the goal of our algorithm is to estimate the 3D coordinates of each curve (Figure 4.1). While the raw user input contains silhouettes on smooth surfaces, we ignore those, as they do not reflect actual shape features and are often poorly drawn. The network can consist of multiple layers (Figure 4.1a, the curves are in 3 different layers indicated by rectangles of dashed lines, Chapter 5). Setup: We represent curve segments as piecewise cubic (4-point) B´ezier splines, since designers are trained to draw using smooth inflection-free strokes and breakup undulating curves with intersecting curves (inset) [BBS08]. Cubic B´eziers capture such curve segments adequately and further reduce our problem to one of estimating the 3D position of each control point, in keeping with the minimal variation principle discussed in Chapter 3. We thus parameterize input curves to have a 4-point curve segment between each network intersection, while allowing for a minimum number of additional control points, if necessary, to accurately capture the sketched 2D geometry (Figure 4.2). We explicitly enforce all 2D network intersections on the same layer to remain such in 3D. The chosen parameterization simplifies this task, and also avoids unnecessary unknowns. 15 (a) Input curves (b) Cross-section planes (c) 3D curves satisfying geometric and design properties (d) Surfaced model Figure 4.1: Algorithm: Given an annotated sketch containing front and back facing layers (a) we proceed to first recover the cross-section planes (b) and then the 3D curves that satisfy geometric and design properties (c). Dashed lines represent the original curves. The reconstruction is completed by mirroring the curves that can then be surfaced using [BWSS12]. 4.1 Formulation Our formulation is based on the curve network properties discussed in Chapter 3 and uses mandatory cross-section characteristics [SBSS12] as a scaffold serving to lift the entire curve network into 3D. In theory most of these properties should be optimized using outlier-robust norms, ones that allow for exceptions to each rule. However, to obtain a formulation that can be reliably and efficiently solved, we use L2 norm throughout and perform several other approximations. 4.1.1 Cross-section characteristics We express cross-section planarity for a curve c consisting of B´ezier segments B i by constraining all their control points Bik (Figure 4.2) to satisfy the same plane equation Bik · nc + d c = 0, 16 (4.1) Bj Bi Bh B1j B2j B0j Bk B2 h B1h B2 i B1i B3i =B3j =B0h = B0k B k 1 B0i (a) Bézier segments B3h B2k B3k (b) Control points (c) Input with control points Figure 4.2: Curve network with corresponding cross-section B´ezier segments and control points (blue) and polygons (dashed lines). where nc and d c are the unknown plane normal and offset respectively. To reduce the number of unknowns, we set the z component of each normal to 1 instead of enforcing normals to be unit length. This renormalization is possible as long as no cross-section plane is perpendicular to the view plane, a property that holds under the general view assumption. For each pair of intersecting cross section curves c and c respectively we enforce orthogonal plane, nc · nc = 0, (4.2) and orthogonal tangent constraints [SBSS12]. The tangents at the end points of a B´ezier curve are simply the vectors to the adjacent control points. Assuming the curves intersect at control points Bi0 and B0j respectively, we express tangent orthogonality as (Bi1 − Bi0 ) · (B1j − B0j ) = 0. 4.1.2 (4.3) Local symmetry Designers often draw geodesic cross-section curves, i.e. curves that serve as local symmetry planes. If the cross-section curve c defines the local symmetry plane at an intersection with another curve c then the tangent of c at this intersection must be collinear with the normal nc [SBSS12], Csym (c, c ) = nc × (B1j − B0j ) = 0. (4.4) Unless manually specified, we do not know a priori which planes are symmetry planes, either locally or globally. Enforcing or even optimizing symmetry for non17 P1 P2 P0 P3 (a) Four-sided patch P1 P2 P0 P3 (b) Two consecutive corners P2 P1 P3 P0 (c) T-junction Figure 4.3: Three types of quad configurations we aim to co-planarize: (a) corners of four sided cycles; (b) two adjacent corners and their tangents; (c) a t-junction, two cycle corners and a mirrored image of the t-junction. symmetric cross-sections can distort the output. We therefore use soft rather than 2 , and relax these constraints locally hard symmetry constraints, minimizing ∑ Csym when they are not fully satisfied as discussed in section 4.2. The sum only includes cross-section/cross-section intersections, with symmetry at intersections with trim curves handled indirectly via the conjugacy term, described next. 4.1.3 Curve conjugacy We leverage the conjugacy property of principal curvature lines to communicate 3D information between different network curves on multiple granularity levels. On the coarsest level we optimize corner co-planarity over all four-sided curve cycles (Figure 4.3a). We next refine the granularity of the considered cycles, and observe that on a sub-cycle level, the surface curvature lines are expected to evolve smoothly along each principal direction [BWSS12]. We use this observation to relate the geometry of consecutive curves within a cycle. We consider quads formed by two consecutive corners on a curve cycle and the tangents to the first and last participating curves (Figure 4.3b). This quad can be perceived as formed by sweeping the middle curve along the sides generating an intermediate curvature line. We use a similar sweep construction to relate adjacent cycles across t-junctions. The quad is formed by the t-junction, the preceeding or subsequent intersection, the opposite intersection and a fourth point on the opposite side computed to be at the same arc length as the t-junction (Figure 4.3c). 18 No conjugacy With conjugacy Figure 4.4: Effect of the conjugacy term on a reconstructed four-sided cycle (arrow on the left shows point of view for the surface shots). Without conjugacy optimization (center) the curvature flow is diagonal to the patch sides, with the term (right) it is aligned with them. We express corner co-planarity via a linear relation between the corner points P0 , P1 , P2 , P3 : Ccon j (P0 , P1 , P2 , P3 ) = a0 P0 + a1 P1 + a2 P2 + a3 P3 = 0. (4.5) To obtain the four coefficients ai we rely on the minimal variation principle and assume that the quad proportions do not significantly change during reconstruction. We solve for ai that satisfy the above relations for the positions of the four corners in the input 2D sketch, normalizing them to sum to one. We optimize ∑ Ccon j 2 over all the quadruplets discussed above. The terms are normalized by a weight 2 w = e(d/2σ ) + ε, (4.6) where d is the length of the longest diagonal in each quad in 2D, σ is set to 1/3 of the sketch bounding box diagonal and ε = 0.01. The weighting reflects the expectation that smaller quads reflect denser curvature flow sampling and thus are more planar. Figure 4.4 shows the impact of using the conjugacy term on a single four sided cycle. 4.1.4 Minimal variation The minimal variation principle predicts that locally along each curve the shape in 2D should reflect its shape in 3D, with no unexpected changes or “surprises”. 19 Using the B´ezier curve representation this expectation can be restated in terms of the relations between consecutive control points along each curve. To optimize curve continuity and preserve straight lines, two important corollaries of minimal variation, for all sequences of three collinear control points, we minimize Ccol = Bik − (c1 Bik−1 + c2 Bik+1 )/(c1 + c2 ) 2 . (4.7) The coefficients c1 and c2 are set to the inverse of the distances from Bik to Bik−1 and Bik+1 in 2D. In the general case a straight forward approach to express shape similarity is to similarly codify it via 2D/3D similarity of triangles formed by three consecutive control points. Unfortunately this formulation is non-linear and hard to optimize for non-collinear points. B2i B3i =B0h To optimize shape preservation elsewhere B1h B2 h B1i B3h B0i we utilize the barycentric formula introduced in the conjugacy formulation above (Equation 4.5) this time applied to sequences of control points along each curve, linking control points within each quadratic B´ezier segment B i and between adjacent segments B i and B j (red and blue in the inset): Cmv = ∑ a0 Bi0 + a1 Bi1 + a2 Bi2 + a3 Bi3 2 (4.8) i + ∑ (a1 Bi1 + a2 Bi2 + a3 B1j + a4 B2j 2 . i, j skipping collinear points as in the Figure, since for such points the barycentric relationship is ill-defined. The major advantage of this formulation is that it links 2D and 3D curve shape using a linear relationship. Its disadvantage is that this relation holds for any planar reconstruction of the curves. To explicitly indicate the preference for minimally foreshortened reconstructions we combine this term with an explicit minimal foreshortening term C f s = ∑ Bik (z) − Bik+1 (z) 2 . 20 (4.9) Since this term is used to primarily differentiate between near-equal-quality reconstructions it is assigned a minuscule weight and is only optimized at cross-section intersections. To account for uneven sampling density the terms in Cmv and C f s are weighed using the weights in Equation 4.6, where foreshortening d is set to the 2D difference between the control point positions. 4.1.5 Input approximation To minimize re-projection error between the 3D curve network and its 2D counterpart we combine control polygon edge preservation with preservation of control point positions Capp = min ∑ (Bik+1 (x, y) − Bik (x, y)) − i,k (B¯ ik+1 (x, y) − B¯ ik (x, y)) 2 , (4.10) Bik (x, y) − B¯ ik (x, y) 2 , (4.11) Cpos = min ∑ i,k where B¯ ik are the control points of the original 2D curve. The entries in Capp are weighted using Equation 4.6 with d = B¯ i (x, y) − B¯ i (x, y) . The second sum is k+1 k used primarily to anchor the result in 2D. Hence, similar to the minimal foreshortening term it only includes cross-section intersections and is assigned a very small weight when added into the global optimization functional. The flexibility allowed by approximating rather than interpolating the input is best evident in the highly inaccurate stapler sketch, which we manage to convert into a realistic looking stapler by correcting for multiple input inaccuracies (Figure 4.5c). 4.1.6 Combined functional The combined functional assigns equal weights of one to the symmetry, conjugacy and minimal variation terms as all are viewed of equal importance. Since violation of collinearity goes against the general view assumption, we use a higher weight of 10.0 for Ccol . We use a weak weight of 0.01 for foreshortening as we don’t want it to compete with any other terms. The weight of the approximation terms depends on the trust we have in the input accuracy. For all the hand-drawn inputs we used 21 1.0 as the weight of Capp and 0.01 as the weight of Cpos . We increased the weights by a factor of 100 when processing ground truth inputs (Chapter 6). Lastly, the solution using all the terms above is not unique since the result can move arbitrarily along the depth axis. To get a unique solution we add a stabilizer term with weight 0.0001 indicating preference for the 3D curves to lie near the origin of the 3D space: Cstab = min ∑i (d i )2 . 4.2 Solver While our ultimate goal is to estimate the 3D control points for all the network curves, solving for all the unknowns (control points and cross-section planes) at once yields a large non-linear optimization with multiple non-linear constraints (cross-section characteristics). Without a good initial guess, i.e. one that satisfies the constraints we aim to enforce, traditional solvers either fail or take an excessive amount of time to get a solution. We thus require a tailored solver to achieve a solution within a reasonable timeframe. We notice that many of our unknowns are related by the underlying structure of the cross-section network, and observe that when cross-section planes are fixed the entire formulation reduces to a quadratic optimization with linear constraints. We use this observation to derive a two-step algorithm that estimates our solution in a multi-scale fashion, first solving for crosssection planes and then for the remaining variables. 4.2.1 Step I: cross-section scaffold In a first step, we solve for the cross-section planes, cross-section curve intersections and their tangents at these intersections (Figure 4.1b). To make the tangents in Equation 4.3 scale invariant, we express each tangent at an intersection by a separate variable tc , thus removing the locations of the control points adjacent to the intersections from the formulation. We replace the approximation term at intersections Capp (equation 4.10) by tc − t¯c , where t¯ is the 2D tangent normalized to have unit length, and substitute the tangent tc into every term above involving control points adjacent to the intersection. Since at this point we only have a local context, we use high position and approximation weights w pos = wapp = 10 to avoid unnecessary deviation from the 2D sketch. To avoid optimizing symme22 try at non-symmetric cross-sections, we evaluate the individual symmetry terms Csym (equation 4.4) on both the initial guess and the first step solution and discard symmetry terms from the optimization if they are far from satisfied, i.e. the value of Csym is above a given threshold (we use 0.01). If terms are discarded after the first solution we repeat the optimization to obtain a relaxed solution. The objective function is as following: min[w posCpos + wappCapp + w f sC f s + wcon jCcon j + wmvCmv + wsymCsym + wstabCstab ] = min [w pos ∑ Bik (x, y) − B¯ ik (x, y) 2 + Bik ,tki ,ni ,d i i,k wapp ∑ tki − t¯ki 2 + i,k w f s ∑ Bik (z) − Bik+1 (z) 2 + i wcon j ∑ a0 P0 + a1 P1 + a2 P2 + a3 P3 2 + wmv ∑ a0 Bi0 + a1 Bi1 + a2 Bi2 + a3 Bi3 2 + i wsym ∑ ni × tkj 2 + i,k wstab ∑(d i )2 ] i (4.12) with constraints Bik = Bkj , ni · n j = 0 and t i · t j = 0. As mentioned before, w pos = 2 wapp = 10, w f s = 0.01, wsym = 1. For wcon j and wmv we use = e(d/2σ ) + ε, where for wcon j , d is the length of the longest diagonal in each quad in 2D; for wmv , d is the length of the longest line segment of of the 4 points. For both wcon j and wmv , σ is set to 1/3 of the sketch bounding box diagonal and ε = 0.01. The variables that we are solving for are the coordinates of control points at intersections (Bik , described in equation 4.1), tangents tki at intersections, the plane normal ni of each cross-section curve, and the offset d i of the plane of each crosssection curve, where i is the index of the curve and k is the index of the intersection along the curve. Here we use j to indicate the index of the other curve that intersects curve i at intersection k. P0 to P3 are points on cross-section curves that form quad loops, as described in Figure 4.3(a). Bi0 to Bi3 are subsets of Bik that are con23 secutive control points at intersections without any three of them being collinear, as described in the inset of equation 4.8. Coefficients a0 to a3 are calculated from P¯0 (x, y) to P¯3 (x, y), namely the original 2D locations from the 2D sketch. Similarly, the coefficients a0 to a3 are calculated from the B¯ 0 (x, y) to B¯ 3 (x, y). In practice, we substitute Bik for each Bkj wherever there is a constraint Bik = Bkj . The resulting minimization, while remaining non-linear, involves only a fraction of the unknowns as we keep the rest of the control points fixed and can be solved efficiently using standard optimization tools. We use the solution given by Shao et al. [SBSS12] as an initial guess for this step and use the MATLAB implementation of the interior point method to obtain a solution. 4.2.2 Step II: curve details The cross-section planes estimated in the first step form a 3D scaffold for our target 3D curves. In our second step, we fix these planes and optimize for the position of the cross-section control points inside the planes, as well as for the position of the trim curves while keeping the tangents at intersections close to those given by step one by minimizing ∑ (Bi1 − Bi0 ) × t c 2 . The entire minimization looks like following: min[w posCpos + wappCapp + wcon jCcon j + wmvCmv ] = min[w pos ∑ Bik (x, y) − B¯ ik (x, y) 2 + Bik i,k wapp ∑ (Bik+1 (x, y) − Bik (x, y)) − (B¯ ik+1 (x, y) − B¯ ik (x, y)) 2 + (4.13) i,k wcon j ∑ a0 P0 + a1 P1 + a2 P2 + a3 P3 2 + wmv ∑ a0 Bi0 + a1 Bi1 + a2 Bi2 + a3 Bi3 2 ] i with constraint Bik = Bkj . Here we use 1.0 as the weight of Capp and 0.01 as the weight of Cpos . We increased the weights by a factor of 100 when processing ground truth inputs. Other weights remain the same as Step I. The symbols are the same as Step I except for that we are solving for coordinates Bik of all control points of all curves as opposed to only at cross-sections intersection points in Step I. 24 In practice, to avoid the constraint Bik = Bkj we use the same variables for Bik and Bkj . ∑i,k Bik (x, y) − B¯ ik (x, y) 2 is only applied for control points on intersections, and the value B¯ i (x, y) is from the output of Step I. Notice that we have obtained the k tangents at each intersection for each cross-section curve. Thus, if the curve is a cross-section curve, we can express the Bi1 (or Bi2 ) which is next to a cross-section intersection Bi0 (or Bi3 ) via Bi0 + Lt where t is the tangent vector and L stands for the magnitude of the tangent. Therefore, for such control point Bi1 (or Bi2 ) we solve for single scalar value instead of 3D position. Since we have obtained the normal n and offset d from first step, we can express the z coordinate of the control points on cross-section curve via the plane equation (equation 4.1) using x, y coordinates. We may have several disconnected cross-section networks that are connected by trim curves, for which we need to move the entire cross-section networks to make the two networks connected in 3D while satisfying the properties we discussed. To address this issue, we add an offset variable zi to each cross-section networks. To solve for zi we modify the plane equation (equation 4.1) to be (Bik + (0, 0, zi )) · nc + d c = 0. To obtain unique solution for zi of each cross-section network we first group all the cross-section networks that are connected by trim curves. Then in each group we fix one arbitrary cross-section’s network offset to be 0. As the planes are fixed, the optimization problem is reduced to a simple quadratic minimization with linear constraints easily solved via a linear system solve. If desired the problem can be recast as a Gauss-Seidel iteration, re-solving for planes based on the new 2D positions of the control points. However we found this unnecessary. 4.2.3 Regularization While hand-drawn sketches are inexact, the type of models we aim to recover are often highly regular. To regularize the resulting models, we enforce the following structural constraints: (1) straight lines, (2) parallel tangents, and (3) parallel cross-section planes. We detect nearly regular structures, either directly from the sketches (straight lines and parallel tangents) or after full or partial reconstruction (parallel cross-section planes) and enforce them throughout the entire system with 25 additional constraints. Straight lines. To detect straight lines, we evaluate the collinear equation Ccol = Bik − (c1 Bik−1 + c2 Bik+1 )/(c1 + c2 ) 2 for 2D and test it against a threshold (set to be 0.01 in our case). Every collinear triplet of consecutive control points in 2D is deemed collinear in 3D. We enforce straight lines by adding equation Ccol to the minimization in both Step I and Step II with weight 10.0. In the minimization we set c1 and c2 to the value calculated from the original sketch, as we do not want the control points to move a lot. Parallel tangents. If two tangents at adjacent intersections (like the t1 two tangents in the inset) are close to be parallel in 2D, we expect t2 them to be parallel in 3D. To detect parallel tangents we calculate the angles between two neighbor 2D tangents based on the original sketch and test it against a threshold (set to be 10 degrees in our case). We then enforce the parallelism by adding minimization term t1 − t2 2 to both Step I and Step II. Parallel cross-section planes. We first solve for Step I and detect near parallel planes then enforce the parallelism of these planes. To detect parallel cross-section planes we use a standard clustering algorithm with a threshold (set to be 10 degrees in our case). Then we enforce the parallelism by using the same normal variable for all the curves in the same cluster in Step I and solve for Step I again. An example of this feature is the stapler (Figure 4.5) where we detect and enforce parallelism between the horizontal cross-sections in the base and top parts. 4.2.4 Disconnected networks A sketch can contain several disconnected networks of curves, drawn in different layers, e.g. the car in Figure 8.2, which needs to be consistently positioned along the depth axis. Notice that it is different from the disconnected cross-section networks in Step II. The natural assumption in this case is that the output component depths should be as close as possible while avoiding interpenetration and respect26 (a) (b) (c) (d) Figure 4.5: Tracing the curves on a coarse artist sketch (a,b) we are able to automatically construct a realistic mock-up in just a few minutes, plausibly correcting for input inaccuracies (c). ing the layer order. We use a z-buffering like algorithm to obtain these depths. We start with all components at the same depth and for each pair of in-front/behind ones, pull the front component closer to the viewer just enough to avoid intersections. The depth order testing takes into account both 3D curves and interpolating surfaces generated independently for each component, using the surfacing method of [BWSS12]. 27 Chapter 5 User Interface We use standard vector drawing tools to create and annotate the curves, either from scratch or on top of a pre-existing sketch. Curve drawing. Users can draw and mark an entire curve as cross-section, trim or silhouette. In addition, we provide layer annotations to handle occlusions and disconnected networks of curves. Our interface supports per-segment layering to allow users to draw the visible and hidden parts of a cross-section as a single curve. In the case of disconnected networks, we assume that users order the layers according to depth. Finally, we snap multiple intersections together when they are close-by, which often occurs when drawing cubic corners or transitions between visible and hidden segments over a silhouette. We automatically extract the curve cycles from the 2D network of curves by constructing a planar map [GHPvT89] which generates a list of regions bounded by curve segments lying in the same layer. Symmetric models. Many designer shapes contain one or more symmetry planes. It is redundant to ask artists to draw the two or more symmetric portions, especially as doing so in a way that accurately captures the symmetry is far form trivial. Instead we have artists draw only one portion of the model bounded by the symmetry planes and then flip the 3D result around the plane. We strictly enforce the symmetry constraints (Equation 4.4) at all intersections of the symmetry plane. 28 Chapter 6 Evaluation To evaluate our hypotheses and solution, we designed a set of 3D curve networks as ground truth data (Figure 6.1, left column). These models capture the variety in the curve geometry of real-world design sketches with shapes ranging from straight lines (seat and wrinkle), circular arcs (revolve), inflections (seat and cross) and highly non-planar trim curves (saddle). One of the models (cross) has several disconnected cross-section networks. We then picked typical generic views for these models as input sketches for our algorithm, which successfully constructed a 3D curve network for each input. We first validated our input sketches as ground truth data by testing that they were meaningfully and consistently perceived by artists. We did this by asking two artists to draw orthogonal views to the given sketch as they imagined it using any construction lines or other drawing aids. While one artist commented that drawing orthogonal to a non-canonical viewpoint was somewhat cumbersome, both produced meaningful sketches that qualitatively matched the input 3D data in orthogonal views (see Figure 6.1). We also asked a trained 3D modeler to use the input sketches as a visual reference to model the perceived shapes using traditional CAD software. We note that qualitatively, ground truth, 3D modeler output, user sketches and our algorithmic output, are visually similar in the views orthogonal to the input sketch (see Figure 6.1). Of relevance to our solution was the validation of the minimal variation principle in that straight 2D lines were perceived as straight 3D 29 seat revolve wrinkle saddle cross Figure 6.1: The curves in the extreme left column (ground truth) are shown to artists as the input sketch. The other columns show a view orthogonal to the sketch to illustrate perceived depth. From left to right we show ground truth curves, artist modeled 3D surfaces, alternate view curves sketched by two artists and our algorithmic output (green). lines, and the general shape of the curve, such as the number of inflections in 2D was preserved in 3D. Finally, we asked the 3D modeler to subsequently view the ground truth data and our algorithmic result alongside his creations interactively in 3D and comment on them. He pointed out that our algorithmic cross-sections on the revolve sketch were elliptical rather than circular and that our seat was not as flat as a seat should be. Both of these observations were ramifications of high-level shape recognition that we do not address. Summarily however, he felt that all three 30 Figure 6.2: Several abstract and real shapes reconstructed with FlowShape. The toothpaste and box are inspired by the sketches in Figure 2. forms of output captured the essence of the shape intended by the input sketch and would make worthy 3D mock-ups for conceptual design. Arguably however, the best form of evaluation is that were are able to construct 3D concept models automatically from complex real-world design sketches (see Figures 8.1, 8.2, 8.3, 8.4, 8.5, and 8.6). 31 Figure 6.3: Reconstructions of the evaluation study models. 32 Chapter 7 Implementation Our system is mainly implemented in C++. To solve the optimization we use the MATLAB implementation of the interior point method. 7.1 Dependency Our system utilizes several libraries. Following is the list of dependency: • Eigen [GJ+ 10], for matrix related operations, as well as linear solver • Openexr [MI13], for image related operations • libQGLViewer [lib13], to ease the creation of OpenGL 3D viewers • NLopt [Joh13], a C++ based non-linear optimization library • QT [Dig13], a GUI framework • MATLAB [Inc1a], to solve the non-linear optimization library with interior point method • Cloud Shao’s code [SBSS12], as code base for the UI system 7.2 Performance Our system is currently at research stage, so it is not fully optimized for performance. Also it is not yet a standalone application as it still uses MATLAB for the 33 first step of solving. The whole computation takes about 1 minute for a typical input like the sewing machine 8.5. The performance remains as a future work as there is still space to improve with maybe a redesign of data structure. 34 Chapter 8 Results As demonstrated by the results (Figures 4.5, 6.2, 6.3, 8.1, 8.2, 8.3, 8.4, 8.5, and 8.6) our method is able to generate plausible 3D shapes from a wide-range of inputs, from boxy shapes such as the toothpaste or suitcase (Figure 6.2) to complete geometries such as the guitar (Figure 8.1) or the sewing machine (Figure 8.5). These models were sketched using our interface (see Section 5) either from scratch or over existing designer sketches. We are not constrained by sketch topology, and can construct objects comprised of multiple parts (stapler, sewing machine) and with disconnected cross-sections (cross). Our 3D curve networks are also robust to input inaccuracy, deviating as necessary from noisy and inaccurate sketch inputs such as the stapler (Figure 4.5c) to establish the various 3D curve network properties formulated in Section 3. This is a fundamental distinction from 3D sketch rendering [SBSS12] where the sketch itself is immutable and any inaccuracies in the sketch must be absorbed by approximations in the induced 3D normal field. At the same time the method works equally well on exact inputs (Figure 6.3), where to conform to the input we simply increase the weight of Capp by a factor of a hundred. Using the insight that cross-section curves often lie on bilateral symmetry planes of the object, we allow designers to sketch only half (or quarter, see ring Figure 8.4) of the model, by simply labeling some of the curves as defining symmetry in the sketch. The symmetry plane and 3D curves are solved for simultaneously by our algorithm and reflected across the symmetry plane. Visualizing the 35 symmetric half of the sketch in itself is a useful tool for designers in 2D, given that drawing symmetric pairs of curves accurately from arbitrary viewpoints is difficult [SKSK09]. Statistics: We have tested our framework on models with dozens of curves (e.g. sewing machine). Our current bottleneck is the optimization algorithm which takes of the order of a couple of minutes in MATLAB for the larger models and under a minute on simpler ones. The rest of the computation takes seconds to complete. Limitations: Like most research our approach has limitations. Theoretically, we require the existence of meaningful intersecting cross-sections to help define a scaffolding for the 3D curves. While we are able to successfully construct shapes with highly non-planar trims such as the saddle in Figure 6.2, we are unable to process shapes such as the inset helix where one family of curvature lines is highly non-planar. On the practical side our current system is limited by the model complexity that designers can cognitively handle using single-view sketching. Undulating surfaces with more than 2 or 3 levels of occlusion can be cumbersome to both imagine and draw from any single view. 36 Input 2D curves Output 3D curves 3D models with surfaces Figure 8.1: Result of a guitar sketch. The reconstruction is completed by mirroring the curves that can then be surfaced using [BWSS12]. Input 2D curves Output 3D curves 3D models with surfaces Figure 8.2: Result of a racecar sketch. The reconstruction is completed by mirroring the curves that can then be surfaced using [BWSS12]. 37 Output 3D curves Input 2D curves 3D models with surfaces Figure 8.3: Result of a iron sketch. The reconstruction is completed by mirroring the curves that can then be surfaced using [BWSS12]. Input 2D curves Output 3D curves 3D models with surfaces Figure 8.4: Result of a quarter of a ring sketch. The reconstruction is completed by mirroring the curves that can then be surfaced using [BWSS12]. 38 Input 2D curves Output 3D curves 3D models with surfaces Figure 8.5: Result of a sewing machine sketch. The reconstruction is completed by mirroring the curves that can then be surfaced using [BWSS12]. 39 Input 2D curves Output 3D curves 3D models with surfaces Figure 8.6: Result of a spoon, cup and fork sketch. The reconstruction is completed by mirroring the curves that can then be surfaced using [BWSS12]. 40 Chapter 9 Conclusions We presented a new framework for reconstructing believable 3D models from single-view design sketches and demonstrated its applicability on a large set of inputs. We evaluated our results against artist outputs created based on the same input sketches, confirming that our results are qualitatively similar. Our method is based on the types of curves artists a priori routinely use in their sketches and thus requires minimal overhead. For future work, on the theory side the most interesting extension can be to investigate the use of outlier-robust norms as a replacement for our L2 based formulation, ones that may better handle exceptions to the conjugacy, symmetry and minimal variation properties, and do so without affecting solver robustness or speed. On the more practical side we can see two immediate extensions. Our setup uses a fairly small number of regularization constraints, other constraints such as enforcing planar cycles, or circular arcs can potentially be added to the formulation. While our system is based on the single-view sketching metaphor, our algorithmic formulation should work with minimal changes in concert with a sketch-rotatesketch interface allowing users to choose the tool that best suits their needs. 41 Bibliography [AS11] Alexis Andre and Suguru Saito. Single-view sketch based modeling. In Proc. Symp. on Sketch-Based Interfaces and Modeling, 2011. → pages vi, 9 [ASN07] Alexis Andre, Suguru Saito, and Masayuki Nakajima. Crosssketch: freeform surface modeling with details. In Proc. Symp. on Sketch-Based Interfaces and Modeling, pages 45–52, 2007. → pages vi, 8, 9 [BBS08] S.H. Bae, Ravin Balakrishnan, and Karan Singh. ILoveSketch: as-natural-as-possible sketching system for creating 3d curve models. In Proc. User Interface Software and Technology, 2008. → pages 1, 6, 15 [BR11] M. Bordegoni and C. Rizzi. Innovation in Product Design: From CAD to Virtual Prototyping. Springer, 2011. → pages 1, 12 [BWSS12] Mikhail Bessmeltsev, Caoyu Wang, Alla Sheffer, and Karan Singh. Design-driven quadrangulation of closed 3d curves. Transactions on Graphics (Proc. SIGGRAPH ASIA 2012), 31(5), 2012. → pages 1, 4, 10, 12, 16, 18, 27, 37, 38, 39, 40 [Coo08] Martin Cooper. Line Drawing Interpretation. Springer, 2008. → pages 10 [dC76] Manfredo P. do Carmo. Differential Geometry of Curves and Surfaces. Prentice-Hall, Englewood Cliffs, NJ, 1976. → pages 2, 12 [Dig13] Digia. Qt. http://qt.digia.com/, 2013. → pages 33 [ES08] Koos Eissen and Roselien Steur. Sketching: Drawing Techniques for Product Designers. Bis Publishers, 2008. → pages vi, 3, 5, 8, 12 42 [ES11] Koos Eissen and Roselien Steur. Sketching: The Basics. Bis Publishers, 2011. → pages 1, 2, 5, 13 [Gah10] A. Gahan. 3D Automotive Modeling: An Insider’s Guide to 3D Car Modeling and Design for Games and Film. Elsevier Science, 2010. → pages 1, 12 [GHPvT89] Michel Gangnet, Jean-Claude Herv´e, Thierry Pudet, and Jean-Manuel van Thong. Incremental computation of planar maps. SIGGRAPH, 23:345–354, July 1989. → pages 28 [GIZ09] Yotam Gingold, Takeo Igarashi, and Denis Zorin. Structured annotations for 2D-to-3D modeling. ACM Trans. on Graph. (Proc. SIGGRAPH Asia), 28(5), 2009. → pages vi, 1, 7 [GJ+ 10] Ga¨el Guennebaud, Benoˆıt Jacob, et al. Eigen v3. http://eigen.tuxfamily.org, 2010. → pages 33 [IMT99] Takeo Igarashi, Satoshi Matsuoka, and Hidehiko Tanaka. Teddy: a sketching interface for 3d freeform design. SIGGRAPH, 1999. → pages vi, 1, 6 [Inc1a] The Mathworks Inc. 2010.version R2011a. → pages 33 [Joh13] Steven G. Johnson. The nlopt nonlinear-optimization package. http://ab-initio.mit.edu/nlopt, 2013. → pages 33 [LFG08] Sangwon Lee, David Feng, and Bruce Gooch. Automatic construction of 3d models from architectural line drawings. In Proc. of the symposium on Interactive 3D graphics and games (I3D), pages 123–130, New York, NY, USA, 2008. ACM. → pages 11 [lib13] libQGLViewer. libqglviewer. http://www.libqglviewer.com, 2013. → pages 33 [Low87] D G Lowe. Three-dimensional object recognition from single two-dimensional images. Artif. Intell., 31(3):355–395, March 1987. → pages 11, 14 [LPW+ 06] Yang Liu, Helmut Pottmann, Johannes Wallner, Yong-Liang Yang, and Wenping Wang. Geometric modeling with conical meshes and developable surfaces. ACM Trans. Graphics, 25(3):681–689, 2006. Proc. SIGGRAPH. → pages 2, 12 43 [LS96] H. Lipson and M. Shpitalni. Optimization-based reconstruction of a 3d object from a single freehand line drawing. Computer-Aided Design, 28:651–663, 1996. → pages 11, 14 [LSMI10] Manfred Lau, Greg Saul, Jun Mitani, and Takeo Igarashi. Modeling-in-context: user design of complementary objects with a single photo. In Proceedings of the Seventh Sketch-Based Interfaces and Modeling Symposium, SBIM ’10, pages 17–24, Aire-la-Ville, Switzerland, Switzerland, 2010. Eurographics Association. → pages 11 [LWC+ 11] Yangyan Li, Xiaokun Wu, Yiorgos Chrysanthou, Andrei Sharf, Daniel Cohen-Or, and Niloy J. Mitra. Globfit: Consistently fitting primitives by discovering global relations. ACM Transactions on Graphics, 30(4):to appear, 2011. → pages 3 [Mal87] Jitendra Malik. Interpreting line drawings of curved objects. International Journal of Computer Vision, 1(1):73–103, 1987. → pages 10 [Mat08] G. Mather. Foundations of sensation and perception. Taylor and Francis, 2008. → pages 13 [MI13] Industrial Light & Magic and ILM. Openexr. http://www.openexr.com/, 2013. → pages 33 [MKL05] M. Masry, D. Kang, and H. Lipson. A freehand sketching interface for progressive construction of 3d objects. Computers & Graphics, 29(4):563 – 575, 2005. → pages 11 [ML98] Pascal Mamassian and Michael S. Landy. Observer biases in the 3D interpretation of line drawings. Vision research, 38(18):2817–2832, 1998. → pages 5, 12 [MZL+ 09] Ravish Mehra, Qingnan Zhou, Jeremy Long, Alla Sheffer, Amy Gooch, and Niloy J. Mitra. Abstraction of man-made shapes. ACM Transactions on Graphics, 28(5):#137, 1–10, 2009. → pages 3 [NISA07] Andrew Nealen, Takeo Igarashi, Olga Sorkine, and Marc Alexa. Fibermesh: designing freeform surfaces with 3d curves. ACM Trans. on Graph. (Proc. SIGGRAPH), 26, July 2007. → pages 1, 6 [NS92] K. Nakayama and S. Shimojo. Experiencing and Perceiving Visual Surfaces. Science, 257:1357–1363, 1992. → pages 2, 13 44 [OSSJ09] L. Olsen, F.F. Samavati, M.C. Sousa, and J. Jorge. Sketch-based modeling: A survey. Computers & Graphics, 33, 2009. → pages 5, 6 [PAHK07] Helmut Pottmann, Andreas Asperl, Michael Hofer, and Axel Kilian. Architectural Geometry. Bentley Institute Press, 2007. → pages 2, 12 [Pip07] Alan Pipes. Drawing for Designers. Laurence King, 2007. → pages 5 [SBSS12] Cloud Shao, Adrien Bousseau, Alla Sheffer, and Karan Singh. Crossshade: Shading concept sketches using cross-section curves. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2012), 31(4), 2012. → pages vi, 1, 2, 9, 10, 14, 16, 17, 24, 33, 35 [SKKS09] Ryan Schmidt, Azam Khan, Gord Kurtenbach, and Karan Singh. On expert performance in 3D curve-drawing tasks. In Proc. Symp. Sketch-Based Interfaces and Modeling, 2009. → pages 14 [SKSK09] Ryan Schmidt, Azam Khan, Karan Singh, and Gord Kurtenbach. Analytic drawing of 3d scaffolds. ACM Trans. on Graph. (Proc. SIGGRAPH Asia), 28(5), 2009. → pages vi, 1, 4, 7, 8, 36 [Ste81] Kent A. Stevens. The visual interpretation of surface contours. Artificial Intelligence, 17, 1981. → pages 5, 12 [Sut64] I.E. Sutherland. Sketch pad a man-machine graphical communication system. In Proceedings of the SHARE design automation workshop, pages 6–329. ACM, 1964. → pages 1 45
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Flowshape : 3d concept modeling from single-view design...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Flowshape : 3d concept modeling from single-view design sketches Xu, Baoxuan 2013
pdf
Page Metadata
Item Metadata
Title | Flowshape : 3d concept modeling from single-view design sketches |
Creator |
Xu, Baoxuan |
Publisher | University of British Columbia |
Date Issued | 2013 |
Description | This work presents an automatic creation of 3D models from single view design sketches. We observe that these sketches typically employ networks of trim curves and cross-sections to convey shape. Combined together these curves define the representative flow-lines of the model, reflecting principal curvature and feature lines across the target surface. Artists design these lines to serve as a visual proxy of the 3D object and to effectively convey all surface details. Cross-sections, in particular, are known to impose a set of geometric constraints on the imagined surface, that help position the surface in 3D. We formulate the problem of reconstructing believ- able 3D curve geometry from design sketches via an optimization framework that leverages the geometric properties of flow-line networks, the constraints imposed by cross-section curves, and observations on how people perceive and sketch such networks. This algorithm utilizes these criteria to simultaneously construct the 3D curves and correct for inevitable inaccuracies in free-hand sketches, which if retained would hinder constraint satisfaction and may lead to noticeable artifacts in the reconstructed 3D models. We validate our framework by producing believable 3D curve networks and surfaces from design sketches based on cross-section and trim curves, conducting a qualitative comparison to artist-estimated models, and visual validation by designers. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2013-04-19 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-ShareAlike 3.0 Unported |
IsShownAt | 10.14288/1.0052203 |
URI | http://hdl.handle.net/2429/44274 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2013-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-sa/3.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2013_spring_xu_baoxuan.pdf [ 37.52MB ]
- Metadata
- JSON: 24-1.0052203.json
- JSON-LD: 24-1.0052203-ld.json
- RDF/XML (Pretty): 24-1.0052203-rdf.xml
- RDF/JSON: 24-1.0052203-rdf.json
- Turtle: 24-1.0052203-turtle.txt
- N-Triples: 24-1.0052203-rdf-ntriples.txt
- Original Record: 24-1.0052203-source.json
- Full Text
- 24-1.0052203-fulltext.txt
- Citation
- 24-1.0052203.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0052203/manifest