<H1>1 Introduction</H1>
      
      Physically-based cloth animation has been a problem of interest to the graphics community for more than a decade. Early work by Terzopoulos et al. [ 17 ] and Terzopoulos and Fleischer [ 15 , 16 ]
 on deformable models correctly characterized cloth simulation as a problem in deformable surfaces, and applied techniques from the mechanical engineering and finite element communities to the problem. Since then, other research groups (notably Carignan et al. 
[ 4 ] and Volino et al. [ 20 , 21 ]
; Breen et al. [ 3 ]; and Eberhardt et al. [ 5 ]) have taken up the challenge of cloth. Although specific details vary (underlying representations, numerical solution methods, collision detection and constraint methods, etc.), there is a deep commonality amongst all the approaches: physically-based cloth simulation is formulated as a time-varying partial differential equation which, after discretization, is numerically solved as an ordinary differential equation
      
        1
        ẍ = M −1 − ∂E + F . ∂x
      
      In this equation the vector x and diagonal matrix M represent the geometric state and mass distribution of the cloth, E—a scalar funcAuthor affiliation (September 1998): David Baraff, Andrew Witkin, Pixar Animation Studios, 1001 West Cutting Blvd., Richmond, CA 94804. Email: deb@pixar.com , aw@pixar.com . This is an electronic reprint. Permission is granted to copy part or all of this paper for noncommercial use provided that the title and this copyright notice appear. This electronic reprint is ©1998 by CMU. The original printed paper is ©1998 by the ACM.
      tion of x—yields the cloth’s internal energy, and F (a function of x and x) describes other forces (air-drag, contact and constraint forces, internal damping, etc.) acting on the cloth. In this paper, we describe a cloth simulation system that is much faster than previously reported simulation systems. Our system’s faster performance begins with the choice of an implicit numerical integration method to solve equation (1). The reader should note that the use of implicit integration methods in cloth simulation is far from novel: initial work by Terzopoulos et al. [ 15 , 16 , 17 ] applied such methods to the problem. 1 Since this time though, research on cloth simulation has generally relied on explicit numerical integration (such as Euler’s method or Runge-Kutta methods) to advance the simulation, or, in the case of of energy minimization, analogous methods such as steepest-descent 
[ 3 , 10 ]. This is unfortunate. Cloth strongly resists stretching motions while being comparatively permissive in allowing bending or shearing motions. This results in a “stiff” underlying differential equation of motion 
[ 12 ]. Explicit methods are ill-suited to solving stiff equations because they require many small steps to stably advance the simulation forward in time. 2 In practice, the computational cost of an explicit method greatly limits the realizable resolution of the cloth. For some applications, the required spatial resolution—that is, the dimension n of the state vector x—can be quite low: a resolution of only a few hundred particles (or nodal points, depending on your formulation/terminology) can be sufficient when it comes to modeling flags or tablecloths. To animate clothing, which is our main concern, requires much higher spatial resolution to adequately represent realistic (or even semi-realistic) wrinkling and folding configurations. In this paper, we demonstrate that implicit methods for cloth overcome the performance limits inherent in explicit simulation methods. We describe a simulation system that uses a triangular mesh for cloth surfaces, eliminating topological restrictions of rectangular meshes, and a simple but versatile formulation of the internal cloth energy forces. (Unlike previous metric-tensor-based formulations 
[ 15 , 16 , 17 , 4 ]
 which model some deformation energies as quartic functions of positions, we model deformation energies only as quadratic functions with suitably large scaling. Quadratic energy models mesh well with implicit integration’s numerical properties.) We also introduce a simple, unified treatment of damping forces, a subject which has been largely ignored thus far. A key step in our simulation process is the solution of an O(n) × O(n) sparse linear system, which arises from the implicit integration method. 

In this respect, our implementation differs greatly from the implementation by Terzopoulos et al. 
[ 15 , 17 ], which for large simulations
      1 Additional use of implicit methods in animation and dynamics work includes Kass and Miller [ 8 ], Terzopoulos and Qin 
