Augmentation of Coarse Meshes with WrinklesbyRussell GilletteB. Eng, McMaster University, 2013A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2015c© Russell Gillette, 2015AbstractFolds and wrinkles are an important visual cue in the recognition of realisticallydressed characters in virtual environments. Wrinkles must, however, move dynam-ically within the context of an animation to retain much of this realism. Addingwrinkles to real-time cloth visualization proves challenging, as the animations usedin games, pre-render visualization, and other such applications, often have no refer-ence shape, an extremely low triangle count, and poor temporal and spatial coher-ence. I contribute approaches towards the persistence of wrinkles over time, and thecreation and rendering of wrinkle geometry in a real-time context, towards a novelreal-time method for adding believable, dynamic wrinkles to coarse cloth anima-tions. With this method we trace spatially and temporally coherent wrinkle pathsand overcomes the inaccuracies and noise in low-end cloth animation. We employa two stage stretch tensor estimation process, first detecting regions of consistentsurface behaviour, and then using these regions to construct a per-triangle, tempo-rally adaptive reference shape and a stretch tensor based on it. We use this tensor todynamically generate new wrinkle geometry on coarse cloth meshes through use ofthe GPU tessellation unit. Our algorithm produces plausible fine wrinkles on real-world data sets at real-time frame rates, and is suitable for the current generationof consoles and PC graphics cards.iiPrefaceThe ideas and algorithms described in this thesis, unless otherwise stated below,were developed by myself in concert with Craig Peters, and in consultation withDr. Alla Sheffer and Nicholas Vining. They were submitted in the research paper:• R. Gillette, C. Peters, N. Vining, E. Edwards, and A. Sheffer. Real-time dy-namic wrinkling of coarse animated cloth. In Proc. Symposium on ComputerAnimation, SCA ’15, 2015 [15]Figures and text taken from the publication are copyright (c) SCA (Symposiumon Computer Animation) and have been re-used with permission.Chapter 4 describes an algorithm developed by Craig Peters in consultationwith Dr. Alla Sheffer. The text from this chapter appears in the above publicationand has been included here for the sake of completeness.My contributions are found in Chapters 6, 7, and 8. Chapter 6 covers the explo-ration of shape contours of wrinkles, chapter 7 discusses rendering, and Chapter8 describes the considerations for proximity tests on both the CPU and GPU. Thecomparison of tessellation and per fragment rendering approaches, as described inChapter 9, may also be largely attributed to me.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Physical Simulation . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Accelerating Simulation with the GPU . . . . . . . . . . . . . . . 72.3 Data-Driven Approaches . . . . . . . . . . . . . . . . . . . . . . 92.4 Real-Time Cloth and Wrinkle Simulation . . . . . . . . . . . . . 102.5 Offline Wrinkle Augmentation . . . . . . . . . . . . . . . . . . . 112.6 GPU-based Wrinkle Augmentation . . . . . . . . . . . . . . . . . 123 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Compression Field Construction . . . . . . . . . . . . . . . . . . . . 184.1 Compression Pattern Extraction . . . . . . . . . . . . . . . . . . 18iv4.1.1 Triangle Stretch Tensor . . . . . . . . . . . . . . . . . . . 194.1.2 Graph Cut Formulation . . . . . . . . . . . . . . . . . . . 204.2 Local Reference Triangles . . . . . . . . . . . . . . . . . . . . . 225 Wrinkle Path Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . 255.1 Wrinkle Initialization . . . . . . . . . . . . . . . . . . . . . . . . 265.2 Temporal Persistence . . . . . . . . . . . . . . . . . . . . . . . . 275.2.1 Solution 1: Restriction to Edges . . . . . . . . . . . . . . 285.2.2 Solution 2: 3D Projection . . . . . . . . . . . . . . . . . 325.2.3 Merging and Length Update . . . . . . . . . . . . . . . . 336 Wrinkle Shape Parameters . . . . . . . . . . . . . . . . . . . . . . . 376.1 Wrinkle Contour . . . . . . . . . . . . . . . . . . . . . . . . . . 376.2 Path Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 Fast GPU-Based Wrinkle Modeling . . . . . . . . . . . . . . . . . . 437.1 GPU Rendering Pipeline . . . . . . . . . . . . . . . . . . . . . . 447.2 GPU Performance Considerations . . . . . . . . . . . . . . . . . 467.3 Wrinkle Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 487.4 Wrinkle Normals . . . . . . . . . . . . . . . . . . . . . . . . . . 507.5 Blending . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528 Proximity Testing Around Wrinkle Paths . . . . . . . . . . . . . . . 538.1 Necessary Precision . . . . . . . . . . . . . . . . . . . . . . . . . 538.2 Bounds Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 549 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569.1 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579.3 Comparison to Alternative Strategies . . . . . . . . . . . . . . . . 6110 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . 66Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68vList of TablesTable 9.1 Performance statistics for various models processed with ouralgorithm. Lmin computed as percent of character height. Alltimes in milliseconds. . . . . . . . . . . . . . . . . . . . . . . 58viList of FiguresFigure 1.1 Typical example highlighting input mesh coarseness and fin-ished results. . . . . . . . . . . . . . . . . . . . . . . . . . . 2Figure 2.1 (a) Off-line wrinkling of simulated clothing using a user-providedreference shape [43]. (b) Our method adds wrinkles to a coarsecloth mesh typical of real-time applications, where no refer-ence shape exists and where the animation is too coarse tocapture fine intrinsic motion. . . . . . . . . . . . . . . . . . . 6Figure 3.1 Thesis algorithm pipeline and chapter mapping . . . . . . . . 14Figure 3.2 Algorithm components: (a) input animation frames; (b) com-pression(blue)/stretch(red)/neutral(green) labeling; (c) local stretchtensors shown by oriented ellipses; (d) temporally coherentwrinkle paths; (e) final wrinkled cloth rendered at real-timewithout and (f) with texture. . . . . . . . . . . . . . . . . . . 15Figure 3.3 Typical game animation frames with intrinsic deformation (stretch)tensor computed with respect to the first (top) and previous(bottom) frame. The shape of the tensor shows compressionstretch magnitude ratio and color reflects the larger betweenthe eigenvalues (blue for compression, red for stretch). Usingcompression on the top tensor as cue for wrinkling, will gener-ate no wrinkles on the left knee (an inverse reference pose willgenerate no wrinkles on the right). The local tensor (bottom)provides better, but noisy cues. . . . . . . . . . . . . . . . . . 16viiFigure 3.4 On coarse meshes smoothing the piecewise constant tensorfield (left) to generate a piecewise linear one (right) leads toloss of details, such as the compression on the shoulder andacross the chest (left) which are no longer distinguishable onthe right. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16Figure 4.1 Left to right: per-triangle stretch tensor with respect to previ-ous frame (red to blue shows stretch to compression ratio); rawdeformation classification (blue - compression, red - stretch,green - rest ); spatially and temporally coherent classification. 19Figure 4.2 The unary cost functions for label assignment depend on λ˜ iminand λ imax. Left: A(i,C), Right: A(i,R). These eigenvalues mea-sure deformation between two frames, not to the rest frame. . 21Figure 4.3 Evolution of reference triangles (bottom) throughout the ani-mation process. . . . . . . . . . . . . . . . . . . . . . . . . 22Figure 5.1 A single iteration Laplacian smooth over wrinkle paths to re-move sharp changes . . . . . . . . . . . . . . . . . . . . . . 27Figure 5.2 Wrinkle paths generated independently per frame vary signif-icantly in both direction and length as highlighted when ren-dering both current and previous paths (center); our temporallycoherent wrinkle paths change gradually across all modalities(right). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Figure 5.3 Drastic change in wrinkle due to repropagation from seed . . 29Figure 5.4 Recomputation of wrinkle path when wrinkle crosses a vertex 30Figure 5.5 Recomputation of wrinkle path across multiple edges whencrossing a vertex . . . . . . . . . . . . . . . . . . . . . . . . 31viiiFigure 5.6 Methods of projecting points in 3-space back onto the meshsurface. Left Column: navigating the mesh to find the pro-jection of the new first point of the wrinkle. Right Column:Navigating between points until the end of the wrinkle to com-pute all subsequent edge collisions. (a–b): finding the closestpoint between line segments. (c–d): finding intersections withthe plane between start and end points. . . . . . . . . . . . . . 34Figure 5.7 Methods of projecting points in 3-space back onto the meshsurface. Left Column: navigating the mesh to find the pro-jection of the new first point of the wrinkle. Right Column:Navigating between points until the end of the wrinkle to com-pute all subsequent edge collisions. (a–b): finding the edgeintersection as a projection along face normals. (c–d): findingthe edge intersections as a projection along an average normalplane. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Figure 5.8 Discontinuity in the point chosen due to the method of pro-jection can result in terminating the walk along wrinkle pathsearly. (a-c) show how such a situation arises, while (d) resolvesthis problem. . . . . . . . . . . . . . . . . . . . . . . . . . . 36Figure 6.1 Estimation of wrinkle contour used by Rhomer et al.for calcu-lation of height and width values that preserve area . . . . . . 39Figure 6.2 We numerically solve for the height h, knowing the maximalwrinkle width s, and current width L. Since s is defined as themaximal width, we note that h = 0 implies, L = s. . . . . . . . 39Figure 6.3 Wrinkle contour using three quadriatic b-splines . . . . . . . 40Figure 6.4 Cross-section contour possibilities. . . . . . . . . . . . . . . . 41Figure 6.5 Example of each cross-section contour in use. a) quartic b)circular arcs c) sinusoidal d) b-spline . . . . . . . . . . . . . 41ixFigure 7.1 Left to right: wrinkles rendered using only normal maps; tes-sellated wrinkle region; wrinkles rendered using displacement(tesselation); wrinkles rendered using displacement and nor-mal maps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43Figure 7.2 Summary of the rendering pipeline (fixed functionality in yellow) 45Figure 7.3 Wrinkle data is packed in three dynamically sized buffers tominimize data associated with each triangle (uncouple fromproblem size) and to minimize total data transferred over theCPU-GPU bus. Untessellated triangles require 8 bytes each,while tesselated ones require 16. This may feasibly be reduceto 4 and 8 using half-byte types. . . . . . . . . . . . . . . . . 47Figure 7.4 Projection of a point p to the winkle segment vivi+1. . . . . . 48Figure 7.5 Given two wrinkles paths along theie respect z-axes, shownis the signed distance from each wrinkle (orange and blue),and the linear interpolation that would result across a primitive(brown). Wrinkle orientation may result in the overlap of sim-ilarly signed distance values (top), or opposite signed distancevalues (bottom). . . . . . . . . . . . . . . . . . . . . . . . . . 51Figure 7.6 Result without (left) and (with) wrinkle blending. . . . . . . . 52Figure 9.1 Impact of different choices of parameter values τ and Lmin. . . 57Figure 9.2 Left: Artist drawn static texture and our wrinkles without (cen-ter) and with same texture (right). . . . . . . . . . . . . . . . 58Figure 9.3 Use of interpolated normals may introduce artifacts for evenwide wrinkles when reducing tessellation level to reach realtime frame rates. From left to right the tesselation refinementis reduced, and we begin to see inconsistency in the normalsof the highlighted area, resulting from insufficient granularityto determine the contributing wrinkle path. . . . . . . . . . . 59Figure 9.4 For large numbers of small wrinkles, the reduction of tessella-tion level results in visible artifacts well before reaching playableframerates. Three levels of tesselation with corresponding frametimes are shown with normal inconsistencies highlighted in red. 60xFigure 9.5 Fragment shader is not dependent on geometry tessellation forperformance, and offers a stable, mid-level performance ascompared to the range offered by a tessellation solution. . . . 61Figure 9.6 Some wrinkling results: input frames on top, wrinkled below. 63Figure 9.7 Some wrinkling results: input frames on top, wrinkled below. 64Figure 9.8 Some wrinkling results: input frames on top, wrinkled below. 65xiAcknowledgmentsI would like to extend a heart-felt thank you to all the individuals who helped bringthis thesis to fruition.First and foremost, two individuals contributed more to the success of this the-sis than I could ever have wished for. Thank you Craig, for being a great partner,for working through this project with me, and for the invaluable knowledge youbrought, without which this thesis would never be what it is today. Thank you alsoDr. Alla Sheffer, for your immeasurable help and focus. You provided us withexperience, knowledge, and helped to navigate the endless pitfalls that would haveotherwise been our demise.I want to thank everyone in the lab: Mikhail, Nicholas, Essex, and I-Chao, forthe tireless hours of work you put in to help get our paper published.Lastly, I would like to thank Darcy, and again Essex, for always being availableto bounce ideas off of, and further, for always being available to answer questionsor explain concepts. I can’t begin to list all the stuff you taught me, thank you somuch.xiiChapter 1IntroductionWrinkles and folds form at seams, bends, and other regions of cloth where materialhas been pushed or pulled from its original shape. This behaviour provides strongvisual cues towards the recognition of shape and motion in garments, and playsa vital role in the representation of believable cloth in virtual environments suchas film, animation, digital media or games [10]. Wrinkles can be considered finedetails on cloth when compared to general draping movement or the size of thewhole mesh. To capture this level of detail in a physical simulation requires a meshof sufficient resolution to represent the wrinkles, much finer than is required tocapture global draping behaviour. While simulation of large scale motion in cloth isoften feasible in modern real-time applications, the fine resolution and subsequentcomputation required to simulate fine wrinkle details proves prohibitive to real-time applications. Offline computation of wrinkles is often not a suitable solution,as real-time applications may smoothly blend between animations to account foruser input, or else use other dynamically generated content that therefore procludesthe use of precomputed results. We introduce a new method for achieving finedetail wrinkling in real-time on low-resolution cloth animations, targeted towardsgames and virtual environments. An example is shown in Figure 1.1.Cloth animation for games is not typically generated by a pure physics simu-lation; the shape of a garment on a character reacts to player input and is drivenby a combination of coarse simulation, inverse kinematics, and animation blend-ing from multiple sources [29]. Rather than trying to capture fine wrinkling in the1Figure 1.1: Typical example highlighting input mesh coarseness and finishedresults.2simulation, we are motivated by offline approaches for adding wrinkles and foldsto cloth simulation as a post-process [24, 35, 43], as illustrated in Figure 2.1, top.These post-processing methods operate on the key observation that cloth is incom-pressible [21], and that a mesh without sufficient resolution to show wrinkles willappear to visually stretch and compress within a local, temoral window. This de-formation is quantified as compression with respect to a known reference shapefree of deformation in order to determine the amount of material lost due to lackof resolution. A refined, or user generated mesh of sufficiently high resolution toexpress the wrinkles is then mapped to the low resolution input so that areas ofcompression may be deformed to account for lost material by forming wrinklesnormal to the mesh and orthogonal to the direction of compression.Cloth meshes for video games are generated without a meaningful referenceshape against which to measure compression [14]. The animations are non-physical,and thus a single meaningful reference shape free of deformation may not exist.We therefore construct an approximate frame of reference, in the form of a localper-triangle reference shape, which is accurate enough with respect to recently ob-served frames of animation to create temporally plausible wrinkles. This referenceshape is allowed to change and evolve over time as animation is seen by the viewer,and is progressively updated as new frames are processed in response to user inputand intrinsic changes in triangle shape are measured. In each frame, we computethe compression of the current triangle with respect to the per-triangle referenceshape, and use this information to seed and modify wrinkles.Creating wrinkles to resolve the loss of material indicated by our computedlevel of compression requires a mapping of geometry from the coarse input meshto a high resolution counterpart. Performing this mapping on the CPU requiresthe generation or storage, deformation, and transfer to the GPU of high fidelitymeshes. Transfer to the GPU for rendering results in a copy of the high resolutionmesh existing on both the CPU and GPU and may prove a bottleneck for largemeshes. We resolve these situations using an adaptive tesselation scheme on theGPU. The mesh is refined only in areas needing high precision, similar to Rohmeret al. [43], and a high resolution wrinkle mesh exists only on the GPU. In thismanner we have removed the duplicate high resolution and spread computation ofthe refined mesh across the many specialized cores of the GPU.3We directly operate on the piecewise constant tensor data, tracing wrinkle pathsacross areas of high compression in our per-triangle compression field. We updateexisting wrinkle paths by solving for spatially and temporally smooth positions thatare well aligned with the desired fold directions. We smooth our piecewise paths,as splines, on the GPU to provide sub-triangle precision and reduce data trans-fered to the GPU. We use programmable GPU tessellation to selectively refine anddeform the mesh around wrinkle paths: adaptively generating wrinkle geometry.Normals are computed using a modified distance field and weighted by the heightof each contributing wrinkle to allow visually smooth convergence and divergenceof wrinkles, and to avoid discontinuities arising from euclidean distance calcula-tions based on piecewise wrinkle paths. This approach enables the generation ofcloth wrinkles across low-end animations at sustained framerates of 60 frames persecond, making it ideally suited for game environments.Our key technical contributions are three-fold. First, we introduce a method forgenerating a temporally adaptive reference shape for typical video game cloth an-imation sequences, consisting of low-triangle count, hand-animated meshes. Ourapproach makes no assumptions about cloth developability, does not rely on a pa-rameterization of the underlying mesh, has no specific authoring requirements, anddoes not rely on training data sets that require updating for every new garment.Our second contribution is a method for dynamically seeding and evolving wrinklepaths on a coarse cloth mesh following a piecewise constant per-triangle compres-sion field. Finally, we show how to generate and render smooth, plausible wrinklegeometry on cloth in real-time, from piecewise input data, with full use of theGPU shading and tesselation capabilites. This thesis focuses on the generation ofwrinkle paths, and subsequent mesh refinement and rendering of wrinkles in thispipeline.We demonstrate our method on a variety of animated garments taken from real-world video game titles. We validate our approach by comparing it to alternativeapproaches and artist drawn static texture-level folds.4Chapter 2BackgroundSince being posed to the graphics community in works by Weil [52] and Ter-zopoulos et al.[46], the problem of accurately representing and simulating clothhas played a vital role in the modeling of virtual environments for movies, anima-tion, advertisement, and games [9]. Simulation of cloth requires attention to manyimportant concerns, such as the selection of an appropriate physical model and ad-equate handling of collisions; these concerns are outside the scope of this thesis.Our work falls in the category of “wrinkle augmentation” research, which attemptsto refine a coarse cloth simulation with fine details.The application of graphics hardware to problems in computer graphics has adiverse history. Modern increases in hardware capability have allowed for workand problems that were traditionally handled on the CPU to be offloaded to theGPU. In many cases the GPU is not only an extra computation resource, but alsomore efficient at particular tasks. Our work makes heavy use of these capabilitiesin a way not previously explored in research.5(b)(a)Figure 2.1: (a) Off-line wrinkling of simulated clothing using a user-providedreference shape [43]. (b) Our method adds wrinkles to a coarse clothmesh typical of real-time applications, where no reference shape existsand where the animation is too coarse to capture fine intrinsic motion.2.1 Physical SimulationIn mechanics, the bending outwards from a surface caused by compressive forceson a thin material is known as buckling. Buckling occurs when internal forcesare overcome by applied compressive forces to result in a state of disequilibrium[30]. The wrinkling of fabrics is a buckling behaviour heavily dependant on boththe physical properties and geometric structure of the fabric in question[28]. Inwoven textiles, for example, internal sheer of the weave structure may be more orless prevalent as a result of geometric weave strength and material friction betweenfibres [21, 28], and may allow for initial deformation inline with the surface priorto buckling. The physical simulation of cloth attempts to accurately approximatethese properties and structural behaviour by modelling the internal forces they cre-ate [1, 9, 10].The formulation of an accurate model for cloth simulation is difficult, and many6formulations have been given including: non-rigid body dynamics [8, 46], a non-continuum particle model [6, 11], elastic theory [50], and non-linear shell theory[12]. The difficulty arises in part due to solution stiffness and instability [9, 10],and in part due to cloth’s non-linear and often hysteretic (previous-state dependant)behaviour[10, 21]. Cloth strongly resists stretch and compression, while easily suc-cumbing to bending. Typical formulations of this in cloth simulation produce a stiffset of equations due to the strong penalty on stretch and compression that are bothunstable and highly non-linear [9]. Baraff and Witkin [1] account for this stiff-ness, and allow for larger time steps in their solution, through the use of an implicitintegration approach. Choi and Ko [9] build upon this work using a non-linear for-mulation of bending energy, allowing buckling to begin as soon as compression isapplied, which overcomes the “post-buckling instability” of previous work.The problem of buckling has led to novel approaches such as using non-conformalelements to eliminate stretch and compression during simulation [13] and buildingstrain limits directly into a continuum-based deformation model [47]. A more indepth comparison of past approaches may be found in [10, 33].2.2 Accelerating Simulation with the GPUMany aspects of the problem of cloth simulation lend themselves well to efficientimplementation on the GPU due to the separability and disjoint nature of its com-ponent problems. Vasilev et al.[48] use GPU parallelism to compute velocity, nor-mal, and depth maps for an underlying model. Testing for collision with a pointon the cloth is done efficiently in image space by referencing into the texture at thescreen-space coordinates of the cloth and comparing depth with front- and back-rendered depth buffers. Tang et al.[44] offload the full computation of collision tothe GPU, treating the GPU as a series of highly parallelizable data stream proces-sors for the various stages of bounding volume hierarchy tests. Each stream pro-cessor is responsible for one of the underlying functional modules of the algorithmsuch as hierarchy update, bounding volume pairwise tests, and elementary tests.Li et al.[31] formulate the calculation of forces independently for each vertex andperform collision detection with a grid-based spatial subdivision algorithm origi-nally proposed by Zhang et al. [54, 55]. Having posed both calculations as highly7parallelizable problems, they are able to efficiently compute forces, collisions, andresulting vertex positions on the GPU. They use the CPU to compute and correctthe over-stretching that results from their choice of a mass-spring model.Approaches for partial offloading of simulation to the GPU, such as thoseabove, incur readback costs to the CPU, which impact performance. Alternativeapproaches have been suggested which avoid this cost by pushing the completesimulation to the GPU. Green [17] proposes a method based on Verlet integration[22] to simulate cloth in 4 rendering passes without explicitly storing velocities.The constraint pass used for collision detection however, relies on basic shapesand is unable to handle more complicated cases of intersection arising within orbetween geometry. Zeller [53] improves on the collision detection of this approachwith iterative sets of draw calls to evaluate individual springs on each particle andapply collision constraints. Rodriguez et al. [41] extend the range of acceptableinput meshes to other triangulations and quad meshes with the use of a variablenumber of springs per particle and augment the collision detection using a multiple-camera version of the work by Vassilev et al. [48]. Tang et al. [45] propose a morecomplete cloth simulation based on their own previous work [44] and work by Liet al. [31]. They augment their collision handling with the approach given by Brid-son and Anderson [7], solving the major constraint of available GPU memory withdeferred front bounding volumes and a compressed diagonal matrix format. Thisapproach is limited to square or near square cloth meshes, owing to a compressedsystem matrix used to represent the chosen spring model.A more comprehensive approach is proposed by Rodreguez and Susin [40],computing a finite element solution with linear shape functions, rather than the tra-ditional polynomial, used for interpolation between nodes. This approach provesmore suitable for the GPU, but requires factorization of the rotational part of the de-formation gradient to compute the stiffness term for their Lagrangian formulationof forces. They provide an optimal GPU conjugate gradient method for solvingthis system, and use previous approaches for both self and external collision de-tection. This approach provides plausible results, but the many concessions madefor mathematical stability may introduce error, and the total computational load isquite heavy.Simulation of cloth on the GPU remains computationally expensive and suffers8from limitations imposed on the data representation and model complexity. Ourapproach takes advantage of the parallel nature and computational power of theGPU, runs at real-time rates, and does not suffer from restrictions on geometry.2.3 Data-Driven ApproachesData-driven approaches wrinkle cloth meshes with the use of information gainedfrom offline physical simulations. Guan et al. [18] use a database of simulatedfine garments and mannequins of different shape and pose to generate wrinkles fornew shapes and poses. They construct a per triangle solution from linear trans-formations applied to garment and mannequin parametrizations and solve for aconsistent solution using least squares. Kim et al. [26] construct a secondary clothmotion graph that does not explode in size with exploration by collapsing statesof similar trajectories that share primary motion graph state. They efficiently ex-plore the space of possibilities by expanding the collapsed nodes with the largestphysical error between states. Their novel compression scheme greatly reduce thememory footprint of the secondary graph and enables real-time traversal of over33 gigabytes of cloth training data.Zurdo et al. [56] assume downscaled simulations exhibit similar large scaledeformation and dynamic behaviour to their full resolution counterparts. Theycompute a physical simulation on low- as well as high-resolution meshes offlineand preserve a small set of ”example” poses that best capture fine scale wrinkling.They compute correction vectors on given animations using an adapted pose-spacedeformation on edge distances to generate plausible results. Kavan et al. [24] learnregularization terms from input coarse and fine data sets to solve for upsamplingoperators that minimize low frequency differences between the meshes. They makeuse of a smart factorization with the offline computation of harmonic bases forinput meshes to improve the computation of compute upsampling operators by twoorders of magnitude. Wang et al. [51] index wrinkle patterns generated per jointon high resolution simulations of close fitted clothing. Wrinkle meshes for eachjoint are interpolated from the database and merged together to produce impressiveresults. This work is suitable only for tight-fitted clothing where collision andfriction with the body constrain the range of effect for each joint, and does not9support loose clothing such as dresses or skirts.Hahn et al. [20] compute full-space cloth simulations offline, saving a set ofbasis vectors for each cluster of poses generated by a principal component analysisof the results. At run time, they select a relevant subset of the basis vectors ofneighboring nodes in pose space based on similarity to the gradient of the full-spaceequation of motion. From these basis vectors, they can compute the reduced-spacehessian, and gradient, with which points in the animation may be updated. Thisapproach gives impressive wrinkling and torsional folds, but is not fast enoughfor real-time applications; it requires close-fitting clothing rigged to a skeleton, areference shape, and a set of training simulations.The data-driven methods are most suited for wrinkling garment animationswith similar design and motion to the training data. Adding a new piece of agarment typically requires the construction of new training sets. Our frameworkdoes not require training data or a reference shape.2.4 Real-Time Cloth and Wrinkle SimulationReal-time cloth simulation for games typically uses a mass and spring system on acoarse mesh [29], connecting vertices with simple springs designed to apply shear-ing and stretching forces while maintaining garment structure. These mass andspring systems form a series of differential equations that are typically integratedusing a stable integration method, e.g. [49]. A detailed example of a cloth simula-tion in a commercially available video game is discussed by Enqvist [14]. Typicalreal-time cloth simulation is very coarse and crude (e.g. 600 to 800 vertices [51]),and does not address wrinkling or buckling in any part of the simulation.Adding dynamic wrinkles in video games typically favours simple strategies.Oat [37] introduces artist-painted wrinkle normal-maps designed to fade-in and outwithin key areas of the mesh as cloth stretches and compresses. Wrinkle maps areeasy to implement, with wrinkle regions delineated by texture masks, but are staticand cannot simulate dynamic wrinkle evolution or react to movement not antici-pated by the artist. Mu¨ller and Chentanez [35] attach a high-resolution “wrinklemesh” to a coarse cloth simulation and run a static solver in parallel with the mo-tion of the base mesh to animate the fine-grained wrinkles. This approach requires10a reliable reference shape and assumes the coarse cloth motion to be spatially andtemporally smooth, which is rarely the case for game-type cloth animations.2.5 Offline Wrinkle AugmentationWrinkle augmentation research attempts to sidestep the myriad of problems asso-ciated with high resolution physical simulation by adding wrinkling and fine detailto cloth after an initial simulation is complete. Bergou et al. [2] use constrainedLagrangian mechanics to add physically-based details such as wrinkles to an artistanimated thin shell, such as cloth. They define their objective function as a weakformulation of equality (Petrov-Galerkin) between their low resolution input ani-mation and high resolution output. Petrov-Galerkin equality specifies test functionswhich multiply each term and specify the constraints under which equality is sat-isfied. They design normalized, correlated test functions for the two animations,with buckling dictated by the distribution of test functions along the surface. Theyimplement this distribution as the correlation between test functions of either ani-mation to define a low-distortion mapping between the meshes. Re´millard and Kry[39] extend this work to simulate the detailed deformation of a thin shell surface ona deformable solid. They couple a high resolution thin shell to an attached, embed-ded mesh. Local positional constraints force the shell to match the interior surfaceonly at low spatial frequency, thus allowing wrinkles without inhibiting large scaledeformations.Rohmer et al. [42, 43] compute a smooth stretch tensor field between anima-tion frames and a given garment reference shape. A refined mesh is mapped backto the original mesh, and wrinkles are modelled along paths traced through thetensor field on contour lines of high compression. They assume the underlyinganimation to be sufficiently smooth in time and space to result in visually coherentwrinkles. We are inspired by this work in our use of a stretch tensor field on themesh to measure deformation; however we do not assume the existence of a validreference frame nor expect the garment motion to be smooth. In contrast to theseoffline approaches our method is fast enough to provide real-time performance forinteractive applications.112.6 GPU-based Wrinkle AugmentationA common method of avoiding the difficulties and computational overhead of theabove methods is to augment the animation of a coarse cloth mesh with wrinklesafter the fact. Hadap et al. [19] compute the change of area for each triangle in aninput animation with respect to a given rest pose. They note that cloth does notstretch or compress, and use the patterns within these scalar deformation values togive preference between different artist painted wrinkle textures. Loviscach [32]performs all calculation needed to augment a coarse mesh on the GPU, and thusrequires the pre-calculation of adjacency information that is otherwise unavailable.Assuming the first available animation frame to be an undeformed reference shape,it creates a set of local orthogonal basis vectors in both pre- and post- deformationspace, and solves for a tensor matrix minimizing their quadric error. This approxi-mation is not resilient against noise, nor does it necessarily produce a smooth tensorfield. It constructs wrinkles along this field to have constant width, and models thedeformation of the tensors as a sinusoidal height field across the mesh. To pro-duce a smooth field across vertices varying in height and deformation gradient heminimizes the phase errors between adjacent vertices using gradient decent. Lo-viscach does no mesh refinement or deformation, instead using a modified parallaxmapping technique [23] to account for the difference of view perspective. He com-putes per-fragment normals from the height field and surface normals, resulting inperiodic, uniform, aligned wrinkles, often an unrealistic behaviour.Our approach constructs a smooth tensor field, resilient to noise, and does notassume or require any reference shape. Computing high compression paths throughour field allows us to demonstrate wrinkle divergence behaviour that Loviscachdoes not achieve. Our computation of height values is more efficient, being poly-nomic rather than sinusoidal, and by tesselating the underlying mesh we create amore realistic silhouette, and do not need parallax computations.12Chapter 3OverviewThis thesis addresses the temporal coherence of wrinkle paths and the real-timegeneration and rendering of believable wrinkle geometry on top of low-qualityanimations of coarse meshes. In this setup we cannot rely on the surface anima-tion to capture even the coarse intrinsic surface motion reliably per triangle, andhave no expectation that the mesh will exhibit coherent, temporally and spatiallysmooth deformation with respect to some static reference frame [35, 42] (see Fig-ure 3.3, top). Since we focus on believability rather than correctness, we note thathumans largely rely on local movement when predicting wrinkle appearance onsurfaces. Surfaces lacking wrinkles appear plausible as long as the intrinsic geom-etry is largely unchanged, and human observers expect wrinkles to show up whenthe surface visibly contracts and expect these to dissolve when a surface stretchesfollowing contraction. Real-life wrinkles are also persistent - appearing, movingand disappearing gradually. Humans anticipate similar behavior from virtual wrin-kles - expecting them to evolve gradually, and to stay in place in the absence ofunderlying surface motion.Following these observations, our paper is motivated to analyze the local in-trinsic surface deformation of the mesh to predict wrinkle appearance. Since theinput animation is noisy, our paper denoises this data using spatially and tempo-rally local trends and constructs a per-triangle reference shape from which a stretchtensor feild may then be computed. The per-triangle reference shape is smoothlyupdated as new frames are rendered, to provide a temporally smooth tensor feild13Wrinkle Path TracingCompression Feild ConstructionTemporal CoherenceWrinkle Size ComputationDetermining Wrinkle ShapeWrinkle GeometryDistance to Wrinkle Path ComputationGPU TransferCh. 4Normal ConstructionNormal BlendingProximity Testing Around Wrinkle PathsCh. 6Ch. 7Ch. 5CPUGPUOineCh. 8Figure 3.1: Thesis algorithm pipeline and chapter mappingon which to further operate. The relevant sections of the paper have been includedin this thesis, unmodified, as Section 4.We trace wrinkle paths following the stretch component of the stretch tensorfield, orthogonal to the direction of compression, along the surface of the inputgarment (Section 5, Figure 3.2, d). We generate both more, and deeper wrinklesthrough regions of higher compression. The computed stretch tensor feild is con-stant per-triangle, and thus cannot be leveraged to obtain temporally persistent andspatially smooth wrinkles. Due to the coarseness of our meshes, converting it intoa piecewise-linear tensor field by averaging adjacent tensors at mesh vertices andthen using barycentric interpolation (as suggested by [43], for instance) is unde-sireable due to loss of information (Figure 3.4, b). This thesis examines alternativeapproaches towards maintaining temporal persistence of wrinkles in both 3D andconstrained to the 2D mesh surface (Section 5.2). Our final solution constrains thepoints of wrinkle paths to move only along mesh edges, and directly optimizes the14(a) (b)(c) (d)(e) (f )Figure 3.2: Algorithm components: (a) input animation frames; (b) compres-sion(blue)/stretch(red)/neutral(green) labeling; (c) local stretch tensorsshown by oriented ellipses; (d) temporally coherent wrinkle paths; (e)final wrinkled cloth rendered at real-time without and (f) with texture.15Rest PoseFigure 3.3: Typical game animation frames with intrinsic deformation(stretch) tensor computed with respect to the first (top) and previous(bottom) frame. The shape of the tensor shows compression stretchmagnitude ratio and color reflects the larger between the eigenvalues(blue for compression, red for stretch). Using compression on the toptensor as cue for wrinkling, will generate no wrinkles on the left knee(an inverse reference pose will generate no wrinkles on the right). Thelocal tensor (bottom) provides better, but noisy cues.Figure 3.4: On coarse meshes smoothing the piecewise constant tensor field(left) to generate a piecewise linear one (right) leads to loss of details,such as the compression on the shoulder and across the chest (left)which are no longer distinguishable on the right.shape of the individual wrinkle paths, balancing alignment with compression di-rections against spatial and temporal smoothness (Figure 5.2). The ouput wrinklepaths are piecewise-linear and both well-aligned with the compression field andpersistent over time.The construction of wrinkle geometry requires knowledge of the wrinkle height,width, and the contour shape that the wrinkle will exhibit along the previously con-structed wrinkle path. We determine wrinkle width from the compression magni-tude and material properties of the cloth and compute wrinkle height to perserve16the surface area of the input mesh (Section 6). The wrinkle contour is selectedto visually blend smoothly with the surrounding mesh. In order to achieve sub-triangle precision for later calculations, we subdivide our piecewise-linear path bysampling from a spline of the original points. Performing this subdivision on theGPU allows us to minimize data transfer across the CPU-GPU bus (Section 6.2).The real-time nature of our target domain requires careful consideration of theperformance implications of data transfer to the GPU, optimizing data packing andminimizing coupling to mesh size (Section 7.2). Creating wrinkles on the GPUrequires knowledge of both our generated wrinkle paths and the triangles of themesh that each of these paths effects. Accurate computation of mappings betweenwrinkles and triangles is important to minimize both data transfer size and addi-tional work done by the GPU. We consider the trade-offs of accurate computation,with additional CPU workload in Section 8.Since our input meshes are coarse and not capable of capturing wrinkle detail,we use programmable GPU tessellation to selectively refine and deform the mesharound wrinkle paths and adaptively generate wrinkle geometry (Section 7, Figure3.2, e). This is compared to existing methods on the CPU which directly modify theanimated mesh and require either high resolution input meshes or on-the-fly meshrefinement to adequately capture the wrinkle details [35, 43]. We further improverealism through the computation of per fragment normals. Normals are computedusing a modified distance field and weighted by the height of each contributingwrinkle to allow smooth convergence and divergence of wrinkles, and to avoiddiscontinuities arising from euclidean distances from piecewise wrinkle paths. Thiscombined approach towards realism (Figure 3.2, f) enables the generation of clothwrinkles in low-end animations at a sustained framerate of 60 frames per second.17Chapter 4Compression Field ConstructionThe work presented in this section was developed by Craig Peters in consultationwith Alla Sheffer and Nicholas Vining. It has been included without change for thesake of completeness.4.1 Compression Pattern ExtractionThe first step in computing a reliable stretch tensor field suitable for wrinkle trac-ing is to locate the regions on the surface which undergo noticeable compressionor stretch (Figure 4.1). The first indication of such changes occurring is the purelylocal deformation of an individual triangle within any given frame with respect tothe previous frame; we may classify this behaviour as compressing, stretching, orresting. The strongest cue for this classification is given by the stretch tensor ofthe affine transformation between the two triangles (Section 4.1.1); the indicatedamounts of compression and stretch provide a local measurement of surface be-havior. However, while real-life cloth deformation is typically both spatially andtemporally smooth, meshes for video games are typically coarse and the anima-tion may be noisy, with artifacts such as inter-surface penetration and jitter. Onsuch inputs, these raw measurements are an unreliable indicators of global surfacebehavior (Figure 4.1, b). Therefore rather than using the stretch and compres-sion magnitudes directly to classify the current state of the mesh triangles, we usethis data as input to a more sophisticated labeling process which balances these18(b) (c)(a)Figure 4.1: Left to right: per-triangle stretch tensor with respect to previousframe (red to blue shows stretch to compression ratio); raw deformationclassification (blue - compression, red - stretch, green - rest ); spatiallyand temporally coherent classification.measurements against a preference for spatially and temporally continuous labels(Figure 4.1, c).4.1.1 Triangle Stretch TensorGiven a pair of current and reference triangles we measure the stretch and compres-sion of the transformation between them using the stretch tensor from continuummechanics [3]. Given a current triangle with edge vectors (u1 = (v1− v0),u2 =(v2− v0)), and reference edge vectors (u¯1, u¯2), we define the Deformation Gradi-ent as,F = [u1,u2][u¯1, u¯2]−1. (4.1)The stretch tensor is then defined asU =√FT F . (4.2)The matrix U is symmetric positive definite, has eigenvectors pointing in the di-rections of maximal stretch and compression, and has eigenvalues λmax and λminindicating the ratio of current length to rest length for stretch and compression re-spectively. We define and employ λ˜min = 1/λmin through the rest of the paper, aswe find it more natural to work with. λ˜min is 1 when there is no compression, and19grows as the triangle compresses. Similarly, λmax is 1 when there is no stretch, andgrows as the triangle stretches.4.1.2 Graph Cut FormulationWe formulate the problem of triangle labeling using a graph-cut framework. Wesolve for a label l ∈ (C,S,R) per triangle where C indicates compression, S indi-cates stretch, and R indicates a neutral rest state. We construct a graph G = (N,E)in which each node i ∈ N is a tuple ( f , t) where f is a face and t is a time step.Each node has three spatial neighbors (the three adjacent triangles in the mesh attime t) and two temporal ones ( f in frames t−1 and t +1). Triangles along meshboundaries as well as those in the first or last frames have fewer adjacencies.For each node n we compute a unary cost for assigning it a particular label ln,and for each pair of adjacent nodes we define a label-compatibility cost for eachpair of label combinations assigned to them. We then find a labeling that minimizesthe following discrete functional:∑i∈NA(i, li)+ ∑(i, j)∈EB(li, l j) (4.3)where A(i, li) is the cost of assigning the label li to node i, E is the set of edges inG, and B(li, l j) is the binary cost of assigning labels li and l j to nodes i and j.Our unary costs are functions of the stretch tensor magnitudes λ˜ imin and λ imaxover each triangle i (Figure 4.2). The rest label’s cost is designed to be low whenλ˜min and λmax are both near 1, and grow as they move away from 1 and is set usinga symmetric Gaussian function,A(i,R) = 1− e−‖(λ˜ imin−1,λ imax−1)‖21/2σ2 . (4.4)The stretching and compressing costs are defined symmetrically using the auxiliary20λ˜minλmaxCompression Cost0.9 1 1.1 1.2 1.30.90.9511.051.11.151.21.251.3λ˜minλmaxRest Cost 0.9 1 1.1 1.2 1.30.90.9511.051.11.151.21.251.300.20.40.60.81Figure 4.2: The unary cost functions for label assignment depend on λ˜ iminand λ imax. Left: A(i,C), Right: A(i,R). These eigenvalues measuredeformation between two frames, not to the rest frame.function c(a,b):c(a,b) =(H−h)e−(12 (a−b)2)/2σ2 +h, a > bba(H−1)+1, a < b(4.5)H = e−α(a−1), h = e−βaA(i,C) = c(λ˜ imin,λimax) (4.6)A(i,S) = c(λ imax, λ˜imin) (4.7)We empirically set σ = 0.05, α = 9, β = 90. The motivation for this design ofthe cost function is as follows. We want the cost of the compression label to belarge when λ˜ imin ≤ 1, and want it to decrease both when λ˜ imin increases and when itincreasingly dominates λ imax (i.e. when λ˜ imin−λ imax grows). We want a symmetricbehavior for the cost of the stretch label.The goal of the binary term B(li, l j) is to penalize label changes between adja-cent faces. It depends only on the labels and is zero when li is equal to l j, and ispositive otherwise. As we expect the animation to be gradual, triangles should notimmediately transition from compression to stretch without at some point resting;21Figure 4.3: Evolution of reference triangles (bottom) throughout the anima-tion process.we therefore assign a higher cost of 0.4 for assigning C and S labels to adjacent tri-angles and a lower cost of 0.2 for assigning them the R and either C or S labels.Weuse the same costs for both temporal and spatial adjacencies. We solve the labelingproblem using the solver of Boykov, Komolgorov, et al.[4, 5, 27], which efficientlyminimizes Equation 4.3.As designed, the framework can be applied to a frame sequence of any length.In a scenario where an entire coarse animation sequence is available in advance, wecan therefore label it all at once. In a real-time application where the animation ison the fly, we apply this framework using a one-lookahead window: given each newanimation frame we fix the labels for the previously displayed frame and solve theoptimization problem for the current frame, while taking the binary cost across thetemporal edges linking the current frame to the fixed, previous, one into account.For the first frame in the animation this binary cost is treated as zero. This strategyallows for real-time labeling update and is sufficient to overcome temporal noise inall the animations we tested our method on.4.2 Local Reference TrianglesTo generate a stretch tensor that guides our wrinkle formation we require a lo-cal reference shape. Since no such shape is provided a priori we compute one onthe fly as the animation progresses. Intuitively, for a perfect incompressible clothanimation, for each individual triangle in the mesh its most stretched, or largestinstance in the animation sequence provides the ideal reference shape. However,22in real-life data triangles can and do stretch due to noise and animation inaccu-racy. Our on-the-fly rest triangle estimation (Figure 4.3) is designed around theseobservations.In the first frame of the animation, we set the reference triangles to be identicalto the current one, as we have no other sources of information as to the plausiblereference shape of the garment. The reference triangles are then smoothly updatedas more information becomes available, with the update strategy reflecting the tri-angle’s intrinsic motion as reflected by our labeling.If a triangle is labeled as compressed we theoretically could leave its referencetriangle unchanged. However, we anticipate some noise in our reference triangleestimation, and in particular want to avoid it reflecting outlier stretched triangles.Thus we choose to dampen the reference triangle size, relaxing it toward the currentmesh triangles as these undergo compression. In order for our tensor field to remainsmooth and consistent with previous frames, this relaxation must partially preservethe tensor eigenvectors, while smoothly changing the eigenvalues. We thereforedirectly modify the eigenvalues of the stretch tensor, and then solve for referencetriangles that generate the updated stretch tensor, as follows.Let F = AΣBT be the singular value decomposition of the deformation gradient(Equation 4.1) of the transformation from the reference to the current triangle.Then, the stretch tensor U can be written as BΣBT , with the eigenvectors encodedby B and the eigenvalues on the diagonal Σ. We compute new eigenvalues, thatlie closer to one by setting Σ′ = 0.95Σ+ 0.05I, here I is the identity matrix. Weconstruct a new Deformation Gradient F ′ = AΣ′BT and compute the new referencetriangles as[u¯′1, u¯′2] = F′−1[u1,u2] = BΣ′−1AT [u1,u2].We expect a stretching label to reflect a dissolving compressed, or wrinkled,triangle. In this configuration if both eigenvalues of the stretch tensor from thereference to the current triangle are larger than one they indicate a stretch beyondthe current reference triangle. We interpret this configuration as dissolving of pre-viously undetected compression wrinkles. We consequently replace the previousreference triangle with this, new, less compressed one. Since we aim to enrichthe rendered garments, we prefer to err on the side of overestimating the reference23triangle size, thus we use no smoothing or averaging in this scenario.If a triangle is currently labeled as being in a rest state, we leave its refer-ence triangle as is with no adjustment. This choice results in wrinkles that persistunchanged through periods of the animation with little deformation, such as a char-acter holding a fixed pose.24Chapter 5Wrinkle Path TracingThe first step in creating wrinkles is to trace their paths on the mesh surface usingthe stretch tensor computed with respect to the local reference shape. Our com-putation builds on many of the ideas described by Rohmer et al. [43]; however, incontrast to their formulation that assumes that the tensor field is piecewise linearand smooth, we modify the framework to operate directly on a piecewise constantfield. This results in wrinkle paths that are linear across triangle faces and need tobe smoothed prior to rendering (as discussed in Section 6.2). The reason for thechange is illustrated in Figure 3.4. Since the meshes we operate on are exceedinglycoarse, converting the per-triangle tensors into a piecewise linear field (averagingthe tensors at the vertices using tensor arithmetic [43] and then using barycentriccoordinates to define values across triangles) smooths out critical details.Following the logic of [43], a naive approach to wrinkle tracing would be tomaintain a minimal distance between wrinkle paths while following high compres-sion contour lines in the tensor field. This approach, however, fails to approximatethe behaviour of real wrinkles which can merge or move arbitrarily close to eachother. We instead hold distance constraints only on the points of high compressionat which the wrinkles are seeded, allowing for natural wrinkle behaviour. Sinceour tensor field is piecewise constant, the converging and merging behaviour of thewrinkles cannot be handled implicitly by the field. We address the visual continuityof merging and overlapping wrinkles in chapter 7, and our approach to determiningthe proximity between wrinkles in chapter 8.255.1 Wrinkle InitializationWrinkles are traced in areas of high compression and are placed orthogonally to thedirection of maximal compression. At each time step in the animation we seed newwrinkles at random locations within triangles of compression (λ˜ imin) greater thancompression threshold τ . We initialize wrinkle paths from seed points by propa-gating a polyline along the mesh surface orthogonal to the maximal compressiondirection within each triangle, given by the tensor eigenvectors. Propagation ter-minates once the compression magnitude drops below the compression thresholdτ , or if the propagated path intersects another wrinkle path. Wrinkle seeding pro-ceeds per triangle from most compressed to least, holding seed points a minimumwrinkle width distance from previously generated paths. The parameter τ is set toreflect the desired fabric stiffness [43]; the expectation is that thinner fabrics, e.g.silk, will be more sensitive to compression and will also exhibit more and longerfolds than thicker and stiffer materials such as wool or leather [21]. The compu-tation of wrinkle width is further discussed in Section 6, and further discussionregarding proximity computation is found in Section 8.A theoretical possibility is that the stretch tensor may have equal, high com-pression along both directions; this could occur when a surface region contractssimultaneously in all dimensions, in which case the choice of tracing direction isill-posed. We have not encountered such situations in practice and expect them tobe exceedingly rare. We believe that the best solution in this scenario would beto avoid seeding wrinkles in such triangles, and maintaining the previous wrinkledirection if a wrinkle reaches such a triangle during tracing.While real wrinkles lie on the garment surface and hence follow the local cur-vature of this surface, they typically have low curvature in the tangential spaceof the garment. To mimic this behavior and eliminate undesirably sharp changesin wrinkle direction, we apply one iteration of tangential Laplacian smoothing toeach path after tracing it, moving each intersection of a path with the mesh edgesalong this edge toward the shortest geodesic between the adjacent intersections(Figure 5.1).26Figure 5.1: A single iteration Laplacian smooth over wrinkle paths to removesharp changes5.2 Temporal PersistenceReal-life wrinkles are persistent, changing their shape and position gradually overtime. To replicate this behaviour we present three restrictions on generated wrinklepaths across consecutive frames that preventing jarring discontinuity, and alloweasy association between the motion of a wrinkle and the actions of the animation:1. A wrinkle path should not move very far between time steps2. Any change of relative positioning of a wrinkle’s constituent points shouldbe small and in a similar direction to previous changes3. A wrinkle’s direction should be close to orthogonal to the compression ofthe surrounding regionA simple approach to wrinkle propagation is to reseed wrinkles from scratcheach frame. This approach results in flickering due to the changing positions ofseed points, failing to meet the second of our stated criteria. Rohmer et al. [43]extend this approach for wrinkle path updating by moving the wrinkle seed points27Frame i Frame i+1 Frame i+1Figure 5.2: Wrinkle paths generated independently per frame vary signifi-cantly in both direction and length as highlighted when rendering bothcurrent and previous paths (center); our temporally coherent wrinklepaths change gradually across all modalities (right).based on changes in the stretch tensor field. On a piecewise-constant field or even adiverging piecewise-linear field however, using this approach can drastically movethe traced wrinkles following even minor directional changes in the field (Figure5.3). The solution proposed by Rohmer et al. [43] is to restrict the movement ofwrinkle seeds and subsequent propagation to be within a distance of the previ-ous wrinkle. By adjusting existing wrinkles within this corridor to match theirnew eigenvectors, the discontinuity from repropagation within a piecewise field isavoided. For simplicity this approach requires a 2D parametrization, and our prob-lem assumes that one is not given and may not exist. Without this parametrization,the approach proves quite complex; wrinkle point movement needs to be restrictedin 3D, and a means for determining the best distribution of points within the corri-dor to match the tensor field is unclear.Exploration of possible alternative approaches lead us to two solutions thatmeet our restrictions as listed above. We document them in the following sections.5.2.1 Solution 1: Restriction to EdgesWe represent each wrinkle path as a polyline whose vertices lie on the edges ofthe garment mesh. By restricting the movement of wrinkle points to the directionof edges, we simplify the problem of temporal coherence to one dimension and28Figure 5.3: Drastic change in wrinkle due to repropagation from seedrestrict wrinkle point movement to the surface of the mesh. Continuous movementfrom the previous wrinkle location is easily enforced by restricting the distancetravelled along the edge (accounting for the angle between the edge and the wrin-kle). If the adjustment of a point following the direction of an edge crosses a vertexand thus leaves the mesh, the new wrinkle point will require projection to bring itback to the surface. Following projection, new edge intersections for the geometricneighbourhood of the crossed vertex must be computed, and the wrinkle updated.While this approach can be done in a single update pass of a wrinkle, the geometricupdate of a wrinkle’s constituent points with respect to the eigenvectors of adjacentfaces often over-corrects for changes in the compression field to result in unstablepositions (jitter).We frame our problem as an optimization on our three posed criteria at thebeginning of the section. We encode our wrinkle paths as linear combinations of29Figure 5.4: Recomputation of wrinkle path when wrinkle crosses a vertexthe edge end vertices:pi = v1i ti+ v2i (1− ti). (5.1)We optimize the shape of the path balancing three terms: orthogonality to com-pression direction, preservation of relative path vertex positions on the mesh, andwrinkle shape preservation:E = αn−1∑i=1((pi+1− pi) · ei)2+n∑i=1‖ti− t¯i‖2+n∑i=0‖pi− (pi−1+ pi+1)/2− (p¯i− (p¯i−1+ p¯i+1)/2)‖2 (5.2)p−1 ≡ p1, pn+1 ≡ pn−1at endpointswhere p¯i and t¯i encode the absolute and relative positions of the wrinkle controlpoint from the previous frame, and ei is the direction of maximal compression inthe triangle shared by pi and pi+1. The optimization is over just the small numberof ti variables, as we represent pi as a function of ti. Since our computation isdominated by persistence we use a relatively small α = 0.4. Persistence requiresboth position and shape preservation: preserving shape alone allows wrinkles toslide uncontrollably, while preserving positions alone leads to artifacts when theunderlying mesh triangles undergo significant deformation.While the solve constrains the vertices to lie on the straight line defined by theircurrently associated edges, we avoid explicitly constraining ti to the [0,1] interval30Figure 5.5: Recomputation of wrinkle path across multiple edges when cross-ing a vertexas we want to allow wrinkle paths to slide along the mesh. If and when a computedti lands outside the [0,1] interval, we locate the best position for the vertex on themesh as follows, and then update the polyline accordingly. To compute the vertexposition we parameterize the umbrella around the relevant edge endpoint (v1i ifti < 0 and v2i if ti > 1) and place pi using the continuation of the edge projectionusing Equation 5.1 but constraining it to the umbrella triangles. We then computethe geodesic paths from the previous/next vertices (vi−1,vi+1) to the new locationand use the path’s intersections with the mesh edges as new wrinkle path vertices(Figure 5.4).Lastly, if and when more than one wrinkle path vertex lies in the immediatevicinity of a single mesh vertex (ti < 0.1 or ti > 0.9) we use only one of thesevertices in the optimization above and then use mesh geodesics to update the newset of intersection (Figure 5.5). Without this modification, the locations of thevertices become over-constrained as a movement in their individually preferred31directions would lead to path self-intersection.5.2.2 Solution 2: 3D ProjectionRestriction of wrinkle point movement to edges may simplify the problem, but italso restricts movement of wrinkles, creating difficulty maintaining alignment withthe compression field. An alternative formulation of our restrictions on wrinklemovement with less restriction on direction of motion is given below:E = αn−1∑i=1((pi+1− pi) · ei)2+n∑i=1‖pi− p¯i‖2+n∑i=0‖pi− (pi−1+ pi+1)/2− (p¯i− (p¯i−1+ p¯i+1)/2)‖2 (5.3)p−1 ≡ p1, pn+1 ≡ pn−1at endpointsThis formulation restricts wrinkle point movement by displacement distance in3-space rather than along an edge. Since the solution points are not guaranteed tolie on the surface, this approach requires a method to project the points back ontothe surface and compute new edge intersections.We notice that by enforcing temporal coherence we are in fact restricting thespace where the new wrinkle points can move to a local region on the mesh. Wemake use of this spatial locality to quickly locate corresponding points of projec-tion for each point given by our linear solve. Beginning at a known point on thewrinkle of the previous frame, the mesh is traversed in a greedy descent towardsthe first point given by our linear solve, and then between points of the linear solveuntil reaching the end of the wrinkle. Using euclidean distance, we have reacheda vertex when any movement would send us past the closest point on the mesh tothat vertex. Once the first point of the linear solve is reached, our new wrinkle pathis constructed as the list of all subsequent edge crossings. We note that traversingedges of the mesh towards the points of the linear solve is technically susceptible togetting caught in a local minima (and thus not reaching the point). In practise how-ever, since our wrinkles are restricted in movement and have the same resolutionas the mesh, this is extremely unlikely in the time-step of a single frame.32Each step of mesh traversal tests edges of a current triangle against a knownorientation towards a goal to determine which edge to cross, and the location ofcrossing. Selection of an appropriate algorithm proves important under certaintraversal conditions where inconsistency in the edge crossing computed from dif-ferent triangles may prevent reaching solution points given by the linear solve. Ineach of Figures 5.6 and 5.7, we depict the wrinkle from the previous frame as apath in blue, and the solution points from the linear solve as green spheres.An initial approach to the computation of edge crossings uses the point of min-imal euclidean distance on the line of travel, a line segment between a source andtarget, with a given edge (Figure 5.6 top). This approach generates inconsistentcrossing points between adjacent triangles should the solve point lie directly abovean edge (Figure 5.8 (a)). Two subsequent approaches, differing solely on algorithm,find the intersection of a line segment with a plane orthogonal to the incoming face.The first approach uses the plane through the source and target point and the linesegment of the two edge vertices, and the second approach the reverse (Figure 5.6bottom, Figure 5.7 top). In the case of the second approach, the intersection pointmust be projected along the plane back onto the mesh. These approaches rely onthe normal of the incoming face, and thus generate similar inconsistencies to be-fore (Figure 5.8 (b-c)). The solution is to divide space evenly into cells, finding apoint of intersection in a similar manner to last two approaches, but using planesconstructed as the average of the two adjacent-face normals.(Figure 5.7 bottom)Consideration of our two approaches lead us to the choice of solution one. Acomparison of the complexity in implementation is strongly in favor of the firstsolution, which except at vertices is a single dimensional problem. Furthermore,by parametrizing the curve as a combination of the mesh vertices, the problemsize of the linear solve is greatly reduced to the benefit of performance. While theimprovement in adhering to the compression tensor field may allow for smoothertransitions in poor geometry, it is likely that in most cases it would be unnoticeable.5.2.3 Merging and Length UpdateAs a cloth garment deforms, wrinkles both grow and shrink in length, and migrate33(1)(2) (2) (1)(3)(a) (b)(c) (d)Figure 5.6: Methods of projecting points in 3-space back onto the mesh sur-face. Left Column: navigating the mesh to find the projection of the newfirst point of the wrinkle. Right Column: Navigating between pointsuntil the end of the wrinkle to compute all subsequent edge collisions.(a–b): finding the closest point between line segments. (c–d): findingintersections with the plane between start and end points.34(a) (b)(c) (d)Figure 5.7: Methods of projecting points in 3-space back onto the mesh sur-face. Left Column: navigating the mesh to find the projection of the newfirst point of the wrinkle. Right Column: Navigating between pointsuntil the end of the wrinkle to compute all subsequent edge collisions.(a–b): finding the edge intersection as a projection along face normals.(c–d): finding the edge intersections as a projection along an averagenormal plane.35(a) (b)(d)(c)Figure 5.8: Discontinuity in the point chosen due to the method of projectioncan result in terminating the walk along wrinkle paths early. (a-c) showhow such a situation arises, while (d) resolves this problem.along the mesh. We replicate the change in length of wrinkles, for each frame in theanimation, by extending or triming all existing wrinkles based on the magnitude ofthe underlying stretch field, using the same compression threshold τ as above. Tomaintain temporal continuity, we do not change the length of a wrinkle by morethan 15% per frame. Migration or growth may result in wrinkle paths merging,at which point we truncate one path and allow the other to proceed. Computationof the point at which this occurs is covered in Chapter 8. The truncation of wrin-kles both prevents the undesired crossing or passing of wrinkle paths, and reducescomputation regarding the collision and proximity of duplicate paths.36Chapter 6Wrinkle Shape ParametersTo generate actual wrinkle geometry from the traced wrinkle paths, we need to firstassign a target wrinkle height and width to each point along the path. We then refinethe path, smoothly interpolating heights, and generate appropriate cross-sectionalgeometry across it.6.1 Wrinkle ContourOur goal in the computation of wrinkle height and width is to minimize the changein surface area as compared to our temporally adaptive rest pose. Similar to Rohmeret al. [43], we use a formulation that accounts for both material properties and com-pression values along the wrinkle. The more flexible a material is, the higher weintuitively expect the fabric wrinkles to be.Rohmer et al. represent wrinkle shape as a circle contour offset from the sur-face of the mesh. They define the radius of this circle to be a user defined material-minimum radius, scaled proportional to the compression on the mesh. They deter-mine the offset of the circle from the mesh surface to retain an approximate surfacearea as compared to the rest pose (Figure 6.1).We instead numerically pre-compute a set of wrinkle width-height ratios thatexactly preserve a unit arc length on a circle. Given a minimum wrinkle width atrun-time that accounts for material parameters, we scale and interpolate betweenthese values to compute our desired height. We model our wrinkle shape as a37smooth b-spline contour, using the computed width and height to preserve clotharea. This approach is very fast, requiring a constant-time look up and linear-interpolation at run time. It offers precision based on sample size, and provides amore intuitive material parameter of wrinkle width, which compared to radius is avisible property on the surface of the mesh.Pre-computation of height for given wrinkle widths must be independent of theuser run-time-specified minimal wrinkle width Lmin. Since we seek to maintainsurface area, our arc length s = Lmax, where maximal wrinkle width is computedsimply as the arc length of the minimal width, Lmax = piLmin. To construct a look-uptable that is independent of the user specified Lmin, we can assume our input widthL is unit length, and scale all results at run time. We then need only numericallysolve for the ratio L/s. Using standard trigonometry relationships we can derivethe formula for φ as below:sinφ − Lφs= 0 (6.1)We use Newton’s method to pre-compute values of φ for given ratio L/s. SinceL spans [Lmin,Lmax], our sampling domain for this computation is [ 1pi ,1]. Sincethe height along a circular arc is sinusoidal, we space our samples across the inputdomain as a sinusoidal distribution so that our constructed lookup table has an evendistribution of height. This creates a uniform level of precision for all input wrinklewidths.At run time, we look up the index of our desired height through a binary searchof a table of sampling ratios L/Lmax. We interpolate linearly between the twoclosest height values given the height look-up index. We then scale the height bythe current width to get our final result.Our framework also differs from Rohmer et al.’s, in that the compression fieldwe operate on is piecewise constant instead of piecewise linear. Using pointwisemagnitudes on this input results in discontinuous wrinkle dimensions. Instead weuse the maximal compression along a wrinkle path to obtain the maximal wrinkleheight and corresponding width (Figure 6.2; here the width is L and the height ish). We then use these values as wrinkle parameters at its mid-point. At the wrinkleend points we set the width to be equal to the maximal wrinkle width Lmax, andsmoothly interpolate the width along the rest of the wrinkle path. We then use38Figure 6.1: Estimation of wrinkle contour used by Rhomer et al.for calcula-tion of height and width values that preserve areasLħ RhφFigure 6.2: We numerically solve for the height h, knowing the maximalwrinkle width s, and current width L. Since s is defined as the maxi-mal width, we note that h = 0 implies, L = s.39Figure 6.3: Wrinkle contour using three quadriatic b-splinesthese width values to compute pointwise wrinkle height. Note that when the widthis equal to the maximal width (at the end points) the height is, by construction,zero. This computation leads to smooth naturally dissolving wrinkle shapes alongeach path.While the use of circular arcs to represent wrinkles is well suited for wrinkleheight and width estimation, real-life wrinkle profiles, or cross-sections, deviatefrom this shape and smoothly blend with the surrounding surface. We conciselystate these requirements as a set of boundary conditions on the first derivative ofour cross-section function: f ′(±w) = 0∧ f ′(0) = 0. We offer for considerationfour function families that satisfy these conditions: quartic polynomial, piecewisecircular arcs, sinudsoidal, and piecewise b-spline (Figure 6.4). We empiricallyexamine the rate of fall-off, simplicity of representation, and ease of calculation inour selection of a quadratic B-spline for our wrinkle contour.(Figure 6.3).Quartic polynomials and sinusoidal waves are insufficient for our needs dueto their high curvature at the boundary. Figure 6.5 a) and b) show that the highcurvature results in the perception of a discrete transition due to the Mach bandeffect. Approaches to mitigate this effect, such as the addition of Perlin noise areonly partially successful in removing this artifact, are very dependent on wrinklescale in their implementation, and add unwanted computational overhead to theGPU. Piecewise circular arcs and b-splines do not suffer from this effect (Figure 6.5b and d). The b-spline is the conceptually simpler, and more efficient of the twomethods.400-w wh0quarticcircular arcssinusoidalb-splineFigure 6.4: Cross-section contour possibilities.d)c)b)a)Figure 6.5: Example of each cross-section contour in use. a) quartic b) circu-lar arcs c) sinusoidal d) b-spline416.2 Path SmoothingWe smooth out the path of each wrinkle, replacing the linear segments within eachmesh triangle with Bezier paths whose tangents across triangle edges are set to theaverage of the line segment tangents in the adjacent triangles. For efficiency thiscomputation is done on the GPU in parallel per triangle, and each Bezier segmentis discretized using a polyline.42Chapter 7Fast GPU-Based WrinkleModelingEmbedding fine wrinkles in the actual garment mesh requires a very high meshresolution. Storing and rendering such a mesh would significantly slow the anima-tion display and gameplay. We avoid modifying the underlying surface mesh oranimating a finer mesh in parallel by modeling wrinkles, at render-time, directlyon the GPU; specifically, we use the OpenGL tessellation shader to create coarsewrinkle geometry in real time and use the fragment shader to compute per-pixelwrinkle normal maps to increase rendered wrinkle believability. The combinedmethod creates realistic looking wrinkles and is very efficient, allowing on-the-flywrinkle modeling at 60 frames per second, when the rendered characters occupyFigure 7.1: Left to right: wrinkles rendered using only normal maps; tes-sellated wrinkle region; wrinkles rendered using displacement (tessela-tion); wrinkles rendered using displacement and normal maps.43the majority of the screen on a standard computer monitor. While using normalmaps alone is clearly even faster, the results do not appear as realistic as the ren-dered frames lack inter-wrinkle occlusions and characteristic changes in charactercontours (Figure 7.1). Our approach, which leaves the original mesh unchanged,allows for wrinkle rendering to be enabled or disabled as the character moves fur-ther away from the viewer.7.1 GPU Rendering PipelineThis section is a review of the standard GPU pipeline. Readers already familiarwith this content may skip ahead to Section 7.2. More information may be foundin OpenGL or DirectX online resources [25], [34].The GPU processes data in a highly parallel pipeline designed to efficientlyprocess the large amount of geometry that may be present in a scene. Data istransferred from the CPU to the GPU along a data bus of limited bandwidth, andstored in either buffers or textures allocated from global or texture/constant mem-ory. On each render pass, the GPU reads data from user specified buffers, passingthe data through a series of built in operations and compiled shader programs, theshader pipeline, before outputting the data. Each stage of the shader pipeline op-erates on the output of the previous stage, and is designed towards a specific task(Figure 7.2).The vertex shader (VS) is run independently on each set of vertex informationpassed to the GPU and returns a single corresponding set of output data. The tessel-lation control shader (TCS) then specifies subdivision parameters on the geometry,defining for a given input patch the level of subdivision along the outer boundary,and the number of inner subdivision levels to add. The fixed-function tessella-tor generates new vertices for refined primitives from the input geometry and theTCS parameters. Each newly generated vertex is then placed by the tessellationevaluation shader (TES), which has access to the vertex information from whichit was generated. The geometry shader (GS) operates on the subsequently gener-ated primitives with access to the constituent vertex information. These primitivesare then passed through a number of fixed-functionality (immutable) operationsto generate the fragments on which the Fragment Shader (FS) will operate (Fig-44Vertex ShaderTessellation Control ShaderTessellation Evaluation ShaderGeometry ShaderFragment ShaderTessellation Primitive GeneratorPrimitive AssemblyRasterizationVertex Post- ProcessingPixel UpdateTestsWriteMaskingPixelBlendingCompute ShaderFigure 7.2: Summary of the rendering pipeline (fixed functionality in yellow)ure 7.2).Of the fixed function operations, vertex post-processing consists of transform-feedback and clipping. The transform feedback is unused in our framework, butallows for geometry generated up to this point to be saved for a future render pass.The clipping stage trims primitives to the viewing volume, before applying a trans-formation to account for perspective. The Primitive Assembly stage samples thescene to generate 2D primitives from the geometry, and may discard faces based onorientation. The generated primitives are rasterized to a series of fragments withvalues assigned as either one of, a linear interpolation between, or a perspectivecorrect interpolation between seeding vertices. The generated fragments are oper-ated on by the FS before undergoing a number of optional tests to decide if thosepixels should be updated. These tests check against window focus and visibility(ownership test), fragment screen location (scissor test), fragment depth within thescene (depth test), and comparison of user provided values to the results of a userprovided test (stencil tests). Fragments are finally combined in some combinationwith the existing render target values through blending. Specific write locationsmay be explicitly disabled by the user through a final ’masking’ stage.All stages of the rendering pipeline except the VS may be omitted, in whichcase they simply pass the data to the next stage. The rendering pipeline may beterminated prior to primitive assembly to perform only a transform feedback oper-ation and the omission of a FS will still update the depth and stencil buffers.45An alternative render path is through just a Compute Shader (CS) which usesthe GPU as a highly parallel computing path. The compute path allows the specifi-cation of both the number of compute groups, specified at invocation, and the localsize of each group, specified within the shader. All compute invocations of thesame group may access and synchronize on shared variables and memory, whileseparate groups are disjoint. Compute output may be stored to a local buffer andmapped back to the CPU, or else rendered to a texture from which data can be read.7.2 GPU Performance ConsiderationsBottlenecks in GPU performance often arise due to pipeline stalls as a result ofresource transfer overhead, resource contention in shared memory, or synchroniza-tion of shader invocations. Management of these problems requires resource man-agement and load balancing, and is of particular importance to real-time rendering,as a performance critical program.One common location for pipeline stalls is on the initial transfer of data to theGPU, making it important to minimize the amount of data transferred at any onetime [36]. We refine the wrinkle path for sub triangle precision using a ComputeShader on the GPU so that only coarsely refined wrinkle path data needs to betransferred along the bus. Furthermore, we pack the data intelligently, using threedynamically-sized buffers to removing the need for fixed allocation sizes, and min-imizing the coupling between data transfer size and mesh size (see Figure 7.3).With this scheme, the first buffer stores two values for each triangle: the number ofwrinkles that affect it, and an offset into the subsequent array. Beginning at the off-set into the second buffer, for each triangle with affecting wrinkles, is a set of startand end indices for each affecting wrinkle in the final buffer which stores wrinkleinformation. In this scheme, wrinkle data is passed only once and offsets into thisdata are required only for affected triangles.GPU shaders are run synchronously on multiple shader cores, and may bestalled by conditional statements. In the case that both branches of a conditionalstatement are hit by synchronized shaders, both branches will be evaluated, and thecorrect result chosen for each instance [38] [36].46Data Per TriangleData Per Tessellated TriangleData per rened wrinkle point1023• # Wrinkles• data offset• start index• end index• position• width• normal• height• alpha10111200020212. . .. . .. . .102nottessellated!012301 2Figure 7.3: Wrinkle data is packed in three dynamically sized buffers to min-imize data associated with each triangle (uncouple from problem size)and to minimize total data transferred over the CPU-GPU bus. Untes-sellated triangles require 8 bytes each, while tesselated ones require 16.This may feasibly be reduce to 4 and 8 using half-byte types.47Figure 7.4: Projection of a point p to the winkle segment vivi+1.Global memory access suffers from a high latency and low bandwidth [36],proving to be one of the serious efficiency concerns of our program. The cost ofaccess is difficult to mitigate due to the need for proximity checks on the GPU incomputation of normals, and is one of the key areas in which our algorithm maybe improved.7.3 Wrinkle GeometryWe make use of the tessellation shader to subdivide each mesh triangle that fallswithin a proximity region of the wrinkle path (Figure 7.1, b, Section 8). We up-load the list of wrinkles affecting each triangle for a given frame, and tessellateonly those triangles with non-empty wrinkle lists. We use a uniform tessellationscheme, deciding on Tesselation Control Shader parameters to create a target edgelength that is 38 of Lmin. This target edge length is derived from the observationthat four triangles is a minimal requirement to represent a reasonable wrinkle con-tour. The rate that wrinkle height falls off over the length of a wrinkle allows forminor deviation towards coarser tessellation to improve efficiency. Since wrinklesmerge smoothly with the mesh at their boundaries and fall off completely withintesselated regions, there is no concern over the introduction of T-junctions on theboundary of unrefined and tessellated regions. We offset each generated vertex inthe direction of the triangle normal according to the cross-section height at that48point. To compute the height at a point p we project that point on to the wrin-kle path, evaluate the wrinkle height and width at that point, then use the B-splineshape function to determine the offset at p.Projecting to the wrinkle path using the Euclidean closest-point is a discontinu-ous operation in the vicinity of the medial axis of the path (Figure 7.4 top), leadingto discontinuities in the offsets. We avoid such discontinuities by using a modifiedprojection (Figure 7.4). To find the projection of a point p onto a wrinkle path, wecompute an approximate geodesic Voronoi diagram of the path edges. Within eachVoronoi cell, p is projected parallel to the wrinkle edge vivi+1 onto the Voronoifacets to find points qi and qi+1. We find the barycentric coordinates α and β of pwith respect to these projected points, and then construct the final projection pn onto the wrinkle path using the same barycentric coordinates along the wrinkle edge.To compute the projection efficiently on the GPU, we reformulate this problemas a single projection from p to pn. We note that the direction of projection isa linear combination of the two Voronoi edges given by the intersection of ourVoronoi facets with the mesh. We thus solve for the barycentric coordinate αalong the edge directly, as the coefficient for which our interpolated Voronoi edgedirection matches the vector from point pn along the edge to our given point p. Weneed not formulate this as a minimization on the angle between the two vectors, asthe Voronoi interpolation spans the full space of vector [p, pn], and thus and exactsolution will exist.If we let s0 and s1 correspond to the average direction of the wrinkle (orthogo-nal to the Voronoi edge and easier to compute), then we formulate the problem asbelow:0 = (vi+α ∗ (vi+1− vi)− p) · (α ∗ s0+(1−α)∗ s1) (7.1)We can then simplify the problem by substituting z0 = vi+1−vi and z1 = vi− p,and solve for α .0 = (z1+α ∗ z0) · (α ∗ s0+(1−α)∗ s1) (7.2)0 = (z0 · (s0− s1))∗α2+(z0 · s1+ z1 · (s0− s1))∗α+ z1 · s1 (7.3)497.4 Wrinkle NormalsIn the fragment shader, we use the method shown above to obtain the smooth-distance projected points and corresponding widths on adjacent wrinkle paths.While this is a duplication of much of the work from the Tesselation EvaluationShader, it is necessary to achieve per fragment precision in terms of wrinkle prox-imity. Making use of the interpolation across primitives during rasterization wouldavoid duplication, but is restricted to linear interpolation, and thus loses accuracyon our higher order deviation of normals. Interpolating distance rather than nor-mals gives a good result on a single wrinkle, but results in inconsistent and innacu-rate results when affected by multiple wrinkles. Loss of accuracy in these casesresults in visual artifacts that are visually unappealing.Figure 7.5 elaborates on the interpolation across primitives using a signed dis-tance. We see that between two wrinkle paths distance for either primitive willdeviate linearly. Interpolation across a primitive may result in a good approxima-tion to the real answer (top) or a completely incorrect result (bottom), dependingon the orientation of the wrinkles, and thus the sign of their overlapping distances.Additional information may be passed to resolve this discrepancy (a non-signeddistance), however the linear interpolation still fails to provide sufficient precisionfor visual fidelity. Furthermore, since vertex locations differ between primitives,interpolation boundaries will arise between primitives. Higher order interpolationwould solve these problems, but is not yet available in consumer hardware. A vi-sual comparison between the approaches may be seen in the results (Section 9).Once an accurate distance to the wrinkle path is computed, we use the B-splineshape contour formula to obtain an analytic normal. We shade the wrinkles usingthe Phong shading model, evaluating the lighting equation directly, per-pixel forthe computed normals. Other shading methods, such as Minneart shading andphysical based rendering models, could be computed on the same normal data.50Distance From Wrinkle 2Distance From Wrinkle 1dierence between linear interpolation and real distancedierence between linear interpolation and real distanceFigure 7.5: Given two wrinkles paths along theie respect z-axes, shown isthe signed distance from each wrinkle (orange and blue), and the lin-ear interpolation that would result across a primitive (brown). Wrinkleorientation may result in the overlap of similarly signed distance values(top), or opposite signed distance values (bottom).517.5 BlendingOne of the main challenges when modeling wrinkles is to believably handle caseswhere wrinkles overlap or merge. We found that a simple heuristic generates afeasible result while avoiding the computational overhead of more complicatedblending operators (e.g., [16]). For each tessellation vertex within the region of in-fluence of multiple wrinkle paths, we compute the height offset resulting from eachpath independently and select their maximum as the final offset. While this provesa good approximation of the deformed geometry, the discontinuous transition be-tween contributing wrinkle paths results in an unrealistic, harshly shaded boundarywhen applied to normals. In the Fragment Shader we instead compute offsets andnormals independently per path for fragment influenced by multiple paths. Wegenerate the final normal as an average of these per-path normals weighted by theircomputed offsets (Figure 7.6).Figure 7.6: Result without (left) and (with) wrinkle blending.52Chapter 8Proximity Testing AroundWrinkle PathsWith our wrinkles represented by their path, rather than as inherent constructs ofa particle simulation or height field parametrization, it becomes very important toefficiently manage the computation of distance between wrinkle paths and frompoints on the mesh to these paths. This information is used to properly seed newwrinkles, to truncate wrinkle paths should they merge or cross (so no wrinkle pathsare duplicated), and to determine the region each wrinkle path affects, so that tri-angles may be mapped to wrinkles for tessellation on the GPU. The algorithmchosen for each situation, and the precision it offers in computation of distance,play a large role in both the result and performance of our wrinkle computation onboth the CPU and GPU.8.1 Necessary PrecisionWe measure the precision of a test with respect to the error from the spline ofthe wrinkle path that will be computed on the GPU. The necessary precision forreasonable results varies for each of our use cases. Wrinkle seeding requires themost precision as we may have multiple seeds in each triangle, and want to ensurethat the paths at each seed are disjoint and non-merging. In this situation fullcomputation of the spline of each segment is unavoidable. Fortunately it need only53be done for one wrinkle for each comparison, as comparisons are being done withrespect to the seed point.Tests for wrinkle collisions or merging are less dependent on precision, asslight discrepancies are handled nicely by our normal blending. Truncating wrin-kles upon merging helps reduce the number of wrinkle segments processed on theGPU, and crossing within the precision difference of a spline from its polyline isnon-perceptible. It is sufficient in this case to merely compare shortest distancesbetween the wrinkle paths.In designing the test on proximity of triangles to a given wrinkle path it is notsufficient to test triangles against a bounding a box, as later refinement of the wrin-kle path may curve the path outside of the box, resulting in un-tessellated regionsbegin deformed, and tears forming in the mesh. However with the sheer numberof comparisons being done it is computationally heavy to compute the spline foreach wrinkle; therefore we instead compute bounding ellipses that encapsulates themaximum possible deviation from the path that spline will take. Accuracy playsas much an effect on performance for this application as the algorithm efficiency,since accuracy effects the amount of data that will be passed to the GPU and sub-sequently processed.8.2 Bounds TestingIn all comparison cases it is necessary to narrow down the search space prior toperforming more accurate bounds or distance tests. In the case of wrinkle seedand wrinkle-wrinkle comparisons, we maintain a look-up table for wrinkles andtheir mapped triangles, allowing us to easily avoid the comparisons of wrinkles notpassing through the same triangle. Each segment of a wrinkle path also maintainsthe triangle in which it resides, allowing for simple boolean checks for collision oneach segment of a wrinkle prior to performing an actual distance check.To determining the triangles affected by a given wrinkle for the GPU we walkradially from each wrinkle segment, as their triangles are known, and test eachtriangle we pass against a rough bounding ellipse for distance. We record eachsegment affecting a triangle and pass to the GPU a list of affecting wrinkles foreach triangle, and the start and end segment indices within that wrinkle that affect54the triangle. In the control shader, any triangle with affecting wrinkles is tesselated.55Chapter 9ResultsWe demonstrate our method on a range of meshes and animation sequences, mostof which are taken from currently shipping video game titles. Our method addsbelievable, temporally coherent wrinkles to low-resolution character meshes andgeometry (Fig. 9.6, 9.7, 9.8 and elsewhere in the paper.). The skirt example (Fig.9.8) was provided courtesy of Kavan et al.[24] and is created using coarse physics-based simulation.9.1 ParametersOur system makes use of two tunable parameters closely related to expected ma-terial properties. Compression sensitivity τ is linked to the ease with which amodeled fabric bends, and minimal wrinkle width Lmin is linked to how tightlycompressed a material can to become. Compression sensitivity may also dependon the quality of the animation – one may choose to use a higher sensitivity thresh-old if the animation is more noisy and exhibits more spurious tangential motion.Figure 9.1 shows the impact of changing the parameter values. Table 9.1 list thenumbers used for the animation sequences shown in the paper.56τ = 1.15Lmin= 0.5%τ = 1.25Lmin= 0.5%τ = 1.15Lmin= 1%τ = 1.25Lmin= 1%time = 69ms time = 33ms time = 22ms time = 12msFigure 9.1: Impact of different choices of parameter values τ and Lmin.9.2 PerformanceTable 9.1 shows the run-time performance of our algorithm on various meshes,as well as the mesh triangle counts and wrinkle parameters used. All times arecomputed on an Intel Core i7-3930K CPU running at 3.2 GHz, with 32 GB ofRAM and an NVIDIA GeForce GTX 670 graphics card. Frames were rendered ata resolution of 1920x1080.Figure 9.1 reports the impact of the choice of parameters on performance. Asexpected, performance decreases as the number of wrinkles increases (τ decreases)and their width increase; however, we maintain interactive performance through-out. The majority of our time per-frame is spent in the fragment shader, computingwrinkle normals in real time; in a real world scenario such as a first-person actiongame where models occupy smaller portions of the screen, performance increasesaccordingly.An argument can be made against the choice of combining both tessellationand per-fragment normal computation in terms of performance and results. Exam-ination of this trade-off shows performance using solely a tessellation scheme to beheavily reliant on the level of refinement and thus width of each wrinkle. Figures9.3 and 9.4 use a large number of wrinkles to demonstrate the effect on perfor-mance. Refining the mesh to a degree that artifacts are not exhibited often bringsthe performance well below that of a fragment shader alternative (Figure 9.5). Thefragment shader provides stable results at all levels of refinement, and thus provesthe better choice.57Animation τ Lmin # avg # avg. ref. shapetri. wrinkles computation timeFig. 15 (a) 1.4 0.5% 734 22.75 1.69msFig. 15 (b) 1.3 0.5% 602 5.60 1.69msFig. 15 (c) 1.4 0.5% 534 5.89 1.74msFig. 15 (d) 1.4 0.5% 628 11.80 1.57msFig. 15 (e) 1.2 1% 356 10.57 0.92msFig. 15 (f) 1.4 0.5% 602 19.03 1.72msAnimation avg. path avg. modeling total frametracing time time timeFig. 15 (a) 5.33ms 8.30ms 12.45msFig. 15 (b) 3.92ms 5.53ms 11.69msFig. 15 (c) 2.46ms 4.68ms 7.39msFig. 15 (d) 3.77ms 6.55ms 10.67msFig. 15 (e) 4.84ms 8.95ms 13.19msFig. 15 (f) 5.69ms 9.78ms 14.66msTable 9.1: Performance statistics for various models processed with our al-gorithm. Lmin computed as percent of character height. All times inmilliseconds.(a) (b) (c)Figure 9.2: Left: Artist drawn static texture and our wrinkles without (center)and with same texture (right).58Figure 9.3: Use of interpolated normals may introduce artifacts for even widewrinkles when reducing tessellation level to reach real time frame rates.From left to right the tesselation refinement is reduced, and we begin tosee inconsistency in the normals of the highlighted area, resulting frominsufficient granularity to determine the contributing wrinkle path.59Figure 9.4: For large numbers of small wrinkles, the reduction of tessellationlevel results in visible artifacts well before reaching playable framerates.Three levels of tesselation with corresponding frame times are shownwith normal inconsistencies highlighted in red.60Wide WrinklesPer-Fragment NormalsHigh RenementWide WrinklesPer-Fragment NormalsHigh RenementWide WrinklesPer-Fragment NormalsLow RenementSmall WrinklesPer-Fragment NormalsLow RenementFigure 9.5: Fragment shader is not dependent on geometry tessellation forperformance, and offers a stable, mid-level performance as compared tothe range offered by a tessellation solution.9.3 Comparison to Alternative StrategiesWe validate our algorithmic choices against those used by previous work through-out the paper. Figure 3.3, (top) highlights the infeasibility of employing one of theframes in an animation sequence as a reference shape. Methods such as [35, 43]heavily rely on the existence of such reference shape. Figure 3.4 motivates ouruse of a path tracing strategy designed to operate on piecewise-constant insteadof smoothed piecewise linear stretch tensor fields [43]. Our combined method is61dramatically faster than that of Rohmer et al.who report speeds of over a secondper frame.We also compare our method against the use of artist drawn wrinkles (Figure9.2). We generate temporal motion-driven wrinkles, such as those on the chest,where static wrinkles would be meaningless, and place wrinkles at many concavejoints (elbow, ankle, pelvis) where artist placed similarly shaped wrinkles. Sinceour method is motion based, if part of the anatomy remains fixed we will not gen-erate wrinkles in that area; thus our method lacks wrinkles under the arms wherethe artist chose to place some.62Figure 9.6: Some wrinkling results: input frames on top, wrinkled below.63Figure 9.7: Some wrinkling results: input frames on top, wrinkled below.64Figure 9.8: Some wrinkling results: input frames on top, wrinkled below.65Chapter 10Conclusion and Future WorkWe present a practical method for adding real-time wrinkling to cloth surfaces rep-resented by coarse non-physically animated meshes. We have demonstrated theconstruction of a plausible garment reference shape from diverse mesh and ani-mation inputs, and extracted from it a smooth tensor field through which to tracewrinkle paths. We generate wrinkle paths that are both spatially smooth and tem-porally consistant, and make full, efficient use of the GPU to tesselate, deform andrender our wrinkles in real-time. Our method is suitable for interactive wrinklingof cloth and fabrics for video games on current-generation and next-generationconsoles and hardware.In the future we would like to explore improvements to both performance andrendering quality, as well as the application of our approach to other wrinkling sur-faces, e.g., human skin. Our work addresses only dynamic wrinkles - i.e. thosewhose presence is hinted at by the cloth motion, and would benefit from the ad-dressing of static wrinkles which humans often expect to be present in areas ofnegative Gaussian curvature.Our method, like most previous work, generates outward bulging wrinkles -well suited for tight garments, but physically inaccurate on looser garments. Fu-ture work should explore automatic selection of wrinkle direction, or partial dis-tribution of wrinkle deformation in both directions, to be consistent with humanexpectations. Additionally, our method does not currently handle stretch wrinkles,and incorporating this wrinkling is a source for future investigation.66Our method makes use of simple approximations for the falloff of wrinkleheight towards its ends, and on the rate at which a wrinkle’s length may changeover time and as compared to compression values. Exploring the benefit of moredetailed representations is a direction of future investigation. Further work mayalso explore approaches toward the persistence of wrinkles with less constraint onmotion, or that avoid the need to reconstruct our wrinkle path in the neighbour-hood surrounding a crossed vertex. Our current approach is restricted to movingvertices along edges; revisiting 3D walk approaches may offer smoother transitionin a quickly changing discrete field.A number of possibilities may be explored towards the further improvementof performance on the GPU. Global memory is accessed in 32, 64, or 128 bytememory transactions, and alignment of data to these boundaries times may sig-nificantly reduce the number of fetches required for each access [36]. Storage ofwrinkles in memory location with faster access, such as texture memory or con-stant memory may also warrant examination. Both of these methods would requireresearch into the access patterns and memory layout of wrinkles. An alternative isthe complete reduction of required accesses and tests through the improvement ofproximity testing around wrinkle paths.The duplication of distance calculation to wrinkle paths between the Tesse-lation Evaluation Shader and Fragment Shader has proven unresolvable with thecurrent graphics pipeline, however upcoming revisions to the specification proposechanges that may expose the interpolation function during rasterization to the pro-grammer. This would enable the exploration of higher order approximations fordistance interpolation, or perhaps even height approximations.67Bibliography[1] D. Baraff and A. Witkin. Large steps in cloth simulation. In Proc. AnnualConference on Computer Graphics and Interactive Techniques, SIGGRAPH’98, pages 43–54, 1998. → pages 6, 7[2] M. Bergou, S. Mathur, M. Wardetzky, and E. Grinspun. TRACKS: TowardDirectable Thin Shells. ACM Transactions on Graphics (SIGGRAPH), 26(3):50:1–50:10, 2007. → pages 11[3] J. Bonet. Nonlinear continuum mechanics for finite element analysis.Cambridge university press, 1997. → pages 19[4] Y. Boykov and V. Kolmogorov. An experimental comparison ofmin-cut/max-flow algorithms for energy minimization in vision. IEEETransactions on Pattern Analysis and Machine Intelligence, 26:1124–1137,2004. → pages 22[5] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimizationvia graph cuts. IEEE Transactions on Pattern Analysis and MachineIntelligence, 23:1222–1239, 2001. → pages 22[6] D. E. Breen, D. H. House, and M. J. Wozny. Predicting the drape of wovencloth using interacting particles. In Proceedings of the 21st annualconference on Computer graphics and interactive techniques, pages365–372. ACM, 1994. → pages 7[7] R. Bridson, R. Fedkiw, and J. Anderson. Robust treatment of collisions,contact and friction for cloth animation. In ACM Transactions on Graphics(ToG), volume 21, pages 594–603. ACM, 2002. → pages 8[8] M. Carignan, Y. Yang, N. M. Thalmann, and D. Thalmann. Dressinganimated synthetic actors with complex deformable clothes. In ACMSiggraph Computer Graphics, volume 26, pages 99–104. ACM, 1992. →pages 768[9] K.-J. Choi and H.-S. Ko. Stable but responsive cloth. ACM Trans. Graph.,21(3):604–611, 2002. → pages 5, 6, 7[10] K.-J. Choi and H.-S. Ko. Research problems in clothing simulation.Computer Aided Design, 37(6):585–592, 2005. ISSN 0010-4485.doi:10.1016/j.cad.2004.11.002. URLhttp://dx.doi.org/10.1016/j.cad.2004.11.002. → pages 1, 6, 7[11] B. Eberhardt, A. Weber, and W. Strasser. A fast, flexible, particle-systemmodel for cloth draping. Computer Graphics and Applications, IEEE, 16(5):52–59, 1996. → pages 7[12] J. W. Eischen, S. Deng, and T. G. Clapp. Finite-element modeling andcontrol of flexible fabric parts. IEEE Computer Graphics and Applications,16(5):71–80, 1996. → pages 7[13] E. English and R. Bridson. Animating developable surfaces usingnonconforming elements. ACM Trans. Graph., 27(3):66:1–66:5, 2008. ISSN0730-0301. → pages 7[14] H. Enqvist. The secrets of cloth simulation in Alan Wake. Gamasutra, Apr.2010. → pages 3, 10[15] R. Gillette, C. Peters, N. Vining, E. Edwards, and A. Sheffer. Real-timedynamic wrinkling of coarse animated cloth. In Proc. Symposium onComputer Animation, SCA ’15, 2015. → pages iii[16] O. Gourmel, L. Barthe, M.-P. Cani, B. Wyvill, A. Bernhardt, M. Paulin, andH. Grasberger. A gradient-based implicit blend. ACM Transactions onGraphics (TOG), 32(2):12, 2013. → pages 52[17] S. Green and N. Overview. Stupid opengl shader tricks. In AdvancedOpenGL Game Programming Course, Game Developers Conference, 2003.→ pages 8[18] P. Guan, L. Reiss, D. Hirshberg, A. Weiss, and M. J. Black. Drape: Dressingany person. ACM Trans. on Graphics (Proc. SIGGRAPH), 31(4):35:1–35:10, July 2012. → pages 9[19] S. Hadap, E. Bangerter, P. Volino, and N. Magnenat-Thalmann. Animatingwrinkles on clothes. In Proceedings of the Conference on Visualization ’99:Celebrating Ten Years, VIS ’99, pages 175–182, Los Alamitos, CA, USA,1999. IEEE Computer Society Press. ISBN 0-7803-5897-X. URLhttp://dl.acm.org/citation.cfm?id=319351.319372. → pages 1269[20] F. Hahn, B. Thomaszewski, S. Coros, R. W. Sumner, F. Cole, M. Meyer,T. DeRose, and M. Gross. Subspace clothing simulation using adaptivebases. ACM Trans. Graph., 33(4):105:1–105:9, 2014. ISSN 0730-0301. →pages 10[21] J. Hu. Structure and Mechanics of Woven Fabrics. Woodhead PublishingSeries in Textiles. Elsevier Science, 2004. → pages 3, 6, 7, 26[22] T. Jakobsen. Advanced character physics. In Game Developers Conference,pages 383–401, 2001. → pages 8[23] T. Kaneko, T. Takahei, M. Inami, N. Kawakami, Y. Yanagida, T. Maeda, andS. Tachi. Detailed shape representation with parallax mapping. InProceedings of ICAT, volume 2001, pages 205–208, 2001. → pages 12[24] L. Kavan, D. Gerszewski, A. Bargteil, and P.-P. Sloan. Physics-inspiredupsampling for cloth simulation in games. ACM Transactions on Graphics(SIGGRAPH), 30(4):93:1–93:9, 2011. → pages 3, 9, 56[25] Khronos. Opengl wiki, May 2015. URLhttps://www.opengl.org/wiki/Rendering Pipeline Overview. [Online;accessed 22-Aug-2015]. → pages 44[26] D. Kim, W. Koh, R. Narain, K. Fatahalian, A. Treuille, and J. F. O’Brien.Near-exhaustive precomputation of secondary cloth effects. ACMTransactions on Graphics, 32(4):87:1–7, 2013. URLhttp://graphics.berkeley.edu/papers/Kim-NEP-2013-07/. Proc. SIGGRAPH.→ pages 9[27] V. Kolmogorov and R. Zabih. What energy functions can be minimized viagraph cuts. IEEE Transactions on Pattern Analysis and MachineIntelligence, 26:65–81, 2004. → pages 22[28] T. J. Lahey. Modelling hysteresis in the bending of fabrics. Master’s thesis,University of Waterloo, 2002. → pages 6[29] J. Lander. Devil in the blue-faceted dress: Real-time cloth animation. GameDeveloper Magazine, May 1999. → pages 1, 10[30] T. Le Thanh and A. Gagalowicz. A new buckling model for cloth simulation.In A. Gagalowicz and W. Philips, editors, Computer Vision/ComputerGraphics Collaboration Techniques, volume 6930 of Lecture Notes inComputer Science, pages 251–261. Springer Berlin Heidelberg, 2011. ISBN70978-3-642-24135-2. doi:10.1007/978-3-642-24136-9 22. URLhttp://dx.doi.org/10.1007/978-3-642-24136-9 22. → pages 6[31] H. Li, Y. Wan, and G. Ma. A cpu-gpu hybrid computing framework forreal-time clothing animation. In Cloud Computing and Intelligence Systems(CCIS), 2011 IEEE International Conference on, pages 391–396. IEEE,2011. → pages 7, 8[32] J. Loviscach. Wrinkling coarse meshes on the gpu. In Computer GraphicsForum, volume 25, pages 467–476. Wiley Online Library, 2006. → pages 12[33] N. Magnenat-Thalmann and P. Volino. From early draping to haute couturemodels: 20 years of research. The Visual Computer, 21(8-10):506–519,2005. → pages 7[34] Microsoft. Microsoft dev center, May 2015. URLhttps://msdn.microsoft.com/en-us/library/windows/desktop/ff476882.[Online; accessed 22-Aug-2015]. → pages 44[35] M. Mu¨ller and N. Chentanez. Wrinkle meshes. In Proc. Symposium onComputer Animation, SCA ’10, pages 85–92, 2010. → pages 3, 10, 13, 17,61[36] NVidia. Cuda toolkit documentation, March 2015. URL http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#performance-guidelines.[Online; accessed 24-June-2015]. → pages 46, 48, 67[37] C. Oat. Animated wrinkle maps. In SIGGRAPH Courses, SIGGRAPH,pages 33–37, 2007. → pages 10[38] D. Ra´kos. Opengl developer forum, Sept 2011. URL https://www.opengl.org/discussion boards/showthread.php/175672-shader-conditionals.[Online; accessed 24-June-2015]. → pages 46[39] O. Re´millard and P. G. Kry. Embedded thin shells for wrinkle simulation.ACM Transaction on Graphics, 32(4):50:1–50:8, 2013. → pages 11[40] J. Rodrı´guez-Navarro, A. Susı´n Sa´nchez, et al. Non structured meshes forcloth gpu simulation using fem. EUROGRAPHICS, 2006. → pages 8[41] X. Rodriguez-Navarro, M. Sainz, and A. Susin. Gpu based cloth simulationwith moving humanoids. In Actas XV Congreso Espan˜ol de Informa´ticaGra´fica (CEIG2005), pages 147–155, 2005. → pages 871[42] D. Rohmer, S. Hahmann, and M.-P. Cani. Active geometry for gamecharacters. In Motion in Games, volume 6459 of Lecture Notes in ComputerScience, pages 170–181. 2010. ISBN 978-3-642-16957-1. → pages 11, 13[43] D. Rohmer, T. Popa, M.-P. Cani, S. Hahmann, and A. Sheffer. AnimationWrinkling: Augmenting Coarse Cloth Simulations with Realistic-LookingWrinkles. ACM Transactions on Graphics (Proc. SIGGRAPH ASIA), 29(5),2010. → pages vii, 3, 6, 11, 14, 17, 25, 26, 27, 28, 37, 61[44] M. Tang, D. Manocha, J. Lin, and R. Tong. Collision-streams: fastgpu-based collision detection for deformable models. In Symposium oninteractive 3D graphics and games, pages 63–70. ACM, 2011. → pages 7, 8[45] M. Tang, R. Tong, R. Narain, C. Meng, and D. Manocha. A gpu-basedstreaming algorithm for high-resolution cloth simulation. In ComputerGraphics Forum, volume 32, pages 21–30. Wiley Online Library, 2013. →pages 8[46] D. Terzopoulos, J. Platt, A. Barr, and K. Fleischer. Elastically deformablemodels. In ACM Siggraph Computer Graphics, volume 21, pages 205–214.ACM, 1987. → pages 5, 7[47] B. Thomaszewski, S. Pabst, and W. Straer. Continuum-based strain limiting.Computer Graphics Forum, 28(2):569–576, 2009. → pages 7[48] T. Vassilev, B. Spanlang, and Y. Chrysanthou. Fast cloth animation onwalking avatars. In Computer Graphics Forum, volume 20, pages 260–267.Wiley Online Library, 2001. → pages 7, 8[49] L. Verlet. Computer experiments on classical fluids. i. thermodynamicalproperties of lennard-jones molecules. Physical Review, 159(1):98, 1967. →pages 10[50] P. Volino and N. M. Thalmann. Implementing fast cloth simulation withcollision response. In Computer Graphics International Conference, pages257–257. IEEE Computer Society, 2000. → pages 7[51] H. Wang, F. Hecht, R. Ramamoorthi, and J. F. O’Brien. Example-basedwrinkle synthesis for clothing animation. ACM Transactions on Graphics,29(4):107:1–8, 2010. URLhttp://graphics.berkeley.edu/papers/Wang-EBW-2010-07/. Proc.SIGGRAPH. → pages 9, 1072[52] J. Weil. The synthesis of cloth objects. SIGGRAPH Comput. Graph., 20(4):49–54, Aug. 1986. ISSN 0097-8930. doi:10.1145/15886.15891. URLhttp://doi.acm.org/10.1145/15886.15891. → pages 5[53] C. Zeller. Cloth simulation on the gpu. In ACM SIGGRAPH 2005 Sketches,page 39. ACM, 2005. → pages 8[54] D. Zhang and M. Yuen. A coherence-based collision detection method fordressed human simulation. In Computer Graphics Forum, volume 21, pages33–42. Wiley Online Library, 2002. → pages 7[55] D. Zhang and M. M.-F. Yuen. Collision detection for clothed humananimation. In Computer Graphics and Applications, 2000. Proceedings. TheEighth Pacific Conference on, pages 328–337. IEEE, 2000. → pages 7[56] J. S. Zurdo, J. P. Brito, and M. A. Otaduy. Animating wrinkles by exampleon non-skinned cloth. IEEE Transactions on Visualization and ComputerGraphics, 19(1):149–158, 2013. URLhttp://www.gmrv.es/Publications/2013/ZBO13. → pages 973
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Augmentation of coarse meshes with wrinkles
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Augmentation of coarse meshes with wrinkles Gillette, Russell 2015
pdf
Page Metadata
Item Metadata
Title | Augmentation of coarse meshes with wrinkles |
Creator |
Gillette, Russell |
Publisher | University of British Columbia |
Date Issued | 2015 |
Description | Folds and wrinkles are an important visual cue in the recognition of realistically dressed characters in virtual environments. Wrinkles must, however, move dynamically within the context of an animation to retain much of this realism. Adding wrinkles to real-time cloth visualization proves challenging, as the animations used in games, pre-render visualization, and other such applications, often have no reference shape, an extremely low triangle count, and poor temporal and spatial coherence. I contribute approaches towards the persistence of wrinkles over time, and the creation and rendering of wrinkle geometry in a real-time context, towards a novel real-time method for adding believable, dynamic wrinkles to coarse cloth animations. With this method we trace spatially and temporally coherent wrinkle paths and overcomes the inaccuracies and noise in low-end cloth animation. We employ a two stage stretch tensor estimation process, first detecting regions of consistent surface behaviour, and then using these regions to construct a per-triangle, temporally adaptive reference shape and a stretch tensor based on it. We use this tensor to dynamically generate new wrinkle geometry on coarse cloth meshes through use of the GPU tessellation unit. Our algorithm produces plausible fine wrinkles on real-world data sets at real-time frame rates, and is suitable for the current generation of consoles and PC graphics cards. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2015-09-08 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution 2.5 Canada |
DOI | 10.14288/1.0166683 |
URI | http://hdl.handle.net/2429/54687 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2015-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by/2.5/ca/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2015_november_gillette_russell.pdf [ 80.54MB ]
- Metadata
- JSON: 24-1.0166683.json
- JSON-LD: 24-1.0166683-ld.json
- RDF/XML (Pretty): 24-1.0166683-rdf.xml
- RDF/JSON: 24-1.0166683-rdf.json
- Turtle: 24-1.0166683-turtle.txt
- N-Triples: 24-1.0166683-rdf-ntriples.txt
- Original Record: 24-1.0166683-source.json
- Full Text
- 24-1.0166683-fulltext.txt
- Citation
- 24-1.0166683.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0166683/manifest