Subdivision Models In A Freeform Sketching System
Subdivision Models in a Freeform Sketching SystemWai Kit Addy NganAdvisor: Professor Adam FinkelsteinSecond Reader: Professor David DobkinSubmitted in Partial Fulfillmentof the Requirements of the Degree ofBachelor of Science in EngineeringTo the Department of Computer ScienceofPrinceton UniversityMay 7, 2001
I pledge my honor that this thesis represents my own work in accordance with Princeton University �——————–
Dedicated to my loving mum, dad and brother.
AbstractThis thesis presents the usage of subdivision models in our 3D sketching system. Subdivision surfaces are extremely suitable for our system because of its support for arbitrarytopology, its natural smoothing through refinement, its ability to model creases and corners,etc. We give a brief presentation of some important properties of subdivision surfaces, beforedescribing the Freeform Sketch system. Freeform Sketch is a direct modeling system we develop that utilize gestural input for both modeling commands and geometric descriptions. Itis part of an effort to greatly simplify the modeling process, by sacrificing some precise control on the surface. However, with a support of some basic primitives, in addition to editingtools including oversketching, trimming and joining, the class of shapes we are able to modelexceed that of previous work, with higher quality. One main focus of the thesis is on the trimming operation, which is non-trivial for subdivision surface. We propose an algorithm thatsupport approximate trimming through remeshing and fitting, while adding no extra details tothe surface.
AcknowledgementFirst, I would like to thank Professor Adam Finkelstein for being my thesis advisor and forall of his help and support over the year. Also I would like to thank Professor David Dobkinfor being my second reader. I want to thank Lee Markosian for getting me excited aboutthis project, giving me valuable guidance all the way along, and teaching me everything fromcomputer graphics to coding skills. And thanks go to Lena Petrovic, my graduate studentpartner, for all her hard work and help. I would also like to take this chance to thank ProfessorThomas Funkhouser, whom I worked with throughtout my junior year and the followingsummer, for all of his excellent ideas and advices, and for all the meetings we had that wentover 6 o’clock in the evening.Of course, this work would not be possible without the support of my best friends, YeeWai, Irene and Kueh, for always coming to the graphics lab to give me company, to assurethat I am not alone. Thanks to long-time graphics lab warrior Matt, for all the good time, goodmusic, and good movie trailers we share in the lab. I want to thank my parents and brother fortheir love and support. Finally I would like to thank Hang Seng Bank (Hong Kong) for thegenerous scholarship over the past four years, without which I would not be able to enjoy themost fruitful and exciting education in Princeton. Thank you all!iv
List of Figures1.1Screen shot from 3ds max 4. [1] . . . . . . . . . . . . . . . . . . . . . . . .21.2Class of shapes modeled in (a)Teddy and (b)SKETCH . . . . . . . . . . . .32.1Subdivision curve. [19, Chapter 2] . . . . . . . . . . . . . . . . . . . . . . .62.2Subdivision Surface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.3Refinement of one triangle by splitting each edge. . . . . . . . . . . . . . . .82.4The neighborhood around a vertex vr of valence n. . . . . . . . . . . . . . .92.5Masks for Loop subdivision. . . . . . . . . . . . . . . . . . . . . . . . . .102.6Masks for creases and corners. [8] . . . . . . . . . . . . . . . . . . . . . . .112.7Geri’s game, depicting models with creases of variable sharpness (Pixar). . .112.8Different triangulations of the same shape give different results after subdivision. [14] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12Ripples on a surface generated by the Loop scheme near a vertex of largevalence. [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .133.1Inflation in Teddy. [10] . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153.2Steps to build a mug with a handle . . . . . . . . . . . . . . . . . . . . . . .162.9v
LIST OF FIGURESvi3.2Steps to build a mug with a handle (2) . . . . . . . . . . . . . . . . . . . . .173.3Pen and tablet input for our system. . . . . . . . . . . . . . . . . . . . . . .193.4Four class of gestures recognized . . . . . . . . . . . . . . . . . . . . . . . .204.1Oversketching curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .234.2Primitive surfaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265.1Result from [11] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .315.2Creating the hole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .325.3Remeshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335.4Edge operations include swap, split and collapse. . . . . . . . . . . . . . . .355.5Edge swap. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .365.6Error angle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .365.7Oversampling effect if no fitting is performed . . . . . . . . . . . . . . . . .385.8Error due to reposition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .395.9Improved approximation with fitting. . . . . . . . . . . . . . . . . . . . .406.1Models we made in Freeform Sketch (1). . . . . . . . . . . . . . . . . . . .436.2Trimming of a surface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .446.3A face built using trim and join on a tube. . . . . . . . . . . . . . . . . . . .447.1Bumps after remeshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46
52.1Subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52.1.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52.1.2Basic Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62.1.3Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.1.4Creases and Corners . . . . . . . . . . . . . . . . . . . . . . . . . .102.1.5Dependency on triangulations . . . . . . . . . . . . . . . . . . . . .123Modeling by Sketching143.1An Illustrated Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153.2Gestural Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .183.3Primitive Shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20vii
CONTENTS43.4Trim and Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203.5Oversketching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203.6Dependency Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21Primitives224.1Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .224.1.1Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .224.1.2Oversketching . . . . . . . . . . . . . . . . . . . . . . . . . . . . .234.1.3Issues on resolution . . . . . . . . . . . . . . . . . . . . . . . . . . .24Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .254.25viiiTrimming and Joining285.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .285.2Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .305.2.1Trimming Subdivision Surfaces - Litke et al. . . . . . . . . . . . . .305.2.2Approximate Boolean operations - Kristjansson et al. . . . . . . . . .315.3Creating the hole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .325.4Remeshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335.4.1Repositioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .345.4.2Modify Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . .345.5Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .375.6Alternatives to fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41
CONTENTS5.7Joining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .ix416Results427Discussion and Conclusion45A Mathematical Properties of Subdivision Surfaces48
Chapter 1Introduction3D modeling has always been important in computer graphics and CAGD1 . Animation, rendering, physical simulation, mechanical and architectural designs are all heavily dependenton the ability of modeling shapes in 3D. Well-known representations for 3D models includepolygonal meshes, patches(commonly NURBS2 patches), quadrics, implicit surfaces, andother variations. While these techniques have been developed extensively in the past fewdecades and commonly adopted in different disciplines, they all have some notable shortcomings. For example, polygonal meshes have limited resolution and a large number of polygonsare required to represent smooth surfaces; representations using patches require special handling along boundaries of the patches to enforce continuity; and local editing is hard forimplicit surfaces. On the other hand, the comparably new techniques of subdivision surfaces,combining the strength of polygonal and patch representation, have started to get wide attention in the past few years and have become the newest feature in commercial packages. 3However, previous work on subdivision surfaces has primarily focused on specifying subdivision rules and analysis of their properties, provided with a control mesh. For example, Hoppeet al. presented work on fitting subdivision surfaces to pre-existing sampled data points [8].However, not much work has been done for building subdivision surfaces from scratch. In3ds max 4, for example, subdivision is supported primarily as a finishing tool that provides1Computer Assisted Geometric DesignNon-Uniform Rational B-spline3Subdivision surfaces are supported in 3ds max 4 and Maya 3 Unlimited.21
CHAPTER 1. INTRODUCTION2smoothing and details addition, rather than as a modeling tool. Indeed, the user is requiredto put considerations on the triangulations of the mesh to ensure subdivision can give a niceresult. This thesis is focused on methods of building up subdivision models, in the context ofour Freeform Sketch system, which is described in the next paragraph. More details on theproperties of subdivision surfaces will be described in Chapter 2.Figure 1.1: Screen shot from 3ds max 4. [1]During the past academic year I have been working on a modeling system named FreeformSketch, with Lee Markosian, Lena Petrovic and Adam Finkelstein. Freeform Sketch has adifferent goal from popular commercial packages like 3ds max, Maya, SoftImage, etc. Thesepackages commonly focus on giving the user ability to precisely manipulate models with maximal flexibility. They often expose the controls of the underlying representations to the userand give a large variety of tools, often with numerous menus, toolboxes and dialog boxes. Onthe favorable side, a very wide range of operations are supported, however, the complicateduser interface (See Figure 1.1) often trade off the ease of use. Users are also required to havesubstantial knowledge about the underlying representation of the 3D models in order to make
CHAPTER 1. INTRODUCTION3good use of the tools. Indeed, even for experts, it is quite a time-consuming and difficult taskto create relatively simple 3D models (e.g.mug,table,teddy bear,etc.) in these packages. Also,a system that supports high accuracy and precise control is only desirable in some applications like CAGD. On the other hand, for the casual users, or for cases when stylish models arepreferred to realistic ones, it is often desirable to be able to sketch models in an imprecise way.More importantly, the ability to do 3D sketching is useful for fast prototyping before usingmore sophisticated tools to build the final refined model. Some representative systems in thisdirection include SKETCH [18] and Teddy [10]. These two systems provide interfaces thatare simple to learn and use by specializing the modeling process for certain kinds of shapes– roundish, teddy-bear-like objects in Teddy; and boxy, geometric objects in SKETCH (Figure 1.2). Using these systems it is indeed surprisingly easy to model relatively sophisticatedshapes, however the classes of shapes for which it is possible (roundish or boxy, respectively)is restricted. Modeling many kinds of free-form shapes in either SKETCH or Teddy wouldbe a challenge.(a)(b)Figure 1.2: Class of shapes modeled in (a)Teddy and (b)SKETCHOur system is aimed at a goal similar to Teddy and SKETCH but with the ability to drawa much larger class of objects. The idea is to retain much of the directness and simplicityof those systems, while leveraging more of the users’ drawing ability. We provide a direct,
CHAPTER 1. INTRODUCTION4gestural interface for modeling. We start by drawing planar and non-planar curves in 3Dusing a technique like the one described by Cohen et al. [4]. These 3D curves can then beused to define a variety of primitives, including ruled surfaces, generalized cylinders, and extruded shapes (See Chapter 4). These shapes can then be further refined by oversketching. Insome respects Freeform Sketch strongly resembles both SKETCH and Teddy, but by adapting and generalizing the methods of those systems, and incorporating a more sophisticatedmodel representation based on subdivision surfaces, Freeform Sketch is targeted to producesignificantly more complex, detailed and compelling models.In our system all curves and surfaces are represented using subdivision techniques, appealing to its various advantages (See Chapter 2) which are especially suitable for our system.For example, subdivision naturally provides smoothing, which is important for sketching aswe often desire a smooth surface that approximates but not interpolates the user input. Also,its support of arbitrary topology is handy for building sophisticated models. For example,a mug with a handle, which has genus one, is already a non-trivial object to be representedby patches or implicit surfaces, while no special handling is required using subdivision surfaces. Last but not least, its multi-resolution representation supports level-of-detail techniquesnaturally, which make our system usable even on low-end computer systems.While I have been involved mainly in the implementation of the system during the pastyear, I have particular interest on the use of subdivision techniques in our system. This thesis is thus centered on how we build up and perform various operations on the subdivisioncurves/surfaces, including redefinition by oversketching, trimming and joining; and the advantages and challenges of using subdivision techniques. We will give a brief introductionto our sketching system in Chapter 3, before we delve into details of our geometric primitives(Chapter 4) and our trimming procedure(Chapter 5). We conclude with the results weobtained, and a discussion of potential future works.
Chapter 2BackgroundAs this thesis is focused on subdivision models, we give a brief qualitative discussion ofsubdivision in this chapter, while leaving some of the important mathematical properties toAppendix A. For more in-depth information on subdivision, see [13, 19, 17, 15].2.1 Subdivision2.1.1 IntroductionRecently, subdivision surfaces have gained wide attention because of its numerous advantagesover other modeling techniques: Arbitrary Topology: A subdivision surface uses a polygonal mesh as the base domain,so it can naturally support surfaces with arbitrary topology. It is not necessary to usetrim curves which is common for NURBS surfaces, and also avoids the cumbersomeboundary constraints of joined patches. Natural Representation: 3D models are usually converted to a polygonal representationbefore rendering and graphics hardware are often optimized for rendering polygons.Subdivision surfaces are represented by polygonal meshes and require no conversion5
CHAPTER 2. BACKGROUND6before rendering. Multiresolution support: Subdivision surfaces are intrinsically associated with multiresolution representation. Multiresolution rendering/editing can be supported by storingdetail vectors on subdivided levels. Scalability: Because of its multiresolution structure, it can readily support adaptiveapproximation depending on available system resources.2.1.2 Basic ConceptIn a brief way, subdivision curve or surface is defined by the limit of recursive refinement ofan initial set of control vertices. Figure 2.1 shows the case for subdivision curve. On the leftwe have 4 control vertices, joined by straight line segments. Next to it is a refined version,with new vertices inserted on each line segments of the previous level, and all vertices arerepositioned with respect to some rules. It is intuitive that if the rules are chosen appropriately,the refinement converges and its limit would be a smooth curve. A subdivision curve is definedto be this smooth limit curve. Indeed, B-spline curves with arbitrary degree can be shown tobe just a special case of subdivision curves, away from the endpoints [2].1Figure 2.1: Subdivision curve. [19, Chapter 2]Similarly, the same notion can be defined for surfaces (Figure 2.2). With a control meshand a set of refinement rules, a subdivision surface is defined to be the limit of recursive refine1For example, a uniform cubic B-spline can be constructed by using the subdivision masks (1,6,1) and (1,1)on even and odd vertices respectively.
CHAPTER 2. BACKGROUND7Figure 2.2: Subdivision Surface.ment on the control mesh. However, it is more involved than the case of curves, because therefinement rules are dependent on the connectivity of the vertices, while for curves the connectivity is always the same (i.e.all vertices have valence2 two). Thus in general, closed-formexpression of subdivision surfaces does not exist. As subdivision curves could be regarded asa subset of subdivision surfaces, we will focus only on surfaces in the remaining sections.2.1.3 PropertiesThere are several different rules that operate on different kind of meshes, including Loop[13],Catmull-Clark[3], Butterfly[6], to name a few.3 In our system we employ the Loop scheme,including the rules for defining creases and corners described in [8] and [15], one of thesimplest scheme defined on triangular meshes and the most commonly used.Before going into the details of the Loop scheme, we should note some of the importantproperties among all the subdivision schemes. Local Support : A certain point on the surface is only affected by vertices in a finiteneighborhood. (e.g.vertices in one-ring4 or two-ring neighborhood) This is desirable asit provides ability for local editing, and it also allows very efficient computation during2Number of neighboring vertices.See [19, Chapter 4] for a more complete classification.4By one-ring neighborhood of a vertex we mean all the vertices that share an edge with the vertex. A two-ringneighborhood is the union of one-ring neighborhoods of all the one-ring neighbor, and so on.3
CHAPTER 2. BACKGROUND8Figure 2.3: Refinement of one triangle by splitting each edge.refinement. Convergence and Smoothness : To be able to define a subdivision surface, the schemeof course need to be converging on arbitrary control meshes. Moreover, it is desirablefor it to converge quickly so that a small number of refinements can approximate thelimit surface with small error bound. Also, the limit surface is piecewise smooth, awayfrom predefined creases(See next section).Now we start our discussion on the Loop scheme on the general setting, ignoring creasesat the moment. The Loop scheme is defined on a triangular mesh and it is an approximatingscheme as the limit surface does not interpolate the control mesh. All vertices wit
Of course, this work would not be possible without the support of my best friends, Yee Wai, Irene and Kueh, for always coming to the graphics lab to give me company, to assure that I am not alone. Thanks to long-time graphics lab warrior Matt, for all the good time, good music, and good movie trailers we share in the lab.
FreeForm vs FreeForm Create 33 Enhanced FreeForm mapping workflow today First, assign your master. Then manually map the master pages to the variable pages. New FreeForm Create file merge workflow Choose your master & variable files. Then delete pages as needed, and drag va
With FreeForm and Enhanced FreeForm you merge a master document with a variable document on a Fiery server. In the FreeForm Create standalone application, you use an intuitive graphic interface to merge a master document with variable elements or add variable elements to an existing file without the need to directly access a Fiery server.
Eden Pines Colony Subdivision #277 Big Pine. Tropical Bay Subdivision #459 Geiger. Boca Chica Ocean Shores Subdivision #29 Key Largo Sexton Cove Estates Subdivision #472 Geiger. Geiger Mobile Homes Subdivision #132 Plantation Key #147 Matecumbe K #282 Big Pine #458 Geiger # 28 Key Largo Culvert Installation #293 Big Pine Weed Barrier
subdivision plat index subdivision name tract volume file # beverly heights 5 21 bley-was heights 1094 20 26, 26b bley-was heights - first addition 1102 20 27, 27b bly - first addition 6 37 bly - north 5 17 bly - town of 5 16, 16b bonanza 1 6, 6b bonanza - bowne addition 1b 4a bonanza - davis subdivision 1224 22 21, 21b bonanza - east 1b 12b bonanza - first addition 1 28, 28b
Shirley, Fundamentals of Computer Graphics Loop Subdivision SIGGRAPH 2000 course notes Subdivision for Modeling and Animation (page 70) Catmull Clark Subdivision "Subdivision Surfaces in Character Animation", DeRose, Kass & Truong, SIGGRAPH 1998 Questions? Justin Legakis Toda
PART 5 SUBDIVISION & DEVELOPMENT 27 . Queenstown Lakes District Council -Proposed District Plan Decisions Version (Apr 2022) 27-1. 27 Subdivision and Development . 27.1 Purpose . Subdivision and the resultant development enables the creation of new housing and land use opportunities, and is a key driver of the District's economy.
Freeform optics have become a popular tool with optical engineers and integrators for imaging and illumination applications. 1-4 These optical surfaces lack radial symmetry and may have complex shapes that solve a variety of optical design problems. However, the availability of freeform optics
On the cover: Lake Shore pool with Ocean Blue G3 fi nish. Contents Your Pool: Shapes and Sizes Rectangle Traditional Freeform Modern Freeform Kidney Spas Tanning Ledges Pool Size Index . Fiberglass Pools Traditional Freeform Latham Grand Bay Isle 14' 6" 29' 10" Depth: 3' to 6' 6" Ships from WV Cambridge 16' 36' Depth: 3' 6" to 7' Ships .