[ 18 ], and Tu 
[ 19 ]. 2 Even worse, the number of time steps per frame tends to increase along with the problem size, for an explicit method. Cloth simulations of size n— meaning x ∈ IR O(n) —generally require O(n) explicit steps per unit simulated time. Because the cost of an explicit step is also O(n) (setting aside complications such as collision detection for now) explicit methods for cloth require time O(n 2 )—or worse.
      43
      SIGGRAPH 98, Orlando, July 19–24
      C OMPUTER G RAPHICS Proceedings, Annual Conference Series, 1998
      used an “alternating-direction” implicit (ADI) method [ 12 ]. An ADI method generates a series of tightly banded (and thus quickly solved) linear systems rather than one large sparse system. (The price, however, is that some of the forces in the system—notably between diagonally-adjacent and non-adjacent nodes involved in self-collisions—are treated explicitly, not implicitly.) The speed (and ease) with which our sparse linear systems can be robustly solved—even for systems involving 25,000 variables or more—has convinced us that there is no benefit to be gained from using an ADI method instead (even if ADI methods could be applied to irregular triangular meshes). Thus, regardless of simulation size, we treat all forces as part of the implicit formulation. Even for extremely stiff systems, numerical stability has not been an issue for our simulator.
      
        <H2>1.1 Specific Contributions</H2>
        Much of the performance of our system stems from the development of an implicit integration formulation that handles contact and geometric constraints in a direct fashion. Specifically, our simulator enforces constraints without introducing additional penalty terms in the energy function E or adding Lagrange-multiplier forces into the force F. (This sort of direct constraint treatment is trivial if equation (1) is integrated using explicit techniques, but is problematic for implicit methods.) Our formulation for directly imposing and maintaining constraints is harmonious with the use of an extremely fast iterative solution algorithm—a modified version of the conjugate gradient (CG) method—to solve the O(n) × O(n) linear system generated by the implicit integrator. Iterative methods do not in general solve linear systems exactly—they are run until the solution error drops below some tolerance threshold. A property of our approach, however, is that the constraints are maintained exactly, regardless of the number of iterations taken by the linear solver. Additionally, we introduce a simple method, tailored to cloth simulation, for dynamically adapting the size of time steps over the course of a simulation. The combination of implicit integration and direct constraint satisfaction is very powerful, because this approach almost always allows us to take large steps forward. In general, most of our simulations require on average from two to three time steps per frame of 30 Hz animation, even for (relatively) fast moving cloth. The large step sizes complement the fact that the CG solver requires relatively few iterations to converge. For example, in simulating a 6, 000 node system, the solver takes only 50–100 iterations to solve the 18, 000 × 18, 000 linear system formed at each step. Additionally, the running time of our simulator is remarkably insensitive to the cloth’s material properties (quite the opposite behavior of explicit methods). All of the above advantages translate directly into a fast running time. 
For example, we demonstrate results similar to those in Breen et al. 
[ 3 ] and Eberhardt et al. 
[ 5 ] (draping of a 2,600 node cloth) with a running time just over 2 seconds per frame on an SGI Octane R10000 195 Mhz processor. Similarly, we show garments (shirts, pants, skirts) exhibiting complex wrinkling and folding behavior on both key-framed and motion-captured characters. Representative running times include a long skirt with 4,530 nodes (8,844 triangles) on a dancing character at a cost of 10 seconds per frame, and a shirt with 6,450 nodes (12,654 triangles) with a cost varying between 8 to 14 seconds per frame, depending on the underlying character’s motion.
      
      
        <H2>1.2 Previous Work</H2>
        Terzopoulos et al. [ 15 , 17 ]
 discretized cloth as a rectangular mesh. Energy functions were derived using a continuum formulation. This work recognized the need for damping forces; however, only a simple viscous drag force −k x was used. The linear systems result- ing from the use of implicit integration techniques were solved, for small systems, by direct methods such as Choleski factorization, or using iterative techniques such as Gauss-Seidel relaxation or conjugate gradients. (For a square √ system of n nodes, the resulting linear system has bandwidth n. In this case, banded Choleski factorization 
[ 6 ] requires time O(n 2 ).) As previously discussed, Terzopoulos et al. made use of an ADI method for larger cloth simulations. Following Terzopoulos et al.’s treatment of deformable surfaces, work by Carignan et al. 
[ 4 ]
 described a cloth simulation system using rectangular discretization and the same formulation as Terzopoulos et al. Explicit integration was used. Carignan et al. recognized the need for damping functions which do not penalize rigidbody motions of the cloth (as simple viscous damping does) and they added a force which damps cloth stretch and shear (but not bend). Later work by the same group includes Volino et al. [ 20 ]
, which focuses mainly on collision detection/response and uses a triangular mesh; no mention is made of damping forces. The system uses the midpoint method (an explicit method) to advance the simulation. Thus far, the accumulated work by this group (see Volino et al. 
[ 21 ] for an overview) gives the only published results we know of for simulated garments on moving characters. Reported resolutions of the garments are approximately two thousand triangles per garment (roughly 1,000 nodal points) 
[ 21 ]
 with running times of several minutes per frame for each garment on an SGI R4400 150 Mhz processor. Breen et al. [ 3 ]
 depart completely from continuum formulations of the energy function, and describe what they call a “particlebased” approach to the problem. By making use of real-world cloth material properties (the Kawabata measuring system) they produced highly realistic static images of draped rectangular cloth meshes with reported resolutions of up to 51 × 51 nodes. The focus of this work is on static poses for cloth, as opposed to animation: thus, their simulation process is best described as energy minimization, although methods analogous to explicit methods are used. Speed was of secondary concern in this work. Refinements by Eberhardt et al. [ 5 ]
—notably, the use of higher-order explicit integration methods and Maple-optimized code, as well as a dynamic, not static treatment of the problem—obtain similarly realistic results, while dropping the computational cost to approximately 20–30 minutes per frame on an SGI R8000 processor. No mention is made of damping terms. Provot [ 13 ]
 focuses on improving the performance of explicit methods by a post-step modification of nodal positions. He iteratively adjusts nodal positions to eliminate unwanted stretch; the convergence properties of this method are unclear. A more comprehensive discussion on cloth research can be found in the survey paper by Ng and Grimsdale 
[ 9 ].
      
      
        