UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A method for real-time dynamic cloth wrinkling Peters, Craig 2015

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2015_november_peters_craig.pdf [ 130.89MB ]
JSON: 24-1.0165787.json
JSON-LD: 24-1.0165787-ld.json
RDF/XML (Pretty): 24-1.0165787-rdf.xml
RDF/JSON: 24-1.0165787-rdf.json
Turtle: 24-1.0165787-turtle.txt
N-Triples: 24-1.0165787-rdf-ntriples.txt
Original Record: 24-1.0165787-source.json
Full Text

Full Text

A Method for Real-Time Dynamic Cloth WrinklingbyCraig PetersB.Sc. Honours in Mathematics, The University of British Columbia, 2010B. Computer Science, The University of British Columbia, 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© Craig Peters, 2015AbstractThis work presents a novel technique for generating a plausible rest shape to clothanimations which have none, and adding dynamic folds and wrinkles to them inreal-time. The nature of real-time animations makes this task very challenging.The models used are typically very coarse, and the animations used are often non-physical and exhibit poor temporal and spatial coherence. Since animations canmove and deform in non-physical ways, the notion of a valid rest shape or referenceshape is not well defined. Instead, we utilize a graph-cut framework to smoothlyand consistently measure temporally local deformation in the animation, and usethat to construct a per-triangle temporally adaptive pseudo-reference shape. Fromthis shape we compute a stretch tensor field whose eigenvectors can be used totrace plausible dynamic wrinkle paths. We then harness the GPU tessellation unitto refine and deform the cloth along these paths to create wrinkle geometry.Our method runs in real-time on a variety of data sets.iiPrefaceThe method presented in this thesis was described in the following research paper:R. Gillette, C. Peters, N. Vining, E. Edwards, and A. Sheffer. Real-time dy-namic wrinkling of course animated cloth. ACM Symposium on Computer Anima-tion, 2015.[12]Figures and text from the publication are copyright by the Symposium on Com-puter Animation and reused in this thesis by permission.The work in Chapters 6 and 7 were developed largely by Russell Gillette andare reproduced here for completeness. The work in Chapter 5 was developedjointly between Russell Gillette and myself, and may include some shared text. Theother ideas presented in this thesis were developed mostly by myself and discussedwith Dr. Alla Sheffer, Russell Gillette, Essex Edwards, and Nicholas Vining.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 Compression Field Construction . . . . . . . . . . . . . . . . . . . . 194.1 Compression Pattern Extraction . . . . . . . . . . . . . . . . . . 194.1.1 Triangle Stretch Tensor . . . . . . . . . . . . . . . . . . . 204.1.2 Graph Cut Formulation . . . . . . . . . . . . . . . . . . . 214.1.3 Graph Cut Solver . . . . . . . . . . . . . . . . . . . . . . 234.2 Local Reference Triangles . . . . . . . . . . . . . . . . . . . . . 275 Wrinkle Path Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . 315.1 Wrinkle Initialization . . . . . . . . . . . . . . . . . . . . . . . . 31iv5.2 Temporal Persistence . . . . . . . . . . . . . . . . . . . . . . . . 326 Wrinkle Shape Parameters . . . . . . . . . . . . . . . . . . . . . . . 387 Fast GPU-Based Wrinkle Modeling . . . . . . . . . . . . . . . . . . 418 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57vList of TablesTable 8.1 Performance statistics for various models processed with ouralgorithm. Rmin computed as percent of character height. Alltimes in milliseconds. . . . . . . . . . . . . . . . . . . . . . . 45viList of FiguresFigure 1.1 Coarse game-level cloth animation augmented with realisticlooking wrinkles in real-time. Reproduced from [12]. . . . . . 2Figure 1.2 Coarse game-level cloth animation augmented with realisticlooking wrinkles in real-time. Reproduced from [12]. . . . . . 3Figure 2.1 (a) Off-line wrinkling of simulated clothing using a user-providedreference shape [24]. (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. . . . . . . . . . . . . . . . . . . 8Figure 3.1 A pipeline-diagram of the algorithm components addressedby this thesis. The main components are: (a) input anima-tion frames; (b) compression(blue)/stretch(red)/neutral(green)labeling (Chapter 4); (c) local stretch tensors shown by ori-ented ellipses (Chapter 5); (d) temporally coherent wrinklepaths (Chapter 5). . . . . . . . . . . . . . . . . . . . . . . . . 15Figure 3.2 The remaining algorithm components largely developed by Rus-sell Gillette, included for completeness: (a) final wrinkled clothrendered at real time without and (b) with texture (Chapter 7). 16viiFigure 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. . . . . . . . . . . . . . . . . . 16Figure 3.4 On coarse meshes smoothing the piece-wise constant tensorfield (left) to generate a piece-wise liner one (right) leads toloss of details, such as the compression on the shoulder andacross the chest (left) which are no longer distinguishable onthe right. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Figure 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. 20Figure 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. . 22Figure 4.3 The graph dual of a simple mesh surface patch. . . . . . . . . 24Figure 4.4 The graph Gαβ , constructed from G . . . . . . . . . . . . . . 26Figure 4.5 The graph Gα , constructed from G . . . . . . . . . . . . . . . 28Figure 4.6 Evolution of reference triangles (bottom) throughout the ani-mation process. . . . . . . . . . . . . . . . . . . . . . . . . 28Figure 5.1 A smoothed wrinkle (purple) between the input wrinkle (blue)and geodesic path (orange). . . . . . . . . . . . . . . . . . . 33viiiFigure 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). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Figure 5.3 An example wrinkle updated to better match a new field . . . 34Figure 5.4 A reconstructed polyline as a t value lies outside the [0,1] in-terval. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36Figure 5.5 An example of removing points from the optimization. If allthree interior points were included, then they can only cross themesh vertex by creating a self-intersecting loop in the wrinkle,which produces a high cost in equation 5.3. Thus, we removeall but one vertex and reconstruct the neighbourhood after asolution is reached on the smaller problem. . . . . . . . . . . 37Figure 6.1 The parameters defining the cross-sectional contour of a wrinkle. 38Figure 6.2 The final shape of the cross-sectional contour of a wrinkle. . . 39Figure 6.3 Left to right: wrinkles rendered using only normal maps; tes-sellated wrinkle region; wrinkles rendered using displacement(tesselation) and normal maps. . . . . . . . . . . . . . . . . . 40Figure 7.1 Projection of a point p to the winkle segment vivi+1. . . . . . 42Figure 7.2 Result without (left) and (with) wrinkle blending. . . . . . . . 43Figure 8.1 Impact of different choices of parameter values τ and Rmin. . . 45Figure 8.2 Left: Artist drawn static texture and our wrinkles without (cen-ter) and with same texture (right). . . . . . . . . . . . . . . . 46Figure 8.3 Comparison of labels produced with and without Graph Cut.Top: The raw tensor values. Middle: The labels chosen with-out Graph Cut. Bottom: Our labels, chosen with Graph Cut. . 47Figure 8.4 Comparison of labels produced with and without Graph Cut.Top: The raw tensor values. Middle: The labels chosen with-out Graph Cut. Bottom: Our labels, chosen with Graph Cut. . 48Figure 8.5 Sawing motion. Inputs on top, wrinkling results beneath. . . . 49ixFigure 8.6 Chopping motion. Inputs on top, wrinkling results beneath. . . 50Figure 8.7 Fist pumping motion. Inputs on top, wrinkling results beneath. 51Figure 8.8 Stretching motion. Inputs on top, wrinkling results beneath. . 52Figure 8.9 Jumping Jack motion. Inputs on top, wrinkling results beneath. 53Figure 8.10 Shoveling motion. Inputs on top, wrinkling results beneath. . 54xAcknowledgmentsI would like to express deep thanks to my supervisor, Dr. Alla Sheffer. Her guid-ance and wisdom helped me succeed in my research goals and motivated me topush past setbacks and roadblocks throughout my experience as a Master’s student.I would also like to thank my other collaborators on the project: Russell Gillette,Essex Edwards, and Nicholas Vining. You all contributed vital work towards mythesis, and I am very grateful.Most importantly, I would like to thank my wife for her constant love andsupport, enduring the late nights and encouraging me at every step. I couldn’t havedone it without her.xiChapter 1IntroductionPlausible cloth deformation and wrinkling provide important visual cues necessaryfor believable characters in virtual environments. Recent advances in GPU technol-ogy and parallelism have now made coarse cloth animation possible for real-timeapplications; however, these low-end cloth animations operate on meshes withlow triangle counts and lack the fine wrinkling patterns exhibited by real-worldcloth. Running a sufficiently accurate cloth simulation to capture fine wrinklingbehaviours is both too computationally expensive and challenging to solve numer-ically in real-time. We introduce a new method for achieving plausible wrinklingon low end, coarse cloth for games and virtual environments with real-time perfor-mance (Figure 1.1, 1.2).Games have a variety of constraints that their animations must adhere to. Ifuser input forces a character to move in non-physical ways, the clothing must alsomove non-physically to stay believably fixed to the character. Combined with thecomputational expense of physical simulation discussed above, this forces gamedesigners to use other mechanisms for generating cloth movement in their games.One technique is to perform a crude, approximate simulation, commonly with amass-spring system, whose artifacts are within visually acceptable limits. Anothertechnique to construct novel animation poses is to blend multiple canonical posesthat are predefined by an artist. Often an even simpler technique is used, where thegarment surface is formed by linear blend skinning with respect to an underlying,artist-driven skeleton. These techniques and others are summarized in more detail1Figure 1.1: Coarse game-level cloth animation augmented with realisticlooking wrinkles in real-time. Reproduced from [12].2Figure 1.2: Coarse game-level cloth animation augmented with realisticlooking wrinkles in real-time. Reproduced from [12].3by Lander [19].Rather than trying to capture fine wrinkling in the simulation, we are inspiredby offline approaches for adding wrinkling and folds to high-quality cloth simula-tion as a post-process [16, 20, 24], Figure 2.1, top. These post-processing methodsare motivated by the key observation that cloth is incompressible [15]. We canmeasure whether or not cloth is compressed by comparing its shape to a knownreference shape, which is free of compression and stretch. Since cloth is effectivelyincompressible, we can view any compression observed in the animated cloth withrespect to the reference shape as due to insufficient animation resolution. The post-process therefore resolves the compression and accounts for the loss of material byforming wrinkles perpendicular to the direction of the compression.Unfortunately, the cloth meshes used in video games are generated without ameaningful reference shape [10]. The cloth is not constructed by sewing togetherdevelopable patterns along seams, and the animation framework is not an accu-rate physics simulation. Rather, it is modeled by an artist on a digital character,intrinsically baking gravity, contact, and friction into the cloth configuration. Theanimation techniques outlined by Lander [19] do not employ a reference shape,and thus deform the cloth in non-physical ways, e.g. self-intersection or extremeand bidirectional stretch or compression. For these reasons, a valid reference shapefrom which compression can reliably be measured is not simply unavailable to us;it cannot exist. We therefore construct an approximate frame of reference in theform of a local per-triangle reference shape, which is accurate enough with respectto recently observed frames of animation to create temporally plausible wrinkles.We allow this reference shape to change and evolve over time as new animationframes are processed so that any new information from the animation can be usedto inform our reference shape. At every frame, we measure deformational changeto triangle shape, and use that information as well as the changes in the triangle’slocal neighbourhood to adapt our reference shape. We then compute the com-pression of the current triangle with respect to this reference shape, and use thisinformation to trace and modify wrinkles.Accurately determining a plausible per-triangle reference shape on the fly fromnewly generated frames of animation requires us to overcome the problems oftenpresent in typical real-time animation. Without a proper reference shape, the only4shape we can meaningfully refer to without more a priori knowledge is the previ-ous input frame. However, this measurement tends to be very noisy, nonsmooth,and generally unreliable. To achieve temporal coherence in our local per-trianglereference shape update, we wish to determine smooth, general regions of the gar-ment that are undergoing similar deformations. To that end, we employ a graph-cutsegmentaion technique that labels triangles according to how they are currently de-forming, while penalizing inconsistency from frame to frame and across triangleadjacencies. This step generates a smooth segmentation that indicates how the an-imation is deforming the cloth and can be used to smoothly update our referenceshape. This process ensures that the compression field we compute from this refer-ence shape does not change drastically from frame to frame, and thus our wrinklespaths are consistent in space and time. This update runs in real-time and requiresno preprocessing.We use the per-triangle compression field to trace wrinkle paths across areasof high compression. In order to preserve anisotropy and high frequency details,we directly operate on the piece-wise constant tensor data rather than smooth itto a piece-wise linear field. We form new wrinkles by tracing this field startingfrom highly compressed regions, forming polyline-shaped wrinkle paths. We thenapply a simple smoothing post-process step to produce a smooth path for renderingpurposes. However, for temporal coherence, our wrinkle paths must persist fromframe to frame, so at each time step we also update our pre-existing wrinkle pathsto reflect the updated tensor field, while only allowing subtle adjustments to thepath. As our input meshes are coarse and not capable of capturing wrinkle detail,we use programmable GPU tessellation to adaptively generate wrinkle geometryand normals on the GPU. Taking advantage of programmable hardware in thisfashion enables us to generate cloth wrinkle animations on low-end animations ata sustained framerate of 60 frames per second, making it ideally suited for gameenvironments.This thesis’ first key technical contribution is a technique to address the lackof a reference garment shape in typical real-time animations, namely a temporallyadaptive reference shape. My approach makes no assumptions about cloth devel-opability, since real-time animations often deform non-physically either for styleor lack of computational resources [10]. It does not rely on parametrizations of5the cloth mesh, since the only parametrization typically available in game data isa texture map which would introduce distortion. It also requires no training data,which would limit its ability to handle novel animations and would make it labourintensive to add to an exisiting animation framework.This thesis’ second key contribution is a method for tracing spatially and tem-porally consistent paths through the compression field computed using the abovereference shape. By leveraging a simple tracing scheme and a least squares op-timization framework for the wrinkle update, my approach smoothly traces andupdates wrinkles from frame to frame, all at real-time speeds.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.6Chapter 2Related WorkRealistic cloth simulation has long been an area of interest in the graphics researchcommunity, starting with the foundational work of [1], and is of key importancein film, animation, and virtual environments [7]. Many of the issues addressed bycloth simulation, such as collision handling, are outside the scope of this thesis.My work falls in the category of “wrinkle augmentation” research, which attemptsto refine a coarse cloth simulation with fine details.In mechanics, the wrinkling effect of a physical compressive force applied toa thin sheet of textile material is known as buckling and is particularly apparent insheets that strongly resist stretch and compression, where out-of-plane buckling isenergetically favorable to almost any in-plane deformation. Typical formulationsof cloth simulation with buckling produce a stiff set of equations due to the strongpenalty on stretch and compression that are both unstable and highly non-linear[6]. To address the problem of small time steps, Baraff and Witkin [1] add damp-ing forces and use an implicit integration approach. Since these damping forces areonly added to stabilize the numerical system and are non-physical, they add non-physical motion to the animation. Choi and Ko [6] remove these damping forcesby instead predicting the “post-buckling” shape of the cloth from the input forces,which they model as a circular arc whose dimensions depend on the input forcesand material. Then they fit the cloth to the post-buckling shape in a way that min-imizes their high order formulation of bending energy. English and Bridson [9]approach the problem of buckling by using non-conformal elements to eliminate7(b)(a)Figure 2.1: (a) Off-line wrinkling of simulated clothing using a user-providedreference shape [24]. (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.stretch and compression during simulation. By placing position variables on themidpoints of mesh edges rather than at vertices, they increase the number of sim-ulation variables (as the number of edges is approximately three times the numberof vertices in a triangulated surface), and the mesh has enough degrees of freedomto accurately represent cloth dynamics. However, since the solution only requiresadjacent triangles to meet at edge midpoints and not at vertices, the solution isnon-conforming. For rendering and collision handling, they construct a conformalmesh that closely matches their non-conformal solution. Thomaszewski et al. [25]build strain limits directly into the deformation model. By linearizing the GreenStrain Tensor, they can affordably compute the strain on each element in the sim-ulation. If an element’s strain excedes a material-based threshold, they computean additional velocity to apply to the element to rectify it. Wrinkle augmentationresearch has attempted to sidestep these problems by adding wrinkling and finedetail to cloth after the initial simulation is complete, which allows the simulation8to be much coarser, simpler, and cheaper.Real-Time Cloth Animation and Wrinkling Real-time cloth simulation for gamestypically uses a mass and spring system on a coarse mesh [19], connecting verticeswith simple springs designed to apply shearing and bending forces while maintain-ing garment structure. These mass and spring systems form a series of differentialequations that are typically integrated using a simple integration method like theEuler method, or something more stable, as proposed by Verlet in [26]. Whilethe Euler method uses a simple forward difference scheme to approximate the firstderivative, Verlet uses a centered difference scheme to approximate the secondderivative and thus has smaller error. More specifically, the Euler method is firstorder accurate while Verlet is second order accurate.A detailed example of a cloth simulation in a commercially available videogame is discussed by Enqvist [10]. They simulate cloth through a mixture ofskinning and mass-spring systems. Extra damping is applied when the cloth isin contact with the underlying collision surface , i.e. the human body underneaththe garment, to simulate friction, and all equations are integrated using the Verletscheme [26]. This, and other typical real-time cloth simulation methods operate onvery coarse and crude meshes, e.g. 600 to 800 vertices [27]. This is too coarse toaddress wrinkling or buckling in any part of the simulation as there simply aren’tenough vertices to represent the shape of a wrinkle; wrinkles must instead be addedusing a post-process augmentation step.Adding dynamic wrinkles in video games typically favours simple strategies.Oat [21] introduces artist-painted wrinkle maps designed to fade-in along key areasof the mesh as it stretches and compresses. Oat’s technique is limited in that itcan only represent simple blendings of two static wrinkle maps. As such, it cannotproduce the more complex, dynamic wrinkle states that occur in regions that do notoscillate between two predefined states (e.g. a shoulder, which rotates and movesin multiple directions), or novel animations that an artist may not have predicted.Looser fabric in particular is difficult to predict as it is often animated procedurally.Mu¨ller and Chentanez [20] attach a high-resolution “wrinkle mesh” to a coarsecloth simulation and run a static solver in parallel with the motion of the base meshto animate the fine-grained wrinkles. This solver moves vertices in the fine mesh to9preserve edge length, constrained by a fabric stiffness parameter and a maximumdisplacement parameter from prescribed attachment points on the base mesh. Thehigh resolution mesh can be stored and updated entirely on the GPU, affordinggreat performance. However, this approach requires a reliable reference shape andassumes the coarse cloth motion to be spatially and temporally smooth, which israrely the case for game-type cloth animations.Data-Driven Approaches A range of data-driven approaches add wrinkles tocloth meshes by utilizing information gained from offline physical simulations.Guan et al. [13] parametrize the human body by shape and pose. Then, theyconstruct training data of fine-detail physical simulations of cloth on characterswith known shape and pose parameters. This provides context to a learning al-gorithm, and thus allows it to construct deformational patterns when given novelbody shapes in similar poses. Their technique is limited to fabric surrounding anunderlying body, and does not apply to non-clothing items such as a flag or towel.Kim et al. [17] use a novel compression scheme to make the traversal of over 33gigabytes of cloth training data tractable in real time. As such, they are capableof constructing much more comprehensive, robust training sets. However, like theprevious approaches, they are dependent on a reliable reference shape and smoothanimation inputs.Zurdo et al. [28] remove the reliance on an underlying animation skeleton orcharacter pose information, but instead rely on a more complex training set. Similarto Mu¨ller and Chentanez [20], they utilize two meshes: a coarse mesh and a finemesh. They perform offline physical simulations on both inputs to comprise thetraining set, constraining the simulations so that the resultant animations remain“close” to each other. Then, for each frame at runtime, they compute weights foreach of the coarse training sets. They construct fine wrinkles by applying theseweights to a linear interpolation of the coarse sets’ respective fine sets.Kavan et al. [16] use a learning method to “upsample” coarse cloth simulationsin real-time, using harmonic basis functions learned offline on sample animations.Again, they employ a combination of coarse and fine training data, and constrainthe fine mesh to remain “close” to the coarse mesh. The upsampling operators arelinear, so performance is fast. While the harmonic basis functions represent larger10scale cloth folds well, they do not represent finer details well.Wang et al. [27] develop a model specific to tight fitting clothing only. Withthis assumption, they can utilize the configuration of the human body’s joints topredict wrinkles. More specifically, they assume that the wrinkles in a given posewill be the same, regardless of how that pose was reached. The training stage ofthe algorithm learns what wrinkles appear in the regions around a joint given itspossible configurations. Then at runtime, the joints’ local regions are wrinkledfrom the training data, then merged together to form the global mesh. This workis only suitable for tight-fitting clothing, and does not support loose clothing suchas dresses or skirts.Hahn et al. [14] combine machine learning with a dynamically updated sub-space basis to produce impressive wrinkling and torsional folds, but this approachis not fast enough for real-time applications; it requires close-fitting clothing riggedto a skeleton, a reference 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. Moreover, theconstruction of the training data requires a reference shape, so the training datawould not map well onto the inputs this thesis operates on. Our framework doesnot require training data or a reference shape.Offline Wrinkle Augmentation Bergou et al. [2] use constrained Lagrangian me-chanics to add physically-based details such as wrinkles to an artist animated thinshell, such as cloth. These constraints stop the output mesh from deviating veryfar from the input mesh, while the Lagrangian mechanics force the animation to be“as physical as possible.” The advantage of this technique is that it allows muchmore artistic control over the cloth animation and wrinkles while still remainingphysical. However, it is not real-time, and requires a reference shape to computeforces. This idea was later refined by Re´millard and Kry [22]. They embed the thinshell in a three dimensional lattice, allowing them to approximate the dynamics ofthe interior of the thin shell. When the solid compresses above a material-specificthreshold, they buckle the thin shell along sinusoidal profiles to form wrinkles.This method has the same drawbacks as Bergou et al.11Rohmer et al. [23, 24] compute a smooth stretch tensor field between the ani-mation frames and a reference garment shape. They compute wrinkle paths initiallyby tracing the tensor field lines, and update them at each frame to match the newtensor field, explicitly preventing drastic deviation from the previous frame. Toform wrinkle geometry along these paths, they refine the surface in the region ofinfluence of the wrinkle paths. They model wrinkle shape using generalized cylin-ders, and employ an implicit deformer to deform the refined mesh to the cylinder.This method requires a rest shape and high quality animation. More specifically,the animations must be physically based for the stretch tensor field to be an accu-rate indicator of compression.We are inspired by this work in our use of a stretch tensor field on the meshto measure deformation; however we do not assume the existence of a valid ref-erence frame nor expect the garment motion to be smooth. Rather, we employ agraph labeling strategy to detect deformation trends in the animation, and use thisinformation to construct our temporally adaptive reference shapeLabeling Problem and Graph Cut To construct my temporally adaptive rest pose,I first determine an indicator or label for each triangle in each frame of what localdeformation it is experiencing. This can be formulated as a labeling problem, andis summarized briefly here but discussed at length in chapter 4.A labeling problem is the problem of assigning a label to each node on a graphin a way that minimizes an energy function typically composed of two terms: a sumof unary cost functions, namely the cost of assigning each node its label; a sum ofbinary or edge cost functions, namely the cost of assigning labels to adjacent nodes:∑i∈NA(i, li)+ ∑(i, j)∈EB(li, l j) (2.1)Typically, the unary cost is constructed to encourage each node to fit local data,while the binary cost is constructed to encourage smoothness between neighboursin the labeling.This problem as described can be solved via a graph-cut framework, as shownby Boykov, Komolgorov, et al. [4, 5, 18].A graph-cut on a graph with two terminal nodes (nodes which are adjacent to12every non-terminal node) is a list of edges in the graph which, when removed, sep-arate the graph into two disjoint subgraphs each connected to a different terminal.A minimum cut is one whose severed edges have minimum total cost. Ford andFulkerson [11] show that the minimum cut problem is equivalent to finding theminimum flow in a network, and can be solved in polynomial time.When there are more than two terminals, this problem is naturally referred toas the multiway cut problem. Dahlhaus et al. [8] show that it is NP-Hard, and thuswe are forced search for approximate schemes. An effective approximate solution[4, 5, 18] is discussed in chapter 4.13Chapter 3OverviewThis thesis addresses two primary components I developed for [12], namely theconstruction of a temporally adaptive reference shape by leveraging a graph-cutlabeling process, and spatiotemporally consistent wrinkle tracing and adjustment,all done at real time frame rates. The nature of typical real-time animation inputsmakes these problems difficult and interesting. We cannot directly utilize the sur-face animation because it is too spatiotemporally coarse and nonphysical, and hasno static reference frame from which to measure any useful deformational infor-mation. Our key insights to guide the temporally adaptive reference shape con-struction and wrinkle tracing and adjustment are as follows. First, since we aim forbelievability rather than physical correctness, we note that local movement is a pri-mary factor in human prediction of wrinkle appearances. As a surface compresses,we expect the surface to buckle in the formation of wrinkles, and as it releasescompression, we expect those wrinkles to dissipate. This will guide our referenceshape construction. Our second key insight is that real-life wrinkles are persistentand adapt gradually and smoothly over time. Any wrinkle tracing and adjustmentprocedure must adhere to this information to remain believable.Guided by these insights, we measure local surface deformation to inform ourtemporally adaptive reference shape construction (Chapter 4). However, relyingon this information in its raw state alone is vulnerable to the spatiotermporal noisecommon in real-time inputs (see Figure 3.3). Instead, we use local deformationaldata to produce a labeling of the mesh, with a label for every triangle in every frame14(a) (b)(c) (d)Figure 3.1: A pipeline-diagram of the algorithm components addressed bythis thesis. The main components are: (a) input animation frames; (b)compression(blue)/stretch(red)/neutral(green) labeling (Chapter 4); (c)local stretch tensors shown by oriented ellipses (Chapter 5); (d) tempo-rally coherent wrinkle paths (Chapter 5).15(a) (b)Figure 3.2: The remaining algorithm components largely developed by Rus-sell Gillette, included for completeness: (a) final wrinkled cloth ren-dered at real time without and (b) with texture (Chapter 7).Rest 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.16Figure 3.4: On coarse meshes smoothing the piece-wise constant tensor field(left) to generate a piece-wise liner 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.(Chapter 4.1). We formulate this labeling problem as a graph-cut problem, whichdetects coherent, local contraction and stretch paterns. This graph-cut segmenta-tion assigns meaningful labels to each triangle that identify the local deformationwhile incorporating the deformation of neighbouring triangles, which encouragessmoothness and consistency. The solver we use [4, 5, 18] is fast (0.92 - 1.74 ms perframe on our inputs), and is independent of the rest of the wrinkling process. Wetherefore run it entirely in parallel to the rest of our method, and it has negligibleeffect on the overall performance.With a reference shape in hand, we can compute the stretch tensor across thesurface at each frame. Ideally, we would smooth this constant-per-triangle fieldto the vertices and create a continuous field through barycentric interpolation (assuggested by [24], for instance). However, this results in a significant loss of in-formation (See Figure 3.4), and can be prohibitively expensive for real time meth-ods. Instead, we directly trace wrinkles through highly compressed regions in theconstant-per-triangle field, where compression magnitude and direction are mea-sured with the stretch tensor computed against the reference shape (Chapter 5, Fig-ure 3.1, d). This generates a polyline-shaped path that we smooth in a post-processstep. For smooth and gradual temporal persistence, we optimize each wrinkle’sadjustment over time, balancing alignment with the compression field and spatialand temporal smoothness (Figure 5.2).The last step in our algorithm for wrinkle generation was largely developed byRussell Gillette, which I will summarize here for completeness. We smoothlywrinkle the garment surface along the traced paths in real-time (Chapter 7, Figure173.2, a). Existing wrinkling methods directly modify the animated mesh; to capturefine wrinkles they either require the input mesh to be sufficiently fine to representwrinkle geometry, or perform on-the-fly mesh refinement to adequately capture thewrinkles [20, 24]. Both approaches require significant memory and time overhead.Instead, we employ the tessellation shader to generate high-resolution wrinkle ge-ometry on the GPU. We further improve the believability of the wrinkles by com-puting normals in the fragment shader to correctly shade the wrinkled material atan even higher resolution than the tessellated geometry. The combined methodgenerates believable wrinkles (Figure 3.2, b) at a real-time speed of over 60 framesper second on typical inputs (Chapter 8).18Chapter 4Compression Field Construction4.1 Compression Pattern ExtractionAs discussed earlier, the first step in computing a reliable stretch tensor field suit-able for wrinkle tracing is to locate the regions on the surface which undergo no-ticeable compression or stretch (Figure 4.1). The first indication of such changesoccurring is the purely local deformation of an individual triangle within any givenframe with respect to the previous frame; we may classify this behaviour as com-pressing, stretching, or resting. The strongest cue for this classification is givenby the stretch tensor of the affine transformation between the two triangles (Sec-tion 4.1.1); the indicated amounts of compression and stretch provide a local mea-surement of surface behavior. However, while real-life cloth deformation is typi-cally both spatially and temporally smooth, meshes for video games are typicallycoarse and the animation may be noisy, with artifacts such as inter-surface penetra-tion and jitter. For example, a triangle may undergo both compression and stretchin perpendicular directions. On such inputs, these raw measurements are unreli-able indicators of global surface behavior (Figure 4.1, b). Therefore rather thanusing the stretch and compression magnitudes directly to classify the current stateof the mesh triangles, we use this data as input to a more sophisticated labelingprocess which balances these measurements against a preference for spatially andtemporally continuous labels (Figure 4.1, c).19(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.4.1.1 Triangle Stretch TensorGiven a pair of current and reference triangles we measure the stretch and com-pression of the transformation between them using the stretch tensor from con-tinuum mechanics [3]. Given a current triangle in 2D with edge vectors (u1 =(v1− v0),u2 = (v2− v0)), and a reference triangle with edge vectors (u¯1, u¯2), wedefine the Deformation Gradient 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 has several important properties. First, assuming the triangle and itsreference triangle are not degenerate, the matrix is always well defined (That is, theinverse always exists in equation 4.1, and there always exists a unique positive def-inite square root in equation 4.2). Second, it is symmetric positive definite, which(excluding multiples of the identity matrix) guarantees two unique eigenvalues andeigenvectors. Last, the eigenvectors indicate the directions of maximal compres-sion and stretch, and their corresponding eigenvalues (λmin and λmax respectively)20are the ratios of compression to rest length and stretch to rest length along thosedirections. We define and employ λ˜min = 1/λmin through the rest of this thesis,as we find it more natural to work with. λ˜min is 1 when there is no compres-sion and grows as the triangle compresses, approaching infinity as a triangle edge’slength approaches zero. Similarly, λmax is 1 when there is no stretch and grows asthe triangle stretches, approaching infinity as a triangle edge’s length approachesinfinity.4.1.2 Graph Cut FormulationWe wish to solve for a label l ∈ (C,S,R) per triangle, per frame, where C indicatescompression, S indicates stretch, and R indicates a neutral rest state. We formulatethe problem of triangle labeling using a graph cut framework.We construct a graph G = (N,E) in which each node i ∈ N is a tuple ( f , t),where f is a face in the mesh and t is a time step in the animation. Each node hasthree spatial neighbors (the three adjacent triangles in the mesh at time t) and twotemporal ones ( f in frames t − 1 and t + 1). Nodes representing triangles alongmesh boundaries as well as those in the first or last frames have fewer adjacencies.For each node i ∈ N we compute a unary cost for assigning it a particular labelli, 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)21λ˜minλmaxCompression Cost0.9 1 1.1 1.2λ˜minλmaxRest Cost  0.9 1 1.1 1.2 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.The stretching and compressing costs are defined symmetrically using the auxiliaryfunction c(a,b), where a and b are stretch tensor eigenvalues: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 not22immediately transition from compression to stretch without at some point resting;we therefore assign a higher cost of 0.4 for assigning C and S labels to adjacenttriangles and a lower cost of 0.2 for assigning them the R and either C or S labels.We use the same costs for both temporal and spatial adjacencies. We solve thelabeling problem using the solver of Boykov, Komolgorov, et al. [4, 5, 18], whichefficiently minimizes Equation 4.3. We present a summary of the method in thenext section.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.1.3 Graph Cut SolverWe will now discuss how the labeling problem can be framed as a multiway-cutproblem, and how to approximately solve this problem through an effective opti-mization scheme. We omit proofs that the cut solutions that compose the optimiza-tion scheme exactly solve the labeling, as it is largely intuitive. For more rigor,we refer the reader to [5] where these ideas are drawn from. The labeling problemcan be formulated as a minimum multiway cut on the graph Gmulti constructed asfollows:• Add every node and edge of G. These edges between the original nodes iand j are assigned the weight B(li, l j).• Add a terminal node representing each label, and add edges between eachterminal node and each non-terminal node. These edges have weight Ki−A(i, l), where i is the non-terminal node, l is the label representing the termi-nal node, and Ki > maxl′(A(i, l′)) is a constant.23213412 34αβK2 − A(2, l2) K3 − A(3, l3)K1 − A(1, l1)K4 − A(4, l4)B(l1, l2)B(l1, l3)B(l1, l4)K2 − A(2, l2)K1 − A(1, l1)K4 − A(4, l4)K3 − A(3, l3)Figure 4.3: The graph dual of a simple mesh surface patch.Figure 4.3 illustrates this graph dual.The minimum multiway cut on Gmulti partitions the nodes into subsets con-nected to only one terminal node. Each node is assigned the label correspondingto its connected terminal node, and this labeling minimizes the energy in equation4.3. As stated in Chapter 2, this problem is NP-Hard, so Boykov, Komolgorov,et al. take an iterative optimization approach that employs a more easily solvablegraph-cut problem at each step.24To start, let the graph G be assigned an arbitrary labeling. A naive optimiza-tion technique would be to repeatedly find one node whose label could be switchedto reduce the energy in equation 4.3 until convergence. However, with such asmall optimization step (that is, the labeling before and after an optimization stepis largely the same), this is likely to converge to a suboptimal local minimum.Instead, Boykov, Komolgorov, et al. define two optimization steps that adjust mul-tiple labels at once. The first step they define is called an αβ -swap. An αβ -swapstep from a labeling l is any labeling l′ where any node with label α or β in l iseither α or β in l′. Any node not labeled α or β in l must remain the same in l′.The second step they define is called an α-expansion. An α-expansion step from alabeling l is any labeling l′ where any node with label α must remain the same in l′,and any node not labeled α in l must remain the same or swap to α . They guaranteeconvergence of their solver using αβ -swaps when B from equation 4.3 is a semi-metric - it is commutative, non-negative, and only zero when the inputs are equal.They guarantee the convergence of their solver using α-expansion when B is a met-ric (that is, a semi-metric that also satisfies B(α,β )≤ B(α,γ)+B(γ,β ),∀α,β ,γ).In the case of the α-expansion algorithm, the solution is within a constant factor ofthe optimal energy (given our B function, this factor is 4).To find an optimal αβ -swap step, they define a graph Gαβ as follows:• Add every node labeled α or β in G, and add edges between nodes if theyare adjacent in G. Assign weights B(α,β ) to these edges.• Add terminal nodes representing labels α and β , and add edges betweenthese and every non-terminal node. Assign weights A(i,α) or A(i,β ) ac-cordingly to each of these edges, where i represents the non-terminal nodein the edge.Figure 4.4 illustrates the graph Gα,β .The minimum cut on Gαβ represents the minimum energy within a single αβ -swap step of the current labeling l.To find an optimal α-expansion step, they define a graph Gα as follows:• Add every node in G regardless of label25α γα βαααββB(α, β) B(α, β)B(α, β)A(2, α)1234123A(1, α)A(3, α)A(1, β)A(2, β)A(3, β)Figure 4.4: The graph Gαβ , constructed from G26– If two nodes i, j adjacent in G have the same label, add an edge betweenthem. Assign weight B(li,α) to this edge. Note that since i, j have thesame label, li = l j.– If two nodes i, j adjacent in G do not share a label, add an auxilliarynode k, and add edges (i,k) and (k, j). These edges have weight B(li,α)and B(l j,α) respectively.• Add an α-terminal node representing the label α and an α¯-terminal noderepresenting all other labels.– Add an edge between each non-auxilliary node i and the α-terminalwith weight A(i,α).– Add an edge between each non-auxilliary node i and the α¯-terminalwith weight A(i, li) if li 6= α , ∞ otherwise.– Add an edge between each auxilliary node k and the α¯-terminal withweight B(li, l j), where i, j are the two non-auxilliary nodes adjacent tok.Figure 4.5 illustrates the graph Gα .The minimum cut on Gα represents the energy within a single α-expansionstep of the current labeling l.The optimization scheme iteratively takes either αβ -swap or α-expansion stepsby solving their appropriate graph-cut problems above until the energy determinedby evaluating equation 4.3 converges. The choice of which labels to use for α andβ can be sequential or random.4.2 Local Reference TrianglesTo generate a stretch tensor that guides our wrinkle formation we require a localreference shape. Since no such shape is provided a priori we compute one on-the-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,27α γ α α β β αα γ α α β β ααα¯k k k k1 2 3 4 5 6 7∞∞∞∞B(α, α) B(β, β)A(i, α)B(α, α)B(β, α)B(γ, α)A(i, β)A(i, γ)B(α, γ)Figure 4.5: The graph Gα , constructed from GFigure 4.6: Evolution of reference triangles (bottom) throughout the anima-tion process.28in real-life data triangles can and do stretch due to noise and animation inaccu-racy. Our on-the-fly rest triangle estimation (Figure 4.6) 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.Stretch Label We expect a stretching label to reflect a dissolving compressed,or wrinkled, triangle. In this configuration if both eignevalues of the stretch tensorfrom the reference to the current triangle are larger than one they indicate a stretchbeyond the current reference triangle. We interpret this configuration as dissolv-ing of previously undetected compression wrinkles. We consequently replace theprevious reference triangle with this, new, less compressed one. Since we aim toenrich the rendered garments, we prefer to err on the side of overestimating thereference triangle size, thus we use no smoothing or averaging in this scenario.Compression Label If a triangle is labeled as compressed we theoreticallycould leave its reference triangle unchanged. However, since our animations areoften non-physical, triangles may adopt overly stretched outlier configurations astheir reference shape throughout the animation. Thus when a triangle is assigneda compression label, we choose to dampen the reference triangle size, relaxing ittoward the current mesh triangle. In order for our tensor field to remain smooth andconsistent with neighbouring triangles and previous frames, the relaxed referencetriangle must produce the same eigenvectors, but smoothly altered eigenvalues.We therefore directly modify the eigenvalues of the stretch tensor, and then solvefor reference triangles that generate the updated stretch tensor, as follows.Let F = AΣBT be the singular value decomposition of the deformation gradi-ent (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 regularized eigen-values, that lie closer to 1 by setting Σ′ = 0.95Σ+ 0.05I, here I is the identitymatrix. We construct a new Deformation Gradient F ′ = AΣ′BT and compute the29new reference triangles as[u¯′1, u¯′2] = F′−1[u1,u2] = BΣ′−1AT [u1,u2].Rest Label If a triangle is currently labeled as being in a rest state, we leaveits reference triangle as is with no adjustment. This choice results in wrinkles thatpersist unchanged through periods of the animation with little deformation, suchas a character holding a fixed pose.Without the labeling, the naive strategy to achieve similar behaviour wouldbe to perform the same reference triangle updates as above, but selected basedon raw eigenvalues rather than labels. Unfortunately, this would have negativeartifacts. It is common for triangles to undergo both stretch and compression (inperpendicular directions) on coarse inputs when compared to the previous frame(See Figure 4.1b). The interleaved red and blue triangles indicate that the regionis undergoing both compression and stretch). This makes it difficult to determinewhether a stretch or compression reference triangle update should be performed.These updates are very different, and a region where similar triangles undergodifferent updates will consequently have inconsistent reference triangles, and byextension, an unreliable compression field. The labeling strategy is essential formaintaining this consistency.30Chapter 5Wrinkle Path TracingThe ideas presented in this chapter were developed jointly between Russell Gilletteand myself. The Wrinkle Initialization section was largely developed by Russell,while the Temporal Persistence section was largely developed by me, though wecollaborated throughout.The first step in creating wrinkles is tracing their paths on the mesh surfacebased on the stretch tensor computed with respect to the local reference shape. Ourcomputation builds on many of the ideas described by Rohmer et al [24]; however,in contrast to their formulation that assumes that the tensor field is piecewise linearand smooth, we modify the framework to operate directly on a piecewise constantfield. The reason for the change is illustrated in Figure 3.4: since the meshes weoperate on are exceedingly coarse, converting the per-triangle tensors into a piece-wise linear field (averaging the tensors at the vertices using tensor arithmetic [24]and then using barycentric coordinates to define values across triangles) smoothsout critical details. We refer the reader to [24] for fine details on the wrinkle pathtracing and here focus on the overall process and the main points of differencebetween the two algorithms.5.1 Wrinkle InitializationWrinkles are placed in areas of high compression and are traced orthogonally tothe direction of maximal compression. At each time step in the animation, we seed31new wrinkles at random locations within highly compressed triangles (where λ˜ iminis greater than compression threshold τ), keeping the seeds at least a wrinkle widthaway from previously generated paths to prevent wrinkle overlap, which does nothappen with real wrinkles. The computation of wrinkle width is discussed in Sec-tion 6. We then initialize the path by propagating a polyline across the mesh surfaceorthogonal to the maximal compression direction within each triangle. The prop-agation terminates once the compression magnitude drops below the compressionthreshold τ . It also terminates if the propagated path intersects another wrinklepath. The parameter τ is set to reflect the desired fabric stiffness [24]; the expecta-tion is that thinner fabrics, e.g. silk, will be more sensitive to compression and willalso exhibit more and longer folds than thicker and stiffer materials such as woolor leather [15].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 space ofthe garment. To mimic this behavior and eliminate undesirably sharp changes inwrinkle direction, we apply one iteration of tangential Laplacian smoothing to eachpath after tracing it, moving each intersection of a path with the mesh edges alongthis edge toward the shortest geodesic between the adjacent intersections (see fig-ure 5.1).5.2 Temporal PersistenceReal-life wrinkles are persistent, changing their shape and position gradually overtime. To mimic such persistence, instead of regenerating wrinkle paths in eachframe from scratch, we first adjust existing wrinkles accounting for both the extrin-sic and intrinsic deformation the garment undergoes between frames (Figure 5.2),32Figure 5.1: A smoothed wrinkle (purple) between the input wrinkle (blue)and geodesic path (orange).Frame 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).33Figure 5.3: An example wrinkle updated to better match a new fieldand only then add new wrinkles away from the evolved ones.A light-weight approach used by Rohmer et al. [24] is to move wrinkle seedpoints based on changes in the stretch tensor field and then repropagate the wrinklepaths from scratch. However on coarse meshes using this approach can drasti-cally move the traced wrinkles following even minor directional change in the field(see figure 5.3). To achieve the desired temporal persistence while accounting forchanges in the stretch field directions and magnitudes we employ a global opti-mization framework.We represent each wrinkle path as a polyline whose vertices lie on the edgesof the garment mesh, and encode them as linear combinations of the edge endvertices: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−1 at endpoints34where 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.The first sum in equation 5.2 encourages compliance with the new compres-sion field. This sum vanishes either when the polyline segment is aligned withthe compression field, or has zero length. However, the second and third sums dis-courage a zero length solution. The second sum vanishes when points remain in thesame location, which keeps the polyline from changing drastically between frames.The final sum encourages the polyline to maintain a similar shape to the previousframe. The vector pi− (pi−1+ pi+1)/2 encodes the relative positioning of pi withrespect to its neighbours. Thus, the sum vanishes when the relative positioning ofthe polyline points remains the same. We initially used only the first two sums, butfound that long lasting wrinkles tended to move away from a more natural lookingwrinkle shape, e.g. introducing a small kink segment in the polyline that is poorlyaligned with the field, but allows the rest of the polyline to align well.While the solve constrains the vertices to lie on the straight line defined bytheir currently associated edges, we avoid explicitly constraining ti to the [0,1]interval as we want to allow wrinkle paths to slide beyond mesh vertices. If andwhen a computed ti lands outside the [0,1] interval, we locate the best positionfor the vertex and its neighbours on the mesh as follows. To compute the vertexposition we parameterize the umbrella around the relevant edge endpoint (v1i ifti < 0 and v2i if ti > 1) into 2D. Then, we place pi using Equation 5.1, but usingthe positions of v1i and v2i in the 2D parameterization, constraining it to within theumbrella triangles if ti is too extreme (though this never occurred in practice). Wethen place pi−1, pi+1 in the 2D parameterization using Equation 5.1. Lastly, weadd path vertices at the mesh edge intersections with straight lines from pi−1 to piand pi to pi+1 (see figure 5.4).Lastly, if and when more than one wrinkle path vertex lie 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 the same mesh geodesic schemeused above to update the new set of intersections (see Figure 5.5). Without this35Figure 5.4: A reconstructed polyline as a t value lies outside the [0,1] inter-val.modification, the locations of the vertices become over constrained as a movementin their individually preferred directions would lead to path self-intersection.Length Update As a cloth garment deforms, wrinkles can grow and shrink inlength. To replicate this process for each frame in the animation, we extend or trimall existing wrinkles based on the magnitude of the underlying stretch field, usingthe same compression threshold τ . To maintain temporal continuity, we do notchange the length of a wrinkle by more than 15% per frame.36Figure 5.5: An example of removing points from the optimization. If all threeinterior points were included, then they can only cross the mesh vertexby creating a self-intersecting loop in the wrinkle, which produces ahigh cost in equation 5.3. Thus, we remove all but one vertex and re-construct the neighbourhood after a solution is reached on the smallerproblem.37Chapter 6Wrinkle Shape ParametersThe ideas presented in this chapter were developed largely by Russell Gillette, andare reproduced here for completion.To generate actual wrinkle geometry from the traced wrinkle paths, we need toassign a target wrinkle height and width to each point along a path and generateappropriate cross-sectional geometry across it. We follow Rohmer et al. [24] inour computation of wrinkle height and width, using a formula that accounts for thematerial properties and the amount of compression along the wrinkle. Intuitively,the more flexible the material the higher the wrinkles are expected to be, and thehigher the amount of compression the larger the ratio between the cross-sectionlength and the cross-section width should be. Given a user-specified minimal wrin-kle radius Rmin the radius of a wrinkle as a function of compression magnitude isset to (1−2/pi)/λ˜minRmin. The wrinkle local width and height are then expressedvia the radius as described by Rohmer et al. [24].Figure 6.1: The parameters defining the cross-sectional contour of a wrinkle.38Figure 6.2: The final shape of the cross-sectional contour of a wrinkle.Our framework differs from Rohmer et al.’s, in that the compression field weoperate on is piece-wise constant instead of piece-wise linear. Using pointwisemagnitudes on this input results in discontinuous wrinkle dimensions. Instead weuse the maximal compression along a wrinkle path to obtain the maximal wrinkleperimeter and height, and the corresponding width, see figure 6.1; here the widthis 2r and the perimeter is 2r/(1− λmin). We then use these values as wrinkleparameters at its mid-point. At the wrinkle end points we set the width to be equalto the perimeter, and smoothly interpolate the width along the rest of the wrinklepath. We then use these width values to compute pointwise wrinkle height. Notethat when the width is equal to the perimeter (at the end points) the height is, byconstruction, zero. This computation leads to smooth naturally dissolving wrinkleshapes along each 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. To achieve thiseffect we define wrinkle cross-sections using a quadratic B-spline (see figure 6.2).We also smooth out the path of each wrinkle, replacing the linear segments withineach mesh triangle with Bezier paths whose tangents across triangle edges are set tothe average 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.39Figure 6.3: Left to right: wrinkles rendered using only normal maps; tessel-lated wrinkle region; wrinkles rendered using displacement (tesselation)and normal maps.40Chapter 7Fast GPU-Based WrinkleModelingThe ideas presented in this chapter were developed largely by Russell Gillette, andare reproduced here for completion.Embedding 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 occupythe 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 6.3). Our approach which leaves the original mesh unchanged al-lows for wrinkle rendering to be enabled or disabled as the character moves furtheraway from the viewer.41Figure 7.1: Projection of a point p to the winkle segment vivi+1.Wrinkle Geometry We use the tessellation shader to subdivide each mesh trianglethat falls within the radius of influence of a wrinkle path (Figure 6.3, b). We uploada list of wrinkles affecting each triangle in each frame, and a triangle is tessellatedonly if it has a non-empty wrinkle list. We use a uniform tessellation scheme, and atarget edge length that is half of rmin. We then offset each vertex in the direction ofthe triangle normal according to the cross-section height at that point. To computethe height at a point p we project that point on to the wrinkle path, evaluate thewrinkle height and width at that point, then use the B-spline shape function todetermine 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.1 top), leadingto discontinuities in the offsets. We avoid such discontinuities by using a modifiedprojection (Figure 7.1). 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.42Figure 7.2: Result without (left) and (with) wrinkle blending.Wrinkle Normals In the fragment shader, we use the method above to obtain theprojected path points and corresponding widths on adjacent wrinkle paths, and usethe B-spline formula to obtain an analytic normal. We shade the wrinkles usingPhong shading, using this computed normal in the fragment shader and directlyevaluating the lighting equation per-pixel. Other shading methods, such as Minn-eart shading and physical based rendering models, could be computed on the samenormal data.Blending One of the main challenges when modeling wrinkles is to believablyhandle cases where wrinkles come close by or overlap. We found that the follow-ing simple heuristic generates visibly believable results while avoiding time con-suming explicit geometry blending (Figure 7.2). For each tessellation vertex whichis within the radius of influence of multiple wrinkle paths, we compute the offsetindependently for each path and then use the maximum of the offsets as the newoffset. For each pixel which is within the radius of influence of multiple wrinklepaths, we compute both offsets and normals independently per path. We generatethe final normal by averaging these per-path normals using the computed offsets asweights.43Chapter 8ResultsWe demonstrate our method on a range of meshes and animation sequences, mostof which are taken from currently shipping video game titles. Our method plausiblyadds believable, temporally coherent wrinkles to low-resolution character meshesand geometry (Fig. 8.5 - 8.10 and elsewhere in the paper.). The skirt example(Fig. 8.9) was provided courtesy of Kavan et al[16] and is created using coarsephysics-based simulation.Parameters The two tunable parameters in our system are compression sensitiv-ity τ and minimal wrinkle width Rmin. Both are linked to the expected materialproperties – how easily the modeled fabric bends and how wide the wrinkles areexpected to be. Compression sensitivity may also depend on the quality of theanimation – one may choose to use a higher sensitivity threshold if the animationis more noisy and exhibits more spurious tangential motion. Figure 8.1 shows theimpact of changing the parameter values. Table 8.1 list the numbers used for theanimation sequences shown in the paper.Performance Table 8.1 shows the run-time performance of our algorithm on var-ious meshes, as well as the mesh triangle counts and wrinkle parameters used.All times are computed on an Intel Core i7-3930K CPU running at 3.2 GHz, with32 GB of RAM and an NVIDIA GeForce GTX 670 graphics card. Frames wererendered at a resolution of 1920x1080.44τ = 1.15Rmin= 0.5%τ = 1.25Rmin= 0.5%τ = 1.15Rmin= 1%τ = 1.25Rmin= 1%time = 69ms time = 33ms time = 22ms time = 12msFigure 8.1: Impact of different choices of parameter values τ and Rmin.Animation τ Rmin # 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 8.1: Performance statistics for various models processed with our al-gorithm. Rmin computed as percent of character height. All times inmilliseconds.45(a) (b) (c)Figure 8.2: Left: Artist drawn static texture and our wrinkles without (center)and with same texture (right).Figure 8.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.Graph Cut Results The efficacy of our graph cut approach can be seen in Fig-ures 8.3 and 8.4. The labels chosen without a graph-cut strategy are inconsistent,and provide no information beyond what the single-frame stretch tensor provides.Utilizing graph-cut produces a much smoother labeling, which in turn providesreliable inputs for our temporally adaptive rest pose update.Comparison to Alternative Strategies We validate our algorithmic choices againstthose used by previous work throughout the paper. Figure 3.3, (top) highlightsthe infeasibility of employing one of the frames in an animation sequence as areference shape. Methods such as [20, 24] heavily rely on the existence of such a46Figure 8.3: Comparison of labels produced with and without Graph Cut. Top:The raw tensor values. Middle: The labels chosen without Graph Cut.Bottom: Our labels, chosen with Graph Cut.reference shape. Figure 3.4 motivates our use of a path tracing strategy designed tooperate on piecewise-constant instead of smoothed piecewise linear stretch tensorfields [24]. Our combined method is dramatically faster than that of Rohmer et alwho report speeds of over a second per frame.We also compare our method against the use of artist drawn wrinkles (Fig-ure 8.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.For video footage of our algorithm, please visit our project page:http://www.cs.ubc.ca/labs/imager/tr/2015/CoarseClothWrinkle/index.html47Figure 8.4: Comparison of labels produced with and without Graph Cut. Top:The raw tensor values. Middle: The labels chosen without Graph Cut.Bottom: Our labels, chosen with Graph Cut.48Figure 8.5: Sawing motion. Inputs on top, wrinkling results beneath.49Figure 8.6: Chopping motion. Inputs on top, wrinkling results beneath.50Figure 8.7: Fist pumping motion. Inputs on top, wrinkling results beneath.51Figure 8.8: Stretching motion. Inputs on top, wrinkling results beneath.52Figure 8.9: Jumping Jack motion. Inputs on top, wrinkling results beneath.53Figure 8.10: Shoveling motion. Inputs on top, wrinkling results beneath.54Chapter 9ConclusionWe present a practical method for adding real-time wrinkling to cloth surfaces.Our method operates in real-time, on arbitrary cloth meshes and animations, and issuitable for interactive wrinkling of cloth and fabrics for video games on current-generation and next-generation consoles and hardware. We overcome the chal-lenges presented by low-quality meshes and animations with no rest pose by firstsmoothly labeling the graph, and using this to construct a temporally adaptive ref-erence shape. Then we trace smooth wrinkle paths through the compression fieldcomputed against this shape, updating existing wrinkle paths each frame to bet-ter match the compression field while preserving temporal coherence. Lastly, weharness the GPU to refine and deform the mesh along the wrinkle paths to form awrinkle.Future work involves improvements to both performance and rendering qual-ity, as well as applying the technique on other wrinkling surfaces, e.g. human skin.Our method has a few limitations that merit further research. Our work addressesdynamic wrinkles – i.e. those whose presence is hinted at by the cloth motion;we do not address static wrinkles which humans often expect to be present in ar-eas of negative Gaussian curvature. This could be addressed effectively by eitherincorporating the curvature eigenvalues and eigenvectors into the labeling costsdiscussed in Chapter 4, or using them to construct a second labeling to adjust thereference shape after it has been updated by our existing labeling. Our method,like most previous work, generates outward bulging wrinkles - well suited for tight55garments. Future work should explore automatic selection of wrinkle directionconsistent with human expectations. Additionally, our method does not currentlyhandle stretch wrinkles, and incorporating this wrinkling is a source for future in-vestigation.56Bibliography[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 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 20[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 12, 13, 17, 23[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 12, 13, 17, 23[6] K.-J. Choi and H.-S. Ko. Stable but responsive cloth. ACM Trans. Graph.,21(3):604–611, 2002. → pages 7[7] 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 7[8] E. Dahlhaus, D. Johnson, C. Papadimitriou, P. Seymour, and M. Yannakakis.The complexity of multiway cuts. ACM Symp. Theory of Computing, pages241–251, 1992. → pages 1357[9] E. English and R. Bridson. Animating developable surfaces usingnonconforming elements. ACM Trans. Graph., 27(3):66:1–66:5, 2008. ISSN0730-0301. → pages 7[10] H. Enqvist. The secrets of cloth simulation in Alan Wake. Gamasutra, Apr.2010. → pages 4, 5, 9[11] L. Ford and D. Fulkerson. Flows in Networks. 1962. → pages 13[12] R. Gillette, C. Peters, N. Vining, E. Edwards, and A. Sheffer. Real-timedynamic wrinkling of coarse animated cloth. ACM Symposium on ComputerAnimation, 2015. → pages iii, vii, 2, 3, 14[13] 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 10[14] 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 11[15] J. Hu. Structure and Mechanics of Woven Fabrics. Woodhead PublishingSeries in Textiles. Elsevier Science, 2004. → pages 4, 32[16] 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 4, 10, 44[17] 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 10[18] 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 12, 13, 17, 23[19] J. Lander. Devil in the blue-faceted dress: Real-time cloth animation. GameDeveloper Magazine, May 1999. → pages 4, 9[20] M. Mu¨ller and N. Chentanez. Wrinkle meshes. In Proc. Symposium onComputer Animation, SCA ’10, pages 85–92, 2010. → pages 4, 9, 10, 18, 4658[21] C. Oat. Animated wrinkle maps. In SIGGRAPH Courses, SIGGRAPH,pages 33–37, 2007. → pages 9[22] 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[23] 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 12[24] 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, 4, 8, 12, 17, 18, 31, 32, 34, 38, 46, 47[25] B. Thomaszewski, S. Pabst, and W. Straer. Continuum-based strain limiting.Computer Graphics Forum, 28(2):569–576, 2009. → pages 8[26] L. Verlet. Computer experiments on classical fluids. i. thermodynamicalproperties of lennard-jones molecules. Physical Review, 159(1):98, 1967. →pages 9[27] 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, 11[28] 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 1059


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



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"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items