Next: 3. Cloth Simulation Experiments Up: thesis Previous: 1. Introduction Contents
Cloth simulation has been a topic of active research in the computer graphics community since it was introduced by Terzopolous et al. [102] in 1987. We refer the reader to Bridson's Ph.D. thesis [18] for an excellent overview of recent papers in the field, and to the second chapter [14] of Breen and House's book [52] for a broader overview of the modelling techniques used in the cloth simulation literature. See also Ng and Grimsdale's survey paper [82] for a more complete review of early cloth simulation methods. Each of these sources has a distinct interpretation, and we personally tend to agree more with Bridson's analysis than with Breen's approach.
Most cloth simulation techniques can be classified into three general groups: elastic deformation models, particle-based models and finite element (or continuum mechanics) models. We refer the reader to [5,38,39,103,114,117].
Feynman [42] treated cloth draping using a thin plate flexure model in his 1986 thesis. He modelled cloth as a grid of points, invented his own energy expressions for internal strain and bending resistance and then minimised the energy using a multigrid method.
In their 1987 and 1988 papers [101,102], Terzopolous et al. considered a range of types of deformable surfaces, including cloth. They gave a broad introduction to the theory of elasticity, and referred readers to texts in the calculus of variations. For their simulation, they used differential equations of motion and an implicit integration scheme, and they discretised the equations using a regular grid.
In 1992, Breen et al. [13,15,53] adopted a different formulation for cloth. They minimised energy functions in a manner similar to Feynman, but their energies were not derived from the assumption that cloth is a continuous flexible material, nor did they use elastic shells. Instead, they modelled the static drape of cloth using a set of interacting particles, and insisted that cloth is a mechanism, not a continuum. Each particle is intended to represent the crossing-point of warp and weft threads. This interpretation is problematic, since it makes computation intractable if every thread crossing-point must be simulated. In their demonstrations, a large tablecloth was modelled using a small number of particles (51×51), much less than the number needed to represent every thread crossing-point.
One interesting aspect of Breen et al.'s system was their consideration of material properties [16,17]. They used a Kawabata [66] system to measure the physical properties of real cloth, and used these material properties directly in their cloth simulation model. They observed that shearing behaviour (which they called trellising) was responsible for much of the differences between materials, and for maintaining constant surface area. Later work with DeVaul [34,54] extended the Breen algorithm to include dynamic motion. Finally, this group has also had extensive contact with the textile research community, including publication in journals in that field.
Members of MIRAlab have studied the problem of generating clothes for virtual actors over the last decade. The earliest contribution of researchers at MIRALab was Carignan et al.'s synthesis of a full set of clothing on a digital character in a 1992 paper [25], which was a first for computer graphics at the time. This paper described collision processing and garment panel stitching, and used Terzopolous' dynamics with added damping forces. In 1995, Volino et al. [107] represented the cloth mechanics using an elastic deformation model, but removed topological restrictions on the model by allowing an unstructured triangle mesh; a later 1997 paper [108] simplified their approach. More recent papers from the lab have covered a range of topics, including a comparison of integration methods [110], collision detection [109] and many other subjects [30,47,111].
In a 1995 paper, Provot [89,90] used a mass-spring model for cloth, which he correctly identified as a variant of the elastic deformation models. Provot made the important observation that traditional methods of cloth simulation produce a "rubbery'' appearance in the cloth motion. To get around this, most users set a high spring stiffness, but explicit integration of the resulting stiff system is slower. He introduced an ad hoc method to keep spring lengths constant, greatly reducing the elastic appearance of cloth motion. Provot also treated collision response in a later paper [91].
Researchers at the University of Tübingen have been studying cloth since the mid-1990s. Eberhardt et al. [37] improved Breen's method to include cloth motion. A later paper by Eberhardt [35] studied implicit-explicit schemes for animation using particle systems, while papers by Hauth et al. [49,50,51] compared the performance of a range of numerical methods and preconditioners. In an upcoming paper, Etzmuß et al. [40] establish a connection between continuum mechanics and particle systems. Finally, Etzmuß et al. [41] and Mezger et al. [79,80,81] studied collision response in some detail, and Eberhardt et al. [36] studied knit fabrics.
More recently, a 1998 paper by Baraff and Witkin [6,7] returned to the approach of Terzopolous et al., and introduced a new, more efficient technique for animating cloth and clothing. One major contribution of their scheme was an implicit integration scheme using a conjugate gradient solver. Since Terzopolous' work, researchers had used explicit integration schemes, leading to either "rubbery'' cloth movement or a stiff system that was hard to solve, as observed by Provot. By using an implicit scheme, Baraff and Witkin were able to take large timesteps and avoid "rubbery'' looking cloth. Baraff and Witkin's system also included position and velocity constraints on individual nodes, and they followed Volino's lead by using an unstructured triangular mesh. Their force model was based on energy functions, with bend forces calculated using the dihedral angle between adjacent triangles. They simulated cloth with more nodes than previous work, demonstrating one example with 8800 vertices. Unfortunately, their bending model and integration scheme required the introduction of nonphysical damping terms to reduce instability, and their system tended to remove fine wrinkles and geometric detail in the cloth.
Baraff and Witkin later extended [8] their system to solve the problem of cloth tangles when self-intersection occurs in character animation. Ascher and Boxerman [4] improved the efficiency of Baraff and Witkin's integration scheme, and demonstrated the convergence of their modified conjugate gradient method. Desbrun et al. [32,33,78] made major approximations to Baraff and Witkin's model to achieve realtime performance with a coarse cloth discretisation, and Kang et al. [61,62,63,64,65] made further approximations for the sake of speed.
Choi and Ko [27] addressed the issue of buckling in cloth. In their 2002 paper, they observed that the behaviour of cloth is quite different under compressive and tensile forces. Cloth strongly resists a tensile force, acting like a stiff spring to preventing stretching. Under a compressive load, however, it prevents compression by buckling. Choi and Ko used a heuristic model of the post-buckling shape of cloth, and introduced a more complicated spring model to separate compressive and tensile forces. They used an implicit integration scheme for efficient computation, but unfortunately required a structured rectangular mesh. A recent paper [28] addressed this limitation by extending their model to triangular meshes, and discussed instabilities in traditional formulations of shear forces.
Bridson et al. [19] initially tackled cloth collision processing. Most of their 2002 paper dealt with collision detection and response, and also with friction. To process the collisions, they also introduced a new integration scheme similar to central time differencing. They also adopted and corrected some of Provot's techniques.
In a recent 2003 paper [20], Bridson et al. treated problems more directly related to cloth simulation, focusing particularly on the preservation of wrinkles. They noted that fine tessellation of the cloth surfaces required small timesteps when damping forces were treated with an explicit integration scheme. To resolve this, they proposed an implicit integration scheme for damping forces combined with an explicit integration scheme for internal cloth dynamics, which also avoided the excessive damping of wrinkles seen in Baraff and Witkin's work. In the same paper, Bridson et al. introduced a new bending model, based on the angle between adjacent triangles in a manner similar to Baraff and Witkin. Much of their simulation model is similar to Baraff and Witkin's approach, except for a separated treatment of compression and tensile forces, an approach first used by Choi and Ko. They also treated further details of collision processing.
There have been a wide range of other interesting papers touching on cloth simulation. Van Gelder et al. [104,105] examined the relation between mass-spring models and elasticity theory. Parks and Forsyth [85] studied the generalised-α integration scheme. Hutchinson et al. [56], Zhang et al. [116], Volkov et al. [112] and Villard et al. [106] have studied adaptive refinement techniques. Aono et al. [1,2,3] studied the novel problem of "dart insertion'' in the aerospace industry, where cloth must precisely fit a particular surface shape without wrinkles. Li et al. [70,71,72,73,74] studied the motion of cloth in an air flow. Xu et al. [113] used a specialised rod-based model model to simulate curtain motion. Romero et al. [92,93,94] and Lario et al. [67,68] considered parallel algorithms for cloth simulation, and Zara et al. [115] looked at solving cloth simulation using a cluster. Fuhrmann et al. [43], Mezger et al. [79,80,81] and Huh et al. [55] all studied collision detection in cloth simulation.
Louchet et al. [75] were the first to attempt to recover cloth simulation parameters from motion data. They assumed that some unspecified vision system would provide their input data, which consisted of 3D positions of gridpoints on the cloth; for their tests, they used synthetic data. They used a genetic algorithm to solve an optimisation problem, yielding five unknown cloth simulation parameters. Their cloth simulator was a simple mass-spring system, and their input data was essentially a combination of geometric and parametric (fixed gridpoint) information.
Jojic [57,58,59,60] considered static draped cloth, whose shape is captured via a range scanner. The cloth range data was treated as a solid surface, and a cloth simulation was run to drape the cloth over the range data. An external force was applied to attract the cloth to the range data. The process was then repeated using different parameters until a solution was found, using an optimisation approach. For the cloth simulation, he used a simple mass-spring model. His error metric in the optimisation process included only distance from the range data.
Jojic's approach had several limitations. First, he treated only static simulation parameters and did not consider dynamic movement of cloth, although his approach might be extended to include dynamic behaviour. Second, he only made use of the cloth's geometry, and did not incorporate surface parameterisation data, apart from the manually detected corners of the cloth. Third, he made several assumptions about the cloth drape, including a known drape configuration (e.g., known underlying geometry). Finally, his results were mostly synthetic and were not very convincing, and he did not attempt to work with a range of fabrics.
Bhat et al. [11] adopted the same general framework as Jojic, using an optimisation technique to fit simulation parameters to range data. Their input was a video sequence under structured light, and they did consider dynamic behaviour, such as damping parameters. Their error metric was based on the fit to the video data, using both silhouette matching and a thresholded "angle map'' representing regions of high curvature or discontinuities. They used the cloth simulation algorithm introduced by Baraff and Witkin [6], but were forced to use explicit integration to avoid excessive damping. They also noted some problems with scale invariance of parameters in Baraff and Witkin's model, and suggested a new model for air drag forces.
Like Jojic, Bhat et al. did not make use of surface parameterisation in their optimisation, although they did present some useful data about the optimisation space. They did study a range of real-world fabrics, and also tested the generalisation of their measurements by synthesising new motion using the estimated parameters. Finally, they presented a comparison of complex synthesised motion and real cloth movement, although the results were not very convincing.
The effectiveness of Bhat et al.'s error metric is very unclear. In Figure 3 of their paper, they show angle map error as a function of the bend and stretch parameters, varied over one order of magnitude. In this figure, error seems to be almost independent of the bend parameter, implying that they cannot reliably measure this parameter. In Figures 8 and 9, they have a good match between the simulated cloth and the captured video of static cloth. In Figure 10, however, the match is much poorer for moving cloth.
It is difficult to evaluate the quality of the results obtained by either Jojic or Bhat et al. Both show clear discrepancies between the physical data and the simulation, but it is hard to determine whether these errors are due to their own methods, or due to the cloth simulation system used in their inner simulation loop. Bhat et al. describe some problems with the damping model used by Baraff and Witkin's cloth simulation, and similar issues have been discussed at length in the cloth simulation community.
Both Jojic and Bhat et al. relied only on 3D geometric data. This data should contain information about folds and wrinkles in the cloth, but cannot capture local internal deformation such as stretching and shearing. Consequently, they were able to measure the relative strength of bend forces, but should have had difficulty determining the strength of stretch and shear forces. Naturally, stretch and shear forces will have some impact on the global shape and drape of the cloth, but much of the effects will be hard to detect using only geometric data. Finally, without parametric information it is very difficult to deal with occluded regions of the cloth. Near a fold, it is impossible to tell how much fabric is contained in the occluded region without parametric information.
Consequently, our measurement of both geometric and parametric data is a valuable contribution to the cloth parameter measurement problem.
The computer vision community has shown interest in recovering the motion of non-rigid surfaces, such as cloth.
The work of Guskov et al. [44,46] is most relevant to the problem of cloth parameterisation. Guskov used cloth with a checkered pattern printed on it, and he tracked the corners of the quads to recover sparse parametric information. In a recent paper [45], he extended his earlier work to include 3D reconstruction of the surface geometry using multiple cameras. His system was targeted at real-time performance, and could not capture a large number of feature points. His accuracy degraded as the size of the quads drops below 20×20 pixels. Furthermore, he could not use stereo correspondence to recover detailed geometry, since his checkered pattern lacks high-frequency texture.
Torresani et al. [103] used rank constraints on optical flow to track features and reconstruct 3D geometry from monocular video data. They showed some promising results for human torso, face and shoe motion, but did not attempt the more challenging problem of cloth tracking. Their tracking approach would still require a recognition phase to form an initial correspondence between features and parametric (u,v) positions.
Carceroni [23,24] attempted the extremely difficult task of recovering 3D shape, reflectance and non-rigid motion of a dynamic scene using a surfel model. His results were quite promising, demonstrating the tracked position and velocities of a sheet of patterned cloth under reasonably quick motion. His approach dealt reasonably well with difficult problems such as occlusion. Like Torresani et al., Carceroni's approach would still require an initial recognition phase to establish the starting (u,v) correspondence.
Each of these methods suffers from one common failing: a relatively small number of features is tracked. Our approach tracks an order of magnitude more features than any of the previous work. Finally, all of the previous work tackled the motion tracking problem, while our approach is more of a recognition method. As a result, we do not need any temporal history to allow recognition of features in an arbitrary deformed state.
There have been a number of less directly relevant efforts at cloth capture. Haddon and Forsyth [48] tracked the formation of folds and wrinkles in video sequences, but did not recover geometry or parameterisation. Ruiz and Buxton [95] attempted to improve the capture of fine wrinkles in static cloth geometry, but ignored parameterisation.