FlowRep: Extracting Descriptive Curve Networks fromFree-Form Design ShapesbyGiorgio GoriB. in Informatics, Universita` della Svizzera Italiana, 2014A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University of British Columbia(Vancouver)August 2017c© Giorgio Gori, 2017AbstractThis thesis presents FlowRep, an algorithm for extracting descriptive compact 3Dcurve networks from meshes of free-form man-made shapes. FlowRep output net-works provide a concise visual description of the underlying surface, and can beused as a compact proxy for shape compression, editing and manipulation. Whileartists routinely and successfully create descriptive curve networks to depict com-plex 3D shapes in 3D space or on 2D media, the method described here is the firstto achieve this goal algorithmically. FlowRep infers the desired compact curvenetwork from complex 3D geometries by using a series of insights derived fromperception, computer graphics, and design literature which point to two sets of ge-ometric properties that such networks should satisfy. These sources suggest thatvisually descriptive networks are cycle-descriptive, i.e their cycles unambiguouslydescribe the geometry of the surface patches they surround. They also indicate thatsuch networks are designed to be projectable, or easy to envision when observedfrom a static general viewpoint; in other words, 2D projections of the networkshould be strongly indicative of its 3D geometry.Research suggests that both properties are best achieved by using networksdominated by flowlines, surface curves aligned with principal curvature directionsacross anisotropic regions and strategically extended across sharp-features andisotropic areas. The algorithm leverages these observations in the construction ofa compact descriptive curve network. Starting with a curvature aligned quad dom-inant mesh I first extract sequences of mesh edges that form long, well-shaped andreliable flowlines by leveraging directional similarity between nearby meaningfulflowline directions. This process overcomes topological noise, and inaccuraciesand singularities in the underlying curvature field. I then use the extracted flow-iilines and the model’s sharp-feature, or trim, curves to form a projectable networkwhich describes the underlying surface. Finally, I simplify this network while pre-serving its descriptive power to obtain the final result. My co-authors and I validateour method by demonstrating a range of networks computed from diverse inputs,using them for surface reconstruction, and showing extensive comparisons withprior work and artist generated networks.iiiPrefaceThe ideas and algorithms described in this thesis, unless stated below, were devel-oped by myself in consultation with Dr. Alla Sheffer, Dr. Nathan Carr and Dr. TaoJu.The content of Section 4.5 (Regularization) was developed by Nicholas Viningin consultation with Dr. Alla Sheffer and included here for completeness. Theuser studies mentioned in Section 8.3 (Figures A.1, A.2) were conducted by En-rique Rosales and Nicholas Vining with UBC approval (UBC BREB Number H16-02320).All the ideas and algorithms described were submitted in the research paper:• Giorgio Gori, Alla Sheffer, Nicholas Vining Enrique Rosales, Nathan Carrand Tao Ju. 2017. FlowRep: Descriptive Curve Networks for Free-FormDesign Shapes. ACM Trans. Graph. 36, 4, Article 59 (July 2017), 14 pages.[23]ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1 Curvature Aligned Meshes. . . . . . . . . . . . . . . . . . . . . . 62.2 Mesh Segmentation and Reverse Engineering. . . . . . . . . . . . 72.3 Quad Patch Layout. . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 Feature Curves and Curve Networks. . . . . . . . . . . . . . . . . 82.5 Shape Proxies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.6 Analysis of Design Networks and Drawings. . . . . . . . . . . . . 103 Descriptive Curve Networks . . . . . . . . . . . . . . . . . . . . . . 113.1 Cycle Description . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Flowline Dominance . . . . . . . . . . . . . . . . . . . . . . . . 123.3 Network Projectivity . . . . . . . . . . . . . . . . . . . . . . . . 13v4 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . 174.2 Solution Framework . . . . . . . . . . . . . . . . . . . . . . . . 174.3 Strand-based Flowline Extraction . . . . . . . . . . . . . . . . . . 184.4 Network Computation . . . . . . . . . . . . . . . . . . . . . . . 194.5 Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 Measuring Network Properties . . . . . . . . . . . . . . . . . . . . . 225.1 Cycle Descriptiveness . . . . . . . . . . . . . . . . . . . . . . . . 225.2 Flowline Cost. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245.2.1 Flowline Projectivity . . . . . . . . . . . . . . . . . . . . 245.2.2 Flowline Dominance . . . . . . . . . . . . . . . . . . . . 266 Flowline Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 286.1 Initial Strands and Flowlines. . . . . . . . . . . . . . . . . . . . . 296.1.1 Initial Strands . . . . . . . . . . . . . . . . . . . . . . . . 296.1.2 Initial Flowline Extraction . . . . . . . . . . . . . . . . . 306.2 Reliable Strands and Flowlines. . . . . . . . . . . . . . . . . . . . 306.2.1 Reliable Strands . . . . . . . . . . . . . . . . . . . . . . 306.2.2 Reliable Flowline Extraction . . . . . . . . . . . . . . . . 317 Network Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 337.1 Top-Down: Dense Descriptive Network Computation . . . . . . . 347.1.1 Network Initialization . . . . . . . . . . . . . . . . . . . 347.1.2 Network Refinement . . . . . . . . . . . . . . . . . . . . 347.1.3 Flowline Shortening . . . . . . . . . . . . . . . . . . . . 347.2 Bottom-Up: Network Simplification . . . . . . . . . . . . . . . . 357.2.1 Simplification . . . . . . . . . . . . . . . . . . . . . . . . 367.2.2 Connectivity Optimization . . . . . . . . . . . . . . . . . 367.2.3 Post-process Local Optimization . . . . . . . . . . . . . . 378 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398.1 Comparison to Artist Generated Networks . . . . . . . . . . . . . 398.2 Comparison to Prior Art . . . . . . . . . . . . . . . . . . . . . . 40vi8.3 Qualitative Evaluation . . . . . . . . . . . . . . . . . . . . . . . 438.4 Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469.1 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469.2 Network Resolution . . . . . . . . . . . . . . . . . . . . . . . . . 469.3 Impact of Design Choices . . . . . . . . . . . . . . . . . . . . . . 479.4 Input Mesh Impact . . . . . . . . . . . . . . . . . . . . . . . . . 489.4.1 Curvature re-alignment . . . . . . . . . . . . . . . . . . . 499.5 Parameters and Runtimes . . . . . . . . . . . . . . . . . . . . . . 509.6 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5010 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53A Supporting Materials . . . . . . . . . . . . . . . . . . . . . . . . . . 58viiList of FiguresFigure 1.1 Artist generated 3D (a) and 2D (b) descriptive curve networkssuccinctly convey complex free-form shapes. . . . . . . . . . 1Figure 1.2 FlowRep describes complex free-form 3D geometries (a) by acompact network of descriptive and projectable curves (e) thatcan be used to both depict and reconstruct (f) the input (L2distance between (a) and (f) is 0.1% of bounding box diago-nal). Given an input quad mesh (a) it extracts strands of dom-inant flowlines (b), uses those to computes a dense descriptivenetwork (c) and then systematically simplifies it to obtain thedesired compact net (d). . . . . . . . . . . . . . . . . . . . . 2Figure 1.3 Quad-meshing methods that optimize for mesh regularity, suchas [7], use quad partitions (a) as a starting point and often ex-hibit systemic misalignment with curvature directions as high-lighted in (b). Meshing methods that seek to adhere to curva-ture directions more strictly often result in meshes with multi-ple sporadic singularities and non-quad elements (c). To avoidsystemic curvature misalignment we use the latter type of meshesas a starting point for generating descriptive curve networks(d). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4viiiFigure 2.1 Projectivity and cycle descriptiveness (all renders show thesame 3D model in same view). Projection of an orthogonalquad mesh (b) conveys the underlying 3D geometry better thanthat of a non-orthogonal mesh (a). A flowline network (f) overa curvature aligned field (e) succinctly describes the surface,while a network (d) generated from an arbitrary smooth cross-field (c) does not. . . . . . . . . . . . . . . . . . . . . . . . . 6Figure 3.1 Descriptiveness; The curve network in the middle incorrectlyconjures a flat surface, while the cycles on the right are de-scriptive of the originating surface on the left. . . . . . . . . . 11Figure 3.2 Examples of artist drawn lines to demarcate roundings. . . . . 12Figure 3.3 A less (a) and more (b) projectable curve network in two views.All figures show the same model. . . . . . . . . . . . . . . . 13Figure 4.1 Algorithm stages: (a) Input quad-dominant mesh; (b) flowlinestrands; (c) compact descriptive network; (d) regularized finalnetwork. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15Figure 4.2 Detailed algorithm overview: (a) Input quad-dominant mesh;(b) initial flowline strands; (c) initial conservative flowlines;(d) final flowline strands; (e) reliable flowlines; (f) dense de-scriptive network; (g) simplified network; (h) network post lo-cal optimization; (i) regularized final network. . . . . . . . . . 16Figure 4.3 Examples of flowlines. . . . . . . . . . . . . . . . . . . . . . 16Figure 4.4 Overview of the method steps. . . . . . . . . . . . . . . . . . 18Figure 4.5 Flowlines extracted with just local information (left) and withglobal information (right). . . . . . . . . . . . . . . . . . . . 19Figure 4.6 Independently formed flowlines (a,b,e) can be sub-optimal andmay occasionally persist through network computation (e). Strandcomputation (c,d,f) correctly splits edges between different strandsoverriding purely local alignment and resulting in better finalnetworks (f). . . . . . . . . . . . . . . . . . . . . . . . . . . 20Figure 4.7 Regularization; Before (left) and after (right). . . . . . . . . . 21ixFigure 5.1 (a) More (green) and less (red) well described cycles on a row-boat, before and after local optimization. (b) Flowlines coloredby decreasing projectivity (blue to red). (c) More (blue) andless (red) dominant flowlines. . . . . . . . . . . . . . . . . . 22Figure 5.2 Coverage; At the vertex v, interpolating along the flowline f1the boundary normals n11 and n21 yield the prediction np1 . Theerror is the difference between np1 and the actual normal n.Similarly, another error is computed interpolating along f2.FlowRep aggregates all of those errors for every vertex in theregion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23Figure 5.3 Projectivity; Three planes are fit to a sliding sequence of ver-tices from vi to vi + 2k. Their normals n j, nk, and nh areused to compute planarity (as the difference between them)and geodesicity (comparing them against the vertex normals). 25Figure 5.4 Normal predictions match the actual normals (left). Remov-ing the middle flowline affects the normal predictions (right),that then diverge from the actual normals, leading to a highdominance cost. . . . . . . . . . . . . . . . . . . . . . . . . . 26Figure 6.1 Dominant flowline strands on the mug: (a) initial edge strandsand (b) extracted conservative flowlines; (c) final strands and(d) flowlines. . . . . . . . . . . . . . . . . . . . . . . . . . . 28Figure 6.2 Positive and negative cluster associations of edges around edge e 29Figure 7.1 Network computation: (a) Initial trim curve network; (b) de-scriptive dense network; (c) final network. . . . . . . . . . . . 33Figure 7.2 A flowlines is shortened to terminate at trim curves when pos-sible (left) or to other flowlines (right). . . . . . . . . . . . . . 35Figure 8.1 Comparison against artist generated networks: (left to right)input model, artist generated 2D design drawings and 3D net-work (red), and our algorithmic result (blue). . . . . . . . . . 40xFigure 8.2 Suggestive contours combined with ridge and valley lines [17](b) convey the overall input shape (a); a FlowRep descriptivenetwork (c) provides a more detailed and accurate descriptionof the input geometry. . . . . . . . . . . . . . . . . . . . . . 40Figure 8.3 Surface segmentation (e.g. VSA [14]) (b) and reverse engi-neering methods (d,e) are not designed for, and do not produce,projectable curve networks; their output is often not descrip-tive to a human observer. FlowRep networks (c,f) satisfy bothcriteria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Figure 8.4 (a) Quad-partition [7] of the treball and ellipsoid (a) comparedto our network (b). Quad partitions, here [24], are highly de-pendent on the singularity locations in the initial mesh driftingfrom curvature directions (c). FlowRep result on same model(d). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Figure 8.5 While exoskeletons [16] only roughly capture coarse part struc-tures of shapes (b), our method describes the geometry in moredetail (c). Planar slices [32] are restricted in their ability toconvey free-form shape (e,h), while FlowRep networks arewell suited for this task (f,i). . . . . . . . . . . . . . . . . . . 43Figure 8.6 Study questionaire layouts: FlowRep compared to artists (left)and FlowRep compared to previous work (right). . . . . . . . 43Figure 8.7 Reproduction. Pairs of input models with computed FlowRepnetworks (wireframes) and these networks resurfaced using[36] (blue). . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Figure 8.8 Reproduction. Input curve networks (green), surfaces producedby [3, 36], and our networks (blue) computed from these sur-faces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Figure 9.1 Networks with different descriptiveness thresholds, shown onthe ellipsoid model. . . . . . . . . . . . . . . . . . . . . . . . 47xiFigure 9.2 Alternative network extraction methods: (a) bottom-up cycleclustering results in poorly descriptive networks with highlyirregular connectivity; network optimization using only flow-line projectivity (b) or only their dominance (c), versus fulloptimization (d). . . . . . . . . . . . . . . . . . . . . . . . . 47Figure 9.3 Impact of systemic mesh vs curvature tensor misalignment: (a)Interleaved spiral flowlines resulting from curvature drift mayresult in undesirable T-junctions (mesh from [28]); (b) moresignificant misalignment predictably distorts the network ori-entation (mesh from [7]); (c) large patches of randomly alignedquads (top of the hat) similarly lead to artifacts. . . . . . . . . 48Figure 9.4 Curve networks generated from different meshes of same model:(a) [7], (b) ArtMesh. The input mesh in (a) exhibits featuredrift (sharp features migrating between mesh flowlines); lead-ing FlowRep to preserve these flowlines generating visual re-dundancy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Figure 9.5 Impact of halving/doubling default algorithm parameters(weights used for correlation clustering; weights of differentelements of En (Eq. 4.1)). . . . . . . . . . . . . . . . . . . . 50Figure 9.6 Additional results. . . . . . . . . . . . . . . . . . . . . . . . 51Figure A.1 User Study 1. . . . . . . . . . . . . . . . . . . . . . . . . . . 59Figure A.2 User Study 2. . . . . . . . . . . . . . . . . . . . . . . . . . . 60xiiAcknowledgmentsMany thanks to Nathan Carr from Adobe and Tao Ju from Washington Universityin St. Louis for helpful discussion, insight and feedback.I would like to thank my supervisor Alla Sheffer for guidance, support and forbeing my academic sounding board in the past two years.Thanks to Nicholas Vining, Enrique Rosales and Chenxi Liu for the help whenwas most needed and for complementing my skills.Many thanks to University of British Columbia and the Department of Com-puter Science for offering me this fantastic opportunity and for the financial aidthey provided.Thanks especially to my parents, who encouraged and supported my choice ofstudying far from home.xiiiChapter 1Introduction(a) (b)Figure 1.1: Artist generated 3D (a) and 2D (b) descriptive curve networkssuccinctly convey complex free-form shapes.Artists employ sparse descriptive networks of 3D curves lying on the surfaceof imagined objects as a starting point for modeling such envisioned shapes, withcurve generation followed by surfacing, and quickly communicate 3D shapes onpaper by sketching 2D projections of such 3D curve networks depicted from infor-mative viewpoints (Figure 1.1). In addition to providing an effective visual com-munication tool, sparse descriptive curve-network representations of 3D modelsprovide designers with intuitive handles for shape editing [21]; facilitate compactshape representation and abstraction [33]; support shape-preserving mesh simplifi-cation [22]; and enable other high-level operations. This thesis proposes FlowRep,a method for computing visually descriptive compact curve networks of free-form1(a) Input(b) Flow-line Strands (c) Dense Network (d) Sparse NetworkIntermediate Stages(e) Output (f) ReconstructedFigure 1.2: FlowRep describes complex free-form 3D geometries (a) by acompact network of descriptive and projectable curves (e) that can beused to both depict and reconstruct (f) the input (L2 distance between (a)and (f) is 0.1% of bounding box diagonal). Given an input quad mesh(a) it extracts strands of dominant flowlines (b), uses those to computesa dense descriptive network (c) and then systematically simplifies it toobtain the desired compact net (d).2man-made, or designed, shapes from existing models (Figure 1.2). FlowRep net-works effectively convey the shape of an input 3D object geometry to human ob-servers and can be used for the range of applications described above. They accu-rately encode input geometry enabling both perceptual and geometric reconstruc-tion; the mouse in Figure 1.2f was accurately reconstructed from our curve networkalone using the method of [36].While previous methods have addressed the related problems of surface parti-tioning [4, 10, 14, 20, 34] and extraction of sets or networks of different featurecurves [17, 22, 33], the partition boundaries or sets of curves they produce do notprovide a detailed description of complex man-made free-form shapes (Chapter 2);the compact sets of curves they generate either do not allow a human viewer to vi-sualize the detailed 3D shape that they represent, or are not sufficient to reconstructthe shape using existing surfacing methods. In contrast, and as demonstrated bythe comparisons presented later in this thesis, FlowRep addresses the fundamentalproblem of generating a curve network that unambiguously defines the target shapefor human observers and allows for effective reconstruction of the shape from thecurves alone using perception-driven surfacing techniques [3, 36].The first challenge that I face in extracting the desired curve networks from in-put models is determining the properties these networks must possess to adequatelydescribe a given shape. The design literature points to two sets of criteria that thesecurve configurations should satisfy (Chapter 3). The desired curve networks shouldbe projectable - i.e. the 3D shape of the curves should be predictable from their 2Dprojection when viewed from non-accidental viewpoints - and the network cyclesshould clearly describe the surface regions they bound. As observed by previousliterature [36, 45], artist drawn networks are typically dominated by a combinationof trimming curves, which indicate sharp features, and flowline curves, or sur-face curves aligned with principal curvature directions in anisotropic regions andsmoothly extending into and traversing isotropic areas. These flowlines are key toboth network projectivity and cycle descriptiveness (Chapter 3). By construction,curvature tensor-aligned curves are orthogonal; this is a key property for recov-ering their 3D shape from a 2D projection of the curve network [45]. Moreover,human observers tend to mentally surface 3D network cycles by interpreting mostcycle curves as aligned with principal curvature directions on an imaginary surface.3Figure 1.3: Quad-meshing methods that optimize for mesh regularity, such as[7], use quad partitions (a) as a starting point and often exhibit systemicmisalignment with curvature directions as highlighted in (b). Meshingmethods that seek to adhere to curvature directions more strictly oftenresult in meshes with multiple sporadic singularities and non-quad ele-ments (c). To avoid systemic curvature misalignment we use the lattertype of meshes as a starting point for generating descriptive curve net-works (d).They consequently envision surfaces on which the curvature directions are interpo-lating the directions of these curves and the curvature magnitudes are a blend of thecurvatures along these curves [3, 36]. When extending flowlines across isotropicregions, artists leverage the extra degree of freedom these regions provide to op-timize both curve projectivity and descriptiveness. While dense flowline and trimnetworks adequately describe shape, the design literature indicates a strong pref-erence for using compact, minimalist, cycle-descriptive networks to avoid visualclutter [18]. When creating such compact networks, artists use dominant flowlinecurves to delineate regions with monotone curvature variation, whose geometry isconsequently well described by their boundaries. Using these guidelines for cre-ating the desired descriptive networks, I seek to compute a compact descriptiveset of projective dominant flow lines on the input shapes. To extract this compactnetwork, I leverage observations about the desired properties of such curves de-rived from design and modeling literature (Chapter 3) and use those to quantifydominance, descriptiveness and projectivity. I then employ these definitions in anetwork computation algorithm.Tracing individual flowlines, especially across isotropic regions and near curvature-field singularities, is inherently unreliable. This thesis provides global contextfor flowline computation by using a curvature aligned quad-dominant mesh as4a starting point for our algorithm. Edge sequences on such meshes are largelyaligned with curvature directions in anisotropic regions and typically smoothly ex-tend across isotropic ones; such edge sequences provide a natural starting point fortracing an initial set of flowlines from which we can subsequently distill the desireddominant subset.Using such meshes as a starting point, however, introduces different challenges.First, quad-meshing methods balance mesh quality and vertex regularity againstcurvature alignment. Generation of more regular meshes, e.g. [7, 11], often re-quires significant deviation from curvature directions (Figure 1.3b). In my setting,the requirement for curvature field alignment is paramount, necessitating the useof curvature aligned, but potentially highly irregular, meshes with singular verticesand non-quad faces (Figure 1.3c). I and my co-authors extrapolate projectableand dominant flowlines, overcoming misaligned edges and mesh irregularities, byleveraging directional affinity between adjacent meaningful flowlines. We note thatdominant principal curvature directions are characterized by clusters, or strands,of adjacent similarly directed flowlines or sequences of mesh edges. My flowlineextraction method first clusters the mesh edges into strands, and then extracts indi-vidual flowlines from these strands. We use the extracted flowlines to compute thedesired network. We first assemble a dense descriptive trim and flowline networkthat describes the input surface within a given tolerance, and then simplify and op-timize this network using the dominance, projectivity and descriptiveness metricsidentified above to obtain the desired compact solution.The contribution of this thesis is two-fold. I identify and enumerate the keyproperties of descriptive curve networks suitable for communicating complex de-signer shapes; I then propose the first curve network extraction algorithm that gen-erates networks with these desired properties. I and my co-authors test the methodon a diverse range of inputs, showcasing its ability to generate the desired results oncomplex free-form models, and validating it through comparison to artist outputs,designer evaluation, and comparisons to prior art (Chapters 8, 9). As this validationconfirms, the output networks successfully capture and convey the essence of theinput shapes both in 3D space, and when viewed from general viewpoints.5Chapter 2Related WorkWhile our focus on computing perceptually descriptive curve networks for designshapes is new, our method is related to a range of works that seek to either partitionsurfaces, or to extract different types of feature curves from an input mesh. I brieflyreview these works, analyzing how well their outputs adhere to our three goals:descriptiveness, projectivity, and compactness.2.1 Curvature Aligned Meshes.At the finest level, curvature aligned polygonal meshes provide two of the qual-ities we seek: descriptiveness and projectivity (Figure 2.1b). For example, Al-liez et al. [1] extract a curvature aligned quad-dominant mesh from the curvatureFigure 2.1: Projectivity and cycle descriptiveness (all renders show the same3D model in same view). Projection of an orthogonal quad mesh(b) conveys the underlying 3D geometry better than that of a non-orthogonal mesh (a). A flowline network (f) over a curvature alignedfield (e) succinctly describes the surface, while a network (d) generatedfrom an arbitrary smooth cross-field (c) does not.6tensor field. However, such meshes are clearly not compact. We use them as astarting point for our framework, which compacts them while maintaining thesetwo key properties (Figure 2.1f).2.2 Mesh Segmentation and Reverse Engineering.Methods for mesh segmentation, e.g. [14, 29] and reverse engineering, e.g. [4, 35,44] aim to segment models into regions with particular surface characteristics, forinstance developable surfaces, planes, or conics. Cohen-Steiner et al. [14] approx-imate the mesh with geometric proxies and Wu et al. [44] expand that method byusing different primitives. Julius et al. [29] segment the mesh in quasi-developablecharts. Nieser et al. [35] use feature lines and surface curvature to reverse engi-neer the surface in regions. Beniere et al. [4] detect various geometric primitivesand their intersections to reverse engineer CAD models. All those methods payminimal attention to the properties of the boundary networks that arise from thepartition they produce, and at best optimize for boundary straightness or compact-ness. While they facilitate algorithmic reconstruction of approximate input geom-etry from the curve network and compactly encoded region descriptors (such assurface type, axis of revolution or radius), the curve networks they generate areoften not cycle-descriptive and, when projected to 2D space, provide little infor-mation on the originating 3D curves (Figure 8.3). The key distinguishing featureof our method compared to these approaches is our focus on network propertiesrather than region properties, and consequently the ability to concisely and effec-tively describe input surfaces independent of their specific geometry using networkcurves alone.2.3 Quad Patch Layout.A range of methods extract coarse quad patch layouts to facilitate parameteriza-tion and surface fitting. Early methods, such as [5] generate such layouts semi-manually based on a coarse layout provided by the user. This approach is stillpopular; for example Campen et al. [9] let the user specify “elastica strip” (closedgeodesic loops aligned with curvature) while Zhuang et al. [47] have the userchoose segmentation boundaries by picking geodesics in a carefully crafted met-7ric. More recent frameworks use motorcycle graphs, starting at quad mesh singularpoints [20] to obtain singularity-free quad patches. Recent works [6, 42] improvethe patch layouts by simplifying spiraling patch boundaries and merging nearbysingularities. Gunpinar et al. [24, 25] augment the graph tracing with geometricconsiderations, leading to better capture of prominent features. Alternative ap-proaches use a curvature-aligned tensor field instead of a mesh as a starting point[7, 10, 34, 38] and trace separatrices from field singularities to form quad patches.Bommes et al. [7] use a mixed-integer approach to produce reliable quad-meshes.Campen et al. [10] construct patch layouts guided by the curvature field, then ex-tract the dual graph and finally generate the quad mesh. Myles et al. [34] generatea parameterization aligned with a cross field by tracing along the field and thenoptimizing for consistent parametric edge lengths. Razafindrazaka et al. [38] for-mulate the problem of finding patch layouts as a global optimization on the crossfield singularity graph. Whether starting from a quad mesh or a field, the results ofthese methods are highly dependent on the location of singularities and can there-fore be significantly misaligned with curvature directions (Figures 1.3,8.4). Evenwhen aligned with curvature the separatrice boundaries used by such networksform irregular valence vertices, resulting in networks that contain few orthogonalintersections, making the mental leap from the network to the underlying surfacechallenging (Figure 8.4a). Similar to the first group of layout methods, we usemeshes as a starting point; however, we seek a distinctly different set of networkcurves, one aimed at perceptual rather than purely geometric approximation of theinput model.2.4 Feature Curves and Curve Networks.A large body of research addresses detection of both sharp features and prominentcurves, such as ridge and valley lines on meshes. Hildebrandt et al. [26] presenta stable algorithm to produce visually pleasing feature lines, while Lai et al. [31]detect and classify features into ridges, valleys and prongs (a slender pointed part).These curves are often used to augment contours when generating sketches of in-put models, e.g. [17], and are effective at quickly conveying the overall shape ofobjects [15, 18] (Figure 8.2b). When aiming to convey proportions and geometric8details, artists utilize more detailed descriptive, or “precise”, drawings [18] whichaugment contours and sharp feature curves with dominant flowlines and typicallydo not include smooth ridges or valleys (Figure 1.1). Our work focuses on captur-ing the curve networks artists use in the latter context (Figures 8.1, 8.2c).Mehra et al. [33] represent 3D shapes using networks of sharp feature curveswith specified normals along them, selecting a suitable curve subset to achieve adesired abstraction. To describe smooth regions, they augment those networks toinclude the boundaries of coarse planar segmentation regions [14] (Figure 8.3b).Gehre et al. [22] allows for a more effective control of network density using aglobal scale parameter and support inclusion of other feature curves, such as ridgesand valleys in the output networks. As noted earlier, feature curves alone arenot sufficient to accurately describe smooth shapes, while segmentation bound-ary networks are rarely projectable and are therefore not suitable for our needs.Moreover, while the network resolution constraints these methods use are largelyspatial, FlowRep network density is controlled by its descriptiveness, resulting inmuch denser spacing on prominent details, such as the mouse wheel, and sparserones on more monotone areas such as the top of the mouse (Figure 1.2).2.5 Shape Proxies.de Goes et al. [16] propose a user-assisted method for coarse abstraction of naturalshapes. They first segment models into roughly convex parts, and then partitionthose using an extension of VSA [14] that seeks to reduce T-junction count. Ourautomatic framework targets free-form man-made shapes and is designed to accu-rately capture their geometry (Figure 8.5, top).Planar curves, or slices, aligned with major curvature direction or key symme-try planes are successfully used to fabricate real-life proxies of 3D shapes [13, 32].This representation requires a leap of imagination to envision the intended surface,and performs worst when curvature streamlines are non-planar (Figure 8.5,e,h),leading Cignoni et al. [13] to use hundreds of slices to obtain recognizable rep-resentations of medium complexity shapes. Our alternative approach effectivelydescribes shapes of similar complexity with just a few curves (Figure 8.5,f,i).92.6 Analysis of Design Networks and Drawings.There is a growing body of work on recovering 3D information from professionaldesign drawings [27, 39, 45]. Iarussi et al. extrapolate line directions in designerdrawings to form a cross field and then estimate the 3D surface normals. Shao et al.[39] use the intersections between sketch lines to infer the normals. Xu et al. [45]reconstruct 3D curve networks from design sketches using multiple insights fromperception and design literature. Recent methods use such reconstructed or artist-created 3D networks to extract the 3D surface; Bessmeltsev et al. [3] interpolate theinput curves with a set of quad patches whose iso-lines match the input network.Pan et al. [36] iteratively adapt a triangle mesh to optimize the agreement betweenits curvature field and the input. This line of work has been the catalyst for ourexploration of the inverse problem - extracting a descriptive network from a given3D geometry. We discuss the insights we derive from these papers and which weutilize in our work in Chapter 3.10Chapter 3Descriptive Curve NetworksOur goal is to compute a sparse network of curves on the surface of an arbitrary 3Dmodel that succinctly describes the model’s shape (Figure 1.1). Based on obser-vations from design tutorials and relevant perception and computer graphics liter-ature, we identify and formulate three major sets of geometric criteria that jointlydetermine the overall network effectiveness: cycle description, curve dominance,and network projectivity.3.1 Cycle DescriptionA curve cycle is a collection of curve segments that demarcate the boundary of asingle surface patch, whether that surface is a real surface or merely implied. Per-ceptual studies [40], validated by recent modeling research [3, 36], suggest that,X×Figure 3.1: Descriptiveness; The curve network in the middle incorrectlyconjures a flat surface, while the cycles on the right are descriptive ofthe originating surface on the left.11when shown a curve cycle consisting of several smooth curve segments, humanobservers opt for a unique mental interpretation of the cycle’s implied interpolatingsurface. Specifically, viewers tend to perceive most of the provided curves as rep-resentative curvature lines on an imaginary underlying surface. They subsequentlyimagine a surface whose principal curvature lines smoothly blend these curves.Since surface principal curvatures fully define its geometry, viewers consequentlyimagine a unique surface interpolating this cycle.Observation of industrial design practices [8, 18] indicates that artists leveragethis property when creating 3D curve networks or depicting 3D geometry in 2Dspace. Their networks are dominated by flowline curves aligned with principalcurvature directions in anisotropic areas and extended across isotropic regions andare augmented by trimming curves which demarcate open boundaries and sharpfeatures. As demonstrated in Figure 3.1, for the surface on the left the trimmingcurve alone (middle) incorrectly conjures a flat surface, while the cycles of therightmost network are descriptive of the originating surface on the left.3.2 Flowline DominanceFigure 3.2: Examples of artist drawn lines to demarcate roundings.Design literature [8, 18] highlights the need to keep the number of networkcurves minimal for aesthetic reasons. It consequently provides helpful guidelinesas to what subset of flowlines and trimming curves is dominant, or best at suc-cinctly conveying surface geometry. This literature indicates a preference for usingflowlines which delineate large areas of monotone curvature, and are representativeof one of the curvature directions within these areas. As a specific example, Eissen12and Steur [2008] recommend that artists demarcate roundings (marked in red inFigure 3.2). They also recommend using “bigger sized curves first” and addingmore curves as necessary “to emphasize the transformation of the surface”. Thisadvice suggests a preference for hierarchical network constructions - first captur-ing major anisotropic regions by tracing their dominant principal curvature stream-lines, and then refining the network to add finer details.3.3 Network Projectivityfront viewside viewfront viewside view(a) (b)Figure 3.3: A less (a) and more (b) projectable curve network in two views.All figures show the same model.Artist-generated descriptive curve networks are designed to serve as a self-sufficient proxy of the 3D shape. Consequently, evidence indicates that artistsconstruct networks whose 2D projections in many, if not all, views can be usedby human observers to successfully predict their 3D shape [32]. In Figure 3.3the network on the right satisfies this property, while the one on the left does not.Perception research [40] points out that smoothly crossing 2D curves in designdrawings are universally perceived as orthogonal. As highlighted by [39, 45] thiscue is critical when extrapolating depth from line drawings. Artists ubiquitously13employ such crossing orthogonal 3D curves in their networks. Curves meetingat T-junctions are similarly perceived as likely orthogonal, unless contradicted bythe surrounding context [45]. There is no indication in research that any othertype of intersection or curve ending contributes to viewer understanding of 3Dnetwork geometry given a 2D projection. These observations suggest a preferencefor orthogonal curve networks dominated by regular (valence-4) vertices, with noopen-ended curves.Human observers are more successful at inferring 3D curve shape from 2Dprojections of flatter curves [40, 43]. While restricting the set of network curves tostrict planes reduces the set of models one can effectively describe [45], artists arestrongly encouraged to use planar curves when depicting shapes [18], wheneverpossible.Lastly, artists are strongly encouraged to draw local symmetry, or geodesiccurves when depicting complex surfaces [18, 19]. The symmetry cue is known tobe helpful in recovering the 3D shape of network curves from a 2D view [39, 45].14Chapter 4OverviewFigure 4.1: Algorithm stages: (a) Input quad-dominant mesh; (b) flowlinestrands; (c) compact descriptive network; (d) regularized final network.Based on the criteria outlined in the previous chapter, I seek to construct asparse cycle-descriptive network of trim curves and projective dominant flowlines.I seek flowlines that are aligned with curvature directions in anisotropic areas, andwhich smoothly extend across features and isotropic regions.To make the problem tractable, this thesis discretizes the solution domain bystarting from a finite set of potential flowlines. While one could start from a net-work constructed by directly tracing on a smooth curvature-aligned tensor field,tensor field tracing raises numerous accuracy issues [34, 37] and requires the con-sideration of subtle streamline seeding and termination choices [11, 34]. Ex-isting methods for generating curvature-aligned quad-dominant meshes robustlyaddress these issues, and their outputs can provide a suitable starting point forthe method presented. Most of the edges in anisotropic regions on such meshes15(a) (b) (c) (d) (e) (f) (g) (h) (i)Figure 4.2: Detailed algorithm overview: (a) Input quad-dominant mesh; (b)initial flowline strands; (c) initial conservative flowlines; (d) final flow-line strands; (e) reliable flowlines; (f) dense descriptive network; (g)simplified network; (h) network post local optimization; (i) regularizedfinal network.f1f2f3Figure 4.3: Examples of flowlines.are, by design, aligned with curvature directions, and most edges in isotropic re-gions are aligned with a smooth extension of the curvature field. Moreover suchmeshes, when dense enough, satisfy both projectivity and cycle-descriptiveness(Figure 1.3c, Figure 2.1e); the task can therefore be formulated as extracting acompact subset of the mesh edges which maximally retains both properties. I con-trol the trade-off between compactness and descriptiveness by imposing a boundon the cycle-descriptiveness error, and optimizing for the most compact dominantand projective edge network that satisfies this bound.In this chapter, I give a high-level formulation of the problem and overviewthe key components of our method. Details of the formulation and method will bediscussed in the next three chapters.164.1 Problem StatementGiven an input quad-dominant mesh M (Figure 4.2a), I formulate the computationof our target network N as selection of a subset of mesh edges with the followingproperties. Define a flowline as a (possibly closed) path made up of a sequenceof vertex-adjacent edges (see Figure 4.3; three flowlines f1, f2, f3 are identified bythree different colors). Each flowline f is associated with positive projectivity anddominance costs p f and d f . These costs are designed to decrease as a flowline’sprojectivity or dominance increases. Each network cycle c is also associated witha descriptiveness error dc. The exact formulations of p f , d f and dc are detailedin Chapter 5. Using these measures, the discrete optimization goal can then beformulated as computing a connected set of network flowlines f that minimizesnetwork cost while satisfying a descriptiveness threshold:minEN =∑(p f +d f ) (4.1)subect to maxdc < dmax ∀c ∈ NHere dmax is a user specified descriptiveness threshold that controls the networksparsity.Two key properties make this problem distinct from those addressed by tra-ditional discrete mesh segmentation frameworks. First, the network computationoperates on two distinct sets of entities. While the optimization function is definedon flowlines, or sequences of mesh edges, the constraints are defined on the cy-cles, or patches of mesh faces, that the flowlines bound. Second, unlike classicalsegmentation frameworks, the function to optimize is essentially independent ofthe number of edges within each selected flowline, but highly dependent on the apriori unknown number of network flowlines and their overall properties.4.2 Solution FrameworkThe algorithm developed in this thesis obtains the desired output network, by usingthe observation that an assignment of mesh edges to flowlines can be made largelyindependently of the choice of which flowlines will be eventually used in the final17network. Therefore I first group sequences of edges into flowlines (Figure 4.2b-e)and then select a subset of these flowlines, in combination with the surface trimcurves, to assemble the desired network (Figure 4.2f-h). I contrast our approachagainst classical segmentation methods in Chapter 8.Flowline ExtractionInitial Flowline ComputationEdge Correlation ClusteringInitial Flowline ExtractionReliable Flowline ComputationFlowline Correlation ClusteringReliable Flowline ExtractionNetwork ComputationDense Network ComputationSimplication(Optional) RegularizationFigure 4.4: Overview of the method steps.The following sections contain overviews of the solution framework steps (Fig-ure 4.4), then Chapter 6 describes in detail flowline extraction and Chapter 7presents network computation.4.3 Strand-based Flowline ExtractionIn general I expect pairs of similarly directed edges that share a common vertex tobelong to the same flowline and orthogonal adjacent edges to belong to differentflowlines. I use these criteria to determine when flowlines should terminate, i.e.under which conditions adjacent edges should belong to different flowlines, andwhen local geometry allows for multiple alternatives to determine which pairs ofadjacent edges should be joined into the same flowline. Due to meshing artifacts,singularities, misaligned edges, and inaccuracies in curvature field computation,making these choices based on purely local geometry around the edges in question18× XFigure 4.5: Flowlines extracted with just local information (left) and withglobal information (right).(Figure 4.5, left) can introduce flowlines misaligned with dominant flow directions.I obtain flowlines aligned with dominant flow (Figure 4.5, right) by takingglobal context into account. I note that dominant and meaningful curvature cross-field directions on the surface are characterized by groups of multiple long, adja-cent, similarly directed streamlines, or streamline strands. FlowRep leverages thisbehavior by first extracting similarly directed flowline strands (Figure 4.2b-d) andthen using these strands to extract individual, reliable flowlines (Figure 4.2e). I donot know a priori the number of strands we seek; however, as noted earlier, I gen-erally expect consecutive edges across vertices and opposite edges within quads tobelong to the same strand if they have similar directions, and expect orthogonaledges and intersecting flowlines to belong to different strands. I use these observa-tions to formulate strand extraction as a correlation clustering problem [2] (Figure4.2d). I then use these strands to extract individual, reliable flowlines (Chapter 6,Figure 4.2e). Figure 4.6 demonstrates the differences between the local and globalapproaches on real-life inputs.4.4 Network ComputationSelecting an optimal subset of the computed flowlines requires solving a discreteconstrained optimization problem within a large solution space. Adding flowlinesinto a network individually is problematic. While humans can easily identify dom-inant curvature streamlines i.e. surface curves across which curvature changes19Figure 4.6: Independently formed flowlines (a,b,e) can be sub-optimal andmay occasionally persist through network computation (e). Strand com-putation (c,d,f) correctly splits edges between different strands overrid-ing purely local alignment and resulting in better final networks (f).non-linearly, algorithmically identifying such locations on a mesh is error prone.Absent this information, dominance is best assessed in the context of an existingnetwork, where it can be directly evaluated by comparing the impact on cycle-descriptiveness of removing individual flowlines from the network. Intuitively,keeping more dominant flowlines results in a more cycle-descriptive network. Us-ing all flowlines at once to first form a dense network, and then simplifying it bygradually removing flowlines, provides an adequate solution but is computationallyexpensive as it involves multiple redundant insertion and removal operations.To efficiently compute the desired network I adopt a mixed top-down/bottom-up strategy. The network construction process starts from a minimal network ofonly trim curves (Figure 7.1a) and progressively refines the inadequately describedcycles on this network (Figure 7.1, Section 7.1). At each refinement stage I add allflowlines that span, or cross, these cycles into the network (Figure 7.1b), delayingthe decision on which of them are best until the network is sufficiently descriptive.Refinement terminates once all network cycles are sufficiently described; specif-ically, when the description error dc for each cycle is below our threshold dmax(Figure 4.2f).At this point I have sufficient context to proceed with the simplification pro-cess, and can remove redundant flowlines (Section 7.2, Figures 4.1c, 4.2g, 7.1c).I greedily remove less dominant and less projectable flowlines while enforcing thedescriptiveness threshold. I then further reduce the network energy EN , subject20to the descriptiveness constraints, by reassessing local flowline selection (Figure4.2h). While this combined process is not guaranteed to converge to a global mini-mum, it works well in practice, resulting in networks of similar complexity to thoseproduced by artists.4.5 RegularizationThe work presented in this section (Section 4.5) was developed by Nicholas Viningin consultation with Alla Sheffer and is provided here for completeness.Figure 4.7: Regularization; Before (left) and after (right).The network produced by the framework discussed so far is constrained by theunderlying mesh discretization. This can lead to sub-optimal wiggles along flow-lines and some approximately orthogonal, rather than strictly orthogonal, flowlineintersections (Figure 4.7, left). As a post-processing step, we eliminate these ar-tifacts by directly optimizing flowline geometry. We first use an iterative Gauss-Seidel smoother which straightens flowlines while maintaining and improving flow-line orthogonality at their intersections. Specifically, for each interior flowline ver-tex we project its neighbors to its tangent plane and the vertex toward the average ofthese projections. We relocate flowline intersections by applying the angle equal-izing mesh formula proposed by [41]. The newly computed positions are projectedto the input surface at each step. Finally, we detect all near-planar flowlines (aflowline is near-planar if every point on the flowline is less than half of the av-erage mesh edge length from its best-fit plane, computed via least squares) andmake them strictly planar, and straighten all near-linear flowlines (using the samedistance threshold, but tested against the best-fit line) (Figure 4.2i).21Chapter 5Measuring Network PropertiesFigure 5.1: (a) More (green) and less (red) well described cycles on a row-boat, before and after local optimization. (b) Flowlines colored by de-creasing projectivity (blue to red). (c) More (blue) and less (red) domi-nant flowlines.The framework of this thesis seeks to solve the optimization problem describedby Equation 4.1. I now derive the formulas used to measure the optimized energyand constraints. To enable meaningful combination of different values I express allquantities as angles (measured in degrees).5.1 Cycle DescriptivenessMy descriptiveness metric assesses how well a given network curve cycle describesthe region it surrounds (Figure 5.1a). Intuitively, I wish to measure how well thecurvature directions and magnitudes in the interior of a region can be reproducedfrom the magnitudes and directions along the boundary. However, estimating cur-vature differences is sensitive to different scales in high versus low curvature re-22n11n21np1nv f1f2Figure 5.2: Coverage; At the vertex v, interpolating along the flowline f1 theboundary normals n11 and n21 yield the prediction np1 . The error is thedifference between np1 and the actual normal n. Similarly, another erroris computed interpolating along f2. FlowRep aggregates all of thoseerrors for every vertex in the region.gions. To enable conservative and robust descriptiveness computation I use dif-ferences in normals as proxy for curvature changes: in particular, I measure theangle differences between real normals across the patch and ones predicted basedon normals along the cycles.I predict interior normals based on the boundary by locally mimicking themethod of Bessmeltsev et al. [2012]. Specifically, I follow each flowline fi fullytraversing the region from boundary to boundary. I use the normals at the cycleintersections n1i and n2i to obtain a normal prediction for each vertex v that belongsto the flowline and is inside the region (Figure 5.2):npi =d1d1+d2n1i +d2d1+d2n2i (5.1)Where di is the distance along the flowline from v to respective intersection point.I consider as the error the angle difference between the predicted normal and theactual surface normal n, which is defined as the average of the normals of the facesadjacent to the vertex that belong to the region:d(vi) = 6 (npi ,n). (5.2)23In theory I could extend this mechanism to handle vertices with no crossing flow-lines, e.g. by computing some directed paths from them to the boundary. However,given that the normals within the regions change gradually, if the region is suffi-ciently well spanned by flowlines, I found that it is safe to simply omit all suchvertices from my region descriptiveness computation.I seek a conservative descriptiveness estimate. Thus I refrain from using vertexdescriptiveness average as the per cycle value, yet I also wish to avoid using theworst value as it may be an outlier. Thus, rather than using the largest angle d(v)as the per-cycle error dc, I collect all errors for the vertices along a flowline strandand compute their 90th percentile value, then set dc to the maximum of those perstrand errors.It is possible that a region does not have enough spanning flowlines, or evennone at all. During the previous step I keep track of how many vertices wereprocessed, and if more than a third of the total were missed, I then fallback to asimple planarity test. I compute the average of all face normals of the region, thenset dc as the maximum difference of each normal to the average normal.5.2 Flowline Cost.This thesis assigns a cost p f + d f to each flowline based on how its presence im-pacts the descriptiveness d f and projectivity p f of the network N.5.2.1 Flowline ProjectivityI measure raw flowline projectivity by locally evaluating its planarity, its deviationfrom local geodesics, and its connections within the network. For each flowlinef I use short odd-length sliding sequences of vertices vi, . . .vi+k, . . . ,vi+2k to as-sess planarity and geodesicity (we use k = 5). I fit planes to triplets of verticesvi,vi+ j,vi+2k j ∈ [1,2k− 1]. We then measure sequence planarity as the averageangle between the normal of the central plane nk and those of the other planes n jfitted to the sequence:Pi =1k−1 ∑j∈[1,2k−1], j 6=k6 n jnk.24vi+kvivi+j vi+hvi+2knknj nhFigure 5.3: Projectivity; Three planes are fit to a sliding sequence of verticesfrom vi to vi + 2k. Their normals n j, nk, and nh are used to computeplanarity (as the difference between them) and geodesicity (comparingthem against the vertex normals).The planarity of the entire flowline is in turn the average of local sliding sequenceplanarity costs:P( f ) =1|i ∈ s|∑i∈sPi (5.3)Recall that a curve is locally considered a geodesic if its local fitting plane containsthe surface normal. I thus measure geodesicity by evaluating the angle between thenormal to the surface n at vi+k and the plane pk. Strictly speaking, geodesicity is aboolean property - in a continuous setting, a curve is either a geodesic or it is not.Thus the angle measure becomes meaningless above a certain value, leading us tocompute geodesicity asG( f ) =1|i ∈ s|∑i∈smin(6 nkn(vi+k),Gm) (5.4)where Gm = 15◦.As observed earlier, the interaction between network curves, specifically theirintersections, plays a major role in the projectivity of the overall network. Wheninterpreting the geometry conveyed by the network, human observers leverage or-thogonal crossings both between flowlines and between flowlines and trimmingcurves. I therefore prioritize retaining flowline curves that form such crossingsby associating endiness costs E1( f ) and E2( f ) with the ends of open flowlines. I25use an endiness value of 30 for flowline/trimming-curve T-junctions, and 60 for allothers. Both values are set to zero for a closed loop.The flowline projectivity is set p f as follows, weighing geodesicity by dmax/Gmto bring all values to a common scale,p f = P( f )+dmaxGmG( f )+E1( f )+E2( f ) (5.5)5.2.2 Flowline DominancePredicted normalsActual normalsFigure 5.4: Normal predictions match the actual normals (left). Removingthe middle flowline affects the normal predictions (right), that then di-verge from the actual normals, leading to a high dominance cost.Assessing dominance by measuring curvature continuity, as suggested by de-sign literature, is unreliable in a discrete setting. Instead, I observe that a flowline’sdominance within a network context can be evaluated by measuring the impact ofremoving this flowline on the descriptiveness of the affected cycles. The higher theresulting descriptiveness error, the more dominant the flowline. Recalling that thedominance error is computed as a maximum along two spanning flowline direc-tions, I note that removing a network flowline impacts only one of these directions(Figure 5.4). Accordingly, to better pinpoint the impact of each network flowline,I use a modified cycle descriptiveness metric when assessing the impact of the re-moval. For each cycle resulting from removing a flowline f , I only consider thedifferences between the predicted and actual normal for normals predicted usingflowlines crossing f , and ignore the differences along other flowlines. I then usethe maximum of the cycle errors as a dominance estimate D( f ). Since I want the26cost to be smaller the more dominant a flowline is, we used f = 360−D( f ) (5.6)as the cost. Figure 5.1 visualizes some flowlines colored based on projectivityand dominance. Note that these costs are only meaningful in the context of anetwork. Thus when computing flowlines prior to network construction, I requireproxy values to predict flowline properties, as discussed in the next chapter.27Chapter 6Flowline ComputationFigure 6.1: Dominant flowline strands on the mug: (a) initial edge strandsand (b) extracted conservative flowlines; (c) final strands and (d) flow-lines.The goal of the flowline computation stage is to generate a set of reliable flow-lines which we can use to assemble the network (see Chapter 7). Since purely localreasoning about individual flowline formation is unreliable I employ a global ap-proach that leverages directional similarity between edges associated with adjacentflowlines (Figure 4.6). First I form strands, or clusters, of similarly directed edges,and then extract individual flowlines from these strands.When forming strands I employ the following positive (likely to be in samestrand) and negative (likely to be in different strands) cues. Edges are expected tobelong in the same strand if they are roughly parallel, and either share commonvertices or lie on opposite sides of common quads (Figure 6.2).They are expected to belong to different strands if they share common vertices28e+++−−−−Figure 6.2: Positive and negative cluster associations of edges around edge eand are roughly orthogonal. Once formed, flowlines belonging to the same clustershould not cross one another. While the no-crossing constraint is a very strongclustering cue, I cannot apply it to our raw input consisting of individual edges. Totake advantage of this cue, I employ a two-stage process: I first form initial strandsusing only cues applicable to edges and extract initial conservative flowlines fromthose; I then use those initial flowlines to generate a set of reliable strands using thefull set of clustering cues; and finally use those strands to extract reliable extendedflowlines.The combination of positive and negative cues that I use for strand formationnaturally feeds into a correlation clustering framework [2]. I employ the version ofcorrelation clustering that maximizes ∑e ceYe, where Ye ∈ 0,1 is 0 if the end nodesof the arc e are in different clusters and 1 if they are in the same cluster. Whilethe general correlation clustering problem is NP-hard, it has a number of efficientapproximation methods. I use the method of [30] to compute the clusters; whilenot optimal, it performs well in practice. The specific edge weights used in my twoclustering steps are defined below.6.1 Initial Strands and Flowlines.6.1.1 Initial StrandsTo form initial strands using correlation clustering (Figure 4.2b) mesh edges aretreated as graph nodes, and I associate non-zero weights with the arc connecting29edge nodes i, j when these either share a common vertex, or form opposite sides ina mesh quad. When a pair of mesh edges i, j share a common vertex, I define thearc weight ci j asci j =e−( αi jσ1)2, if αi j ≤ 45wne−( 90−αi jσ2)2, otherwise(6.1)αi j is the angle difference between the unsigned edge directions projected to thevertex tangent plane, wn =−5, σ1 = 5, and σ2 = 15. This weight is positive whenedge directions are closer to parallel than orthogonal, and negative otherwise. Forarcs connecting opposite edges within each quad, I define the weight asci j = wpe−( αi jσ3)2. (6.2)I set σ3 = 5◦ and use a very small parallel coefficient wp = 0.05, as at this stage Idesire clusters dominated by local flowline smoothness.6.1.2 Initial Flowline ExtractionI generate flowlines from strands by segmenting the connected components of eachstrand into individual flowline edge sequences (Figure 4.2c). I avoid making anypotentially ambiguous choices by using all irregular (non valence 4) and trim curvevertices within such components as flowline termination points and define eachresulting one-dimensional edge sequence as a flowline.6.2 Reliable Strands and Flowlines.6.2.1 Reliable StrandsThe initial flowlines allow for more global reasoning about, and consequently ex-traction of, more reliable strands and flowlines (Figure 6.1). I use a similar processfor extracting these flowlines as for the initial ones, but incorporate additional in-formation provided by the current segments. I obtain reliable strands using ourcorrelation clustering setup by treating the initial flowlines as graph nodes, andassociating arcs with pairs of flowlines f , f ′ that share common end vertices or30contain edges on opposite sides of mesh quads. At each shared end vertex, I firstcompute the tangent vectors for the emanating flowlines f , f ′ using the averageacross a local neighborhood set to five average mesh edge lengths. I then computec f , f ′ as a function of the angle between these tangents using Equation 6.1, but witha more tolerant value, σ1 = 7.5. For flowlines that share two endpoints I sum upthe values obtained at both ends.For each pair of flowlines, f and f ′, that contain opposite edges i ∈ f , j ∈ f ′on shared quad mesh faces, I compute the arc weight as a function of both theangles between such pairs of opposite edges, and the proportion of such oppositeedges as a function of the length l of the shorter flowline. Intuitively, the biggerthis proportion, the more likely the flowlines are to be in the same strand:c( f , f ′) =2l ∑i, je−( αi jσ3)2. (6.3)As observed earlier, crossing flowlines should not belong to the same cluster. Itherefore associate a large constant negative arc weight c( f , f ′)=−25 with each pairof crossing flowlines ( f , f ′). The overall score function that strand computationseeks to maximize is max∑c( f , f ′)Y( f , f ′) where Y( f , f ′) is 1 if the two flowlines are inthe same cluster and 0 if not.6.2.2 Reliable Flowline ExtractionI use the obtained strands to extract extended reliable flowlines (Figure 4.2e). Theconnected components of flowline strands can form a range of graph configura-tions, allowing for multiple individual flowline configurations. I form our reliableflowlines using a greedy process which prioritizes extraction of more projectableand longer flowlines within each component. I measure projectivity using the met-ric in Section 5.2. Flowline endiness costs E1,E2 (Section 5.2) dominate all otherprojectivity components and are lowest for closed loops. Thus for each connectedcomponent I extract all closed loop flowlines first, prioritizing more projectableclosed loops when given multiple options. I then use a greedy process to extractthe longest open flowlines that cannot be extended, i.e. ones that start and end at avalence one vertex, again prioritizing more projectable ones, given multiple same31length alternatives. Mesh artifacts can result in spiraling flowlines, where one edgeis directly or indirectly parallel to another edge. While sometimes these spiral flow-lines need to be included in the final network for description purposes, one cycleis often sufficient to describe the surrounding geometry. To facilitate processingof individual cycles, I detect spirals in the same way as for conservative flowlines,and split them at the point where they complete a full cycle but have yet to becomeparallel. If there are multiple such points, I select the one(s) which result in themost projectable flowlines.Algorithm 1 Compute Flowlinesprocedure COMPUTEFLOWLINES(mesh = (V,E))Construct a graph G1 where each node is an edge of meshfor each edge i ∈ E dofor each edge j connected to i doG1[i, j]← ci j (Eq. 6.1)for each edge j face-opposite to i doG1[i, j]← ci j (Eq. 6.2)C1 = CorrelationClustering(G1) . maximize ∑e ceYeJoin connected edges in each c ∈C1 into initial flowlinesConstruct a graph G2 where each node is a flowlinefor each flowline f dofor each flowline f ′ sharing an end-point v with f doG2[ f , f ′]← ci j (Eq. 6.1, with i and j being tangential vectors of fand f ′ at v.)for each flowline f ′ intersecting f doG2[ f , f ′]← (−25)for each flowline f ′ parallel to f doG2[ f , f ′]← c f , f ′ (Eq. 6.3)C1 = CorrelationClustering(G2) . maximize ∑e ceYeJoin connected flowlines in each c ∈C2 into reliable flowlines32Chapter 7Network ComputationFigure 7.1: Network computation: (a) Initial trim curve network; (b) descrip-tive dense network; (c) final network.I use the computed flowlines to form a descriptive network by employing amixed top-down/bottom-up strategy. Starting with a network of trim curves only, Ifirst progressively add flowlines to obtain a dense network that describes the inputmodel within the given descriptiveness threshold dmax (Figure 4.2f, 7.1b); I thensimplify it by removing redundant flowlines (Figure 4.2g, 7.1c).337.1 Top-Down: Dense Descriptive Network Computation7.1.1 Network InitializationI compute feature curves on the input model using ridge and valley detection [46]with conservative settings designed to capture only sharp features. The boundaryand extracted feature curves form the initial network, which I use to partition theinput surface into a set of cycles surrounded by network curves (Figure 7.1a). Ievaluate the descriptive error dc of each cycle and classify these cycles as eithercovered or uncovered depending on whether it is below, or above, the descriptive-ness threshold dmax. Note that the trim curve network may not form any cycles,and may even be empty; in this case, the initial cycle set contains one uncoveredregion which spans the entire input surface.7.1.2 Network RefinementI define a flowline as spanning a region if it splits it into two or more separate re-gions. I refine the network by iteratively incorporating flowlines that span currentlyuncovered regions: for each uncovered region, I detect all flowlines that span it; Iadd all located spanning flowlines into the network, shortening them as describedbelow to avoid forming undesirable network topology. I then compute the cycle-descriptiveness error (Section 5.1) for all newly formed regions. The algorithmrepeats the above step until all regions are covered or there are no more flowlinesthat can be added to the network.7.1.3 Flowline ShorteningAs noted in Chapter 3, network projectivity depends on its connectivity. In partic-ular, flowlines are least projectable when terminating at valence one or two end-points and T-junctions between flowlines and trim curves are more projectable thanT-junctions between flowlines.I maximize the projectivity of each open flowline we embed in the network, bycollapsing open end-points to T-junctions (Figure 7.2, right) and collapsing purelyflowline T-junctions to flowline-trim curve T-junctions (Figure 7.2, left), while con-straining the shortened flowline to span the same set of uncovered regions. I first34××fFigure 7.2: A flowlines is shortened to terminate at trim curves when possible(left) or to other flowlines (right).identify the section of each flowline that spans this set of regions and the excesssections on either end of it. If an excess section does not end at a trimming curve,but does intersect one, I shorten it to the closest such intersection to its current endpoint. Similarly, if it ends at a valence 1 or 2 vertex, I shorten it to end at the nearestflowline intersection to the current end point.7.2 Bottom-Up: Network SimplificationI formulate the extraction of a compact network out of the dense descriptive net-work produced by the previous step as a direct optimization of the constrainedproblem formulated in Chapter 4. In contrast to the original formulation, whichoperated by assigning edges to flowlines, I keep the flowlines computed in the pre-vious stage largely fixed, and focus on selecting the optimal subset among them(Figure 4.2g).My discrete optimization goal can consequently be formulated as computingthe subset of flowlines f ∈ N that minimizes EN , subject to the constraint thatmaxdc < dmax over all cycles c in the resulting network. While such discrete con-strained minimization problems often require sophisticated machinery to optimize,my co-authors and I found that a greedy approach that mimics classical mesh sim-35plification, followed by local flowline movement, works sufficiently well for ourneeds.7.2.1 SimplificationI place the flowlines in a priority queue ordered by their cost (Section 5.2), thenrepeatedly remove the highest cost flowlines whose removal does not violate thedescriptiveness constraint from the network. After each flowline is removed, Iupdate the cost of its neighboring flowlines and compute the descriptiveness errorfor the newly formed, merged, regions. This process terminates when no flowlinescan be removed without violating the constraints. A typical simplification outputis shown in Figure 7.1.Removing a flowline from a network can result in undesirable valence 2 or1 joints at the endpoints of remaining flowlines. To avoid these, I shorten suchremaining flowlines by removing the sections between the undesirable endpointsand their nearest network intersections. Before shortening the flowlines I checkif doing so would violate the descriptiveness threshold. If the threshold would beviolated I abort the precipitating flowline removal; otherwise I remove the flowlineand perform the shortening step.7.2.2 Connectivity OptimizationWhen two or more flowlines end at a common valence four vertex, removing oneof these flowlines reduces network projectivity by reducing the valence of the in-tersection. It is important to penalize valence reduction, but not completely preventit. Prior to starting the simplification, I locate all sequences of compatibly orientedflowlines that share common endpoints. Flowlines are deemed compatible if theangle between their tangents at the shared point is obtuse. I merge these sequencesinto composite flowlines. A composite flowline is a proxy for the flowline formedby its components, shares the same score and properties of a regular flowline andis placed in the same simplification queue. For each flowline within a compos-ite flowline we set the endiness Ei cost (Section 5.2) for the endpoint within thecomposite to zero, decreasing the likelihood of these flowlines being targeted forremoval, before the composite. The result is that the simplification algorithm can36remove a whole composite flowline in a single step, but it can also potentially re-move a part of it, if appropriate. During simplification, when any such interiorflowline is removed, I update the composite and the cost of the other flowlinesinterior to this composite accordingly.7.2.3 Post-process Local OptimizationPost-simplification I locally further optimize the network as follows (Figure 4.2h,5.1a). First, for each flowline, I locate its immediately adjacent left and right flow-lines in the same strand, and test the impact of removing the current flowline fromthe network and adding its immediate neighbor instead. I perform the substitu-tion if it decreases the network energy and the resulting network still satisfies thedescriptiveness threshold. I repeat these steps as long as the energy decreases.After local optimization, I once again shorten open network flowlines, remov-ing end-sections if doing so replaces valence 1 or 2 endpoints with T-junctions orreplaces pure flowline T-junctions by flowline-trim curve ones, and does not violateour cycle-descriptiveness threshold.As in many other segmentation setups, output networks may occasionally endup with close by parallel flowlines none of which can be removed without liftingthe descriptiveness error for a neighboring cycle just above the threshold. To avoidvisual clutter, I detect such pairs of adjacent parallel flowlines (using a distancebound of two average mesh edge lengths) and examine the impact on the descrip-tiveness error of removing either one or the other. I select as a candidate a flowlinewhose removal increases the error the least. I remove this flowline if the increasein the descriptiveness error is less than 20%.37Algorithm 2 Network Computationprocedure COMPUTENETWORK(network N)for each trimming curve t do . Network RefinementN← (N∪{t})while ∃(cycle c) | dc < dmax dofor each cycle c with dc > dmax dofor each flowline f splitting c in two parts doN← (N∪{ f})Construct all composite flowlines fc . Network SimplificationLet C be the set of all composite flowlinesLet Q be a priority queuefor each flowline f ∈ (N∪C) doCompute flowline cost p f +d f of f (Eq. 5.5, 5.6)Q← Q∪{ f}while Q is not empty dof ← maximal cost flowline in QQ← (Q\{ f})if ∀cycles c ∈ (N \{ f}),dc < dmax thenN← (N \{ f})Update costs p fn +d fn of neighbors fn of ffor each flowline f ∈ N do . Local Optimizationfor each neighbor fn of f doif p fn < p f ∧∀cycle c ∈ ((N \{ f})∪{ fn}),dc < dmax thenN← ((N \{ f})∪{ fn})38Chapter 8ValidationThe user studies presented in this chapter were conducted by Enrique Rosales andNicholas Vining, in consultation with Alla Sheffer and myself. They are describedhere for completeness.We validate the results produced by our method in a number of ways: by com-paring our outputs against artist-generated networks and prior art, by performing aqualitative evaluation study, and by demonstrating that the networks generated byour method can be used to closely reproduce the originating models.8.1 Comparison to Artist Generated NetworksWe selected 4 models (rounded cube, treball, mouse, boat) ranging from simple(cube) to highly complex (mouse, boat) and provided them to three industrial de-signers/artists. We asked one artist to manually generate descriptive 3D curve net-works for these models, and asked two artists to create design drawings of themfrom given descriptive views. While the artist results are, as expected, not iden-tical, they all share common characteristics, which are similarly captured by ouroutputs (Figure 8.1). It took the artist over three hours to generate the 3D curvenetworks (two hours for the mouse, one for the boat, and about half an hour totalfor the simpler two models). Our fully automatic method takes a fraction of thistime, generating all four results in under five minutes.To provide further comparison to artist-created networks, we qualitatively com-39Figure 8.1: Comparison against artist generated networks: (left to right) inputmodel, artist generated 2D design drawings and 3D network (red), andour algorithmic result (blue).pared our output to the inputs used by [3, 36] (Figure 8.8, right). We directlyprocessed quad-meshes produced by Bessmeltsev et al. [2012] (coffee-machine,airplane). We also quad-meshed and processed the dog-head surface producedby Pan et al. [2015]. Our output networks (blue) are very similar to their inputs(green).8.2 Comparison to Prior ArtFigure 8.2: Suggestive contours combined with ridge and valley lines [17] (b)convey the overall input shape (a); a FlowRep descriptive network (c)provides a more detailed and accurate description of the input geometry.Figures 8.2, 8.3, 8.4, and 8.5 show representative comparisons of our outputsagainst prior art. As Figure 8.2 demonstrates, while suggestive contours combinedwith ridge/valley lines convey the overall input shape, our networks provides a40Figure 8.3: Surface segmentation (e.g. VSA [14]) (b) and reverse engineer-ing methods (d,e) are not designed for, and do not produce, projectablecurve networks; their output is often not descriptive to a human ob-server. FlowRep networks (c,f) satisfy both criteria.more precise description of the input. Figure 8.3 contrasts our networks with thosegenerated by planar segmentation and reverse engineering approaches; as demon-strated FlowRep outputs support better mental visualization of the input than suchapproaches.41Figure 8.4: (a) Quad-partition [7] of the treball and ellipsoid (a) comparedto our network (b). Quad partitions, here [24], are highly dependenton the singularity locations in the initial mesh drifting from curvaturedirections (c). FlowRep result on same model (d).As demonstrated in Figures 1.3 and 8.4a, quad partition boundaries (e.g. [7])are not projective, making it hard for viewers to envision the originating geom-etry. They are also often misaligned with curvature directions as highlighted bythe mismatch between shading and curve directions in Figure 8.4c (network cour-tesy of [24]). Such misalignment results in non-descriptive cycles. Our networksare strictly aligned with curvature directions (Figure 8.4d) and enable viewers toenvision the originating shape from a 2D projection.While exoskeletons [16] reduce the number of T-junctions formed by uncon-strained VSA [14], this semi-automatic method is only suitable for coarse abstrac-tion, while our automatic framework captures much finer details on the same ge-ometry (Figure 8.5, top). As highlighted by Figure 9.2, mimicking their bottom-upapproach using an automatic process results in fragmented flowlines. Lastly, asshown in Figure 8.5 (bottom) planar slice proxies [32], while descriptive of multi-part simple shapes, compare poorly to our networks on typical design shapes.42Figure 8.5: While exoskeletons [16] only roughly capture coarse part struc-tures of shapes (b), our method describes the geometry in more detail(c). Planar slices [32] are restricted in their ability to convey free-formshape (e,h), while FlowRep networks are well suited for this task (f,i).8.3 Qualitative EvaluationHow well do the design drawings on the bottom reflect the shape on the top?A B C DWhich figure on the bottom (B or C) more accurately describes the shape on the top (A)?B CAFigure 8.6: Study questionaire layouts: FlowRep compared to artists (left)and FlowRep compared to previous work (right).We showed seven designers (including the two who produced the drawn net-works) images of our results and of the results produced by the artists, withouttelling them which is which. To ensure uniform style we used identical views, linestyle and color, and generated non-transparent renders for the 3D models. The43model was shown in top row and the renders in bottom row (Figure 8.6, left). Wethen asked the designers “How well do the design drawings on the bottom reflectthe shape on the top?”. All seven designers assessed all the shown networks asreflective of the input, ranking ours on par with other renders; three of them com-mented on our mouse and boat as being most descriptive. The positive commentsincluded “easier to understand”, “precise and simple”, “great sense of depth”. Onthe negative side one commented that some of our curves were not smooth, andone designer felt that the curves on the mouse were too close to one another.We also conducted a study to compare our outputs to previous work. We asked34 nonexpert users to compare our outputs to curve networks generated by alter-native methods. Each query in this study included an input model (A, top) andtwo curve networks (B and C, bottom), arranged in random order and presentedside by side: one generated by our algorithm, and one generated by an alterna-tive method (suggestive contours [17], quad patch layouts generated by [7] and[24], variational shape approximation [14], exoskeletons [16], and planar slices[32], totaling eight queries.) (Figure 8.6, right). Users were asked the question,“Which figure on the bottom (B, or C) more accurately describes the shape on thetop (A)?”. Across all queries participants preferred our outputs to the alternatives92% of the time. The individual comparison with lowest majority preference forour method (80%) was against quad partition [7] on the ellipsoid (Figure 8.4). Thenetwork drawings used for the evaluation were generated using descriptive views,and the same view was used for all models. The exact questionnaires used in theevaluation are included in our supplementary material.8.4 ReproductionOur method aims to create networks that can be used to reproduce the input shapesboth mentally and algorithmically. To validate the algorithmic reconstruction fea-ture we ran the surfacing framework of [36] on a subset of our outputs (Figure 8.7).As shown, the surfaced networks look very similar to the input models. The L2distance between the inputs and the re-surfaced networks measured using [12] wasunder 0.3% of the bounding box diagonal, leading us to conclude that our networksdo not only describe the models perceptually but also compactly and accurately en-44Figure 8.7: Reproduction. Pairs of input models with computed FlowRepnetworks (wireframes) and these networks resurfaced using [36] (blue).Figure 8.8: Reproduction. Input curve networks (green), surfaces producedby [3, 36], and our networks (blue) computed from these surfaces.code their geometry.45Chapter 9ResultsThis thesis demonstrated my method on a large set of inputs, ranging from simple(rounded cube, spiral, torus, bump) to highly complex (shuttle, boats, mouse, toi-let). I tested various models including open surfaces (beetle, bathtub), ones withsharp features (mouse, row-boat), and smoother, more organic ones (treball, spi-ral, ellipsoid, phone handle, dog-head, big buck bunny). I tested my method oncoarsely meshed complex shapes (beetle, at 4K triangles) as well as fine meshedones (mouse, boat, toilet, at 30K triangles each). My results on all these modelsare consistent with human expectations.9.1 SymmetryMost quad-meshers do not detect or enforce global symmetry. To produce globallyreflectively symmetric results we use external code to detect global reflective sym-metries, quad-mesh one half of a symmetric model, and use a reflected mesh asinput. We used this approach for the boat, mouse, bottle, phone-handle, big buckbunny, and dog-head.9.2 Network ResolutionOur framework allows users to control the density of the output curve networks bychanging the descriptiveness threshold dmax, as illustrated in Figure 9.1. By defaultwe use a threshold of 20◦. For the rowboat and wineglass we used thresholds of46Figure 9.1: Networks with different descriptiveness thresholds, shown on theellipsoid model.30◦ and 10◦ to obtain more aesthetically pleasing results. We use 30◦ for moreorganic models (doghead, phone).9.3 Impact of Design ChoicesFigure 9.2: Alternative network extraction methods: (a) bottom-up cycleclustering results in poorly descriptive networks with highly irregularconnectivity; network optimization using only flowline projectivity (b)or only their dominance (c), versus full optimization (d).Figures 4.6 and 9.2 demonstrate the impact of the key algorithmic choices onthe final results. Figure 4.6 demonstrates the importance of using my strand forma-tion process to obtain reliable flowlines. This process contributes to my success inprocessing highly irregular meshes, with singularities and numerous edges whichare misaligned with curvature directions. Figure 9.2 shows a comparison againsta number of alternative network formation strategies. The first mimics [16] asit uses a bottom up cycle growth strategy directly optimizing EN (Equation 4.1)while aiming to keep consecutive flow-lines or edges together to minimize the ap-pearance of T-junctions. Even on simple models, this strategy results in highly47irregular networks with redundant T-junctions and fragmented flowlines.Figures 9.2b and c show the impact of using a network simplification strategythat takes only flowline projectivity (b) or only its dominance (c) into account. Bothnetworks satisfy the descriptiveness threshold, but select different representativeflowlines within individual strands. Absent dominance (Figure 9.2b) the result hasmore geodesic flowlines but has some less well described cycles; in contrast inFigure 9.2c the cycles are well described but the interior symmetry curve is notincluded. My solution (Figure 9.2d) balances both sets of criteria, and is morereflective of traditional drawings of such toroidal shapes.9.4 Input Mesh ImpactFigure 9.3: Impact of systemic mesh vs curvature tensor misalignment: (a)Interleaved spiral flowlines resulting from curvature drift may result inundesirable T-junctions (mesh from [28]); (b) more significant misalign-ment predictably distorts the network orientation (mesh from [7]); (c)large patches of randomly aligned quads (top of the hat) similarly leadto artifacts.Figure 9.4: Curve networks generated from different meshes of same model:(a) [7], (b) ArtMesh. The input mesh in (a) exhibits feature drift (sharpfeatures migrating between mesh flowlines); leading FlowRep to pre-serve these flowlines generating visual redundancy.I tested my framework on quad-meshes produced by a range of sources. Mostof our inputs were generated using ArtMesh (http://www.topologica.org) or were a48priori given to me in quad-mesh format (spiral, glass, bathtub, beetle). The planeand coffee-machine in Figure 8.8 were generated by [3]. I also tested inputs gen-erated using quad-patch layout [7] (Figures 9.4, 9.3b) and Instamesh [28] (phonehandle, and Figure 9.3a). As the examples demonstrate, FlowRep is largely agnos-tic to mesh artifacts, such as non-quad elements, irregular connectivity, and unevenelement sizing, e.g. Figure 1.3b. The method is more sensitive to consistent curva-ture misalignment and irregular mesh flow in isotropic areas (hat, Figure 9.3c). In-put meshes whose edges form long spirals due to systemic edge direction drift [28]may lead to extra T-junctions in the final output (Figure 9.3a). While FlowRepcan process meshes whose edge directions consistently and significantly deviatefrom curvature directions, such as those sometimes produced by quad-patch layout(e.g. [7]), the results in this case are, as expected, less reflective of human expecta-tions (Figure 9.3b).9.4.1 Curvature re-alignmentArtMesh meshes are generated with quad shape and size in mind, often sacrificingedge alignment to curvature for those properties. For this thesis the regularity ofthe quads is not as important as the alignment to the flow, so I need to undo thatprocess and optimize for better alignment.Consecutive segments of the same flowline at any given point on the surfacetend to share the same tangent and the tangents of intersecting streamlines to beorthogonal, up to discretization accuracy. I therefore wish for all angles on themesh to be as close as possible to either 90◦ or 180◦.For each vertex v, consider the angle α described by one of its adjacent facesf . We find whether α is closer to 90◦ or 180◦ and compute its difference ω to that.ω =α−90◦ if α < 135◦α−180◦ otherwise (9.1)Then, I simply push or pull v away or to the center of the face, according to ω .v = v+ω(v− center( f )) (9.2)49I repeat the above for every face of every vertex with valence 4 or less. Highervalence vertices are often misleading, meaning that the procedure would improvethe wrong angle, and are best left untouched.9.5 Parameters and RuntimeshalfdoubleWn Wp D(f) G(f) pfFigure 9.5: Impact of halving/doubling default algorithm parameters(weights used for correlation clustering; weights of different elementsof En (Eq. 4.1)).With the exception of the descriptiveness threshold dmax all other algorithmparameters are fixed across all inputs, and as shown in Figures 9.2, 9.5 changingthem has fairly minimal impact on the outcome.FlowRep runtimes range from 3 seconds for simple models such as the wine-glass (5K faces) to 48 and 111 seconds for complex ones such as the mouse (30Kfaces) and the toilet (28K faces) respectively. Roughly 75% of the time is spentperforming edge correlation clustering for flowline initialization. Once initial flow-lines are formed, the simplification stage dominates, taking another 20%. Overall,the dominating runtime factors are the original mesh resolution and geometric com-plexity.9.6 LimitationsMy method relies on curvature-aligned quad-dominant meshes to serve as a reli-able proxy of a curvature aligned tensor field smoothly extended across isotropicareas. It successfully overcomes sporadic topological noise (e.g. Figure 1.3) butis affected by systemic misalignment and uneven mesh sizing (Figure 9.3). The50Figure 9.6: Additional results.trade-off I require is supported by many research and commercial meshers. Myframework does not explicitly account for symmetries, beyond global reflection,even when these are present in the mesh. Detecting such symmetries at the meshlevel using existing methods, and then enforcing similar processing on symmetricedges and flowlines, would alleviate this concern.51Chapter 10ConclusionsThis thesis presented FlowRep, the first algorithm for computing descriptive com-pact curve networks from an input mesh. My output networks succinctly describecomplex free-form shapes and are suitable for both perceptual and algorithmicreconstruction. When computing the networks my method optimizes two maincriteria: cycle-descriptiveness, or the network’s ability to describe the underlyingsurface, and network projectivity — the ability to perceive the network’s 3D shapefrom its 2D projection. I use these properties to first trace reliable flowline curveson the surface, then use the flowlines to extract an initial projectable and descriptivenetwork, and finally coarsen the network while maintaining a given descriptivenessthreshold. Combined together, these steps result in descriptive networks compara-ble with those produced by artists, and which have been extensively validated toshow that they agree with viewer perception.This work opens many avenues for future research. As noted, the results arecontingent on the quality of the input quad meshes. Producing initial meshes tunedto optimally adhere to my requirements can both simplify the algorithm and im-prove its results. Mine is the first attempt to evaluate network suitability for the taskat hand. Additional perception research may be able to improve this formulation,and machine learning algorithms based on perceptual studies might better pinpointthe necessary balance between the key geometric properties I have identified.52Bibliography[1] P. Alliez, D. Cohen-Steiner, O. Devillers, B. Le´vy, and M. Desbrun.Anisotropic Polygonal Remeshing. ACM Trans. Graph., 22(3):485–493,2003. → pages 6[2] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Mach. Learn.,56(1-3):89–113, 2004. ISSN 0885-6125. → pages 19, 29[3] M. Bessmeltsev, C. Wang, A. Sheffer, and K. Singh. Design-drivenquadrangulation of closed 3d curves. ACM Trans. Graph., 31(6):178:1–178:11, 2012. ISSN 0730-0301. → pages xi, 3, 4, 10, 11, 23, 40, 45,49[4] R. Bnire, G. Subsol, G. Gesquire, F. L. Breton, and W. Puech. Acomprehensive process of reverse engineering from 3d meshes to CADmodels. Computer-Aided Design, 45(11):1382 – 1393, 2013. ISSN0010-4485. → pages 3, 7[5] D. Bommes, T. Vossemer, and L. Kobbelt. Quadrangular parameterizationfor reverse engineering. volume 5862 of Lecture Notes in Computer Science,pages 55–69. Springer, 2008. → pages 7[6] D. Bommes, T. Lempfer, and L. Kobbelt. Global structure optimization ofquadrilateral meshes. Computer Graphics Forum, 30(2):375–384, 2011. →pages 8[7] D. Bommes, M. Campen, H.-C. Ebke, P. Alliez, and L. Kobbelt. Integer-gridmaps for reliable quad meshing. ACM Trans. Graph., 32(4):98:1–98:12,2013. ISSN 0730-0301. → pages viii, xi, xii, 4, 5, 8, 42, 44, 48, 49[8] M. Bordegoni and C. Rizzi. Innovation in product design. Springer, 2011.→ pages 1253[9] M. Campen and L. Kobbelt. Dual strip weaving: Interactive design of quadlayouts using elastica strips. ACM Trans. Graph., 33(6), 2014. → pages 7[10] M. Campen, D. Bommes, and L. Kobbelt. Dual loops meshing: Qualityquad layouts on manifolds. ACM Trans. Graph., 31(4):110:1–110:11, 2012.ISSN 0730-0301. → pages 3, 8[11] M. Campen, M. Ibing, H.-C. Ebke, D. Zorin, and L. Kobbelt.Scale-Invariant Directional Alignment of Surface Parametrizations.Computer Graphics Forum, 2016. → pages 5, 15[12] P. Cignoni, C. Rocchini, and R. Scopigno. Metro: Measuring Error onSimplified Surfaces. Computer Graphics Forum, 1998. → pages 44[13] P. Cignoni, N. Pietroni, L. Malomo, and R. Scopigno. Field-aligned meshjoinery. ACM Trans. Graph., 33(1):11:1–11:12, 2014. ISSN 0730-0301. →pages 9[14] D. Cohen-Steiner, P. Alliez, and M. Desbrun. Variational shapeapproximation. ACM Trans. Graph., 23(3):905–914, 2004. ISSN0730-0301. → pages xi, 3, 7, 9, 41, 42, 44[15] F. Cole, A. Golovinskiy, A. Limpaecher, H. S. Barros, A. Finkelstein,T. Funkhouser, and S. Rusinkiewicz. Where do people draw lines? ACMTrans. Graph., 27(3), 2008. → pages 8[16] F. De Goes, S. Goldenstein, M. Desbrun, and L. Velho. Exoskeleton: Curvenetwork abstraction for 3d shapes. Comput. Graph., 35(1):112–121, 2011.ISSN 0097-8493. → pages xi, 9, 42, 43, 44, 47[17] D. DeCarlo, A. Finkelstein, S. Rusinkiewicz, and A. Santella. Suggestivecontours for conveying shape. ACM Trans. Graph., 22(3):848–855, 2003.→ pages xi, 3, 8, 40, 44[18] K. Eissen and R. Steur. Sketching: Drawing Techniques for ProductDesigners. Bis Publishers, 2008. → pages 4, 8, 9, 12, 13, 14[19] K. Eissen and R. Steur. Sketching: The Basics. Bis Publishers, 2011. →pages 14[20] D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf. Motorcycle graphs:Canonical quad mesh partitioning. In Proceedings of the Symposium onGeometry Processing, pages 1477–1486, 2008. → pages 3, 854[21] R. Gal, O. Sorkine, N. J. Mitra, and D. Cohen-Or. iwires: Ananalyze-and-edit approach to shape manipulation. ACM Trans. Graph., 28(3):#33, 1–10, 2009. → pages 1[22] A. Gehre, I. Lim, and L. Kobbelt. Adapting Feature Curve Networks to aPrescribed Scale. Computer Graphics Forum, 2016. → pages 1, 3, 9[23] G. Gori, A. Sheffer, N. Carr, T. Ju, N. Vining, and E. Rosales. Flowrep:Descriptive curve networks for free-form design shapes. ACM Transactionon Graphics, 36(4), 2017. doi:http://dx.doi.org/10.1145/3072959.3073639.→ pages iv[24] E. Gunpinar, M. Moriguchi, H. Suzuki, and Y. Ohtake. Feature-awarepartitions from the motorcycle graph. Comput. Aided Des., 47:85–95, 2014.ISSN 0010-4485. → pages xi, 8, 42, 44[25] E. Gunpinar, M. Moriguchi, H. Suzuki, and Y. Ohtake. Motorcycle graphenumeration from quadrilateral meshes for reverse engineering. Comput.Aided Des., 55:64–80, 2014. ISSN 0010-4485. → pages 8[26] K. Hildebrandt, K. Polthier, and M. Wardetzky. Smooth feature lines onsurface meshes. In Proc. SGP 2005, SGP ’05, Aire-la-Ville, Switzerland,Switzerland, 2005. Eurographics Association. ISBN 3-905673-24-X. →pages 8[27] E. Iarussi, D. Bommes, and A. Bousseau. Bendfields: Regularized curvaturefields from rough concept sketches. ACM Trans. Graph., 2015. → pages 10[28] W. Jakob, M. Tarini, D. Panozzo, and O. Sorkine-Hornung. Instantfield-aligned meshes. ACM Trans. Graph, 34(6), 2015. → pages xii, 48, 49[29] D. Julius, V. Kraevoy, and A. Sheffer. D-Charts: Quasi-Developable MeshSegmentation. Computer Graphics Forum, 2005. → pages 7[30] M. Keuper, E. Levinkov, N. Bonneel, G. Lavoue´, T. Brox, and B. Andres.Efficient decomposition of image and mesh graphs by lifted multicuts. InProc. ICCV, 2015. → pages 29[31] Y.-K. Lai, Q.-Y. Zhou, S.-M. Hu, J. Wallner, and H. Pottmann. Robustfeature classification and editing. IEEE Trans. Vis. Comp. Graphics, 13(1):34–45, 2007. → pages 8[32] J. McCrae, K. Singh, and N. J. Mitra. Slices: A shape-proxy based on planarsections. ACM Trans. Graph., 30(6), 2011. → pages xi, 9, 13, 42, 43, 4455[33] R. Mehra, Q. Zhou, J. Long, A. Sheffer, A. Gooch, and N. J. Mitra.Abstraction of man-made shapes. ACM Trans. Graph., 28(5), 2009. →pages 1, 3, 9[34] A. Myles, N. Pietroni, and D. Zorin. Robust field-aligned globalparametrization. ACM Trans. Graph., 33(4):135:1–135:14, 2014. ISSN0730-0301. → pages 3, 8, 15[35] M. Nieser, C. Schulz, and K. Polthier. Patch layout from feature graphs.Comput. Aided Design, 42(3), 2010. → pages 7[36] H. Pan, Y. Liu, A. Sheffer, N. Vining, C. Li, and W. Wang. Flow alignedsurfacing of curve networks. ACM Trans. Graph., 34(4), 2015. → pages xi,3, 4, 10, 11, 40, 44, 45[37] N. Ray and D. Sokolov. Robust polylines tracing for n-symmetry directionfield on triangulated surfaces. ACM Trans. Graph., 33(3):30:1–30:11, 2014.ISSN 0730-0301. → pages 15[38] F. H. Razaflndrazaka, U. Reitebuch, and K. Polthier. Perfect matching quadlayouts for manifold meshes. In Proceedings of the EurographicsSymposium on Geometry Processing, pages 219–228, 2015. → pages 8[39] C. Shao, A. Bousseau, A. Sheffer, and K. Singh. Crossshade: shadingconcept sketches using cross-section curves. ACM Trans. Graph., 31(4),2012. → pages 10, 13, 14[40] K. A. Stevens. The visual interpretation of surface contours. ArtificialIntelligence, 17, 1981. → pages 11, 13, 14[41] V. Surazhsky and C. Gotsman. High quality compatible triangulations. Eng.Comput. (Lond.), 20(2):147–156, 2004. → pages 21[42] M. Tarini, E. Puppo, D. Panozzo, N. Pietroni, and P. Cignoni. Simple quaddomains for field aligned mesh parametrization. ACM Trans. Graph., 30(6):142:1–142:12, 2011. ISSN 0730-0301. → pages 8[43] J. Todd and F. Reeichel. Visual perception of smoothly curved surfaces fromdouble-projected contour patterns. J. of Exp. Psych.: Human Percep. andPerformance, 16:665–674, 1990. → pages 14[44] J. Wu and L. Kobbelt. Structure recovery via hybrid variational surfaceapproximation. Computer Graphics Forum, 24(3):277–284, 2005. → pages756[45] B. Xu, W. Chang, A. Sheffer, A. Bousseau, J. Mccrae, and K. Singh.True2Form: 3D Curve Networks from 2D Sketches via SelectiveRegularization. ACM Trans. Graph., 33(4), 2014. → pages 3, 10, 13, 14[46] S. Yoshizawa, A. Belyaev, and H.-P. Seidel. Fast and robust detection ofcrest lines on meshes. In Proc. Symp. on Solid and Physical Modeling, SPM’05, pages 227–232, 2005. → pages 34[47] Y. Zhuang, M. Zou, N. Carr, and T. Ju. Anisotropic Geodesics for Live-wireMesh Segmentation. Computer Graphics Forum, 2014. ISSN 1467-8659.→ pages 757Appendix ASupporting Materials58How well do the design drawings on the bottom reflect the shape on the top?A B C DHow well do the design drawings on the bottom reflect the shape on the top?A B C DHow well do the design drawings on the bottom reflect the shape on the top?A B C DHow well do the design drawings on the bottom reflect the shape on the top?A B C DFigure A.1: User Study 1.59Which figure on the bottom (B or C) more accurately describes the shape on the top (A)?B CAACBWhich figure on the bottom (B or C) more accurately describes the shape on the top (A)?ACBWhich figure on the bottom (B or C) more accurately describes the shape on the top (A)?B CAWhich figure on the bottom (B or C) more accurately describes the shape on the top (A)?ACWhich figure on the bottom (B or C) more accurately describes the shape on the top (A)?BACWhich figure on the bottom (B or C) more accurately describes the shape on the top (A)?BB CAWhich figure on the bottom (B or C) more accurately describes the shape on the top (A)?ACWhich figure on the bottom (B or C) more accurately describes the shape on the top (A)?BFigure A.2: User Study 2.60
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- FlowRep : extracting descriptive curve networks from...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
FlowRep : extracting descriptive curve networks from free-form design shapes Gori, Giorgio 2017
pdf
Page Metadata
Item Metadata
Title | FlowRep : extracting descriptive curve networks from free-form design shapes |
Creator |
Gori, Giorgio |
Publisher | University of British Columbia |
Date Issued | 2017 |
Description | This thesis presents FlowRep, an algorithm for extracting descriptive compact 3D curve networks from meshes of free-form man-made shapes. FlowRep output networks provide a concise visual description of the underlying surface, and can be used as a compact proxy for shape compression, editing and manipulation. While artists routinely and successfully create descriptive curve networks to depict complex 3D shapes in 3D space or on 2D media, the method described here is the first to achieve this goal algorithmically. FlowRep infers the desired compact curve network from complex 3D geometries by using a series of insights derived from perception, computer graphics, and design literature which point to two sets of geometric properties that such networks should satisfy. These sources suggest that visually descriptive networks are cycle-descriptive, i.e their cycles unambiguously describe the geometry of the surface patches they surround. They also indicate that such networks are designed to be projectable, or easy to envision when observed from a static general viewpoint; in other words, 2D projections of the network should be strongly indicative of its 3D geometry. Research suggests that both properties are best achieved by using networks dominated by flowlines, surface curves aligned with principal curvature directions across anisotropic regions and strategically extended across sharp-features and isotropic areas. The algorithm leverages these observations in the construction of a compact descriptive curve network. Starting with a curvature aligned quad dominant mesh I first extract sequences of mesh edges that form long, well-shaped and reliable flowlines by leveraging directional similarity between nearby meaningful flowline directions. This process overcomes topological noise, and inaccuracies and singularities in the underlying curvature field. I then use the extracted flowlines and the model's sharp-feature, or trim, curves to form a projectable network which describes the underlying surface. Finally, I simplify this network while preserving its descriptive power to obtain the final result. My co-authors and I validate our method by demonstrating a range of networks computed from diverse inputs, using them for surface reconstruction, and showing extensive comparisons with prior work and artist generated networks. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2017-08-10 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0353171 |
URI | http://hdl.handle.net/2429/62558 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2017-09 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2017_september_gori_giorgio.pdf [ 22.14MB ]
- Metadata
- JSON: 24-1.0353171.json
- JSON-LD: 24-1.0353171-ld.json
- RDF/XML (Pretty): 24-1.0353171-rdf.xml
- RDF/JSON: 24-1.0353171-rdf.json
- Turtle: 24-1.0353171-turtle.txt
- N-Triples: 24-1.0353171-rdf-ntriples.txt
- Original Record: 24-1.0353171-source.json
- Full Text
- 24-1.0353171-fulltext.txt
- Citation
- 24-1.0353171.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-0353171/manifest