<H1>3. Performance</H1>
        Performance is a key issue in choosing the adequate integration method, as cloth simulation usually involves very large mechanical systems described by a huge number of variables, and the numerical resolution of the system is therefore critical to the total computation time. Performance actually depends on several factors: * The computation time taken for one iteration of the algorithm. This depends on the complexity of the method, and also related to the number of times the forces of the system have to de derived from the system state using the laws of mechanics. * The time step for one iteration, which represents the time discretization required to reach a given accuracy or numerical stability for a given method. * The desired accuracy of the resolution, which may be coarse if only static equilibrium is to be computed, or high if the whole dynamic evolution of the system is desired. Accuracy increases along with time step reduction as better as the method is high-order. * The numerical stability of the method, which also limits the time step for a given method and a given mechanical system. These factors describe our investigation field in the following sections.
        1 0 100 1000 10000 100000 1 Midpoint Runge Kutta Inv Euler (1) 0.1 Inv Euler (2) Inv Euler (4) Inv Euler (8) 0.01 0.001 0.0001 1 0 100 1000 10000 100000 1 0 Midpoint Runge Kutta 1 Inv Euler (1) Inv Euler (2) Inv Euler (4) Inv Euler (8) 0.1 0.01 0.001 Fig.1. Computation time per iteration for the various integration methods. on SGI Octane R10000 200MHz for simplified model (top) and accurate model.(botton) Time (vertical, seconds) per Polygons (horizontal, number).
      
      
        <H2>3.1. Computation Time</H2>
        The total computation time is the time required for computing one iteration times the number of iterations. Our first investigation is to evaluate the iteration computation time for each of these methods. For these measurements, we have simulated a square of fabric with a given discretization both with the accurate and simplified models, using the Midpoint, the RungeKutta and the Backward Euler methods, with 1, 2, 4, 8 iterations in the Conjugate Gradient algorithm for the latter, and measured computation time (Fig.1). From these tests, we can see that with our implementation, the computation times per mesh polygon are roughly the following:
        Method Accurate Simplified Midpoint 32 μs 8 μs Runge-Kutta 95 μs 25 μs Back. Euler (No CG iter.) 31 μs 5 μs Back. Euler (Per CG iter.) 16 μs 2.5 μs
        The most important fact to note is that the application of the Backward Euler method with a reduced number of Conjugate Gradient iterations compares very well with the traditional explicit methods. With one iteration only, it is barely worse than the very simple explicit Midpoint method. Our implementation, described in [ VOL 00 ] does not explicitly construct the matrix of the system to be resolved by the Conjugate Gradient, but computes “on the fly” the product of this matrix with vectors when needed by the Conjugate Gradient algorithm. This gives a very efficient implementation when using a low number of Conjugate Gradient iterations (no heavy preprocessing for building the matrix), which is often sufficient for most applications. These tests will help us to choose the method that gives the best compromise between accuracy and computation speed, as discussed in the next section.
      
      
        <H2>3.2. Dynamic Accuracy</H2>
        For measuring accuracy and numerical stability of the algorithms, we need to set up a “standard” material on which the experiments are carried out, as well as the rules allowing to extrapolate the results to any material of different size and parameters. In the scope of our study, we restrict the experimentation to linear metric elasticity of an isotropic cloth material, described by a Young modulus E and a surface density d. For the simulation, the surface square is discretized into elements which roughly have the length l, and the computation is carried out with time steps of size t. Defining the Condition Coefficient Thanks to the linearity of the equations describing linear elasticity, we reduce the number of parameters describing a problem using proportionality laws, and we compute a “condition coefficient” K which illustrates the acceleration of a mesh element with normalization to the problem mass, simulation time step and element size, as follows: K = E d 1 l 2 t 2 (1) This non-dimensional coefficient actually measures the “numerical difficulty” of computing an iteration of time step t with the given problem. We checked experimentally with our implementation that any scaling of a simulation along distance, time and mass which leaves K unchanged does not change anything to the simulation result. A typical cloth simulation problem could involve a cotton fabric cloth surface, which typically have a density d = 0.1 kg.m -2 and a Young modulus E = 2 0 N . m 1 . Given a discretization into elements averaging one centimeter and a simulation time step of ten milliseconds, the condition coefficient of the problem computed with (1) is K = 2 0 0 . It is possible to define similar coefficients related to bending and viscosity modulus. The corresponding K coefficients are respectively multiplied by additional l -2 and t factors. In simulations that consider simultaneously all these forms of mechanical behaviors, the dominant K coefficient rules the “numerical difficulty” of the problem. The Free Fall Test Our first test intends to measure the accuracy of the various methods in the context of accurate dynamic simulation. In such kind of simulation, the interest is to reproduce exactly the motion of a cloth object along time, the accuracy of its evolution being the key of the realism of an animation involving simulated cloth. In this experiment, we let a horizontal fabric square of 1.0 m side length, initially still, fall by its own weight, under a gravitation field of 1 0 m . s 2 acceleration (Fig.2). The discretization was set to roughly 400 elements ( l = 0 . 0 5 m ), and its Young modulus was altered in order to obtain various K values, with a simulation time step of t = 0.01 s. When using implicit methods, we perform a preconditioning of the system state variables of the linear system to be resolved using the inverse square root of the mass of the corresponding particle. This allows the iterations of the Conjugate Gradient algorithm to distribute the resolution numerical errors as evenly as possible between the particles, so that to obtain for instance a fall speed that does not depend on the mass of the particle. We measure the time it takes for this fabric piece to fall a height of 1 m . Without any additional external forces considered (no aerodynamic interactions), we expect this to happen in a constant time of 0.45 s. Fig.3. Fall time (vertical, seconds) with various K values (right) and different integration methods (left). Theoretical time: 0.45 s. Null values indicate numerical instability. Several interesting facts arise from this experiment. As a matter of numerical stability, the Midpoint method supports K values up to almost 3 whereas the RungeKutta method supports K values up to almost 100. This indicates that with Runge-Kutta, it is possible to use simulation time steps which are almost six times larger than with Midpoint. Given the fact that a Runge-Kutta iteration takes only three times more computation than a Midpoint iteration (Fig.1), the Runge-Kutta method seems to be computationally two times more efficient than the Midpoint method. As a matter of simulation accuracy, both Midpoint and Runge-Kutta seem to preserve accuracy correctly within their range of numerical stability. While the implicit Euler method seems stable for any K value, its accuracy is however very degraded by high K values and reduced numbers of Conjugate Gradient iterations. More precisely, we see that accuracy is well preserved with one Conjugate Gradient iteration up to a K value of 4, and increasing the iteration number n times also increases the K value n 2 times for the same accuracy. From this, we can see that the Inverse Euler method needs at least four Conjugate Gradient iterations to reach the accuracy of the Runge-Kutta method. We also see that similar requirement of accuracy bring the two methods in parity in terms of computation time (Fig.1). However, it should be noted that the experiment was carried out using a uniformly discretized mesh, and uniform mechanical parameters. Real-world simulations do not have this regularity, and numerical instability with explicit methods occur in the stiffest regions of the mesh, which, even if they are marginal in the whole mechanical system, may totally “explode” and destroy the simulation and therefore will rule the size of the largest time step possible. With implicit methods, the resulting inaccuracies may be unnoticed when taking a time step adapted to the average stiffness. Anyhow, this experiment shows clearly that when accurate reproduction of dynamic motion is required, it is not possible to increase the time step of implicit methods as much as desired, as this cause very noticeable inaccuracy as weak forces will be “neglected” relatively to stiff forces. While this is not an issue for draping problems where only the final state is desired, this aspect has to be taken into account when accurate reproduction of the whole evolution is wanted. While implicit Euler is a good choice for robust simulation where accuracy is not really an issue, the explicit Runge-Kutta offers good possibilities of ensuring high accuracy because of its high-order solution, and also because is provides good possibilities integration error evaluation for efficient time step control which, by the way, is too context-sensitive for being pre-evaluated using only the knowledge of K. Discretization and Computation Time The condition coefficient value is a good indicator of the time step and accuracy that can be expected for a given problem with a given iteration time step. Considering a simulation involving elements n times smaller, maintaining accuracy and stability (preserving K constant in formula (1)) would require a time step n times smaller, and therefore n times as many iterations for simulating the mechanical system along a constant duration. Given the fact that there are also n 2 times more elements to handle, the total computation time is finally multiplied by a drastic n 3 (even n 4 if curvature stiffness rule the simulation accuracy). While this factor is what cause explicit methods to become so inefficient with refined discretizations as this scaling has to be strictly observed for preventing instability, implicit methods are a bit more tolerant if only “visual” accuracy matters, accuracy which is not related to the size of the elements.
        
          
        
        Fig.2. The free fall test: A horizontal fabric square, initially at rest, is dropped from 1 m height in a gravity field of 10 m.s -2 .
        10 9 8 7 6 5 4 3 2 1 0 64 512 4096 (1) Euler Euler (2) (4) Euler Euler (8) (16) Euler Kutta Midpoint 1 8 Inv Inv Inv Inv Runge Inv
      
      
        <H2>3.3. Draping Speed</H2>
        Draping is another context of simulation, where only the final static equilibrium state of the mechanical system is to be computed. Here, the interest is to converge to the equilibrium state as quickly as possible, with minimum computation charge. As the full evolution of the cloth along time is not an interest, accuracy can be traded away for computation speed. From the dynamic study described above, implicit methods should be quite strong on this point, as they do not suffer from numerical instability, and allow large time steps to be used at the expense of dynamic accuracy which can here be neglected. The Draping Test For this test, we let an initially horizontal fabric square, attached along one of its edges, fall by its own weight (Fig.4). The fabric is a cotton sample of 1 m side length, with a Young modulus E = 2 0 N . m 1 and a density d = 0 . 1 k g . m 2 , discretized into 10000 polygons l = 0.01 m, and put in a gravitation field of 1 0 m s 2 . Without any damping, we expect that in its first oscillation, the fabric reach a roughly vertical position after slightly more than half a second. Our purpose is here to find the computation time necessary to obtain the fabric in its vertical position. For this, we count the number of computation iterations necessary for obtaining the fabric in its vertical position in its first oscillation, not being interested by the realism of this motion (Fig.5).
        
          
        
        Fig.4. The draping test: An horizontal 1 m square of fabric fixed along a side falling in a gravitation field of 10 m s-2 . 700 600 500 400 300 200 100 0 Inv (1) Euler (2) Euler Inv Euler (4) Inv Inv Euler (8) (16) Euler Kutta Runge Midpoint 10 0.1 0.001 Inv
        Fig.5. Number of iterations (vertical) required to get the fabric at vertical position, with various time steps (right, seconds), and integration methods (left). Null values indicate numerical instability. Our first finding is that the explicit methods seem quite not adapted for draping. Runge-Kutta requires more than 500 iterations for performing the simulation without instability, with the maximum allowed time step t = 0 . 0 0 1 s , which in fact corresponds to the maximum value of K coefficient experimented in the previous section. The backward Euler method is robust enough to handle the problem without instability for any time step. However, we see that larger time steps do not proportionally translate into fewer steps for performing the draping. As the time step becomes larger, and as the corresponding K coefficient exceeds the theoretical limit observed in the previous section, we quickly observe a “saturation” of the number of iterations to a constant which seems to be inversely proportional to the number of Conjugate Gradient iterations that were performed. From this it is clear that when K exceeds the dynamic accuracy limit of a given implicit integration method, the time step does not really reflect a time interval anymore. In such case, the implicit method will only evaluate an approximation of the rest state of the mechanical system by linear extrapolation from the Hessian matrix, whose accuracy depends on the number of Conjugate Gradient iterations that were used to resolve the corresponding linear system. Hence, there is no real way to “cheat” on the time step for speeding up draping, even if dynamic accuracy is not a concern: The total number of Conjugate Gradient iterations for performing all the simulation iterations of a draping problem cannot go below an incompressible number, related to a kind of “total computational difficulty” for solving a draping problem, which in the case of our experiment seems around 100. Still, this experiment shows the drastic advantage of using implicit methods for draping problems: With our implementation using the accurate elasticity model and the computation times measured in section 3.1, the draping could be computed in 30 seconds with Backward Euler with any large time step, compared to 150 seconds with Runge-Kutta when using an “optimal” time step.
      
      
        <H2>3.4. Dealing with Nonlinear Models</H2>
        Most mechanical simulations work with numerical equations that are not linear. There are two main reasons for such nonlinearity: * The equations describing the mechanical behavior laws are not linear. For instance, the strain-stress relation describing elasticity may actually be complex curves, which furthermore may take into account timedependent and hysteretic behaviors. * During the simulation, the orientation of the mechanical elements change, and this modifies the expressions of the mechanical laws in the world coordinates. While rarely causing numeric “explosions” as with explicit methods, nonlinearity may disrupt the stability of simulations integrated with implicit models with large disturbing vibrations, particularly when using large time steps that cause iterations to converge to the equilibrium state of the mechanical objects rather than simulating accurately their mechanical behavior. This can for instance be observed when simulating stretched flat surfaces without curvature forces. The reason for that is that the hypothetical equilibrium state is derived from the knowledge of the Hessian matrix, which relates the firstorder evolution of the forces as the deformations change. Nonlinearity causes this matrix to change between the successive iterations, and this evaluation to be inaccurate, despite high system resolution accuracy that can be reached with numerous Conjugate Gradient iterations. The solution for this is to approximate the Hessian matrix for taking into account the changes that may be observed from the change of the system state between successive iterations. While an underestimation of de derivatives may lead to an equilibrium state valuation too far from the current state, and by this cause instability, an overestimation of the derivatives will place this evaluation nearer to the current state, therefore stabilizing the simulation, at the expense of extra numerical damping and slow convergence. This is particularly true for drastic linearisations as for example used in [ DES 99 ]. Knowledge of the expected state changes between successive time steps are required to perform this approximation correctly. With nonlinear mechanical behavior, one solution is to take the steepest parts of the curves as derivatives, whereas for the element orientation problem, isotropic derivatives considering force evolution equally in any directions may be considered. However, the more drastic these approximations are, the less accurate the simulation will be for dynamic simulations, and the slower the simulation will converge for draping problems. A nice solution described in [ EBE 00 ], which makes sense when efficiency relies on the use of a constant Hessian matrix, is to perform the implicit resolution on a linear constant approximation, and to simulate the nonlinear and variable component, unlikely to cause stiffness problems, using an explicit method.
      
      
        <H2>3.5. Real Case Simulation</H2>
        In order to test the efficiency of our model in the context of garment animation, the algorithms have been integrated in a 3D design framework allowing the management of complex garment objects in interaction with animated virtual characters. This integration has been carried out in the form of a 3DStudio Max plugin (Fig.6), running on a 500 MHz PentiumIII PC. We have simulated a 2000 Polygon garment made of the cotton material described in Section 3. The mesh elements are roughly five centimeters in size, and therefore the resulting condition coefficient K is roughly 8 with a simulation time step of 10 milliseconds. The cloth simulation process has two stages: * The garment assembly stage, where the patterns are pulled together and seamed around the body. This is a draping problem involving to obtain a rest position of the garment as quickly as possible. * The garment animation stage, where the motion of the garment is computed as the body is animated. The dynamical motion of the cloth is important here. The garment assembly and seaming operations could be performed almost four times faster with the Backward Euler (2 minutes) than with Runge-Kutta (8 minutes), knowing that collision detection and response account for more than the half of the computation time, and actually limits the time step size when contact starts between the cloth and the body. For the dynamical animation, comparable accuracy could be obtained between Runge-Kutta and Backward Euler using eight iterations of the Conjugate Gradient, which gave similar computation times. The backward Euler method however allowed the increase of the time step up to 0.1 seconds, where inaccuracies began to show up: Mostly, excessive “heaviness” of the fabric that failed to follow the motion of the body properly, garments folds that would not disappear quickly, as well as additional artifacts caused by inaccurate collision response.
        
          
        
        Fig.6. Garment simulation in the 3DStudio Max environment.
      
      
        