Model ing Developable Surfaces from Arbi t ra ry Boundary Curves by Kenne th L l o y d Pa t r ick Rose B . M a t h . , Univers i ty of Waterloo, 2005 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Master of Science m The Facul ty of Graduate Studies (Computer Science) The Univers i ty O f B r i t i s h C o l u m b i a August 2007 © Kenne th L l o y d Pa t r ick Rose 2007 Abstract Developable surfaces are surfaces that can be unfolded into the plane with no distortion. Although ubiquitous in our everyday surroundings, there is currently no easy way to model them on a computer. This thesis fills this void by presenting a general method for creating developable geometry that utilizes the connection between developable surfaces and the convex hulls of their boundaries. Given an arbitrary, user-specified 3D polyline boundary, our system generates a smooth discrete developable surface that interpolates this boundary. We identify desirable properties of such surfaces, present a practical algorithm to compute them, and extend it to handle.darts and internal singular points. We demonstrate the effectiveness of our method through a series of examples, from architectural design to garments, using a sketch-based interface to quickly create the boundaries. ii Table of Contents Abstract . . . i i Table of Contents i i i List of Tables v List of Figures v i Preface v i i i Acknowledgements ix Statement of Co-Authorship x 1 Introduction 1 1.1 Developable Surfaces 1 1.2 Appl ica t ions 2 1.3 Developables from Boundaries 4 2 Background 6 2.1 Ru led and Developable Surfaces 6 2.2 Gaussian Curvature under Isometric M a p p i n g 7 2.3 Properties of Developable Surfaces 8 2.4 Developable Boundary Triangulations 10 3 Related Work 12 3.1 Developable Approx ima t ion 12 3.1.1 Discrete Methods 12 i i i Table of Contents 3.1.2 Continuous Methods 14 3.1.3 Benefits and Limitations of Approximation 14 3.2 Direct Modeling 15 4 Constructing Developable Triangulations 19 4.1 Developability and Convexity 20 4.2 Desirable Triangulation Properties 23 4.3 Branch-and-Bound Search Algorithm . . . • 24 4.4 Metrics 29 4.4.1 Triangulation Quality 29 4.4.2 Cover Quality 31 4.4.3 Cover Potential 32 4.5 Darts and Multiple Boundaries 33 4.6 Additional Modeling Control 33 4.6.1 Specifying Rulings 34 4.6.2 Overriding Optimal Selection . . . 34. 4.7 Runtime 35 4.8 Robustness 36 4.9 User Interface 37 4.10 Limitations 38 5 Results 40 5.1 Garments 40 5.2 Architecture 43 5.3 Paper Design 45 5.4 Leather, Wood Veneer, and Metal Goods 46 6 Summary 49 7 Future Work 51 Bibliography 53 iv List of Tables 4.1 Running times for the algorithm on several examples 36 List of Figures 1.1 Examples of developable surfaces and their corresponding patterns 1 1.2 M a p p i n g a sphere to the plane 2 1.3 Appl ica t ions of developable surfaces 3 2.1 Developable and warped ruled surfaces 7 2.2 A composite developable surface and its Gauss map 9 2.3 Tangent planes as support ing planes on developable surfaces. 9 2.4 Loca l ly convex and non-convex interior t r iangulat ion 10 2.5 Developable and warped ruled triangulations interpolat ing the same polyline and corresponding Gauss maps 11 3.1 V i r t u a l garments 13 3.2 Artefacts in using approximate developables for manufacturing. 15 3.3 Torsal boundary tr iangulat ion interpolating polyl ine directrices. 17 3.4 Mode l ing height field developable surfaces 18 4.1 Envelope triangulations for a convex polyl ine 2 l 4.2 Ex t rac t ing a local ly convex tr iangulat ion 22 4.3 P lanar i ty metric 25 4.4 A l g o r i t h m stages on a simple example 26 4.5 Pseudocode of main loop 30 4.6 Compu t ing a lower bound on fairness 32 4.7 Mode l ing a cone by a boundary wi th a single dart 33 4.8 Specifying rulings 34 '4.9 Al ternat ive triangulations for the gazebo example 35 v i List of Figures 4.10 Sketching a shoe overtop of an underlying model of a foot. . . 38 4.11 Boundary i l lustrat ing l imitat ions 39 5.1 Example : Hat 41 5.2 Example : Poncho 41 5.3 Example : Tanktop and Skir t 42 5.4 Example : Dress 42 5.5 Example : Opera House 43 5.6 Example : Gazebo 44 5.7 Example : Skyscraper 44 5.8 Example : Tu l i p L a m p 45 5.9 Example : Helmet 46 5.10 Example : Chairs 47 5.11 Example : Purse 47 5.12 Example : Shoe 48 5.13 Example : Glove 48 Preface Par t of this thesis has been published in the following paper: • Rose, K., Sheffer, A . , Wi the r , J . , C a n i , M . - P . , Th iber t , B . (2007). De-velopable Surfaces from A r b i t r a r y Sketched Boundaries. Eurographics Sympos ium on Geometry Processing 2007. Pages 163 - 172. Acknowledgements Firs t and forefost, I would like to thank my supervisor A l i a Sheffer, wi thout whom this work would not have been possible. There are countless things that I learned w i t h her over these past two years which I a m grateful for. I also would like to thank Mich i e l van de Panne, my second reader, for a l l of his valuable feedback. T h a n k you to everyone in the Imager lab that I had the pleasure of working wi th : T i b i , V lady , Dan , L lach , Michae l , Ian, Steve, Chr i s , Hagi t , M i k e , D a v i d , A b h i , Derek, Chery l , B r a d , Gordon , A a r o n , Stel l ian, Y o e l , and anyone else that I've forgotten. A s well, thank you to everyone at H i l l e l . I take w i t h me many great memories. T h a n k you to my father and sister for understanding m y decision to pur-sue graduate work three t ime zones away. To my housemate Izzet, thank you for many enlightening scientific discussions. To K i r a , thank you for al l of the great times and for making me feel like a part of your family. I also owe a great deal of gratitude to Candice Chatz , who continuously supported me and prevented me from fulfilling the stereotype of a s tarving grad student. F ina l ly , thank you to my late mother, who taught me that everything about life leaves answers. Undeniable, the pursuit of this degree was no exception. K E N N E T H R O S E The University of British Columbia August 2001 ix Statement of Co-Authorship The algori thm described in Chapter 4 was developed together w i t h D r . A l i a Sheffer. D r . Sheffer supervised the project while I performed research and implementat ion. T h e algori thm was combined w i t h a sketch based user interface developed by Jamie Wi the r and Prof. Mar ie -Pau le C a n i . A pa-per describing a system unifying the user interface and the a lgori thm was cooperatively prepared [32]. x Chapter 1 Introduction 1.1 Developable Surfaces Developable surfaces are surfaces that can be unfolded into the plane wi th -out dis tort ion. A s shown in Figure 1.1, cylinders and cones are examples of developable surfaces since each can be unfolded to the plane wi thout stretch-ing or shearing the surface. The unfolded, planar surface is referred to as the pattern or development of the original surface, depending on the appl i -cation. A n example of a non-developable surface is a sphere. T o il lustrate, consider the cartographical problem of representing the 2D curved surface of the earth on a flat map (i.e., a plane). Figure 1.2(b) shows one possible projection, though it exhibits gross stretching at the north and south poles (e.g., Greenland i n white). A s explained in Chapter 2, there is i n fact no way to map a sphere to a plane without introducing distort ion. T h e abi l i ty of a surface to map to the plane wi th l i t t le or no distort ion is extremly pract ical , making developable surfaces useful in several applications. (a) Cylinder (b) Cone Figure 1.1: Examples of developable surfaces and their corresponding pat-terns. 1 Chapter 1. Introduction ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ (a) Spherical Ear th Figure 1.2: M a p p i n g a sphere to the plane. Greenland is highl ighted i n white to indicate distort ion. 1.2 App l i ca t i ons Developable surfaces are commonly used when manufacturing w i t h mate-rials that do not stretch or tear. A n y process manipula t ing fabric, paper, leather, sheet metal or p lywood w i l l benefit from developable surface model-ing techniques since these materials admit l i t t le dis tor t ion. In typ ica l setups, the patterns of the product are first designed by trained individuals , w i th a computer performing a bending simulation to help forecast the manufac-tured result. T h e product is then fabricated by cut t ing out the patterns of the surface from a flat sheet of the respective mater ia l and bending these planar patterns to form the desired shape. Appl ica t ions include model ing ship hulls, buildings, airplane wings, garments, ducts, automobile parts. In ship design, the hul l is usually constructed by segmenting it into pieces fitted wi th large metal sheets. O n singly curved parts of the hu l l , sheets can be fitted by a process called rolling, which s imply bends the sheets to the desired shape. The result of roll ing is a developable surface which is typ-ical ly cyl indr ica l . Ro l l i ng alone is normally not sufficient to construct an entire hul l since some parts of the hul l may be doubly curved and thus non-developable. For example, the bow usually includes a bulbous piece (Figure 1.3(a)) which moves water around the hul l in the direct ion of least resistance, u l t imate ly reducing fuel consumption. In these non-developable regions, a heating process is used to deform a sheet after rol l ing i n order to (b) Mercator Projection Chapter 1. Introduction introduce the addi t ional curvature direction. The heating process is usually performed manual ly by an experienced individual who heurist ical ly deter-mines the parameters required to achieve the correct amount of bending. The heating process is t ime consuming, labour intensive and error prone. Thus, model ing a hul l pr imar i ly w i th developable surfaces minimizes the use of heating and simplifies and improves the fabrication process [11, 12]. (a) Ship Hu l l [38]. (b) Peter B. Lewis bui lding [7]. (c) Connecting tubes [37]. (d) Garment Design [9]. Figure 1.3: Appl ica t ions of developable surfaces. T h e benefits of developable surfaces in ship hul l design are also perti-nent when designing buildings from sheets of mater ial . T h e prolific and contemporary architect Frank Gehry extensively uses developable surfaces i n his structures. Shelden notes that a major accomplishment of Gehry ' s work is the abi l i ty to create innovative designs w i th in the context of con-ventional construction processes [36]. Though any free form shape can be constructed by the digi tal C N C fabrication techniques commonly used by the aerospace and computer animation industries, the costs of these meth-ods are frequently prohibit ive when applied in an architectural setting. B y 3 Chapter 1. Introduction ut i l iz ing developable constraints and. staying wi th in the realm of exist ing fabrication practices, Gehry is able to reduce costs and fabrication error, ensuring the final form is t ight ly correlated to the original design. Figure 1.3(b) shows an image of the Peter B . Lewis bui ld ing at Case Western Re-serve Univers i ty in Cleveland, U S A . T h e brick and steel portions of the bui ld ing are both modeled as piecewise developable surfaces [36]. In duct construction, a common problem is fabricating a metal surface that connects two tubes of different shapes. Specifically, given two space curves p and q, the problem is finding a surface that interpolates both p and q (Figure 1.3(c)) [37]. Though there are an infinite number of such con-necting surfaces, using a connecting developable surface ( C D S ) is desirable since a C D S is most easily fabricated from sheet metal . T h i s problem is straightforwardly solved by the algori thm presented in Chapter 4. In fashion design, developable surfaces have great uti l i ty. Garments are constructed by sewing together panels that are cut out as patterns from fiat sheets of fabric. For example, in Figure 1.3(d), the dress on the right is assembled by cu t t ing out and sewing together the patterns on the left. W h e n designing garments, a core requirement is construct ibi l i ty and ensuring that each panel of the garment can be developed from a flat sheet. A l t h o u g h certain materials stretch slightly due to gravity after assembly (e.g., cotton weave), garments are t radi t ional ly modeled as developable surfaces since the effect of this stretch is negligable when assembling the panels together. Designing sewing patterns is a challenging task, requiring significant t ra ining to understand the many ways that panels can jo in together to correctly form around the geometry of humans. The next section introduces a modeling paradigm that greatly simplifies the task of pattern creation and allows interesting garments to be designed. 1.3 Developables from Boundaries Despite their ubiquity, developable surfaces remain difficult to model , par-t icular ly for non-expert users. Th i s thesis focuses on the problem of easily modeling developable surfaces and presents a method i n which users s imply 4 Chapter 1. Introduction specify the boundaries of each surface patch as a 3D curve. 3D bound-ary curves are a natural modeling choice since they can be easily specified and manipulated through a variety of interfaces (Chapter 5) and provide intui t ive shape control for the underlying surface. T o enable this modeling paradigm, we introduce a method for creat-ing developable surfaces which interpolate arbitrary boundaries (Chapter 4). We observe the correlation between a developable surface interpolat ing a boundary curve and the convex hul l of that curve. T h i s linkage is the basis for a novel a lgori thm that generates interpolating developable surfaces for any given smooth input boundary. T h e method explores the space of possible interpolating surfaces searching for solutions which have a desired set of shape properties. It allows the user to rank the importance of the different properties in order to control the shape of the resulting surface and supports exploration of alternative solutions. Chapters 2 and 3 review the relevant mathemat ical background and survey related work. Chapter 4 describes a novel a lgori thm operating in a discrete setup for computing a developable surface interpolating an arbi t rary polyl ine boundary. Results obtained from this a lgori thm are showcased i n Chapter 5. F ina l ly , Chapters 6 and 7 summarize and discuss future work. 5 Chapter 2 Background Developable surfaces have a lengthy mathematical history originat ing in differential geometry. T h i s section reviews their main properties, focusing on those used by the algori thm presented in Chapter 4. 2.1 Ruled and Developable Surfaces A ruled surface is a surface containing (at least) one one-parameter family of straight lines [22]. A ruled surface S C K 3 may be represented in the form x(s,i) = b(s) + tS(s), where b(s) is called the directrix or the base curve of the surface and S(s) is called a generator. Intuitively, a ruled surface can be thought of as being constructed by continuously sweeping out a line in space (i.e., the generator) w i t h some marked point of the line following the path of the directr ix. In-deed, for a given fixed value of s, the above formula reduces to the equation of a straight line. T h i s line is called a ruling of the surface. A developable surface is a ruled surface wi th the addi t ional property that the tangent plane is constant at a l l points along a given ru l ing [22]. Since the tangent plane at a point can be described by the surface normal at that point, an equivlent requirement is that the surface normal at a l l points along a given rul ing is constant [31]. A ruled surface which is not developable has normal variat ion along its rulings and is thus called a warped ruled surface. A ruled surface is a developable surface if and only if b • (S x 6) = 0 6 Chapter 2. Background where the dot above denotes the derivative wi th respect to s (Theorem 58.1 of [22]). F igure 2.1 shows a developable surface and warped ruled surface sharing the same boundary. (a) Developable Surface (b) Warped Ruled Surface Figure 2.1: Developable and warped ruled surfaces. In (a), the normals are constant along the specified rul ing while in (b), the normals vary along the rul ing. 2.2 Gaussian Curvature under Isometric Mapping A bijective function / : S C M 3 —> T C R 3 is an isometric or length preserv-ing mapping if the length of any arc on S is the same as that of its image on T under / . For example, rotation around a given axis is an isometric mapping. A n extremely useful property is that the intr insic properties of a surface, those depending only on the first fundamental form, are invariant under isometric mapping (Theorem 57.1 of [22]). T h e pr inc ipa l curvatures at a point on a surface measure the min imum and m a x i m u m bending of the surface at that point. Gauss ' theorema egregium states that the Gaussian curvature K, the product of the pr incipal curvatures, is an intr insic property of a surface [19]. Therefore, K is invariant under isometric deformation. 7 Chapter 2. Background 2.3 Properties of Developable Surfaces A port ion of a surface is developable if and only i f K = 0 everywhere on the por t ion (Theorem 59.2 of [22]). Since a plane has K = 0 everywhere, a plane is an example of a developable surface. Furthermore, since K is invariant under isometric deformation and isometries are bijective, any surface that can be isometrically mapped to the plane is developable. T h e converse of this statement, that any developable surface can be isometrically mapped to the plane, is also true and is proved in Theorem 59.3 of [22]. Thus , developable surfaces are the only surfaces that can be isometrically deformed to the plane. Th i s property explains why it is impossible to map a sphere to the plane without distort ion (Figure 1.2). Since a sphere has K > 0 everywhere, it is not developable and thus cannot be isometrically mapped to the plane. T h e Gauss map is a function that maps every point p of an oriented surface in R 3 to the point on the unit sphere that is parallel to the normal at p. In general, the Gauss map of a surface is another surface (right side of Figure 2.5(d)). However, in the case of developable surfaces, since the normals are constant along a given rul ing, the Gauss map degenerates into a curve (right side of Figure 2.5(c)) or possibly a network of curves (Figure 2.2(b)). If the Gauss map is a single curve, then the directr ix of the surface is a single continuous curve. Po t tmann and Wallner [31] refer to these surfaces as developable ruled surfaces or torsal ruled developable surfaces. To avoid ambiguity w i t h ruled surfaces as defined in Section 2.1, these surfaces w i l l be referred to as torsal developable surfaces, in contrast to composite developable surfaces whose Gauss map is a network of curves. A composite developable surface is thus made of a union of torsal developable surfaces joined together by transi t ion planar regions [16], where the latter correspond to the branching points on the Gauss map. In either case, another useful property of developable surfaces is that their image under the Gauss map is one dimensional. O n a developable surface, the tangent planes of most rulings bound some local neighbourhood of the rul ing in one of the two closed half-spaces induced by the plane (Figure 2.3(a)). Therefore, most tangent planes of rulings are 8 Chapter 2. Background (a) (b) Figure 2.2: A composite developable surface and its Gauss map. supporting planes [23], the exception being rulings where the surface has an inflection (Figure 2.3(b)). When the tangent plane of a ruling is a supporting plane, since all rulings in the local neighbourhood lie on one side of the plane, the given ruling lies on the convex hull of the neighbourhood (i.e., the local convex hull) [17]. In contrast, on a warped ruled surface, most rulings lie inside their local convex hull. (a) (b) Figure 2.3: (a) Tangent plane is a supporting plane on a developable surface; (b) Profile view of (a). Only on the inflection ruling is the tangent plane not a supporting plane. 9 Chapter 2. Background 2.4 Developable Boundary Triangulations G i v e n a polyl ine w i th vertices sampled from an input piecewise smooth curve, a boundary tr iangulation is a manifold t r iangulat ion w i t h no interior vertices whose boundary is the polyline. B y construction, any boundary t r iangula t ion is developable, as the triangles can be unfolded into the plane wi th no distort ion. In the l imi t however, as the sampling density of the polyl ine increases, not every tr iangulat ion w i l l approximate a smooth de-velopable surface. Specifically, the l imi t ing surface of a t r iangulat ion is a developable surface if and only if the majori ty of the interior edges of the tr iangulat ion are locally convex [17]. A n interior edge is defined as locally convex if it lies on the convex hul l of its end vertices and the four adjacent polyl ine vertices [17] (Figure 2.4(a)). A n interior edge is non-convex i f it lies inside this convex hul l (Figure 2.4(b)). (a) Locally Convex (b) Non-Convex Figure 2.4: L o c a l l y convex and non-convex interior t r iangulat ion edges PiPj. For a t r iangulat ion to approximate a smooth developable surface, the number of non-convex edges should not depend on the sampling density of the polyl ine. Figure 2.5 shows two triangulations of the same polyl ine, one of which approximates a developable surface, while the other approximates a warped ruled surface. In the first case, a l l the interior edges are local ly convex (Figure 2.5(a)). In the second case, the majori ty of edges are non-convex (Figure 2.5(b)). 10 Chapter 2. Background (a) Developable Triangulation (b) Warped Ruled Triangulation (c) Gauss map of 2.5(a) and of limit surface (d) Gauss map of 2.5(b) and of limit surface Figure 2.5: Developable and warped ruled triangulations interpolat ing the same polyl ine and corresponding Gauss maps. 11 Chapter 3 Related Work In computer graphics and modeling, developable surfaces have raised inter-est in several different contexts including reconstruction from point clouds [12, 29] and mesh segmentation into nearly developable charts for parame-terization and pattern design [20, 35, 43]. The following review only covers methods for modeling developables either v i a developable approximat ion or directly. 3.1 Developable Approximation Given an existing non-developable surface, a large number of methods a im at approximat ing it w i th one or more developable surfaces. Some of the methods operate on triangle meshes in a discrete setup [15, 25, 28, 41] while others operate in a continuous setup for incorporation into N U R B S based model ing systems. 3.1.1 Discrete Methods Wang and Tang [41] increase the developability of a mesh surface by min -imiz ing its Gaussian curvature. Us ing a penalty based function, they solve a global constrained opt imizat ion problem that accounts for Gaussian cur-vature, the amount of deformation, and continuity between patches. Since solving the global opt imizat ion may be slow, they addi t ional ly formulate an iterative local opt imizat ion scheme. The authors note that if a high degree of developability is required, large discrepancies result on the final surface. Since the surface normals are not constrained i n the opt imizat ion, these discrepancies are often manifested as wrinkles, a possibly undesirable 12 Chapter 3. Related Work effect. Simi lar to W a n g and Tang [41], Frey [18] also attempts to increase the developabili ty of a mesh by min imiz ing its Gaussian curvature. Frey at-tempts to introduce singular vertices into a 2.5D developable t r iangulat ion in order to model buckled developable surfaces. E a c h singular vertex is it-eratively moved i n the z direction unt i l the sum of angles around the vertex equals 27T. L i k e many others, Frey translates the property of a developable surface having zero Gaussian curvature everywhere into a requirement that the sum of angles around each vertex equals 2ir. Decaudin et a l . [15] describe a system for designing v i r t ua l garments where a user first constructs a non-developable garment that is segmented into overlapping mesh patches. For each mesh patch, the local ly best approx-imat ing developable surface is computed and the mesh is deformed towards this surface. A s evident in Figure 3.1, the resulting surfaces are "more" developable in the sense that their Gauss map covers less area. (a) Typical Input (b) Approximation (c) Gauss M a p of (d) Gauss M a p of Output 3.1(a) 3.1(b) Figure 3.1: V i r t u a l garments [15]. In their conical meshes paper, L i u et al. [25] address approximat ion in the context of architectural design. Given a quadri lateral t i l i ng of an input model , the method iteratively perturbs vertices to create a t i l i ng w i t h planar faces and the same connectivity as the input. Al te rna t ing the per tubat ion w i t h subdivis ion induces a method for modeling developable strips. 13 Chapter 3. Related Work 3.1.2 Continuous Methods P o t t m a n n and Wal lner [30] approximate an input N U R B S surface w i t h cer-tain types of developable N U R B S surfaces. The i r technique finds a devel-opable surface that approximates a set of tangent planes.sampled from the input surface. The fidelity of the approximation is defined in terms of a distance metric defined between planes. T h i s distance metric is opt imized to construct the approximating developable surface. Chen et a l . [12] focus on approximating ship hulls. T h e y in i t i a l ly seg-ment the input surface using a region growing approach and each segment is approximated ind iv idua l ly by a cone or cylinder of revolution. These pieces can then be joined together w i th Gl continuti ty using [24], or a Gr (r > 2) approximating developable can be found using [30]. Wang et al . [39] increase the developability of a t r immed N U R B S surface by min imiz ing its Gaussian curvature. Analagous to their approach for 3D meshes described in [41], the opt imizat ion function accounts for both the overall Gaussian curvature and the amount of deformation. T h e opt imiza-t ion process adjusts the positions and weights of the control points of the original t r immed surface. The authors note that the running t ime may be significant and that the Gaussian curvature may actually increase locally. , 3.1.3 Benefits and Limitations of Approximation M o d e l i n g developable surfaces through approximation is attractive as de-signers do not have to concern themselves w i t h developabili ty constraints .during the modeling process. Ideally, they can freely ut i l ize a l l sorts of modeling tools (e.g., blends, fillets) and then rely on an approximat ion algo-r i t hm to yield a developable result. In practice though, the approximat ion approach is highly restricted since the methods can only succeed if the orig-inal input surfaces already have fairly smal l Gaussian curvature. Moreover, i n most cases the final result is not analyt ical ly developable. W h i l e this is not a problem for applications such as texture-mapping, it can be problem-atic for manufacturing, where the surfaces need to be realised from planar patterns (e.g., sewing). In these setups the distort ion caused by using un-14 Chapter 3. Related Work folded patterns from approximate developables can be quite significant, as demonstrated in Figure 3.2. In this example from [20], the horse model was segmented into nearly developable charts unfolded into the plane w i t h I? stretch of less than 1.01 [20]. Th i s can be visual ly confirmed by observing that the isolines i n Figure 3.2(a) are perpendicular and define squares of approximately equal area. However, when the patterns created from the unfolding were sewn back together, the resulting toy horse had significantly different proportions from the in i t ia l model (e.g., the front legs). T h o u g h m i -nor surface details are expectedly lost due to the resilience of the fabric and possible sewing and cutt ing errors, a contr ibut ing factor to the discrepancy in proportions is the fact that the charts are not completely developable. (a) (b) Figure 3.2: Artefacts i n using approximate developables [20] for manufac-turing, (a) approximate developable segmentation ( L stretch 1.01); (b) reassembled model . 3.2 Direct Modeling A s opposed to model ing by approximation, another class of techniques d i -rectly model developable surfaces, ensuring that the user has an analyt ica l ly developable surface at a l l times. Mos t existing methods for model ing devel-opable surfaces consider only torsal developable surfaces, surfaces whose normal map is a single curve, and are restricted to model ing four sided 15 Chapter 3. Related Work patches. In the continuous setup, these surfaces are often represented us-ing ruled Bezier or B-Spl ine patches and developabili ty is enforced using non-linear constraints [4, 5, 13]. A u m a n n [4] proposes a general condit ion required for a developable Bezier surface to interpolate two given Bezier curves. To compute such a Bezier surface, the presented method restricts the input boundary curves to lie in parallel planes. T h i s requirement greatly simplifies the non-linear system of equations, though at the expense of the model ing capabi l i ty of the developable patches. C h u and Sequin [13] derive Aumann ' s developability condi t ion [4] geo-metr ical ly from the de Casteljau algori thm. Th i s formulation permits them to work wi th boundary Bezier curves ly ing i n non-parallel control planes. In their method, given one freely specified boundary curve, the second bound-ary curve has five available degrees of freedom. In a later work, A u m a n n [5] extends the de Castel jau style approach of [13] by increasing the number of available design parameters using degree elevation. T h e resulting algori thm generates a developable Bezier surface interpolating two given Bezier curves of arbi trary degree and shape. A common requirement of these continuous methods is that users must clearly specify rul ing directions for the final surface. T h i s type of interaction assumes that users have sufficient geometric knowledge to know what ru l ing directions actual ly are, preventing these methods from being adopted by non-experts. Wang and Tang [40] use a discrete setup for model ing torsal developable surfaces. T h e input to their method is two polyline directrices for the rul ing and the output is a developable triangle strip where each interior edge ap-proximates a rul ing connecting the two directrices (Figure 3.3). T h e y cast the problem as a Dijkstra 's shortest path search [14] on a weighted solution graph whose vertices represent potential edges i n the final t r iangulat ion. The shortest path corresponds to the op t imal t r iangulat ion. Different op-t imiza t ion objectives, such as min imal area or max ima l convexity, can be realized by varying the weights used in the solution graph. Po t tmann and Wallner [31] use a dual space approach to define a plane-16 Chapter 3. Related Work (a) Polyl ine Directrices (b) Torsal Boundary Triangulation Figure 3.3: Torsal boundary tr iangulation interpolat ing polyl ine directr i -ces [40]. based control interface for modeling developable patches. Con t ro l l ing such an interface requires significant geometric expertise. For garment design, a highly time consuming approach presented by some commercial modeling tools [10, 27] is to first design a planar pattern for the surface and then deform it into the desired shape using bending and physical s imulat ion. Since designing sewing patterns is a challenging task, this approach is l imi ted to the realm of expert users. B o and W a n g [8] introduce a modeling system for developable surfaces w i t h an emphasis on paper bending. The system utilizes the relationship between a torsal developable surface and a geodesic curve l y ing on that surface. Users isometrically manipulate a smooth 3D curve representing a geodesic and the system finds the unique torsal developable surface con-ta ining the user's curve. T h e input curve is reparameterized numerical ly at each t ime step to ensure an isometric deformation. Though composite de-velopable surfaces are supported by the system, users must manual ly specify each ind iv idua l torsal piece wi th a separate geodesic curve. Frey [17] describes a method for computing discrete height-field devel-opable surfaces that interpolate a given polyline (Figure 3.4). G i v e n a user-provided projection plane, the method first computes a l l of the possible interior edges in the polygon formed by projecting the polyl ine to the plane. It then classifies edges in terms of their l ikel ihood of being part of a de-velopable surface, g iving a higher priori ty to local ly convex edges. F ina l ly , 17 Chapter 3. Related Work i t selects a subset of the edges that forms a val id t r iangulat ion by simu-lat ing the bending caused by closing a blankholder. A blankholder is the component of a press machine that holds the punch surface, the surface that is pressed over an in i t ia l ly flat sheet (the blank) to cause the blank to bend. T h i s a lgori thm operates under the assumption that the projection to the plane of the desired tr iangulat ion contains no self intersections, re-s tr ic t ing the method to height field (2.5D) surfaces. W h i l e the method is well suited for predict ing the bending of a metal sheet under the closing of a blankholder, using the technique for modeling developable surfaces is difficult since the only available control over the final surface is the user's choice of projection direction. Figure 3.4: Mode l ing height field developable surfaces [17]. T h e following chapter introduces a novel a lgor i thm to compute a de-velopable boundary tr iangulat ion interpolating an arbi t rary smooth input boundary. 18 Chapter 4 Constructing Developable Triangulations A s mentioned in Section 1.3, developable surfaces are difficult to model . Chapter 3 pointed out that approximation techniques may admit too much "distortion to be pract ical for manufacturing setups. Direct model ing ap-proaches, though guaranteeing analyt ical ly developable surfaces, are often difficult to control and require users to have significant geometric expertise. Addi t iona l ly , most direct modeling approaches are l imi ted to only model-ing torsal developable surfaces. In order to model composite developable surfaces w i t h these approaches, users must manual ly segment their desired composite surface into ind iv idua l torsal pieces, a non-intuit ive operation. T h i s chapter describes an algori thm for computing a developable bound-ary t r iangulat ion interpolat ing an input polyl ine. C o m b i n i n g this a lgor i thm w i t h a user interface for specifying 3D curves (Section 4.9) creates an easy-to-use system for modeling developable surfaces. Users s imply specify a closed boundary and the algori thm returns a developable surface w i t h de-sirable surface properties (Section 4.2) that interpolates the boundary. T h e system is easily accessible to non-experts since users are not required to have significant knowledge of geometry or the properties of developable surfaces. T h e algori thm is sufficiently robust and can handle complex boundaries, including boundaries w i th darts (Section 4.5) and tangential discontinuities. The next section introduces the linkage between a developable surface inter-polat ing a boundary curve and the convex hul l of that curve and explains how this can be used as the basis for the algori thm. 19 Chapter 4. Constructing Developable Triangulations 4.1 Developability and Convexity Section 2.4 discussed the potential of boundary triangulations to represent developable surfaces that interpolate a given boundary polyl ine . A s ex-plained, triangulations that approximate smooth developable surfaces have the property that the majori ty of their edges are local ly convex. A gen-eral method for obtaining such triangulations is now described. Section 4.3 refines this method to efficiently search for tr iangulations which satisfy addi t ional requirements. We make the following observation which forms the basis for our method: Since most edges of a desirable triangulation must be locally convex, a natu-ral place to identify developable regions interpolating a boundary polyline is the convex hull of the boundary, where every edge is locally convex. T h i s observation is well motivated by the continuous case where the convex hul l of almost every sufficiently smooth closed space curve consists of planar re-gions and torsal developable surfaces, w i th the torsal developable surfaces interpolat ing parts of the curve [34]. We rely on this observation i n order to significantly narrow the search space when looking for desirable tr iangu-lations. If a smooth space curve lies entirely on its convex hul l (i.e., the curve is convex), the hul l is separated into two developable envelopes [34]. In the discrete case, the convex hul l of a closed polyl ine is a tr iangular mesh containing a subset of the polyline's vertices. If the polyl ine is convex, the hul l is separated into two developable triangulations. These triangulations are the left and right hul l envelopes and are defined w i t h respect to the orientation;of the boundary (Figure 4.1). If the polyl ine is planar, then these envelopes are identical . B y construction, bo th triangulations interpolate the polyl ine. Moreover, as desired, every interior edge in each t r iangulat ion is local ly convex since it is an edge on the convex hul l . If the polyl ine is not convex, it w i l l not separate its convex hul l into two envelopes and a more sophisticated modeling strategy is required. A s mentioned previously, the convex hul l of almost every closed sufficiently smooth space curve consists of planar regions and torsal developable sur-20 Chapter 4. Constructing Developable Triangulations (a) Polyl ine (b) Convex Hul l with (c) Left Envelope (d) Right Envelope Envelopes Figure 4.1: Envelope triangulations for a convex polyl ine. T h e a lgor i thm in Section 4.3 selects (d). faces [34], where each of these torsal developable surfaces interpolates parts of the curve. If a polyline is sampled sufficiently densely from a smooth space curve, its convex hul l w i l l closely approximate the convex hul l of the curve. We observe that the torsal developable surfaces on the hul l of the continuous curve correspond to regions, or charts, of consecutive triangles on the polyline 's hu l l having edges on the polyline (Figure 4.2(b,c,d,e)). Such charts are formally defined as sequences of hul l triangles, such that: 1. each triangle shares at least one edge wi th another triangle in the same chart; 2. each triangle shares at least one edge wi th the input polyl ine; 3. a l l of the triangles are oriented consistently w i t h respect to the poly-line. T h e second requirement implies that charts are separated from each other by interior triangles: triangles of the convex hul l w i th no edges on the polyl ine (shown in brown i n Figure 4.2(b)). The last requirement ensures that the tr iangulat ion constructed by the algori thm is manifold and orientable. Subtracting each chart from the polyline by removing the portions of the polyl ine inside the chart and replacing them wi th the interior boundaries of the chart results i n one or two smaller closed polyl ine subloops (Figure 4.2(c), (d), (e)). If the subloops lie on their convex hulls, their left and right envelopes w i l l provide triangulations, which together w i t h the removed chart 21 Chapter 4. Constructing Developable Triangulations / 1 X (h) (g) Figure 4.2: Ex t r ac t i ng a local ly convex tr iangulat ion: (a) boundary; (b) convex hul l w i t h extracted charts (interior triangle shown in black); (c), (d), (e) ind iv idua l charts and remaining subloops after subtract ion; (f) recursing on the subloop formed by removing the purple chart; (g) result ing t r ian-gulations (the framed tr iangulation is the one returned by the a lgor i thm i n Section 4.3); (h) two of the triangulations created w i t h different chart choices. 22 Chapter 4. Constructing Developable Triangulations w i l l interpolate the original polyline (Figure 4.2(f)). If a subloop does not lie on its convex hul l , we can identify charts on this convex hul l and proceed recursively. B y construction, charts on the subloop hulls w i l l also correspond to torsal developable surfaces interpolating the original polyl ine. It is theoretically possible, though unlikely, for a hu l l to contain no val id charts. In this pathological case, the algori thm treats each hul l triangle as a separate chart. T h e recursion is guaranteed to terminate as the number of polyl ine ver-tices decreases at each i teration and a polyline w i th three vertices always lies on its hul l . In any resultant tr iangulation, the only potential ly non-convex edges w i l l bound adjacent triangles computed at different levels of the re-cursion. A l l other edges are necessarily local ly convex as they originated from wi th in a convex hul l , either that of the original polyl ine or of one of the subloops. A s desired, the number of non-convex edges is very smal l and is related to the boundary complexity and not to the number of boundary vertices. However, as shown in Figure 4.2(g) and (h), the choice of different charts to proceed from leads to drastically different tr iangulations, raising the question of which choice the user would prefer. T h e subsequent sections analyse the desirable shape characteristics of discrete developable surfaces and describe an algori thm which guides the selection to efficiently obtain a good interpolating surface. 4.2 Desirable Triangulation Properties W h e n considering triangulations which approximate a smooth developable surface, we require the majori ty of tr iangulat ion edges to be local ly convex. A n addi t ional constraint, ignored in Section 4.1, is smoothness: requiring the dihedral angles between adjacent triangles to be low. Even w i t h these two restrictions, there may exist mult iple boundary tr iangulations providing a val id solution (see Figure 4.2 (g),(h)), raising the question which of these is expected when a part icular boundary is specified. Clearly, when designing a model ing tool , predictability is a desirable property. H u m a n perception studies indicate that "simplici ty is a principle that guides our perception..." 23 Chapter 4. Constructing Developable Triangulations [6]. T h i s principle is well known in Gestalt theory and is commonly used i n sketch interpretation [21]. In our work, it implies that the surface the user expects is the simplest developable surface fi t t ing a given boundary. Based on numerous examples, we hypothesize that a surface is considered simpler and hence more predictable if its normal map has fewer branches, or equivalently, i f its directr ix has fewer discontinuities. In addi t ion to predictabili ty, or instead of it , we can consider the fairness of the created surface. Frey [17] and Wang and Tang [40] describe a large set of measures of surface fairness, including metrics of mean curvature and bending energy. We found that min imiz ing the integral I2 mean-curvature described as the sum of squared dihedral angles across interior edges re-sults i n visual ly fair triangulations. T h e advantage of this metric is that it can be extended to provide a lower bound on the fairness of a boundary tr iangulat ion given only a subset of its triangles (Section 4.4.1). T h e next section presents a pract ical method for comput ing boundary triangulations that satisfy a l l of these requirements, and thus define which developable surfaces to output. 4.3 Branch-and-Bound Search Algor i thm We now extend the basic methodology described in Section 4.1 to search specifically for smooth triangulations and describe a procedure to efficiently navigate the search space to obtain triangulations that are predictable and fair. We observe that for convex polylines, the two hul l envelopes mentioned above are not necessarily the best solutions wi th respect to smoothness (see the pink and blue envelopes at i teration one in Figure 4.4). Therefore, our a lgori thm extracts not only these envelopes, but also the separate charts that are part of the convex hul l . It then proceeds to explore possible interpolat ing triangulations that contain one or more of the identified charts. Fragmenting the envelopes into charts can increase the number of non-convex edges i n the final t r iangulat ion. However, their number remains a function of boundary complexi ty and does not depend on the number of boundary vertices, as 24 Chapter 4. Constructing Developable Triangulations Figure 4.3: P l ana r i t y metric. The second row is a profile view of the first row. A higher value indicates a more planar polyline. T h e completely planar polyl ine in (a) has a value of o o . desired. A s mentioned previously, if the polyline is planar, then the two hul l envelopes are identical . Clearly, if a polyline is planar then any manifold t r iangulat ion of it is developable. To measure the planar i ty of a polyl ine, we fit an orthogonal distance regression plane to it and consider the ratio of the largest and smallest eigenvalues of the covariance ma t r ix [2]. Th i s metric is positive, scale independent, and approaches infinity as the polyl ine becomes more planar. To illustrate, Figure 4.3 shows increasingly non-planar polylines superimposed wi th their regression planes and the values of their corresponding planarity metric. Polylines whose planar i ty metr ic is larger than a user provided threshold (we use 100 ,000 in our examples) are considered planar and triangulated by a single triangle fan. T o prevent this specific choice of t r iangulat ion from influencing the fairness computa t ion (Section 4.2), internal edges of the tr iangulation are marked as having a dihedral angle of zero across their adjacent faces. T o obtain smooth triangulations we require that any interior edge in a chart has a dihedral angle below a specified threshold. Char t s w i t h larger dihedral angles are not considered for future processing. For instance, i n the first i teration of the algori thm in Figure 4.4, this invalidates the light and dark green charts. We also require the angles on edges between any chart and the adjacent interior triangles to lie below the threshold. W e observe that since these edges are on the convex hul l , the dihedral angle between 25 Chapter 4. Constructing Developable Triangulations Iteration 1 / V a l i d alid ..Ik. Nol valid New covers Popped cover and Envelopes remaining subloop Charts Iteration 2 / v a l i d New cover Popped cover and Envelopes remaining subloop Charts Added to queue Redundant Not added to queue Iteration 3 y Popped cover and Envelopes remaining subloop •^al icT New cover Charts Added to queue Iteration 4 Popped cover and E n v e | o p e s remaining subloop Valid " ^ H ^ - New cover Added to queue Triangulation Figure 4.4: A l g o r i t h m stages on a simple example. Interior triangles are shown in black. T h e framed tr iangulation is the output . T h e cover pushed into the queue in i teration four w i l l be discarded at i terat ion five in stage 1 (it is not better than the best tr iangulation). 26 Chapter 4. Constructing Developable Triangulations the chart and any other triangle formed using these edges is bounded from below by the current angle. Charts which violate this property are also eliminated. In the first i teration i n Figure 4.4, this invalidates the orange and dark yellow charts. To reduce the number of non-convex edges and to speed up processing, we only consider charts larger than a certain percentage of the convex hul l area (we use 1% - 3% in our examples). B o t h the angle and size thresholds can be adjusted depending on the input. If both are completely relaxed, our method w i l l find a solution for pract ical ly any input . G i v e n these definitions of val id charts, our a lgori thm computes bound-ary triangulations that are unions of charts and envelopes. T h e a lgor i thm uses a variat ion of the branch-and-bound approach [14], which helps drive the search towards a good solution while avoiding the explorat ion of non-promising ones. Similar to A * search [33], the method uses a pr ior i ty queue of sets of charts, or covers, that interpolate segments of the polyl ine (Figure 4.4). T h e queue is ini t ia l ized w i t h the empty cover. T h e pr ior i ty function of the queue is based on a potential metric (Section 4.4.2) and orders cov-ers such that the next popped cover is expected to lead to an acceptable boundary t r iangulat ion fastest. D u r i n g processing, the method maintains the best boundary tr iangula-t ion found to that point. The quali ty of a t r iangulat ion is measured w i t h respect to the desired tr iangulat ion properties (Section 4.2). T h e same met-ric is used to measure the quali ty of a cover, as a lower bound on the quali ty of any possible t r iangulat ion containing this cover. A t each i terat ion of the a lgori thm the following sequence of operations is performed as visualized i n Figure 4.4. 1. Pop Cover: The algori thm pops a cover C from the pr ior i ty queue, based on the potential metric. If a boundary t r iangulat ion was already found, the method compares the quali ty of the best triangulation-found .to the quali ty of C. If the quali ty of C is worse, it is immediately discarded. Otherwise, the method obtains the set of polyl ine subloops S formed by subtracting (as defined in Section 4.1) the cover charts 27 Chapter 4. Constructing Developable Triangulations from the original boundary and computes their convex hulls. 2. Explore Possible Triangulations: The method checks if the con-vex hulls of each of the subloops are separable into two envelopes. If the envelopes exist for a l l the subloops, then each permutat ion of them combined wi th the cover's triangles defines a t r iangulat ion of the original boundary. Triangulations having interior dihedral angles above the smoothness threshold are discarded. In Figure 4.4, this dis-cards a l l the boundary triangulations in iterations one through three. If there are mult iple possible triangulations satisfying the smoothness constraint, the algori thm selects the highest qual i ty one among them (Section 4.4.1). If this is the first t r iangulat ion found or i f the new tr iangulat ion is better than the best t r iangulat ion found so far, then the best t r iangulat ion is appropriately updated. 3. Form New Covers: The method then extracts val id charts from the convex hulls of a l l the subloops in S. If a chart shares a boundary w i t h the cover C, i t tests i f the dihedral angle across the shared edge satisfies the smoothness threshold. Charts which fail the test are discarded. For each of the remaining charts the method forms a new cover N combining C and the new chart. 4. A d d to Queue: We observe that a subset of a new cover N may already be present in the pr ior i ty queue. In this case, naively adding N to the queue can lead to repeated computations. To avoid this redundancy, the method checks if N contains a cover already in the queue. If this is not the case then ./V is added to the queue. If a subset of N is i n the queue and the quali ty of N is better than that of the subset one, the subset cover is removed from the queue and N is inserted. If it is worse, then N is discarded. In Figure 4.4, i terat ion two, the blue-red cover is discarded since a better subset of it (the purple cover) was added to the queue at i terat ion one, and was not yet processed. 5. Termination: The algori thm terminates if the queue is empty or if 28 Chapter 4. Constructing Developable Triangulations the best computed tr iangulat ion is deemed to be acceptable, using the measures described in Section 4.4.1. Otherwise, the a lgor i thm goes back to Stage 1. A s mentioned previously, the algori thm uses a variat ion of the branch-and-bound approach [14] and operates s imilar ly to A * search [33]. L ike a l l branch-and-bound methods, the algori thm maintains the best solution found so far and uses it as an upper bound against which the current cover is compared. The algori thm is similar to A * in the sense'that it uses a pr ior i ty queue of par t ia l solutions (i.e., covers) and processes them in the order most l ikely to lead to a solution the fastest. However, unlike classical A * , there is no a priori goal state. A s described i n Stage 5, the a lgor i thm only terminates when the queue is empty or if the best solution found so far is acceptable. Addi t iona l ly , to avoid repeated computat ion, the a lgor i thm does not mainta in an explicit closed list of previously processed covers. Rather , as described i n Stage 4, the method avoids repeated computat ion by checking if the current cover entirely contains a cover already in the pr ior i ty queue, and if so appropriately removes one of these. T h e pseudocode for the algori thm is presented in Figure 4.5. 4.4 Metrics 4.4.1 Triangulation Quality W h e n evaluating t r iangulat ion quality, we consider two of the cr i ter ia dis-cussed i n Section 4.2: predictabil i ty and fairness. We do not need to take smoothness into account as the algori thm automatical ly discards non-smooth triangulations. To evaluate predictability, we compute the number of branching points on the surface normal map. In a discrete setup, these correspond to interior triangles in the tr iangulat ion and hence can be eas-i ly counted. Fairness is measured as the sum of squared dihedral angles across interior t r iangulat ion edges. Note that the op t imum is zero for b o t h metrics. In our setup, we consider predictabil i ty as more important than 29 Chapter 4. Constructing Developable Triangulations Input: Polyl ine orig best <- Null ; PriorityQueue pq ; pq. Insert (Em ptyCover); while pq not empty and best not good enough do C <— pq.PopO; if best is better quality than C then continue ; S <— orig.Subtract (C); ComputeConvexHulls(S); . if every subloop € S has envelopes then foreach permutation P of envelopes do if P + C is smooth then if P + C is better quality than best then best <- P + C ; end end end end foreach subloop 6 S do Charts <— ComputeCharts(hull of subloop); foreach chart 6 Charts do N <— chart + C ;' if N is not smooth then continue ; if N D some other cover R 6 pq then if N is better quality than R then pq.Remove(R); pq.Insert(N); end else pq.Insert (N); end end end end return best Figure 4 . 5 : Pseudocode of main loop. Chapter 4. Constructing Developable Triangulations fairness. Thus , to compare two triangulations, we first compare predictabi l -i ty and only if the predictabi l i ty is the same compare fairness. W h e n determining if a t r iangulat ion is acceptable (Stage 5), the two cri ter ia can be compared against lower bounds set by the user. Us ing such lower bounds can speed up the processing, as the a lgori thm w i l l terminate once an acceptable t r iangulat ion is found. 4.4.2 Cover Quality We consider the same two cri teria when evaluating a cover, wherein a cover evaluation aims to provide a lower bound on the quali ty of any tr iangulat ion that contains i t . The lower bound on predictabil i ty measures the min ima l number of interior triangles in any tr iangulat ion containing the cover. To compute this value, we consider the set of subloops S formed by subtract ing the cover charts from the original boundary. We observe that i f a subloop shares edges wi th more than two cover charts, any t r iangulat ion of it w i l l contain at least one interior t r iangle 1 . A subloop which is adjacent to one or two cover charts can potential ly be tr iangulated wi thout any interior triangles. Thus the predictabi l i ty metric of a cover is the number of subloops adjacent to more than two cover charts. To measure the fairness of a cover we first compute the sum of squared dihedral angles wi th in the cover charts and then add to it a lower bound on the sum of angles for the subloops in S computed as follows. If a subloop has two adjacent cover charts, we first fit an orthogonal distance regression plane to the subloop and compute the dihedral angles a i and OLI between the plane and the chart triangles adjacent to the subloop (Figure 4.6). T h e sum of the two angles gives us a lower bound on the sum of angles on any interpolat ing tr iangulat ion of the subloop and between this t r iangulat ion and the adjacent charts. To bound the sum of squared angles, we assume equal dis t r ibut ion on a l l the n — 1 edges involved, where n is the number of vertices on the subloop 2 . Thus for each such subloop we add to the fairness ' T h e triangulation has n — 2 triangles and less than n — 3 edges on the original boundary, where n is the polyline size. Hence at least one triangle has no boundary edges. 2 W e arrive at n — 1 as the number of interior edges in the triangulation n — 3 plus the 31 Chapter 4. Constructing Developable Triangulations (b) Profile of (a) (c) Dihedral Angles Figure 4.6: C o m p u t i n g a lower bound on fairness, (a) A n orthogonal dis-tance regression plane (blue) is fit to the red subloop and normals are cal-culated, (b) Profile view; (c) Nota t ion used for the dihedral angles. metric (a\ + ct2)2/(n — 1). If a subloop has more than two adjacent cover charts, we pick a random pair and do the same computat ion. If a subloop has only one adjacent chart, we return zero as an estimated lower bound for that subloop. A cover and a t r iangulat ion or two covers are compared i n the same way as two triangulations, by first considering predictabi l i ty and then fairness. Since the cover qual i ty is a lower bound, it can be safely used when deciding to discard a cover if it cannot lead to a t r iangulat ion better than the current one (Stage 1). 4.4.3 Cover Potent ia l The purpose of this metric is to prioritize covers based on their potential to be part of the expected final tr iangulation. T h e final t r iangula t ion is expected to have a very small number of interior triangles. Thus a cover is more l ikely to lead to an acceptable tr iangulat ion if it contains a smal l number of charts, where at least one of the charts is quite large. We first order the covers in ascending order based on the number of charts, and then two edges adjacent to the charts. 32 Chapter 4. Constructing Developable Triangulations (a) (b) Figure 4.7: Mode l ing a cone by a boundary w i t h a single dart, in descending order based on the largest consecutive chart area. 4.5 Darts and Mult iple Boundaries Our method is the first to our knowledge to seamlessly handle darts as well as mult iple boundary loops. Darts are duplicate edges on the boundary and are frequently used in design setups such as garment making to intro-duce points or lines of non-zero curvature onto the surface. To il lustrate, Figure 4.7 shows how a cone can be modeled by a boundary w i t h a single dart. The processing of darts is straightforward and requires only minor data-structure modifications to support coincident polyl ine vertices. W h e n processing boundaries w i th mult iple loops the method priorit izes processing of charts which connect separate loops before processing any other chart. If such charts are unavailable, the method connects the loops by the shortest tree of edges, treating those as interior edges for processing purposes. 4.6 Addi t ional Modeling Control The algori thm, as described, returns the best boundary t r iangulat ion com-puted, based on user indicated preferences in terms of qual i ty metrics. Clearly, there might be cases when a user has addi t ional constraints in mind . For instance, for the gazebo in Figure 5.6 we had a par t icular orientat ion in mind . We provide two mechanisms for users to expl ic i t ly control the final surface: specifying rulings and overriding opt imal selection. 33 Chapter 4. Constructing Developable Triangulations 4.6.1 Specifying Rul ings To influence the final surface, users can specify a few of the rulings they expect to see on the result. These rulings are treated as t r iangulat ion edges which are constrained to be part of the final surface. For the purse example (Figure 5.11) we used this option to specify a rul ing to the right of the handle, causing the purse to bulge outwards instead of curv ing inside (Figure 4.8). The specified edges segment the boundary into several separate subloops and the a lgor i thm is run separately on each subloop, considering only the original polyl ine edges as boundary edges for chart extract ion. 4.6.2 Over r id ing O p t i m a l Selection In addi t ion to user drawn rulings, we provide another mechanism for obtain-ing alternative triangulations. Each t ime the a lgor i thm computes a t r iangu-lat ion, it is immediately visualised and stored while the rest of the processing continues. T h e user thus has the option to interrupt the a lgor i thm when they see a t r iangulat ion that they like, and they may also browse a l l the com-puted triangulations at any point during or after processing. T h e gazebo (Figure 5.6) was selected this way. Alternatives found by the method are shown in Figure 4.9. Figure 4.8: Specifying Rulings, (a) Or ig ina l input boundary network; (b) Surface structure of (a); (c) Boundary network and specified rul ing; (d) Surface structure of (c) 34 Chapter 4. Constructing Developable Triangulations Figure 4.9: Al te rna t ive triangulations for the gazebo example (Figure 5.6) found by our method, (a) Or ig ina l input boundary; (b) Solu t ion used to make gazebo; (c), (d), (e) Al ternat ive solutions. 4.7 Runtime The search space for the algori thm is exponential i n the number of charts found. However, using the pr ior i ty queue combined w i t h the potent ial and qual i ty estimations, the method typical ly performs only a smal l number of iterations (less than two thousand for a l l the models shown in Chapter 5). A t each i terat ion the dominant component of the runtime is the convex hul l computat ion, which takes 0(n log n) t ime in the number of vertices on the input boundaries. Thus, in practice, the overall runt ime varies from a few seconds for simple models such as the Opera House (Figure 5.5), to a few minutes for more complex models. We observe that the to ta l runt ime strongly depends on the number of charts formed at each i terat ion, which is direct ly l inked to the complexity of the input boundary rather than to the number of vertices on it. Table 4.1 lists running t ime statistics for sev-eral of the examples presented in Chapter 5. The to ta l t ime is the amount of t ime passed unt i l the pr ior i ty queue of covers is empty, at which point the algori thm terminates since it has exhausted its search space. Since we permit overriding the opt imal selection (Section 4.6.2), we also show the solution t ime which is the amount of time for the a lgor i thm to first ar-rive at the presented surface as a solution. For some of the examples such as the skyscraper roof or the paper lamp leaf, the presented surface was found almost immediately, though the algori thm continued to find alterna-tive solutions unt i l its search space was exhausted. T h e running times were collected on a computer w i th an A M D Opteron 2218 processor and 4 G B of 35 Chapter 4. Constructing Developable Triangulations M o d e l # Vertices Solut ion T i m e (s) To ta l T i m e (s) Skir t (back) 737 17.8 19.9 Skir t (front) 736 31.2 34.7 Tanktop (back) 354 4.2 4.6 Tanktop (front)* 358 38.7 156.8 Opera House 245 2.8 2.8 Skyscraper B o d y 300 + 400 8.9 11.2 Skyscraper R o o f 400 0.9 82.7 Paper L a m p PetaU 509 13.2 243.2 Paper L a m p Leaf* 300 1.4 476.0 Helmet (back middle) 214 3.8 4.0 Helmet (back left/right) 466 4.1 4.3 Helmet (front middle) 310 4.3 9.2 Helmet (front left/right) 835 15.7 17.8 B r o w n Cha i r 244 4.5 5.3 R e d C h a i r 232 1.5 1.6 *1.5% t 2% Table 4.1: R u n n i n g times for the algori thm on several examples. Solut ion t ime is the amount of t ime for the algori thm to first arrive at the presented surface as a solution. Tota l t ime is the amount of t ime passed un t i l the pr ior i ty queue of covers is empty and the algori thm has exhausted its search space. A l l of the examples were run wi th an area threshold of 3%, unless otherwise specified. ma in memory. 4.8 Robustness We observe that the topology of a convex hul l is easily affected by noise in the input polyline. Th i s can drastically affect the a lgor i thm runtime as it leads to chart fragmentation and can sometimes also influence the resulting surface. To ensure a robust convex hul l calculation, the a lgor i thm expects smooth and sufficiently well sampled polylines as input . To further increase the robustness of the hul l calculat ion, the a lgor i thm computes the center of mass C of the polyline boundary and slightly offsets each vertex radial ly from it . Th i s offsetting effectively makes the curve more 36 Chapter 4. Constructing Developable Triangulations " convex". T h i s pre-processing drastically reduces the number of interior t r i -angles on the hul l and improves stability. The offsetting also bends nearly a l l planar portions of the boundary, which would otherwise allow for ambiguous triangulations and possible numerical issues when comput ing the planari ty metric. A d d i t i o n a l offsetting from a sl ightly shifted center is performed in the rare cases where C is in the same plane as part of the boundary. 4.9 User Interface3 The algori thm requires as input a polyline boundary which is assumed to be sampled from an underlying smooth 3D space curve. There are several ways of specifying such a 3D space curve. For example, support for edi t ing N U R B S curves is common in most commercial modeling packages (e.g., [1], [3]). However, to make our modeling metaphor feasible for non-expert users, a fast, sketch-based interface, based on [15], is available. Though easy to use, this interface is sufficiently powerful to generate r ich and complex examples. Indeed, the majori ty of the examples in Chapter 5 were created using this sketch-based interface. In the interface, users can create the 3D boundary curves by first sketch-ing them in one plane and then deforming them from a different viewpoint . Addi t iona l ly , s imilar to [15], the sketching system infers depth information from a single sketch when the polyl ine is drawn over an exist ing model (F ig-ures 4.10). The polyline is then set at a frontal distance to the model that interpolates the two distances at the extremities. T h i s feature is especially useful for our garment examples (Section 5.1), where we drew the desired boundaries on top of a 3D mannequin automatical ly keeping the boundaries at the desired distance from the body. T h e sketching system identifies darts as polyl ine sections that start from a closed boundary loop. W h e n a dart is detected, this section is duplicated and added twice to the parent polyline while its orientation is switched, forming a single closed boundary. Lastly, when the t ip of a dart reaches 3 T h e user interface for specifying boundaries is not a contribution of this thesis and is discussed only for completeness. 37 Chapter 4. Constructing Developable Triangulations (a) User's Sketch (b) Extracted Boundary Figure 4.10: Sketching a shoe overtop of an under lying model of a foot. the same boundary again, the latter is split into two loops, enabling easy generation of a boundary network. Since a user's sketch may have smal l amounts of noise due to j i t te r i n their hands, the interface smooths the sketch strokes by fit t ing a piecewise B-spline curve. T h i s curve is then sufficiently sampled to create a polyl ine that is satisfactory for the algori thm. 4.10 Limitations T h e theoretical setup of our algori thm assumes that the polyl ine boundaries are sampled from a sufficiently smooth curve. A s shown by the examples, the algori thm remains robust even when this is not the case. A s noted earlier, though it is possible that a convex hul l may not contain any va l id charts, such situations are extremely rare. If such a si tuat ion occurs the runt ime is significantly increased, but the method is s t i l l guaranteed to find a solution. We also observe that there may exist smooth developable surfaces where no rul ing of the surface appears on the convex hul l of its boundary. One such example is provided by Wang [42]. Consider a non-intersecting smooth curve C ly ing on the unit sphere centered at origin. C should be sufficiently long so that its convex hul l contains the origin in its interior. A n offset curve C is then constructed by radial ly extruding C inwards towards the origin (Figure 4.11(a)). A developable surface D w i t h boundaries C and C 38 Chapter 4. Constructing Developable Triangulations (a) (b) (c) (d) (e) Figure 4 .11: Boundary i l lustrat ing l imitations, (a) Bounda ry curve defined w i t h its outer por t ion ly ing on the unit sphere centered at the or ig in . T h e inward por t ion is created by extruding the outer por t ion radia l ly towards the origin; (b) A developable surface is defined by connecting correspond-ing points on the outer and inner portions wi th straight lines; (c) T h e de-velopable surface in (b) is entirely contained inside the convex hul l of its boundary. None of the rulings of the surface lie on the convex hul l ; (d) The boundary is split into two parts by specifying a single rul ing; (e) E a c h part how has a convex hul l containing rulings from the surface i n (b). is then defined by connecting together corresponding points on C and C (Figure 4.11(b)). Since a l l rulings pass through the or igin and the origin lies inside the convex hul l , no rulings lie on the convex hul l . Therefore, D is entirely contained inside the convex hul l of its boundary (Figure 4.11(c)). In cases like this, our method w i l l not find the desired developable surface D. However, adding one or two extra rulings (Figure 4.11(d)) would typica l ly break such surface into parts that part ial ly lie on the respective boundary hulls and are thus computable by the method (Figure 4.11(e)). 39 Chapter 5 Results T h i s chapter demonstrates the applicat ion of our method on a variety of inputs coming from different applicat ion areas where developables are used. T h e purple and white coloring of the surfaces shows the surface structure wi th torsal developable surfaces shown in purple and interior triangles, cor-responding to planar transi t ion regions, in white. 5.1 Garments Figures 5.1, 5.2, 5.3, and 5.4 show several garments generated from simple sketches using our system. The modeling of each of the garments took only a few minutes compared to hours using t radi t ional garment model ing tools such as [27] where the user is required to manual ly specify the 2D patterns for the garment. Rea l garments at rest are always piecewise developable since they are assembled from flat fabric pieces. Once worn by a character or a mannequin they stretch slightly due to gravity and collisions. T h e main challenge when modeling garments is obtaining the rest shape and the corresponding 2D patterns. Once these exist, s tandard s imulat ion or procedural techniques can be applied to account for collisions and gravity [1, 15, 27]. In the examples in this thesis, we focused on obtaining the rest shapes. We then used a standard simulat ion tool, Autodesk 3ds M a x w i t h Reactor [1], to visualise the garment behaviour for the poncho, skirt and tanktop, and dress subject to the physical forces involved. A s expected, the results after s imulation appear less stiff but remain very similar to the developable rest shapes. We note that in a l l of the examples the garments are generated using a network of seams. Each ind iv idua l panel surrounded by seams is a developable surface, but the surfaces are not developable across 40 Chapter 5. Results JPh> 13' 13 ' (a) Boundary Net- (b) Composite So- (c) Torsal Solution (d) Rendering of work lution (c) Figure 5.1: Ha t (modeled from six panels) seams. Mos t of the examples in this section uti l ize darts as part of the input polylines which are robustly handled by our method. In most cases, the created surfaces are composite developable surfaces, each containing several torsal developable surfaces connected by transi t ion planar regions. Since the created surfaces are analyt ical ly developable, the patterns (e.g., F igure 5.3(e)) can be used as-is to create reliable real-life replicas of the garments and the garment texture exhibits no distortion. (a) Boundary Network (b) Front Structure (c) Back Structure (d) Simulation Result (e) Front Pattern (f) Back Pattern Figure 5.2: Poncho (modeled from two panels, front and back) 41 Chapter 5. Results (a) Boundary (b) Front (c) Back Struc- (d) Simulation (e) Patterns Network Structure ture Result Figure 5.3: Tanktop (modeled from four panels) and Ski r t (modeled from two panels) (a) Boundary (b) Front Struc- (c) Back Struc- (d) Sim- (e) Patterns Network ture ture ulation Result F igure 5.4: Dress (modeled from seven panels) 42 Chapter 5. Results 5.2 Architecture Figures 5.5, 5.6, and 5.7 show examples of architectural structures generated using our method. T h e Opera House model (Figure 5.5) was inspired by the Sydney Opera House and created by duplicat ing a single developable surface six times at different scales. The boundary for the developable surface was generated using the sketch based system. T h e gazebo (Figure 5.6) is an example of a complex composite surface which cannot be projected to a plane without intersection and hence could not be easily generated by any previous method for modeling developables. It was modeled by sampling a B-spline curve wi th control vertices ly ing on the surface of a cone. T h e skyscraper (Figure 5.7) was created from two surfaces, one for the body of the bui ld ing and one for the roof. The body surface is an example of a mul t i -loop boundary that is easily handled by our method. S imi la r to the gazebo, the roof of the skyscraper is a complex composite developable surface that cannot be projected to a plane without intersection. (a) Boundary (b) Surface Struc- (c) Rendering ture Figure 5.5: Opera House 43 Chapter 5. Results (a) Boundary (b) Surface Structure (c) Rendering Figure 5.6: Gazebo (a) Boundary (b) Surface (c) Rendering Structure Figure 5.7: Skyscraper 44 Chapter 5. Results 5.3 Paper Design Paper and foil are both commonly used materials used i n the design of home artifacts. T h e tul ip lamp modeled from developable petals and leaves (Figure 5.8) is mimick ing Ar t -Nouveau paper lamps. The flower is created by dupl icat ing and scaling a developable petal surface. W h i l e the gold-foil leaves are composite developable surfaces the paper petals are torsal ruled surfaces and thus could be modeled by previous techniques, e.g. [40]. However, i n contrast to these approaches, w i t h our approach the user is not required to specify the rul ing directions or even know what ru l ing directions are, allowing non-experts to use the system. Furthermore, the method, not the user, is able to determine that a single torsal developable surface interpolat ing the boundary exists, a non-tr ivial observation, mak ing the method more attractive for non-experts. (a) Boundaries (b) Surface (c) Rendering Structures Figure 5.8: Tu l i p paper lamp wi th developable paper petals and gold-foil leaves 45 Chapter 5. Results (a) Boundary (b) Smooth Solu- (c) Sharp Angles (d) Rendering of Network tion Solution (c) Figure 5.9: Helmet , (b) Solut ion obtained w i t h a smoothness threshold of 60° ; (c) Solut ion obtained wi th a smoothness threshold of 100° . B y relaxing the smoothness threshold, we create the appearance of metal ridges. 5.4 Leather, Wood Veneer, and Metal Goods Figures 5.9, 5.10, 5.11, 5.12, and 5.13 show a variety of objects designed from flat sheet materials: a metal helmet, chairs, a leather purse, a shoe, and a glove. Despite the complexity of the modeled surfaces, no model ing expertise was required when sketching them using free-form drawing. The examples also show the control mechanisms available to the user, such as the use of rulings to guide the construction of the purse as explained i n Section 4.6.1 and the impact of smoothness threshold i n the helmet example, where we relaxed the threshold to create the appearance of metal ridges. The shoe example (Figure 5.12) was inspired by a pair of actual woman's shoes (Figure 5.12(a)). T h e actual shoes were fabricated wi th a single piece of leather and were developable almost everywhere, the only exception being the t ip where the leather was rounded using a heating process. To model this effect using only developable surfaces, we inserted a rounded dart at the t ip of our boundary (5.12(b)). L ike the garment examples (Section 5.1), a l l of these results are analyt ical ly developable, permi t t ing real life replicas to be manufactured. 46 Chapter 5. Results (a) Boundaries (b) Rendering Figure 5.10: Chairs (a) Boundary Network and (b) Surface Structure of (c) Rendering of (b) Specified Rul ing (a) Figure 5.11: Purse 47 Chapter 5. Results (a) Reference Photo (b) Boundary (c) Surface Struc- (d) Rendering ture Figure 5.12: Shoe (a) Boundary Network (b) Surface Structure (c) Rendering (d) Boundary Network (e) Surface Structure (f) Rendering Figure 5.13: Glove 48 Chapter 6 Summary T h i s thesis presents an algori thm for computing developable surfaces in -terpolating arbi trary 3D polygonal boundaries. Combin ing this a lgor i thm w i t h an interface for edi t ing 3D curves results i n an easy to use system for modeling composite developable surfaces i n which users s imply specify the boundaries of each surface patch. Unl ike many previous approaches for modeling developable surfaces, significant geometric expertise is not pre-requisite, which is an attractive option for non-expert users. However, the method permits user interaction and opt imizat ion of different surface prop-erties, granting more advanced users the abi l i ty to finely control the output surface. T h e algori thm is based on the linkage between between a developable surface interpolat ing a boundary curve and the convex hul l of that curve. The method explores the space of possible interpolating developable surfaces searching for solutions which have a desired set of shape properties. T h e presented approach is fairly generic and can be easily extended to handle addit ional shape metrics. The runtime of the a lgori thm is strongly affected by the complexi ty of the input boundary, and to a lesser degree, the number of vertices on the boundary. In practice, the overall runtime is low, ranging from a few seconds for simple boundaries to a few minutes for more complex boundaries. A s demonstrated by the numerous examples in Chapter 5, the method robustly computes developable surfaces interpolating a vast, array of input boundaries and can be used to model an assortment of developable shapes. Dar ts are direct ly supported by the method, making it especially pract ical for garment design setups. In a l l of the presented examples, since the results are analyt ical ly developable, the flattened 2D patterns are available. T h i s 4 9 Chapter 6. Summary permits real replicas of the shapes to be fabricated. 50 V Chapter 7 Future Work The algori thm presented in Chapter 4 presented smoothness, predictabi l -ity, and fairness as desirable surface characteristics. These characteristics were used to guide the algori thm towards an interpolating surface that op-t imized these traits. However, one could consider alternative properties to optimize for. For example, Wang and Tang [40] identify min ima l surface area, m in ima l bending energy, min ima l mean curvature variat ion, and min i -mal normal variat ion as opt imizat ion objectives. Exp lo r ing these and other surface metrics would permit addi t ional user control and further improve the algori thm. G i v e n a network of boundary curves, the a lgori thm runs separately on each surface patch, returning a developable surface interpolat ing each. The resulting composite developable surface thus has C° cont inui ty across its seam lines and the surface is not developable across seams. However, i n certain designs, higher orders of continuity are required. For example, C 2 continuity is necessary to ensure continuous highlights and reflection lines. One approach to support higher geometric continuity would be to modify the algori thm so that it is globally aware of a l l of the patches, not just local ly aware of its current patch. W h e n in i t ia l ly selecting charts on the convex hul l of a patch, it could favour charts having a corresponding "continuation chart" on the convex hul l of an adjacent patch. A d d i t i o n a l support for singularities would be an interesting endeavour. Though the a lgori thm currently supports darts as a mechanism for intro-ducing singular lines, less restrictive results may be achieved by exploring other types of singularities (e.g., crescent singularities and stretching ridges Fina l ly , formalized user studies i n which individuals are tasked wi th de-[26]). 5 1 Chapter 7. Future Work signing developable objects would be beneficial. In addition to helping iden-tify strong and weak points of the user interface, user studies could possibly provide a notion of the amount of design experience required to use the system. 52 Bibliography Autodesk 3ds M a x . http://www.autodesk.com/3dsmax. Sung Joon A h n . Least Squares Orthogonal Distance Fitting of Curves and Surfaces in Space (Lecture Notes in Computer Science). Springer-Ver lag New York , Inc., Secaucus; N J , U S A , 2004. Autodesk Al iasStud io . http://www.autodesk.com/aliasstudio. Giinter A u m a n n . Interpolation wi th developable Bezier patches. Com-puter Aided Geometric Design, 8(5):409-420, November 1991. Gi in ter A u m a n n . Degree elevation and developable Bezier surfaces. Computer Aided Geometric Design, 21(7):661-670, 2004. John. G . Benjafield. The developmental point of view. A history of psy-chology. Needham Heights, M A : Simon and Schuster Company, 1996. bluffton.edu. http: //www. bluff ton. edu/~sullivanm/ohio/ cleveland/gehry/0067minuslights.jpg. Pengbo B o and Wenping Wang . Geodesic-controlled developable sur-faces for modeling paper bending. Eurographics (Computer Graphics Forum), 26(3), 2007. burdamode.com. http://www.burdamode.com/Free_Downloads, 1333669-1413206-1333668,enEN.html. Cat i a . http://www.3ds.com/products-solutions/plm-solutions/ catia/all-products/domain/Mechanical_Design/product/SMD. 53 Bibliography [11] Jul ie Steele Chalfant. Analys is and design of developable surfaces for shipbui lding. Master ' s thesis, Massachusetts Institute of Technology, June 1997. [12] H . - Y . Chen , I . - K . Lee, Stefan Leopoldseder, Helmut Po t tmann , Thomas Randrup , and Johannes Wallner . O n surface approximat ion using de-velopable surfaces. Graphical Models and Image Processing, 61 (2): 110-124, 1999. [13] Ch ih -Hs ing C h u and Car lo H . Sequin. Developable Bezier patches: properties and design. Computer-Aided Design, 34(7):511-527, 2002. [14] Thomas H . Cormen, Charles E . Leiserson, and R o n a l d L . Rivest . In-troduction to Algorithms. M I T Press, 1990. [15] Ph i l i ppe Decaudin, D a n Julius, Jamie Wi ther , Laurence Boissieux, A l i a Sheffer, and Mar ie-Paule C a n i . V i r t u a l garments: A fully geometric approach for clothing design. Computer Graphics Forum (Proc. Euro-graphics), 25(3):625-634, Sep 2006. [16] Manfredo Perdigao do Carmo. Differential Geometry of Curves and Surfaces. Prent ice-Hal l , 1976. [17] W i l l i a m H . Frey. Boundary triangulations approximat ing developable surfaces that interpolate a closed space curve. International Journal of Foundations of Computer Science, 13:285-302, 2002. [18] W i l l i a m H . Frey. Mode l ing buckled developable surfaces by tr iangula-t ion. Computer-Aided Design, 36(4):299-313, 2004. [19] C a r l Fr iedrich Gauss. Disquisitiones generales circa superficies curvas. C o m m . Soc. Reg. Sc. Got t . R e c , 1828. [20] D a n Jul ius , Vlad i s lav Kraevoy, and A l i a Sheffer. D-charts: Quasi-developable mesh segmentation. Computer Graphics Forum (Proc. Eu-rographics), 24(3):581-590, 2005. 54 Bibliography [21] O lga A . Karpenko and John F . Hughes. Smoothsketch: 3D free-form shapes from complex sketches. In SIGGRAPH '06: ACM SIGGRAPH 2006 Papers, pages 589-598, New York , N Y , U S A , 2006. A C M Press. [22] E r w i n Kreysz ig . Differential Geometry. Dover Publ icat ions , 1991. [23] Steven R . Lay. Convex Sets and their Applications. Wi ley , New York , 1972. [24] Stefan Leopoldseder and Helmut Po t tmann . Approx ima t ion of de-velopable surfaces wi th cone spline surfaces. Computer-aided Design, 30(7):571-582, 1998: [25] Y a n g L i u , Helmut Po t tmann , Johannes Wallner , Yong-L iang Yang , and Wenping Wang . Geometric modeling wi th conical meshes and devel-opable surfaces. In SIGGRAPH '06: ACM SIGGRAPH 2006 Papers, pages 681-689, New York , N Y , U S A , 2006. A C M Press. [26] Alexander Lobkovsky, Sharon Gentges, Hao L i , D a v i d Morse , and T . T . W i t t e n . Scaling properties of stretching ridges in a crumpled elastic sheet. Science, 270(5241):1482-1485, December 1995. [27] Autodesk M a y a C l o t h . h t t p : / / c a a d . a r c h . e t h z . c h / i n f o / m a y a / m a n u a l / M a y a C l o t h . [28] J u n M i t a n i and Hiromasa Suzuki . M a k i n g papercraft toys from meshes using strip-based approximate unfolding. In SIGGRAPH '04: ACM SIGGRAPH 2004 Papers, pages 259-263, New Yor k , N Y , U S A , 2004. A C M Press. [29] M a r t i n Peternell . Developable surface fitting to point clouds. In Com-puter Aided Geometric Design, pages 785-803, 2004. [30] Helmut P o t t m a n n and Johannes Wallner . Approx ima t ion algorithms for developable surfaces. Computer Aided Geometric Design', 16(6):539-556, J u l y 1999. 55 Bibliography [31] Helmut Po t tmann and Johannes Wallner . Computational Line Geom-etry. Springer Verlag, 2001. [32] Kenne th Rose, A l i a Sheffer, Jamie Wi ther , Mar ie -Paule C a n i , and Bor i s Th iber t . Developable surfaces from arbi trary sketched boundaries. Eu-rographics Symposium on Geometry Processing, pages 163 - 172, 2007. [33] Stuart Russell and Peter Norv ig . Artificial Intelligence: A Modern Approach. Prent ice-Hal l , Englewood Cliffs, N J , 2nd edit ion, 2003. [34] Vyacheslav D. Sedykh. Structure of the convex hul l of a space curve. Journal of Mathematical Sciences, 33(4):1140-1153, 1986. [35] Idan Shatz, Ayel le t T a l , and George Leifman. Paper craft models from meshes. The Visual Computer, 22(9- l l ) :825-834, September 2006. [36] Dennis R . Shelden. Digital surface representation and the constructibil-ity of Gehry's architecture. M I T , 2002. [37] M e n g Sun. A technique for constructing developable surfaces. Master ' s thesis, Univers i ty of Toronto, June 1995. [38] synfo.com. h t t p : / / w w w . s y n f o . c o m / t h e y a c h t r e p o r t / a r t i c l e s / E x p l o r e r l . j p g . [39] Char l ie C . L . Wang and K a i Tang. Achiev ing developabili ty of a polyg-onal surface by m i n i m u m deformation: a study of global and local op-t imiza t ion approaches. The Visual Computer, 20(8-9):521-539, 2004. [40] Char l ie C . L . W a n g and K a i Tang. O p t i m a l boundary tr iangulations of an interpolating ruled surface. Journal of Computing and Information Science in Engineering, ASME Transactions, 5(4):291-301, 2005. [41] Char l ie C . L . Wang, Y u Wang, and Ma t thew Yuen . O n increasing the developabili ty of a t r immed nurbs surface. Engineering with Computers, 20(l) :54-64, M a r c h 2004. [42] Wenping Wang . Personal Communica t ion , 2007. 56 Bibliography [43] Hi tosh i Yamauchi , Stefan Gumho ld , Rhaleb Zayer, and Hans-Peter Sei-del. M e s h segmentation driven by gaussian curvature. The Visual Com-puter, 21(8-10):649-658, September 2005. 57
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Modeling developable surfaces from arbitrary boundary...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Modeling developable surfaces from arbitrary boundary curves Rose, Kenneth Lloyd Patrick 2007
pdf
Page Metadata
Item Metadata
Title | Modeling developable surfaces from arbitrary boundary curves |
Creator |
Rose, Kenneth Lloyd Patrick |
Publisher | University of British Columbia |
Date Issued | 2007 |
Description | Developable surfaces are surfaces that can be unfolded into the plane with no distortion. Although ubiquitous in our everyday surroundings, there is currently no easy way to model them on a computer. This thesis fills this void by presenting a general method for creating developable geometry that utilizes the connection between developable surfaces and the convex hulls of their boundaries. Given an arbitrary, user-specified 3D polyline boundary, our system generates a smooth discrete developable surface that interpolates this boundary. We identify desirable properties of such surfaces, present a practical algorithm to compute them, and extend it to handle.darts and internal singular points. We demonstrate the effectiveness of our method through a series of examples, from architectural design to garments, using a sketch-based interface to quickly create the boundaries. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-03-10 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0052002 |
URI | http://hdl.handle.net/2429/32322 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2007-0573.pdf [ 11.61MB ]
- Metadata
- JSON: 831-1.0052002.json
- JSON-LD: 831-1.0052002-ld.json
- RDF/XML (Pretty): 831-1.0052002-rdf.xml
- RDF/JSON: 831-1.0052002-rdf.json
- Turtle: 831-1.0052002-turtle.txt
- N-Triples: 831-1.0052002-rdf-ntriples.txt
- Original Record: 831-1.0052002-source.json
- Full Text
- 831-1.0052002-fulltext.txt
- Citation
- 831-1.0052002.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.831.1-0052002/manifest