Design-Driven Quadrangulation of Closed 3D Curves by Caoyu Wang B.S. in Computer Science, Zhejiang University, 2010 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Computer Science) The University Of British Columbia (Vancouver) Novemeber 2012 c© Caoyu Wang, 2012 Abstract This work presents a novel, design-driven quadrangulating method for closed 3D curves. While the quadrangulation of existing surfaces has been well studied for a long time, there are few works that can successfully construct a quad-mesh relying solely on 3D curves, as the shape of the surface interior is not uniquely defined. I observe that, in most cases, viewers can complete the intended shape by envi- sioning a dense network of smooth, gradually changing flow-lines across a pair of input curve segments with similar orientation and shape. The method proposed here mimics this behavior. This algorithm begins by segmenting the input closed curves into pairs of matching segments. I interpolate the input curves by a network of quadrilateral cycles whose iso-lines define the desired flow line network. I proceed to interpo- late these networks with all-quad meshes that convey designer intents. I evaluate my results by showing convincing quadrangulations of complex and diverse curve networks with concave, non-planar cycles, and validate my approach by comparing my results to artist generated interpolating meshes. My algorithm is suitable for use in sketch-based modeling systems as well as in other applications where artist curves can be created. ii Preface The method presented in this thesis was described in the following research paper: • M. Bessmeltsev, C. Wang, A. Sheffer, K. Singh. Design-Driven Quadran- gulation of Closed 3D Curves, ACM Transactions on Graphics (Proc. SIG- GRAPH Asia), 2012 Figures and text from the publication are copyright by the Association of Com- puting Machinery and reused in this thesis by permission. The algorithm in Chapter 4 was mainly developed by Mikhail Bessmeltsev and Dr. Alla Sheffer. Other ideas in this thesis were mostly developed by myself and discussed with Mikhail Bessmeltsev, Dr. Alla Sheffer and Dr. Karan Singh. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1 Quad Meshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Quad Remeshing . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Surface Fitting to Curve Cycles . . . . . . . . . . . . . . . . . . . 10 2.4 Fitting Curve Cycles with Pre-Defined Sides . . . . . . . . . . . . 11 2.4.1 Fitting to Four-sided Curve Cycles . . . . . . . . . . . . . 12 2.4.2 Fitting to n-sided Curve Cycles . . . . . . . . . . . . . . 12 3 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Quadrangulating a Curve Cycle . . . . . . . . . . . . . . . . . . . 16 3.2.1 Segmentation and Matching . . . . . . . . . . . . . . . . 17 iv 3.2.2 Quadrangulation . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Quadrangulating Curve Network . . . . . . . . . . . . . . . . . . 19 4 Segmentation and Matching . . . . . . . . . . . . . . . . . . . . . . 20 4.1 Initial Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Segment Pairing Cost . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 Stable Matching of Segment Pairs . . . . . . . . . . . . . . . . . 25 4.4 Segmentation Refinement . . . . . . . . . . . . . . . . . . . . . . 26 5 Quadrangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.1 Extracting Quad Connectivity . . . . . . . . . . . . . . . . . . . 28 5.2 Extracting Quad Geometry . . . . . . . . . . . . . . . . . . . . . 30 5.3 Meshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.4 Minimizing Flow Dislocation . . . . . . . . . . . . . . . . . . . . 32 6 Processing Curve Networks . . . . . . . . . . . . . . . . . . . . . . . 34 7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 7.1 Configuration File . . . . . . . . . . . . . . . . . . . . . . . . . . 38 7.2 Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 7.3 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 8 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 8.1 Closed Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 8.2 Curve Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 8.3 Quantitative Evaluation . . . . . . . . . . . . . . . . . . . . . . . 43 8.4 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 v List of Tables Table 8.1 Running time (in seconds) in different stages for complex input curve networks. . . . . . . . . . . . . . . . . . . . . . . . . . 45 Table 8.2 Algorithm statistics for different curve networks. . . . . . . . . 46 vi List of Figures Figure 1.1 An example of input network . . . . . . . . . . . . . . . . . . 2 Figure 1.2 An example of output network . . . . . . . . . . . . . . . . . 2 Figure 1.3 Ambiguous 3D curve and unambiguous design intent curve . . 3 Figure 1.4 An example of dual structure . . . . . . . . . . . . . . . . . . 4 Figure 1.5 Artist designed interpolating quad-meshes. . . . . . . . . . . 4 Figure 1.6 Steps to quadrangulating a closed 3D curve loop . . . . . . . 6 Figure 2.1 Examples of different surface fitting algorithm . . . . . . . . 11 Figure 2.2 Examples of Permanent patches . . . . . . . . . . . . . . . . 13 Figure 2.3 Comparision with topological approach and this method . . . 14 Figure 3.1 Pipeline of this quadrangulation method . . . . . . . . . . . . 17 Figure 3.2 Illustration of flow-lines and pair . . . . . . . . . . . . . . . . 18 Figure 4.1 Iterative segmentation refinement . . . . . . . . . . . . . . . 21 Figure 4.2 Estimated bridge curvature for different segment layouts . . . 23 Figure 4.3 Initial bridge direction of segment . . . . . . . . . . . . . . . 24 Figure 5.1 Processing disconnected dual graph . . . . . . . . . . . . . . 29 Figure 5.2 Impact of intersection orders . . . . . . . . . . . . . . . . . . 30 Figure 5.3 Locating an inner vertex . . . . . . . . . . . . . . . . . . . . 30 Figure 5.4 Process of building a quad mesh from the pairing configuration 31 Figure 5.5 Comparision between distance based weighting algorithm to traditional algorithm . . . . . . . . . . . . . . . . . . . . . . 31 Figure 5.6 Removing interior vertices . . . . . . . . . . . . . . . . . . . 32 vii Figure 6.1 Steps of assigning proper interval count to each side . . . . . 35 Figure 8.1 Quadrangulation and meshing of closed curves. . . . . . . . . 41 Figure 8.2 Quad meshes of complex closed curves including interior cycles. 41 Figure 8.3 Artist’s generated model of the boat . . . . . . . . . . . . . . 42 Figure 8.4 Artist’s generated model of the spaceship . . . . . . . . . . . 43 Figure 8.5 Comparision before and after adding human correction . . . . 45 Figure 8.6 Quadrangulation and meshing of a espresso machine . . . . . 46 Figure 8.7 Quadrangulation and meshing of speaker model. . . . . . . . 47 Figure 8.8 Quadrangulation and meshing of plane model. . . . . . . . . 48 Figure 8.9 Quadrangulation and meshing of boat model. . . . . . . . . . 48 Figure 8.10 Quadrangulation and meshing of submarine model. . . . . . . 49 Figure 8.11 Quadrangulation and meshing of car model. . . . . . . . . . . 49 viii Acknowledgments First, I would like to express my deep gratitude to my supervisor, Dr. Alla Sheffer, who has provided me with valuable guidance and support throughout my graduate study. Her enthusiasm and insights helped me greatly during the research process. I would also like to thank my second reader, Dr. Wolfgang Heidrich, for reading this thesis and providing valuable feedback. I would also like to extend my thanks to my colleagues and friends in the Im- ager Lab. Mikhail Bessmeltsev for being a wonderful collaborator, Nicholas Vin- ing for proof-reading and helping to revise my thesis, and all my awesome friends in UBC, whose endless support made my graduate life much more enjoyable. Last but not least, I would like to dedicate this thesis to my parents for their tireless love and encouragement throughout my life. ix Chapter 1 Introduction Curves are a quintessential primitive of visual communication that date back to early cave drawings. In current 3D design practice, curves are universally used to depict both form and function, conveying the essence of a shape [BR11]. Sparse networks of closed 3D curves are the foundation of shape in both traditional CAD modeling [FH99] and sketch-based modeling interfaces [BBS08, NISA07, SKSK09]. Unsurprisingly, recent research confirms that such 3D curve networks effectively convey complex 3D shape [MZL+09, dGGDV11, MSM11] (Figure 1.1 (a)). I aim to recover and compactly represent conveyed shapes (Figure 1.2), for designer- drawn curve networks, such as those generated by Abbasinejad et al. [AJA11] from sketched 3D curves [BBS08]. While arbitrary 3D curve cycles have highly ambiguous interpolating surfaces, designer created curve cycles-even when highly complex-typically convey a uniquely imagined surface (Figure 1.3). These curves are designed to serve as a visual proxy of a 3D object, with the expectation that every element of surface detail is explicitly captured by the network [Gah10]. To this end, design texts repeatedly emphasize the significance of using representative flow-lines of the object [BR11, Gah10] as curve network elements. While design literature provides no precise mathemati- cal definition of flow-lines, design and modeling reference texts [Gah10, SPK04] suggest that flow-lines are strongly correlated to sharp features and lines of curva- ture on a surface, but that these flow-lines also allow for artistic license at surface discontinuities over fine details and in umbilic regions. 1 (a) input curve network (b) curve loop samples Figure 1.1: An Input curve network (a), and two samples of closed 3D curve loops which are selected from the curve network (b). (a) output curve network (b) curve loop samples Figure 1.2: The output mesh generated by the curve network (a), and close- ups of specific patches (b). 2 Figure 1.3: Closed 3D curves: ambiguous hexagonal 3D curve (top) com- pared to complex curves with a clear design intent (bottom). These observations, confirmed by perception studies [Ste81], suggest that any additional flow-line on the surface must be expressible as a blend of the explicitly defined flow lines on the designer-created curve cycles. Viewers complete the in- tended shape by envisioning a dense network of blended, gradually changing flow- lines. An examination of artist-drawn dense networks (Figure 1.5) confirms this observation; moreover, artists take advantage of this property by implicitly pairing opposing representative flow-lines and constructing curve sequences that smoothly evolve from one input flow-line to its mate along the interior surface. The surface described by the union of these sequences and forms a quad-dominant mesh. My surface-fitting algorithm aims to replicate this behavior. Before formally describing the algorithm, I shall introduce some terminology. A 3D curve network is a graph of connected 3D curves where one or more curve cycles have been marked for surfacing by the designer. A quadrangulated curve network (the black curve in Figure 1.4) requires that all curve cycles marked for surfacing be four- sided. 3 Figure 1.4: An example of dual structure. Dual poly-chords are drawn in different colors. Figure 1.5: Artist designed interpolating quad-meshes. A single quad-mesh can be created from quadrangulated curve network cycles by sampling parametric four-sided patches. The dual of a quad network is a graph whose vertices correspond to quad cycles, and whose edges correspond to shared cycle sides. Each dual poly-chord (Figure 1.4) is a sequence of dual edges that corresponds to a chain of quadrilaterals sharing opposite sides [DSSC08]. If I can extract the flow-line pairings that artists use, I can then reconstruct the connectivity in a natural manner using the dual quadrangulation approach de- 4 scribed below. The challenge, therefore, is to obtain a suitable segmentation of a curve cycle into pairs of matching opposite flow-lines. Since I expect internal flow lines to change smoothly and gradually, these bridged segment pairs should have similar orientation and shape. When examining artist generated flow-networks, I observe that the preference for pairing segments becomes more pronounced as the degree of compatibility between them increases, often at the expense of sub- optimal pairings of other segments. This effect is evident in the highlighted regions in Figure 1.5. On the left, the strong preference for the blue pair enforces the far less obvious red one. On the right, the dominant yellow and blue matches enforce the far less attractive purple one. Such a dominant preference order can be formally described as a stable matching. A matching is considered stable when there are no two elements that prefer each other to their current match [Irv85]. I simultaneously compute the segmentation and its corresponding stable pairing using a tailored dis- crete optimization strategy which interleaves matching and segmentation steps. Given the computed segmentation and pairing (Figure 1.6 (c)), I construct a network of quadrilateral cycles (Figure 1.6 (d)). The dual poly-chords of the quadrilateral network connect the matched flow-line curve segments and inter- polates those with tensor-product surface patches. Using this construction, the iso-lines of the patches naturally align with the matched curves, forming a dense flow-line network conveying the intended surface. Connectivity alone is not enough to reconstruct the surface, I expect the inner surface is smoothly changing and capturing the boundaries feature. Popular CAD tools capture the geometry of four-sided curve cycles using Coons patches [Coo64] (Figure 2.1 (d)), whose iso-lines implicitly define a sequence of flow-lines that smoothly bridges the opposite sides of each cycle. Coons patches are restricted to four-sided curve cycles. In reality, curve cycles can be complicated and my segmentation algorithm will segment them into more than four sides. Inspired by Nasri et al. [NSY09], I extend Coons patches to general curve cycles. I first determine the geometry of the boundaries of quadrilateral cycles (e.g. the green curves in Figure 1.6 (d)). I then can easily interpolate each four-sided quadrilateral cycles using Coons patches. A curve network contains several curve loops, which may share common bound- aries with others. A good quadrangulation result should be watertight; there should 5 a) input curve loop b) segmented curve loop c) matching curve segment d) quadrangulation result Figure 1.6: Steps to quadrangulating a closed 3D curve loop (a) : Closed curves are independently segmented (b), then iteratively paired and re- fined to capture dominant flow-lines as well as overall flow-line quality (c); the final quadrangulation in green and dense quad-mesh (d). be no T-junctions on the final result. Even though completely watertight results may not exist [Mit97], I can properly assign number of intervals for each segment, so that the number of T-junctions is minimum. This forms a mixed-integer pro- gramming problem, which is NP-hard but practically solvable in acceptable time by a branch-and-bound tree search algorithm [Opt12]. A watertight and arbitrarily dense quad-mesh describing the target shape can then be created by tracing patch iso-lines (Figure 1.2 (a)). I show that the quad meshes created by my method on a variety of challenging inputs, including both synthetic models and curve networks created by different modeling software, compare favorably against those manually created by design professionals (Section 8). Contribution: I present the first solution to constructing imaginary surfaces interpolating general 3D design curve networks. I represent this surface using a quad mesh whose iso-lines capture the design flow inherent in the network. I are thus faced with a perceptually well-defined, but mathematically ill-posed, prob- lem. Lacking a mathematical model of human perception, I distill perception studies and guidelines from design literature into a mathematical formulation of flow-line matching and segmentation. I evaluate this formalism by showing results 6 that match both viewer expectation and artist created surfaces. My key technical innovation is a simultaneous segmentation and pairing algorithm that locates suit- able end segments for the dual poly-chords of the interpolating quad mesh based on analysis of the input curve geometry. Quad-remeshing techniques often generate rectangular quad elements. I note that my primary objective is to capture flow-lines; since these lines are often related to lines of curvature, I will typically generate well-shaped quads. However, when flow-lines conflict with quad orthogonality, I focus on capturing the flow at the expense of irregularly shaped quads (see Figure 1.1). This ensures that my output is consistent with designer expectations (Figure 1.5). 7 Chapter 2 Related Work Generation of quad mesh has been studied in several different contexts. Quad meshing takes planar regions as an input, and quadrangulates the mesh, while quad remeshing generates a quad mesh based on existing 3D surfaces. If there is no pre- defined surface, the problem is always regarded as surface fitting. Some surface fitting methods build the surface by propagation from the boundary, while some other algorithms use a pre-segmented boundary as reference. The following review covers several typical methods. 2.1 Quad Meshing My work draws on ideas from coarse-to-fine planar meshing approaches, such as sub-mapping [WWBB96, Owe98, RGS10]. The sub-mapping method [WWBB96] first fits the vertices to nearest integer multiple of pi/2, forming a structure where all the edges are horizontal or vertical. It then splits the geometry into patches equiv- alent to a quadrilateral, and map the quadrilaterals back to the original geometry. Whiteley et al. [WWBB96] solve an integer linear problem to keep the mesh com- patibility between the pieces. This method largely depending on the angles of the vertices. If the angles are not near integer multiple of pi/2, this method may lead to unacceptable results. A modified version of sub-mapping [RGS10] works around this drawback considering vertices globally. This work still rounds each vertex to an integer multiple of pi/2, but takes global properties as constraints. This work 8 also extends sub-mapping methods to surfaces with holes, by adding adding a cut between holes and boundaries. In contrast to these approaches, my approach supports irregular quad connec- tivity and automatically introduces irregular interior vertices when warranted by the boundary shape (e.g. Figure 5.4). More significantly, my approach operates on 3D curves without the benefit of a well defined planar domain. While planar meshing methods focus on element quality or shape, my goal is to recover and quadrangulate a surface enclosed by designer-drawn curves. 2.2 Quad Remeshing Quad remeshing is a research area with a long history. It generates a new quadrilat- eral mesh, according to a pre-defined surface, to meet some criteria, such as lower sampling rate or better quadrilateral quality. One class of remeshing algorithms traces lines along the directions defined by geometry properties, and then align quadrilateral elements to these lines [ACSD+03, MK04, MK06]. Alliez et al. [ACSD+03] traces lines of principal curvature in the 2D parameter domain and then uses the intersection of them as the vertices of the new quad mesh. This method may not have plausible result in flat regions, be- cause the estimated curvature may be not reliable enough. Marinov et al. [MK04] overcome this drawback by estimating a confidence value for each face during the calculation of curvature direction. In high-confidence regions this method traces lines of the curvature on the surface using a local parameterization rather than the piecewise linear parameterization used in [ACSD+03]. When the traced line enters a low confidence region, it follows a geodesic curve until it goes back to a high- confidence region again. Using principal curvature, a follow up approach [MK06] proposes using curves which minimize bending energy. This method avoids using curvature tensor field because the estimation of curvature on discrete input mesh is always noisy due to insufficient quality of the mesh. Some parameterization-based methods compute quadrangle surface tilings by contouring isoparameter lines [RLL+06, KNP07, DBG+06, ZHLB10, LL10]. This category of remeshing can also be regarded as the result of parameterization. Ray et al. [RLL+06] introduce a parameterization technique by aligning periodic pa- 9 rameters to the directions along two given orthogonal vector fields. If defining the input vector fields by principal curvature field, this parameterization generates high quality mesh by tracing the iso-contours. Subsequent work [KNP07] maps the cross field to a single vector field on branched covering. Dong et al. [DBG+06] propose an algorithm to extract the quadrangular chart (Morse-Smale complex) from the Laplacian eigenvector, and then modify the chart using a globally smooth parameterization technique. Other publications address the problem of generating high quality quad meshes by first generating a triangle or polygon mesh. Bommes et al. [BLK11] proposed an optimization method over the discrete structure of the mesh that converts a poorly quad mesh into a quad mesh with more regular quadrangular. This algorithm in- troduces a grid-preserving operator which is able to remove helical configurations on the mesh. It then greedily apply this grid-preserving operator on the quad mesh and make the quad mesh more regular. Daniels et al. [DSC09] build level of detail hierarchies and resamples the base domain in the hierarchy to reduce parametric distortions. All the works discussed above are based on a well-defined surface. In my setup, however, no underlying surface is available. Instead, I aim to align my output meshes with the flow-line directions conveyed by the input designer curves, which as noted above strongly correlate with curvature lines. 2.3 Surface Fitting to Curve Cycles There is a large body of work on interpolating closed curves with smooth sur- faces, much of it in the context of hole filling [Mal00]. While a small number of methods [Lev03, DDGG05, FH11, NISA07, Ros07, AJA11] can operate on arbi- trarily shaped curves, the majority assume that the cycle is pre-segmented into n sub-curves and has a low-distortion mapping to a convex planar n-sided polygon, e.g. [Coo64, GR05, VRS11]. The former, more generic, approaches typically utilize a diffusion process that optimizes surface fairness. Abbasinejad et al. [AJA11] use Laplacian diffusion to create a surface with minimum mean curvature, analogous to a soap film expand- ing around the hole (Figure 2.1 (b)). Finch et al [FH11] use thin-plate splines to 10 Figure 2.1: Using Laplacian diffusion (b) or Thin-Plate Splines [FH11](c) to surface a four-sided cycle leads to unintuitive results. (d) In contrast the flow lines on an interpolating Coons patch, by construction, bridge opposite cycle sides. fit a surface with minimum bending energy to a hole (Figure 2.1 (c)). They do not explicitly align flow-lines or curvature directions with the input curves, and thus can fail to capture designer intent on structured inputs (Figure 2.1 (b,c)). Using pre-defined normals along the input curves [Lev03, MZL+09] improves the out- put, but as the normals are uniformly diffused dominant flow-line directions may be lost. Moreover such normals are not part of a typical curve-based modeler’s output [BBS08, NISA07, SKSK09]. The alternative approach of Rose et al. [Ros07] fits developable surfaces to in- put cycles. This approach is too restrictive for a general modeling setup, as many inputs (including the cycle in Figure 2.1 (a)) aim to convey non-developable sur- faces. 2.4 Fitting Curve Cycles with Pre-Defined Sides A variety of popular techniques are available for interpolating and approximating networks of regular quad or triangular patches [Far92]; see [OK11] for a recent sketching motivated approach. These methods, including Coons patches [Coo64] and their discrete extension [FH99] (Figure 2.1 (d)) provide an effective solution which naturally aligns the surface iso-lines with the flow-line sequences indicated by the boundary curves. Design and perception literature [BR11] indicates that designers expect curve cycle boundaries to correspond to representative flow-lines implying surface curvature directions, a behavior captured by Coons interpolation, 11 but not other fitting approaches. These methods are widely used by modelers and designers as the resulting surfaces closely reflect designer intent. 2.4.1 Fitting to Four-sided Curve Cycles Quadrangulating a four-sided curve cycle is the simplest case of fitting segmented curve cycles; the four boundaries define the connectivity well. Determining the position of inner points is usually done by polynomial interpolation [Sal06]. Most patching methods use biquadratic or bicubic surface patches. Bicubic surface patches allow for more freedom, and users can set normal directions on boundary. Coons patches [Coo64] are the most popular surface patch family which focus on the interpolated shape. For each point in the domain, Coons patches blend Laplacian coordinates from the opposite boundary curves; as such, Coons patches are a generalization of lofted surfaces. The original Coons patch linearly blends Laplacian coordinates. Bicubic Coons patches cubicly blend Laplacian coordi- nates, its higher degree allows more freedom. A typical way to define these extra freedom is assuming the derivative on the boundary to be consistent with the two neighboring boundaries. When two such bicubic Coons surfaces are connected, the connection will be smooth if the given boundaries are smoothly connected. An extension of Coons patches, called permanence patches [FH99], blends Laplacian coordinates according to a user-defined blending function rather than linear blending. This gives the designer various choices by select different blending functions. The result includes ordinary Coons patch and the patch using Laplacian diffusion. But the quality of resulting surface largely depends on the given blending function (Figure 2.2). 2.4.2 Fitting to n-sided Curve Cycles For cycles with more than four pre-segmented sides, existing approaches can be classified as either single surface fitting, e.g. [GR05, VRS11], or subdivision into quad or triangular cycles ([SWZ04, NSY09]). The methods in the first category in- terpolate the cycles with a single surface patch by utilizing suitable n-sided convex 2D polygons as parameter domains. As acknowledged by Varady [VRS11], the fit- ted surface quality is strongly dependent on the quality of the 2D parameterization. 12 Figure 2.2: This shows three examples of Permanent patches. The image is from Farin et al. [FH99]. The top patch is a permanent patch which is equivalent to a Coons patch (α = 1). The middle one is a perma- nent patch selected by the author (α = −0.257). The bottom one is a permanent patch which is equivalent to a Laplacian surface (α = 0). 13 Figure 2.3: (top) Using a purely topological approach and applying mid-point subdivision (forming either four or six sides) generates a quad mesh with poor flow line layout (left and center). My method (right) uses geometry driven segmentation and matching to generate smooth flow lines and a predictable surface. (bottom) On a concave cycle, parame- terization onto a convex domain (a rectangle) leads to foldovers (left), my method automatically segments the cycle into convex quadrilaterals leading to a fair surface (right). Subdivision approaches ([SWZ04, NSY09]) quadrangulate the input cycles and then use various techniques to interpolate or approximate the resulting quad network. In the basic midpoint scheme, a single vertex is placed in the center of a patch and then connected to the middle of each side. To generate a water- tight surface across heterogeneous networks, Schaefer et al. [SWZ04] and Nasri et al. [NSY09] introduce more sophisticated quadrangulation schemes that maintain a fixed number of intervals along each side while aiming to control both the number and valence of the added extraordinary vertices [NSY09]. All methods discussed above require the n-sides to be pre-defined and use of the network junctions or sharp corners on the cycle as side end-points. As shown by Figure 2.3 (top) using the actual shape of the curves to determine the end-point locations and induced topology as done by my method can significantly improve 14 both the flow line layout and the resulting surface shape. More significantly, in contrast to all the approaches above, my method can operate on curve cycles with large concavities (Figures 2.3 (bottom) and 1.1 (b)). 15 Chapter 3 Algorithm Overview In this chapter, I briefly overview my algorithm. Starting from the input curve cycles and configuration information (Section 3.1), I first show how to quadrangu- late one curve cycle (Section 3.2). I then extend the algorithm to curve networks (Section 3.3). I use a dual based quadrangulation approach, where I first compute the dual graph of the quadrangulation (Subsection 3.2.1), and then use it to induce the primal quad connectivity and geometry (Subsection 3.2.2). This workflow is illustrated in Figure 3.1. 3.1 Input The input to my algorithm is a curve network designed by artists. A curve network may contain one or more curve cycles. Some optional configuration information is also acceptable. Configuration data consists of global settings such as output mesh density, and/or threshold for segmentation. 3.2 Quadrangulating a Curve Cycle To assemble the dual, I segment the input curve into a small number of matching segment pairs that serve as opposite ends of dual graph poly-chords and corre- sponding primal quad-chains. In this respect, paired segments are analogous to river banks that both bound and define the flow between them; the poly-chord rep- resents a bridge across the flow, connecting the paired segments (Figure 3.2). Each 16 Figure 3.1: After the initial segmentation (a), I alternate matching and refine- ment steps to obtain a pair-based curve segmentation which is converted into a quadrilateral network (c) . To minimize T-junction count (d) I compute global interval assignment, and use it to sample iso-lines on discrete Coons patches. segment in a pair share similar shape and directions with its mate. These matched pairs are used as dual graph poly-chords in the following process. The generated interior curves are positioned using an extension of the quadrangulation scheme of Nasri et al. [NSY09] (Figure 3.1 (c)). This scheme first puts dislocation vertices, and then the curve lines connecting these vertices to the boundary. After that, I have a coarse quadrangulated structure, which can be filled by any methods discussed in Section 2.4.1. 3.2.1 Segmentation and Matching My quadrangulation method is a dual-based quadrangulation approach. Since the curve cycle is not pre-segmented, I simultaneously compute segmentation and pair- ing, which is an ambitious problem. I want to explicitly minimize the average matching cost, while avoiding outlier matches with very high cost. I consider the average, rather than the sum, so that the cost is not affected by the number of 17 ij flow br idg e segment pair (i,j) Figure 3.2: Paired segments < i, j > are analogous to river banks which bound and define the flow between them. The poly-chord is analogous to a bridge across the flow. segments. To render this problem tractable, I use a discrete iterative optimization strategy that interleaves matching and segmentation. Given an existing segmen- tation and an appropriate cost metric, the right pairing strategy is not simply one that minimizes an overall cost, but instead one that prioritizes strongly compatible segment pairs that define dominant flow-lines. As noted in the Introduction, this can be mathematically formulated using the concept of a stable matching; I can find such a stable matching using the method of Irving [Irv85]. Once I have obtained such a pairing, I can then refine my segmentation by look- ing for a subdivision that maximally decreases my average matching cost without increasing the worst match cost (Section 4.4). To find the optimal splitting point(s), I examine the pairings in the current stable matching and consider strategies that improve the current high-cost matches. This new segmentation can then be fed back into the matching stage. To generate the desired segmentation and pairing , I start from an initial segmentation and interleave segmentation and matching steps. Since I aim for a compact quadrangulation, I use a coarse to fine segmentation up- date strategy, starting with the minimal segmentation for which the notion of oppo- site segments, or bridging directions, is well defined. To avoid over-segmentation I stop the refinement process once the improvement to the average match cost be- comes insignificant. 18 3.2.2 Quadrangulation Once I have an optimized segmentation and pairing, I can start constructing the quadragulation. Since good matchings and segmentations do not necessarily de- fine a unique valid dual structure. The dual structure may be separated into several component. I introduce imaginary cut edges to cut the curve cycle into several con- nected component, and connect them together again. As I discussed in Section 5.4, the segmentation and pairing algorithm do not explicitly consider the quad connec- tivity to the final flow, and unnecessary dislocations may lead to unsmooth surfaces. I minimize dislocations by gluing neighbouring duplicate pairing and uncrossing pairs with small impact. To position the internal vertices, I follow the three-step process in [NSY09]. This process adds inner control vertices and lines to convert a surface bounded by the given curve loop into several patches with four sides. Positioning these ele- ments follows the idea of Coons patch, that is the flow-lines between the boundary should be smooth and gradually changing. I then fit each quadralitaral patches by using patching algorithm for four-sided patch. This quadrangulation method is mainly discussed in Chapter 4. 3.3 Quadrangulating Curve Network When I extend my algorithm to curve network which contains multiple curve cy- cles, I want to minimize the number of T-junctions on the common boundary of adjacent cycles. Since I process each curve cycle individually, the segmentation points on a shared boundary can be different in the two adjacent cycles. I first merge adjacent segmentation vertices which are very close to each other. I then decide the number of intervals assigned to each segment curve boundary, with the constraint that the numbers of intervals on the two sides of a curve should be equal. This will form a mixed-integer programming problem. Through this global opti- mization, I then compute a mesh of the entire network with minimum T-junctions as discussed in Chapter 6 (Figure 3.1,(d,e)). 19 Chapter 4 Segmentation and Matching The pseudocode below describes the flow of my iterative segmentation and match- ing process. Every iteration, I subdivide one or more segments to maximally reduce the average matching cost, without increasing the worst-match cost (Section 4.1.4). While the number of curve segments, at intermediate steps of the algorithm may be odd, each iterative refinement increments the number of segments, typically by one, admitting a perfect segment matching after one or two iterations. I continue to iterate until there is no significant drop in the average matching cost, rolling back to the last even segmentation when significant improvement is no longer possible. While this algorithm does not guarantee a globally minimal average match cost, it captures my design goals admirably in that it finds and preserves dominant segment pairs early and then refines segments as necessary to reduce the matching cost of poorly paired segments. Notation: The above steps are described succinctly using notation and pseudo- code as follows: Given a curve segmentation σ = 1, ..,n, I refer to (i, j) as a distinct segment pair with a matching cost ci, j, (i, j) and ci, j are symmetric. ci, j captures the compatibility of any two curve segments to form opposite sides of dual poly- chord in my target quadrangulation. M(σ) is a perfect matching of σ , where each segment is uniquely paired, barring a solitary unmatched segment when the num- ber of segments ||σ || is odd. I define the average cost of a matching M(σ) as cost(M,σ) = (∑(i, j)∈M(σ) c2i j)/(2 · b||σ/2||c). A constant drop = 1.25 captures the factor of average cost reduction below which the iterative algorithm terminates. 20 Figure 4.1: Iterative segmentation refinement: (a) initial segmentation where the matching highlights correct dominant side matches. The match qual- ity is drastically improved by segmenting the bottom curve (b), and re- peating the process (c) to obtain an even segment count. Further refine- ment has no real impact on matching cost. I now elaborate on the rationale and details of each step. 1 σ= initial segmentation (Sec. 4.1.1); 2 M(σ)= stable matching of segment pairs (i, j) using match cost ci, j (Sec. 4.1.3); 3 U∗b = ∞; 4 cost∗ = ∞; 5 repeat 6 if ||σ || is even: 7 then σ∗ = σ ;M∗ = M;cost∗ = cost(M,σ) 8 U∗b = maxM ci, j; 9 σ ′=refine σ (Sec. 5.1.4); 10 M′(σ ′)= stable matching of σ ′; 11 σ = σ ′; 12 until (||σ ′|| is even) and 13 (drop∗ cost(M′,σ ′)> cost∗ or U∗b < maxM′ ci, j); 4.1 Initial Segmentation As described in the Introduction I expect the flow-lines induced between any pair of segments to be smooth. Motivated by the continuity property of flow-lines, I can use any robust corner finding technique, such as computing discontinuities of discrete curvature along the curve [MS09], for my initial segmentation. I further refine this segmentation to ensure that the line segment connecting curve end-points 21 are near linear using a technique similar to [MSM11]. This property helps define coherent bridge directions for matching cost evaluation, described next. 4.2 Segment Pairing Cost Paired segments have a two-fold impact on the final flow-line network. They ex- plicitly define the sequence of flow-lines evolving from one segment to its mate. They also impact the family of flow-lines intersecting this sequence. Since the pairing defines a chain of quadrilaterals in the final quad network, these intersect- ing flow lines connect the two segments by evolving from one pair of end-points to another (see Figure 4.2 (a)). To generate the designer-expected flow-line network, the matching cost must satisfy the following criteria. First, to minimize the varia- tion of flow-lines that evolve from one segment to the next I aim for the segments to be similar. Matching impacts the shape of the intersecting family of curves, or bridge, which in general I want to be as straight as possible, minimizing its curva- ture. Internal flow-lines should reflect input curve geometry, thus I would like the bridge to be aligned with intersecting flow lines evolving from input curve chains connecting the two segments, or, since these chains can be very complex, to at least align with intersecting sequences evolving from neighboring segments. Lastly, to best capture the general correlation between flow-lines and lines of curvature of the imagined surface, I expect intersecting sequences of flow lines to be orthogonal. I capture the last two requirements through a per-segment preferred bridge direc- tion, which depends on the segment and its two neighbors. I use these directions to define bridge curvature bi, j. My matching cost combines bridge curvature, a term measuring similarity between the segments si, j, and a weak distance term di, j used to prioritize more close-by matches ci, j = wbbi, j +wssi, j +wddi, j. As the segments typically have fairly similar shape, bridge curvature dominates the cost with wb = 0.8 and ws = wd = 0.1. 22 ij ti p’ p (b) distance di,j, similarity si,j i j Ti,j di,j L2i,j (a) bridge curvature bi,j using bridge directions ti Figure 4.2: Estimated bridge curvature for different segment layouts mea- sured as angle (red) between bridge direction ti and p− p′ (at a point p). The dashed lines visualize representative intersecting flow-lines (a). Shape similarity and distance cost terms (b). Bridge Curvature: To estimate the curvature of the anticipated intersecting flow lines, or bridge, between segments i and j, I use the predicted bridge directions ti and t j for both ends of the bridge. As illustrated in Figure 4.2, the flow-line shape depends both on these directions and the relative location of the segments. As start and end positions, plus directions, allow for fitting of multiple flow-line curves, explicitly evaluating flow-line curvature is problematic. Instead I use an angle based curvature predictor defined as follows. Let p be a point on the segment i, and let p′ be the point where the angle between the vectors ti and p− p′ is minimal on the segment j, i.e. p′ = argminx∈ j |6 (ti,x− p)|. Then, for a given point, the angle 6 (ti, p′− p) measures the angular difference between the shortest bridge between the segments and the one taken when using the estimated bridge direction ti. To compute deviation across the segment i, ai→ j, I average the angular difference over all points. Finally, I set the bridge curvature to the maximum of the per-segment deviations, namely bi, j = max(ai→ j,a j→i). Bridge directions: The bridge direction ti is the predicted optimal tangent direc- tion for the flow-lines intersecting the segment i. As such, it depends both on the segment orientation, and on the bridge directions at neighboring segments. The initial bridge direction ti, for any segment i, is estimated from the initial segmen- tation (Figure 4.3(a-c)) and then refined in every subsequent algorithmic iteration 23 fi fnfm ti (a) ti=fm+fn (b) ti=fn (c) ti= to fi in best-fit plane to fi ,fm ,fn fi fn fm ti fi fn fm ti Figure 4.3: Initial bridge direction ti of segment i is determined by adjacent segment flow directions fm , fn and its normal. (Figure 4.3(d)). The initial bridge direction ti = ni, is set to capture a direction orthogonal to the segment and lying on the imaginary surface emanating from it. Specifically, I define ni as the perpendicular to the straight line fi connecting its end-points, in the best-fit plane of the segments i and its neighbors. Neighboring segments can also strongly influence bridge direction. An adjacent segment m is considered to influence the bridge direction of i if it is of reasonable arc-length l (1.5∗ lm > li), and if its general flow direction fm is likely to form flow-lines inter- secting those emanating from i ( 6 ( fm, fi)≤ 135 ◦). The bridge direction ti is refined to be the average f of its influential neighbours (Figure 4.3(a)(b)), or left as ni if none exist (Figure 4.3(c)). Then, at every algorithmic iteration, I update bridge directions (Figure 4.3(d)), using dominant pairs, i.e. pairs (i, j) such that ci j < dom, where dom = 0.15. First, I refine the bridge direction of the dominant pairs. I update ti and t j of all dominant pairs (i, j) to their current average (thus implicitly lowering their bridge curvature estimate bi, j). Next, for any segment i that is not dominantly matched but has a neighbor m that is part of a dominant pair, I use tm to update ti. Specifically, I attempt to set ti to either align, or to be orthogonal to, tm. if the angle between ti and tm is less than 135 ◦, I set ti to be orthogonal to tm in the plane defined by ni. If 135 ◦ ≤ 6 (ti, tm) ≤ 225 ◦, I set ti = tm. If ti has two dominant neighbors, I use the one with lower matching cost for the update. The remaining bridge directions are left unchanged in this iteration. 24 Distance and Similarity: The distance di, j is simply the Euclidean distance be- tween the segment centers (Figure 4.2b). Given two curve segments i, j, I measure their similarity in terms of shape and scale. I measure scale as the difference in curve length ‖li− l j‖. To compare shape, I first compute a best-fit affine trans- form Ti, j from i to j. I do this by resampling the curves by arc-length using the same number of points, 50 for all my experiments. I then use a linear least squares formulation to find the affine transformation which minimizes the L2 distance be- tween the two point-sets. I use a generic affine transform instead of a rigid one to allow for non-uniform scale and shear. I then measure similarity as the L2 closest-point distance between the transformed curve and its mate Li, j. All dis- tances are normalized by the diameter of the processed curve, i.e. by the maximal distance between two points on the curve. Similarity between curves is then set to si, j = 0.5‖li− l j‖+0.5(1− e−L2i, j/σ2). The second term measures the affine invari- ant shape difference of two curve segments. Specifically, I define a function that is zero if the curves are identical and 1 if they are maximally different. I achieve this mapping using a Gaussian fall-off function applied to the L2 distance between the curves segments. Normalizing this distance by the diameter of the curve loop and setting σ = 1/3, set using the three-sigma rule, results in the desired shape difference function. 4.3 Stable Matching of Segment Pairs Given a curve segmentation and a cost of pairing any two curve segments to form opposite sides of a poly-chord, this step aims to match segment pairs in a man- ner that maximally satisfies the dominant pairing preferences producing a stable matching. The standard algorithm for computing a stable matching [Irv85] consists of two phases. First, each segment ”proposes” to all other segments in order of pair- ing preference, continuing to the next segment if and when its current proposal is rejected. A segment rejects a proposal if it already holds, or subsequently receives, a proposal from a segment it prefers. In my setup, since matching costs are sym- metric, if the number of segments is even this step ends with each segment holding a proposal from another segment. If the number of segments is odd, one segment 25 is left out by the process and is ignored by the subsequent step. Held proposals form a set S of ordered segment pairs (i, j), where i holds a pro- posal from j ( j is i’s current favorite). S is a stable matching if ( j, i) ∈ S whenever (i, j) ∈ S. A second phase of repeated co-rotations, described below, transforms S into a stable matching. Suppose that (i, j) ∈ S, but not ( j, i). For each such i I identify the current second favorite to be the first successor of j in i’s preference list who would reject their held proposal in favor of i. A rotation relative to S is a sequence (i0, j0),(i1, j1), ...,(ik−1, jk−1) such that (im, jm) ∈ S for each m, and jm+1 is im’s current second favorite (all indices are modulo k). No stable match exists if k is odd. Otherwise, a co-rotation replaces pairs (im, jm), with (im, jm+1)in S. The standard method [Irv85] is proven to provide a stable match for an even number of participants, unless an odd party is found [Tan91], i.e. a rotation such that k is odd, and pi = qi+(k+1)/2 for all i. In that case no stable matching exists. In the case of an odd party, I have an odd-length cycle of segments with equal pairwise costs, e.g. an equilateral triangle or three perfectly symmetric curves (Figure 5.4). This case can be seen as a generalization of the standard midpoint splitting, and is resolved by splitting each segment in the cycle into two. Once the split is performed, a clear difference in cost emerges and the matching is repeated. 4.4 Segmentation Refinement The refinement process looks for a segment, or segments, to subdivide so as to max- imally decrease the average matching cost. My refinement examines two segmen- tation strategies, first searching for a single edge refinement and then a global mid- edge split. Since the number of segments is typically very small, a stable matching computation is practically instantaneous. Using the first approach, I quickly iterate over all segments, segmenting each one and evaluating the cost of the match com- puted with the refined segmentation. I then select the segmentation that maximally lowers the cost. Using this strategy, the one question I need to address is where to place the split, as the location can impact the subsequent segmentation cost. The basic strategy of splitting the segment in half is tested first, then a more targeted strategy that leverages the computed matching is applied to the currently matched segments. Given a current segment i which is matched to j I search for 26 all segments k that are either unmatched, or that prefer to be matched to i rather than their current mate l, i.e. ck,i < ck,l . In such situations, for instance the bottom curve on the basket (Figure 4.1), splitting the curve strategically into i1 and i2 can often satisfy this preference by generating matches (i1, j) and (i2,k). To minimize the cost of (i1, j) and (i2,k) I break i into two possible subdivisions i1, i2 based on arc-length (l) ratio, where li1/li2 = l j/lk or li1/li2 = lk/l j, and li1 + li2 = li, and test the matches induced by these segmentations. While theoretically more comprehensive or global segmentation refinement strategies may exist, I found my approach to work well in practice. It preserves dominant pairs and improves poor matches as intended by my subdivision heuris- tic. 27 Chapter 5 Quadrangulation Once I have an acceptable perfect stable match whose cost cannot be reduced by further segmentation, I use this segmentation and matching, as well as its induced poly-chord graph (see Figure 3.1), to construct a quadrangulation. 5.1 Extracting Quad Connectivity Using standard dual notations [DSSC08] I say that two poly-chords (i, j) and (k, l) intersect in the graph theoretic sense if, and only if, their corresponding curve seg- ments are interleaved on a closed curve. For instance, the purple and red segments on Figure 5.1 are interleaved, resulting in intersecting poly-chords. To generate a valid quadrangulation I require that the poly-chord graph be connected, but the connectivity is not guaranteed by the previous stage. The poly-chord graph can be separated into several components which is invalid to generate quadrangular mesh. To deal with this problem while keeping the meaningful segmentation and match- ing as much as possible, I induce new curve segments (in this project I use straight lines) to connect end-points of common segments belonging to different compo- nents of the poly-chord graph. Each graph component then becomes a smaller closed curve loop and I can re-run my algorithm (Figure 5.1). In the smaller curve loop, to avoid T -junctions I disallow the newly added segments from being further refined. Then I can match up the segments which are matched to the same induced segment. After connecting the different components together, the poly-chord graph 28 Figure 5.1: A disconnected dual graph (left) does not allow for a valid primal quad mesh. Splitting the cycle into two by a temporary curve segment (dashed) generates valid graphs for both parts which combined together induce a valid primal quad mesh (right). forms a valid dual structure. An intersection between two poly-chords corresponds to a quadrilateral in the final network. Connectivity between these quads is determined by the intersection order , e.g. determining the top-down order of the intersections of the green poly- chord with the blue and red ones in Figure 5.2. I define the quad connectivity by incrementally embedding poly-chords into the layout of cells, or regions, bounded by input boundary segments and previ- ously added poly-chords. Given the graph whose vertices are these cells and whose edges connect adjacent cells, I embed a poly-chord by computing the shortest path in this graph between the two vertices or cells, corresponding to the boundary curve segments connected by the poly-chord. This path minimizes the number of inter- sections between the new poly-chord and those already embedded. More impor- tantly, this path is the most intuitive one which better meets viewers expectation. This choice minimizes the number of dual graph cycles. Such cycles correspond to interior primal quadrangulation vertices adding which, as discussed below, can reduce flow smoothness. Given two equal length choices, I prefer one that induces better shaped quadrilaterals, where quality is measured as the scaled Jacobian (Fig- ure 5.2). In Figure 5.2 (a), the green poly-chord intersect the blue one first which has a smooth transition point between the consecutive segments. This path leads to almost 180 degree angles in the final quads. While if I choose another path (Fig- ure 5.2 (b)), all the angles in the result are nearly 90 degrees which has a better quality in terms of scaled Jacobian. 29 (a) (b) Figure 5.2: Two intersection orders induce different quad connectivity, with the one on the right inducing a better quad shape, and consequently a smoother flow. Figure 5.3: Locating an inner point G. Ei are vertices sharing side curves with G, and Ci are the diagonal quad corners oppositing to G. 5.2 Extracting Quad Geometry The dual graph defines the connectivity of my quadrangulation. To position the in- terior vertices and curves I use a two step process which leverages the quad topol- ogy to generate interior curves best reflecting the flow directions. Specifically I note that each chain of quads can be seen as a four-sided uv patch interpolating two flow-line end segments. Associating the v coordinate with the end segments, I expect the patch u-isolines to smoothly interpolate them. My geometry computation builds on the geometry construction in [NSY09] which shares the same goal. I first compute the interior vertex positions that best satisfy my requirements, using a global optimization of a per-vertex formu- lation [NSY09], that sets each vertex G to a weighted sum of vertex positions in neighboring quads (Figure 5.3): G = ∑ni=1(Ei +Ei−1−Ci)/ai ∑ni=1 1/ai (5.1) 30 Figure 5.4: I first position interior vertices (left) and then use the chain-long quads to position the interior curves (center). Finally, the resulting quad cycles are quad-meshed using discrete Coons patches (right). Figure 5.5: My distance based weighting (right) generates smoother flow line evolution than topology based one [NSY09]. where Ei are quad network vertices that share side curves with G, Ci are the diago- nal quad corners between Ei+1 and Ei, and ai = ‖Ei−Ci‖‖Ci−Ei+1‖ is an estimate of the area of the corresponding quad (see Figure 5.3). This formulation assumes the surrounding quadrilateral regions of G are parallelogram, which is good for generating high quality quad mesh in terms of scaled Jacobian. I then generate straight-line edges connecting these and boundary vertices as an intermediate approximation of the quadrangulation. Using this initial network each interior curve is now computed as a u-isoline on the quadrilateral patch containing two bounding flow-lines and the curve paths connecting them, using a discrete Coons formulation [Far92] (Figure 5.4). This formulation takes into account the distance of the new curve from the bounding flow lines, improving on the original formulation of Nasri et al [NSY09] (Figure 5.5). 31 Figure 5.6: Removing interior vertices: (Left) initial match (top) and induced quadrangulation (bottom); (Right) the final match with purple and green pairs flipped (top) has a slightly higher cost but the induced quadrangu- lation (bottom) has no interior vertices, leading to smoother flow-lines. 5.3 Meshing To fit a surface in the interior of each quad-patch I can use any number of meth- ods. The examples shown in the paper use a quad mesh sampled on a discrete bicubic Coons surface [Sal06]. This construction provides continuity across shared boundaries when the cross tangents are continuous. More sophisticated fitting tools which provide better cross-patch continuity can be used as well. 5.4 Minimizing Flow Dislocation The segmentation and pairing algorithm optimizes the cost of the individual flow- line matches, does not explicitly consider the impact of the quad patch connectivity on the final flow. Specifically, at the matching stage it is hard to predict the impact of the introduction of interior patch vertices on the smoothness of the flow lines. In some cases these vertices are essential to forming a good surface such as on the top of the espresso machine (Figure 8.6), but in other cases removing them can improve the flow (Figure 5.6). Thus, I have two approaches to remove unimportant dislocations. Parallel poly-chord (i, j) and (i+1, j−1) is redundant when the transition be- tween the consecutive segments is smooth. To make the quad layout more compact, I merge such adjacent poly-chords. Given a quadrangulation, I test if removing any of the interior vertices can im- prove the surface quality. Recall that each such vertex corresponds to a cycle in 32 the dual graph. I thus attempt to break cycles in the dual graph if the quadrangu- lation quality improves and the increase in the overall matching cost is acceptable. Specifically, for each edge < (i, j),(k, l) > of a cycle in the poly-chord graph I evaluate the consequence of swapping segment pairs to (i, l) and (k, j), or (i,k) and (l, j). A swap is valid if the following three criteria are satisfied: the quad quality, measured using the scaled Jacobian, is improved, no new cycles are intro- duced into the graph and the cost of the matches after the swap is no greater than the worst match cost before it. I thus perform a valid swap for the poly-chord edge of the cycle with the minimum increase in matching cost (Figure 5.6). 33 Chapter 6 Processing Curve Networks Up until now, I have only considered the meshing of a single curve cycle. The reason for this is that in curve networks, the majority of vertices adjacent to two or more cycles define corners that induce my initial segmentation. The remaining vertices form T-junctions that should not bias the flow-lines within cycles where the incident curves are continuous. Once the individual cycles have been quadran- gulated however, I must ensure that the geometry is watertight across the common boundary of adjacent cycles. For a quad-mesh fitting this requires the sampling, or interval count, along shared boundaries to be the same on both sides. This goal is easy to achieve for a conforming quad-patch layout, such as those generated inside each input cycle, using a fixed number of intervals per boundary curve. Special care is needed though, when meshing curve networks where cycle segmentation creates T-junctions. I optimize interval assignment using two modifications to the basic cycle quad- rangulation algorithm described above. The first stage, performed after segmen- tation and matching process, described above, for each cycle, resolves the initial, primary, T-junctions between pairs of neighbouring cycles. A T-junction occurs when one curve has a segment end-point, or vertex, at a boundary point and an- other curve does not. In most situations, this happens when the curve do not have obviouse sharp corners and the segment end-points for both curve are located in a very short distance due to numerical accuracy. Thus, given a T-junction, I first attempt to resolve it by merging adjacent vertices based on a threshold distance, 34 (a) (b) (c) (d) Figure 6.1: Separately processed cycles (a) introduce T-junctions. I first re- solve the T-junctions across pairs of neighbouring patches by propaga- tion (b), generating a well defined hierarchy of matching primary seg- ments. I then use integer programming to compute interval assignments (c) that minimizes the number of T-junctions, typically leading to a wa- tertight mesh (d). 35 while keeping in place both sharp corners and T-junctions present in the original artist input. Throughout my experiments, I set my threshold to 5δ , where δ is the minimum Euclidean distance between adjacent samples of the input polylines. Intuitively, the finer the initial sampling, the more precise the algorithm is, the smaller the merging threshold I need. For any T-junctions that I cannot resolve in this manner, I split the adjacent seg- ment and its matching segment in the corresponding cycle. I then refine the match- ing accordingly. This process resolves all the primary T-junctions, but in turn in- troduces secondary T-junctions where the matching segments are split (Figure 6.1, (b)). These T-junctions are further reduced using another iteration of threshold based merging. Contrary to primary T-junctions, the secondary T-junctions are guaranteed to be contained in primary segments that share clearly defined primary vertices (Fig- ure 6.1, (b)), a property I take advantage of in the final interval assignment stage. At this point, the network is converted to quad-patch topology using the method of Chapter 4. In the final step, when generating the per-patch meshes, I need to assign a consistent interval count to each segment. For a given primary segment, I require that the number of intervals on both sides of the segment are equal. To ensure the assignment is valid for a quad mesh, I further require that each secondary segment (one bounded by primary or secondary vertices) and its matching segment have the same number of intervals. Finally, I wish to minimize the total interval count while enforcing a minimum number of intervals per edge based on its length. If I formulate all of these requirements as a wishlist, as shown by Mitchell [Mit97], there may exist configurations where no valid assignment exists. I therefore relax my watertightness requirement, which allows us to reformulate this problem in terms of a minimization. Consider a pair of adjacent primary segments L and R. By virtue of the first step, I know that L and R share common endpoints; however, they may each contain a diffeing number of secondary segments. If l is a secondary segment on L and r is a secondary segment on R, let nl,R and nr,R represent the num- ber of intervals that the secondary segments l and r are divided into, respectively. I 36 can then express my minimization condition as the following function: min f (x) = w ∑ (L,R) (∑ l∈L nl,L−∑ r∈R nr,R)2 +∑ L,l (nl,L) (6.1) The first term in this equation seeks to minimize the number of mismatched inter- val counts along a given pair of adjacent primary segments. The second term seeks to minimize the total number of intervals for the entire mesh. I use w = 1000 to minimize the number of mismatches as much as possible. This minimization is subject to a number of constraints. I require that opposite segments of each quad patch have the same number of intervals. Additionally, I require that the number of intervals on a given secondary segment does not fall below a specified mini- mum. This minimum is determined by dividing the secondary segment length by a user-specified desired (local or global) interval length. Together, the minimization function and constraints form a quadratic, mixed-integer programming problem, which I solve using Tomlab /CPLEX. This approach lead to valid assignments for all the inputs I tested. Since the secondary segmentation vertices do not convey any geometry mean- ings, I can move these vertices along the primary segment. I prefer to generate a high quality mesh, so I want the intervals distribute as even as possible. I evenly seperate the primary segment into n segments, where n is the sum of the number of intervals assigned to the secondary segments belonging to it. Then I can place the secondary segmentation vertices according to the assigned intervals. 37 Chapter 7 Implementation My system is implemented in C++ as a plug-in for the CML framework. CML provides basic rendering functions and basic geometry classes such as meshes and curves. 7.1 Configuration File The configuration file is a stand-alone .txt file which contains global variables cus- tomized to one network. My system have a default set of variables which is gen- erally applicable to all kind of input. Thus, a configuration file is an option to get potentially better results. 7.2 Dependencies Like many research project applications, my system relies on several libraries. The system’s dependency list includes: • CML [Sur02] for discrete geometry and interface • TAUCS [Tol03] linear solver • MATLAB [Inc1a] and TOMLAB /CPLEX [Opt12] mixed-integer quadratic programming solver 38 7.3 Performance This system is not optimized for performance even though the software packages I relied on are well optimized. There is room for improvement in my own im- plementation. Despite several very complicated regions, the current system has a good performance. Chapter 8 will discuss the performance in detail. 39 Chapter 8 Results 8.1 Closed Curves I generated a number of synthetic test inputs to evaluate the behavior of my method on a variety of closed curves with different side configurations demonstrated in Fig- ures 8.1 and 8.2. These included a variety of convex regions (Figure 8.1 (a-f)) with different degrees of planarity, and different numbers of boundary discontinuities. For some of the inputs, the expected surface shape is best captured by introducing an extraordinary interior vertex (c,d). For other regions with n > 4 sides, such as (e,f), a regular connectivity better captures the intended shape. My method makes the appropriate choice based on analyzing the relationships between the input curve segments and the degree of parallelism between them. This is in contrast to purely connectivity methods, e.g. [NSY09], where the choice is strictly based on the num- ber of segments. Figure 8.1 (b) shows an atypical two-sided region, nevertheless reasonably fitted by my method, (g,h) show non-convex regions, where the optimal pairing is found automatically through refinement of initial segments. The letters in Figure 8.2 show the robustness of the method in the presence of complex non- convex curves, as well as processing of faces with interior loops. To handle such models, I first locate a pair of matching segments on different loops with minimal matching cost and introduce the shortest straight segment connecting those. The method than proceeds as usual on the resulting single cycle. 40 (a) (b) (c) (d) (e) (f) (g) (h) Figure 8.1: Quadrangulation and meshing of closed curves. Figure 8.2: Quad meshes of complex closed curves including interior cycles. 41 Artist Artist Our method Our method Figure 8.3: Artist generated boat models (left) and ours (right) exhibit very similar flow-line patterns. 8.2 Curve Networks I tested my method on a variety of input curve networks (Figure 1.2, 3.1, 8.6, 8.7, 8.8, 8.9, 8.10 and 8.11) generated by different modeling systems [BBS08, SKSK09, Ros07]. These networks contain a variety of complex, non-convex cy- cles. My method successfully captures the designer intent conveyed by the net- works, generating predictable and smoothly flowing quad-meshes interpolating the input curves. While the airplane (Figure 8.8) was created using a classical CAD modeling system, many of the other inputs (car, espresso maker, submarine, star- craft) (Figures 8.6, 8.7, 8.9, 8.10, 8.11) were generated using sketching tools, 42 Artist Artist Our method Our method Figure 8.4: Artist generated spaceship models (left) and ours (right) exhibit very similar flow-line patterns. which easily introduce noise and inaccuracies that hamper traditional surfacing. My method is robust to such artifacts. I compare my outputs on the boat and starcraft to those generated by an artist (Figures 1.5, 8.3, 8.4). The flow-line structure of my meshes is largely identical to the artist generated meshes, with only minor differences, such as flow on the side of the boat cabin. Both my and artist interpretations are feasible (my outputs contain a few extra cycles not present in the artist models). 8.3 Quantitative Evaluation On an Intel i7 CPU 870 2.93GH machine my method takes, on average, two sec- onds to quadrangulate a single curve cycle (most of the time spent on matching), 43 making it amenable for interactive surfacing in a sketch based modeler like ILoveS- ketch [BBS08]. The most time consuming regions are the front of the car (166 sec) and the top of the speaker (66 sec) (Figure 8.7). Intervals assignment is practically instantaneous, taking 0.1s for a an average network and taking 2s to process the largest model (plane). Table 8.1 summarizes the time (in seconds) consumed in the three main stages. The quad statistics for the models I tested are summarized in Table 8.2 and include numbers of input cycles, number of output quad cycles, mesh size(s), and the number of added extraordinary vertices. All the generated meshes are watertight. 8.4 Limitations My approach has three broad limitations which can be addressed by future re- search. Global context: The biggest limitation of my method is lack of global context. My flow-line analysis for each input cycle in a network is independent. In practice however, most adjacent cycles meet at sharp corners, typically resulting in a similar segmentation and flow across shared curve segments. The context of adjacent cy- cles could be useful in enforcing flow line continuity across cycles and predicting the flow within an individually ambiguous cycle. Failure cases: While my algorithm works well on design curve inputs from a variety of sources, it may not provide meaningful results for arbitrarily shaped curve cycles with no perceptible flow-lines. The absence of corners on a com- pletely smooth curve cycle will not provide us a meaningful initial segmentation to refine. In such cases I can impose an initial segmentation based on curvature max- ima and arc-length of the input curve. For example, in the speaker model (Figure [? ]), the front patch have very sharp top curves but relatively smooth bottom curves. Directly ruuning my algorithm do not give a perfect result (Figure 8.5 (Left)), since a short piece on the top matched to the side. If we manually segment the bottom curve, our algorithm gives the best solution (Figure 8.5 (Right)). Algorithmic complexity: While my central idea of flow-line segmentation and matching is conceptually clear, various aspects of my implementation could be streamlined. For example, while most of the parameters used by the method were 44 Figure 8.5: If this algorithm fails to find out the best result (left), people can add corrections to make the result better (right). Table 8.1: Running time (in seconds) in different stages for complex input curve networks. Model Segmentation and Matching solving mix-integer Build Mesh Spherebag 15.78 0.144 1.712 Boat 52.55 0.403 4.129 Spaceship 57.53 0.358 5.027 Car 196.0 0.349 4.273 Espresso 59.00 0.308 8.251 Speaker 88.712 0.321 5.106 Plane 206.4 2.316 34.925 Submarine 64.55 0.441 17.95 derived based on clear algorithmic goals, a few such as drop in Section 4.1) are based on trial-and-error, and could be learned from designer quadrangulated exam- ples. 45 Figure 8.6: Quadrangulation and meshing of a espresso machine. The stars indicate the network locations of the highlighted complex regions. Table 8.2: Algorithm statistics for different curve networks. input cycles output quad cycles mesh size interior vertices Sphere Bag 3 9 987 0 Boat 30 82 4464 9 Spaceship 41 94 5008 6 Car 26 70 5020 13 Espresso 54 75 6904 5 Speaker 13 42 8548 1 Plane 140 192 10705 10 Submarine 39 103 16600 31 46 Figure 8.7: Quadrangulation and meshing of speaker model. The stars indi- cate the network locations of the highlighted complex regions. 47 Figure 8.8: Quadrangulation and meshing of plane model. The stars indicate the network locations of the highlighted complex regions. Figure 8.9: Quadrangulation and meshing of boat model. The stars indicate the network locations of the highlighted complex regions. 48 Figure 8.10: Quadrangulation and meshing of submarine model. The stars indicate the network locations of the highlighted complex regions. Figure 8.11: Quadrangulation and meshing of car model. The stars indicate the network locations of the highlighted complex regions. 49 Chapter 9 Conclusion I have presented, to my knowledge, the first method for quadrangulating general designer specified closed 3D curves and curve networks. My results show an ap- proach robustly process complex curve networks and generating interpolating quad meshes consistent with designer intent. I developed an interleaved segmentation and matching algorithm that pairs dominant flow-lines and uses poor matches to guide segmentation refinement, and that computes a poly-chord graph that cap- tures user-intended bridging directions across a closed curve. I advocate the use of stable matching as the principled way to formulate my quadrangulation goals and anticipate it to be well-suited to other problems relating to shape matching or coherence, where both dominant components and their correspondence is sought. With the segmentation and matching, I build the connectivity and quad geometry following the idea of Coons patch, which is consistent with designer’s expecta- tions. I then extend this method to curve network with minimum T-junctions by solving an quadratic mixed-integer programming problem. My work points to a number of future directions. Rather than restricting my input to a constrained geometric definition of a design curve network, I attempted to quadrangulate any 3D curve network as a designer would, using the principle of flow-line segmentation and matching. A formal perceptual study of the precise difference between ambiguous and design curves (Figure 1.3) is an ambitious but worthy goal. While my segmentation refinement strategy works well in general, approaches with theoretical guarantees of match quality are worth exploring. 50 My method focuses on quad-only meshing. In some cases, however, designer intent is better served by allowing a small number of triangular elements (e.g. Fig- ure 8.1 (b)), motivating a technique for meshing but predominantly quadrilateral meshes. I would also like to apply my technique as-is to the finite-element mesh- ing of closed planar domains, balancing flow-line alignment against mesh quality. 51 Bibliography [ACSD+03] P. Alliez, D. Cohen-Steiner, O. Devillers, B. Lévy, and M. Desbrun. Anisotropic polygonal remeshing. In ACM Transactions on Graphics (TOG), volume 22, pages 485–493. ACM, 2003. → pages 9 [AJA11] Fatemeh Abbasinejad, Pushkar Joshi, and Nina Amenta. Surface patches from unorganized space curves. Comput. Graph. Forum, 30(5):1379–1387, 2011. → pages 1, 10 [BBS08] S.H. Bae, Ravin Balakrishnan, and Karan Singh. ILoveSketch: as-natural-as-possible sketching system for creating 3d curve models. In Proc. Symposium on User interface software and technology, pages 151–160. ACM, 2008. → pages 1, 11, 42, 44 [BLK11] David Bommes, T. Lempfer, and Leif Kobbelt. Global Structure Optimization of Quadrilateral Meshes. Computer Graphics Forum, 30(2):375–384, 2011. → pages 10 [BR11] M. Bordegoni and C. Rizzi. Innovation in Product Design: From CAD to Virtual Prototyping. Springer, 2011. → pages 1, 11 [Coo64] S. Coons. Surfaces for computer aided design. Technical Report, MIT., 1964. → pages 5, 10, 11, 12 [DBG+06] S. Dong, P.T. Bremer, M. Garland, V. Pascucci, and J.C. Hart. Spectral surface quadrangulation. In ACM Transactions on Graphics (TOG), volume 25, pages 1057–1066. ACM, 2006. → pages 9, 10 [DDGG05] K Das, P Diaz-Gutierrez, and M Gopi. Sketching free-form surfaces using network of curves. Sketch-based interfaces and modeling SBIM, 2005. → pages 10 52 [dGGDV11] F. de Goes, S. Goldenstein, M. Desbrun, and L. Velho. Exoskeleton: Curve network abstraction for 3d shapes. Computer and Graphics, 35(1):112–121, 2011. → pages 1 [DSC09] Joel Daniels, Claudio T. Silva, and Elaine Cohen. Semi-regular quadrilateral-only remeshing from simplified base domains. In Proc. Symposium on Geometry Processing, pages 1427–1435, 2009. → pages 10 [DSSC08] Joel Daniels, Cláudio T. Silva, Jason Shepherd, and Elaine Cohen. Quadrilateral mesh simplification. ACM Transactions on Graphics, 27(5):1, 2008. → pages 4, 28 [Far92] Gerald Farin. Curves and surfaces for computer aided geometric design: a practical guide. Academic Press, 1992. → pages 11, 31 [FH99] Gerald Farin and Dianne Hansford. Discrete Coons patches. Computer Aided Geometric Design, 16:691–700, 1999. → pages 1, 11, 12, 13 [FH11] Mark Finch and Hugues Hoppe. Freeform Vector Graphics with Controlled Thin-Plate Splines. ACM Trans. on Graphics (SIGGRAPH Asia), 30(6), 2011. → pages 10, 11 [Gah10] A. Gahan. 3D Automotive Modeling: An Insider’s Guide to 3D Car Modeling and Design for Games and Film. Elsevier Science, 2010. → pages 1 [GR05] Kun Gao and Alyn Rockwood. Multi-sided attribute based modeling. Mathematics of Surfaces XI, pages 219–232, 2005. → pages 10, 12 [Inc1a] The MathWorks Inc. 2010. version R2011a. → pages 38 [Irv85] Robert W. Irving. An efficient algorithm for the ”stable roommates” problem. J. Algorithms, 6(4):577–595, 1985. → pages 5, 18, 25, 26 [KNP07] Felix Kälberer, Matthias Nieser, and Konrad Polthier. Quadcover - surface parameterization using branched coverings. Computer Graphics Forum, 26(3):375–384, 2007. → pages 9, 10 [Lev03] Bruno Levy. Dual domain extrapolation. ACM Transactions on Graphics (Proc. SIGGRAPH), 22(3):364–369, 2003. → pages 10, 11 53 [LL10] Bruno Levy and Yang Liu. Lp centroidal voronoi tesselation and its applications. ACM Trans. Graph., 2010. → pages 9 [Mal00] P. Malraison. N-SIDED Surfaces: a Survey. Defense Technical Information Center, 2000. → pages 10 [Mit97] Scott A. Mitchell. High fidelity interval assignment. In Proceedings, 6th International Meshing Roundtable, pages 33–44, 1997. → pages 6, 36 [MK04] M. Marinov and L. Kobbelt. Direct anisotropic quad-dominant remeshing. In Computer Graphics and Applications, 2004. PG 2004. Proceedings. 12th Pacific Conference on, pages 207–216. IEEE, 2004. → pages 9 [MK06] M. Marinov and L. Kobbelt. A robust two-step procedure for quad-dominant remeshing. In Computer Graphics Forum, volume 25, pages 537–546. Wiley Online Library, 2006. → pages 9 [MS09] James McCrae and Karan Singh. Sketching piecewise clothoid curves. Comput. Graph., 33:452–461, August 2009. → pages 21 [MSM11] James McCrae, Karan Singh, and Niloy J. Mitra. Slices: a shape-proxy based on planar sections. In Proceedings of the 2011 SIGGRAPH Asia Conference, SA ’11, pages 168:1–168:12, 2011. → pages 1, 22 [MZL+09] Ravish Mehra, Qingnan Zhou, Jeremy Long, Alla Sheffer, Amy Gooch, and Niloy J. Mitra. Abstraction of man-made shapes. TOG (Proc. SIGGRAPH Asia), 28(5):1–10, 2009. → pages 1, 11 [NISA07] Andrew Nealen, Takeo Igarashi, Olga Sorkine, and Marc Alexa. Fibermesh: designing freeform surfaces with 3d curves. ACM Trans. Graph., 26, July 2007. → pages 1, 10, 11 [NSY09] A. Nasri, M. Sabin, and Z. Yasseen. Filling N -Sided Regions by Quad Meshes for Subdivision Surfaces. Computer Graphics Forum, 28(6):1644–1658, September 2009. → pages 5, 12, 14, 17, 19, 30, 31, 40 [OK11] Günay Orbay and Levent Burak Kara. Sketch-based modeling of smooth surfaces using adaptive curve networks. In Proceedings of the Eighth Eurographics Symposium on Sketch-Based Interfaces and Modeling, SBIM ’11, pages 71–78, 2011. → pages 11 54 [Opt12] TOMLAB Optimization. Tomlab a library of optimization tools. 2012. → pages 6, 38 [Owe98] S.J Owen. A survey of unstructured mesh generation technology. In Proc. International Meshing Roundtable, 1998. → pages 8 [RGS10] E. Ruiz-Gironés and J. Sarrate. Generation of structured meshes in multiply connected surfaces using submapping. Adv. Eng. Softw., 41:379–387, February 2010. → pages 8 [RLL+06] N. Ray, W.C. Li, B. Lévy, A. Sheffer, and P. Alliez. Periodic global parameterization. ACM Transactions on Graphics (TOG), 25(4):1460–1485, 2006. → pages 9 [Ros07] K.L.P. Rose. Modeling developable surfaces from arbitrary boundary curves. Processing, (August), 2007. → pages 10, 11, 42 [Sal06] David Salomon. Curves and Surfaces for Computer Graphics. Springer-Verlag, 2006. → pages 12, 32 [SKSK09] Ryan Schmidt, Azam Khan, Karan Singh, and Gord Kurtenbach. Analytic drawing of 3d scaffolds. ACM Trans. on Graph. (Proc. SIGGRAPH Asia), 28(5), 2009. → pages 1, 11, 42 [SPK04] Karan Singh, Hans Pedersen, and Venkat Krishnamurthy. Feature based retargeting of parameterized geometry. In Proceedings of the Geometric Modeling and Processing 2004, GMP ’04, pages 163–, Washington, DC, USA, 2004. IEEE Computer Society. → pages 1 [Ste81] Kent A. Stevens. The visual interpretation of surface contours. Artificial Intelligence, 17, 1981. → pages 3 [Sur02] Vitaly Surazhsky. Cml - a mesh processing library. 2002. → pages 38 [SWZ04] S. Schaefer, J. Warren, and D. Zorin. Lofting curve networks using subdivision surfaces. Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing - SGP ’04, page 103, 2004. → pages 12, 14 [Tan91] Jimmy J. M. Tan. A necessary and sufficient condition for the existence of a complete stable matching. J. Algorithms, 12(1):154–178, January 1991. → pages 26 55 [Tol03] Sivan Toledo. Taucs - a library of sparse linear solvers. 2003. → pages 38 [VRS11] T. Várady, Alyn Rockwood, and P. Salvi. Transfinite surface interpolation over irregular n-sided domains. Computer-Aided Design, (iv), 2011. → pages 10, 12 [WWBB96] M. Whiteley, D. White, S. Benzley, and T. Blacker. Two and three-quarter dimensional meshing facilitators. Engineering with computers, 12(3):144–154, 1996. → pages 8 [ZHLB10] M. Zhang, J. Huang, X. Liu, and H. Bao. A wave-based anisotropic quadrangulation method. ACM Transactions on Graphics (TOG), 29(4):118, 2010. → pages 9 56
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Design-driven quadrangulation of closed 3D curves
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Design-driven quadrangulation of closed 3D curves Wang, Caoyu 2012
pdf
Page Metadata
Item Metadata
Title | Design-driven quadrangulation of closed 3D curves |
Creator |
Wang, Caoyu |
Publisher | University of British Columbia |
Date Issued | 2012 |
Description | This work presents a novel, design-driven quadrangulating method for closed 3D curves. While the quadrangulation of existing surfaces has been well studied for a long time, there are few works that can successfully construct a quad-mesh relying solely on 3D curves, as the shape of the surface interior is not uniquely defined. I observe that, in most cases, viewers can complete the intended shape by envisioning a dense network of smooth, gradually changing flow-lines across a pair of input curve segments with similar orientation and shape. The method proposed here mimics this behavior. This algorithm begins by segmenting the input closed curves into pairs of matching segments. I interpolate the input curves by a network of quadrilateral cycles whose iso-lines define the desired flow line network. I proceed to interpolate these networks with all-quad meshes that convey designer intents. I evaluate my results by showing convincing quadrangulations of complex and diverse curve networks with concave, non-planar cycles, and validate my approach by comparing my results to artist generated interpolating meshes. My algorithm is suitable for use in sketch-based modeling systems as well as in other applications where artist curves can be created. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-11-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0052222 |
URI | http://hdl.handle.net/2429/43602 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2013-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2013_spring_wang_caoyu.pdf [ 48.37MB ]
- Metadata
- JSON: 24-1.0052222.json
- JSON-LD: 24-1.0052222-ld.json
- RDF/XML (Pretty): 24-1.0052222-rdf.xml
- RDF/JSON: 24-1.0052222-rdf.json
- Turtle: 24-1.0052222-turtle.txt
- N-Triples: 24-1.0052222-rdf-ntriples.txt
- Original Record: 24-1.0052222-source.json
- Full Text
- 24-1.0052222-fulltext.txt
- Citation
- 24-1.0052222.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:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0052222/manifest