<H1>2. Integration Methods</H1>
      
      The choice of the adequate integration method has to be carried out using various considerations related to the kind of problem to be simulated. Among those considerations, there are: * The size of the problem, mostly related to the number of particles used to describe the mechanical system. * The desired accuracy, which reflects the allowable numerical tolerance between the computed solution and the theoretical evolution expected from the mechanical model. * The simulation context, which can either be an extensive computation of the motion along time requiring accurate evaluation of all the dynamical factors, or a simple relaxation process where the simulation has to converge to the static rest state as quickly as possible. * The stiffness of the problem, mainly related to the rigidity of the particle interactions and the size of the chosen time step, which translated into the “difficulty” the numerical method has to compute the evolution numerically, and which practically causes inaccuracy and instability problems. * The time an iteration takes to compute, and the number of mechanical derivations (computation of particle forces from their position and speed) the methods requires to compute one. The literature is abundant about various integration methods which aim to solve linear systems of first-order ordinary differential equations 
[ PRE 92 ]. One can easily turn the second-order systems relating dynamical mechanical systems into first-order systems by constructing a state vector defined by the concatenation of position and speed states of the system, such as to fit the requirements of any of these algorithms. Among all the available methods, we can identify several main classes: * Explicit methods, which compute the state of the next time step out of a direct extrapolation of the previous states using derivative evaluations. * Implicit methods, which deduce the state of the next time step from an equation system expressing some “reversibility” from the extrapolated solution. * Low-order methods, which use a reduced number of evaluations for computing simple low-order extrapolations, leading to quickly computed, but inaccurate iterations. * High-order methods, which use several evaluations to compute high-order solutions that get much more accurate as the time step is reduced.
      
        <H2>2.1. Scope of the Study</H2>
        We shall restrict our consideration to three different methods which explore the range of these classes, and which seem to fit the best the requirements set for cloth simulation problems, in terms of implementation simplicity and efficiency for particle systems using large numbers of particles that interact sparsely and with a constant topology. The methods that we consider for this application are: * The explicit Midpoint method, which is a simple low-order explicit method. It requires two mechanical derivations per iteration and returns a second-order accurate solution relative to the time step. It also requires two storages of the state vector. We preferred this method to the still simpler first-order Euler method, because of the obvious gains of accuracy and stability which, despite the additional mechanical evaluation, makes it largely more efficient. We implemented this method for garment simulation in 
[ VOL 95 ]. * The explicit Runge-Kutta method, implemented in its fifth-order version with error evaluation 
[ PRE 92 ]. It requires five mechanical derivations per iteration, as well as five storages of the state vector. This method is supposed to provide high accuracy, which increases significantly as the time step is reduced. This method was experimented in [ EBE 96 ] and [ VOL 97 ]. * The Backward Euler method, which is the implicit implementation of its simple forward counterpart. It requires one mechanical evaluation and the resolution of a sparse linear system per iteration, as well as one storage of the system state additionally to those required for the system resolution algorithm. This method is supposed to provide approximate results that are not subject to numerical instability as the time step is increased. We implemented this method combined with a Conjugate Gradient algorithm using linear system matrix products computed on the fly, as described in 
[ VOL 00 ], and thus able to take into account the anisotropy and nonlinearities of the mechanical model as the actual Hessian matric is used for each current state of the mechanical system. No initial matrix setup is required, suppressing also the need of separating linear and nonlinear components as discussed in [ EBE 00 ]. We have also carried out some preliminary tests with the Rosenbrook method, which is an implicit implementation of a fourth-order Runge-Kutta method. It is supposed to combine the stability of implicit methods with the accuracy of high-order methods. We implemented this method using the algorithm described in 
[ PRE 92 ]
, but preliminary experiments have shown very deceptive results, and the gain of accuracy did not compensate the large calculations required for each iteration, whereas increased instability problems did not allow time steps much larger than those used for good accuracy with backward Euler. We did not consider in our tests the methods aimed toward simplifications which might highly approximate and degrade the dynamic behavior of deformable models, such as implicit integration with precomputed inverse matrices [ DES 99 ]
 which involves high simplification and linrarization of the Hessian matrix and which also becomes very unpractical for large matrix sizes (the inverse of a sparse matrix is not necessarily sparse). We simulated such algorithm using accurate resolution on an accordingly approximated constant matrix, and we found that these approximations produced more simulation errors (on dynamic behavior of wrinkles and motion damping particularly) than producing a quick and rough linear system solution using a reduced number of Conjugate Gradient iterations with an accurate matrix. Even more drastic simplifications [ KAN 00 ] reduce the matrices to their diagonal component.
      
      
        <H2>2.2. Implementation</H2>
        All these methods were implemented in a single framework, which allows the simulation of cloth objects, using two different discrete mechanical representations: * A complete surface elasticity model which allows the simulation of anisotropic elasticity (weft and warp Young modulus, shearing, Poisson coefficient) and associated viscosity. Bending is also implemented, but not taken into account in this study. The base element of this simulation is a triangle of the mesh describing the surface, and the elasticity laws are computed as interactions between the three vertices of a triangle reflecting all the mechanical behavior curves which, for this study, are restricted to be linear. * A simplified spring-mass model which represents an approximated equivalent elasticity model using linear viscoelastic springs connecting the particle couples describing each edge of the surface mesh. This model is one of the simplest that a cloth simulation application would use. The implementation also supports collision detection and response, which were disabled for these tests. An object-oriented framework written in C++ integrate all these technologies into a single application allowing simulation of cloth objects of any shape with specified parameters. The application is run on a SGI Octane having a 200 MHz R100000 processor, and enough memory for working without swapping. Performance timings are done on the mechanical computation only, and do not take into account display and data structure management.
      
      
        