Comparing Numerical Integration Methods in a Simulator for the Draping Behavior of Cloth

By: Michael Liberatore, Advised by: Dr. Denise Byrnes

The College of Wooster

Wooster, OH

Problem and Motivation:

The soft-body dynamics of cloth, water, and smoke are often implemented using systems of interconnected particles to which forces can be applied. In order to animate such a system, the position of each particle must be calculated at each step in a simulation based on the force acting upon it.  The acceleration of a particle is determined by application of Newton’s second law of motion to the particle’s force and mass. Finally, the velocity and position of a particle are approximated using a numerical integration technique. While many numerical integrators exist, the fourth order Runge-Kutta method (RK4) is touted as both stable and accurate. Recently, the Verlet integration technique has surfaced in informal physically-based cloth simulations and it appears in publications unrelated to cloth modeling. Verlet integration is used as an alternative to more complex numerical integrators for its ease of programming and computational speed. Currently, little empirical information is available that compares RK4 and Verlet integrators, especially in cloth modeling. The goal of this project is to provide such evidence to determine which technique is more suitable for modeling the dynamic draping behavior of cloth with a system of interconnected particles. The results serve as a guideline for selecting a numerical integrator when implementing a cloth simulation.

Background and Related Work:

Through abstractions, assumptions, and approximations of the natural behavior of cloth, many techniques have been developed over the last three decades to facilitate modeling cloth in a physically-based and visually acceptable manner. Most systems, however, rely on a grid of points that represent the crossing intersections of threads. One of the first physically-based cloth models [8] used this approach by tracing the catenary curves between the constraint points of hanging cloth. In this work, Weil focuses on achieving a visually acceptable surface rather than an accurate physically-based result. Breen [1] was the first to use an interacting system of particles to model the behavior of cloth. This was quite innovative as research in this era of physically-based particle systems viewed particles as independent entities [4]. In 1995, a mass-spring particle system was developed [3], making the realistic visualization of cloth behavior a reality. In the mass-spring particle system, the theoretical threads that connect particles are treated as springs that give the cloth elastic behavior. Three spring types are used in the mass-spring particle system. Structural springs give the cloth its basic shape, shear springs prevent particles from bending unnaturally out of their plane, and flex springs allow the cloth to bend more easily. The particle connections made by the three spring types are depicted in Figure 1.

Figure 1: Structural, shear, and flex spring connections in a particle grid.

More modern techniques employ creative strategies in the model's implementation. In 2007, Zink and Hardy [9] made use of the mass-spring particle system to create arbitrarily complex cloth models and objects with which they can collide using geometry images. In 2008, Kaldor and James [2] presented a model that simulates cloth at the micromechanical structure of yarn, employing knits and interactions between individual threads. Many of today's new and innovative cloth models are incapable of being rendered in real-time simulations due to their complexity, with the exception of [9].

While none of the models described are perfect representations of cloth, many physically-based particle systems rely on numerical integration to find the position of each particle at each time step. Several current systems in published works use RK4 integration [5], but recent, unpublished simulations on the web rely heavily on Verlet integration. Verlet integration is a technique developed by Loup Verlet [7] in the late 1960s. The Verlet method is easy to implement, as it does not require the use of ordinary differential equations, and it does not explicitly incorporate velocity. The Verlet method also produces visual results that appear reasonable. A more stable form of the Verlet integrator, called Velocity Verlet, incorporates velocity, and consists of Equations 1 and 2, as presented in [6]. Velocity Verlet solves for position r and velocity v at time n+1 using position and velocity at time n, time step size h, and acceleration f.

r_n+1 = r_n + hv_n + h²f(r_n)/2 (1)

v_n+1 = v_n + h[f(r_n+1) + f(r_n)]/2 (2)

While this technique is quite simple to implement in a simulation, its accuracy is not clearly discussed in the literature, and there is no evidence supporting or rejecting it as a stable integration technique.

Uniqueness of the Approach: 

Typically, publications in cloth modeling focus on creating new approaches which are more physically accurate than those of the past. Rarely is there more than one integration technique discussed, nor are there reasonable comparisons in terms of the speed and accuracy of such techniques. In most cases, the techniques used for integrating particle positions are completely abstracted from model descriptions, resulting in models incapable of reproduction by readers. Rather than create a new approach to modeling cloth, we created an incredibly robust simulation interface that employs the mass-spring particle model in order to maintain real-time, interactive experimentation. This system allows for complete control over particle and spring variables, environmental forces, rendering, and numerical integration techniques. 

The interface supports side-by-side visualizations of separate cloth models that use different integrators, as depicted in Figure 2. Using this system for experimentation, the integration techniques are tested for maintenance of stability within the particle grids. The mass-spring particle model is by no means an accurate representation of real world cloth. However, its simplified approach facilitates real time simulation. Models that employ a mass-spring particle structure are meant only to visually simulate real-world cloth, rather than accurately depict its realistic behavior. For this reason, data obtained in the tests are based on visual stability. With deformations applied to the cloth models employing RK4 and Velocity Verlet, particles are examined for oscillating behavior caused by the loss of accuracy due to the approximation error of the integrators. A model that shows no oscillation is considered visually stable. Using independent variables of grid-size and particle mass, the time step sizes for which oscillation begins to occur in each model are recorded and compared. In an additional test, the spring strengths, represented by a constant value, are increased until oscillation occurs, and are recorded separately for each model. Instead of providing yet another complex model, the goal of this research is to provide evidence to help support those in need of a robust numerical integration technique for cloth modeling. 

Figure 2: The simulation interface; visualizing two cloth models.

Results and Contributions:

Little information is available about the difference in effectiveness and performance of RK4 and Velocity Verlet. Since both integrators are used in simulating deformable objects, empirical evidence is needed to determine which integrator is most suitable for cloth modeling. The first experiment compares the visual stability of the integrators with the independent variable of grid-size. The time step sizes that produce oscillating behavior in RK4 were quite large compared to those of Velocity Verlet. In fact, Velocity Verlet was only able to remain visually stabile at very low time steps sizes. Results from the first test are shown in Figure 3. The grid-sizes used in the first test represent a range of cloth sizes, from a simple 10x10 grid of particles to a 27x27 grid. Larger grid-sizes were not used because real-time simulation is hindered by the computational cost of integrating additional particles.

Figure 3: The results from the grid-size test showing the time steps sizes that begin to produce oscillation.

The second test, which used a constant grid-size and an independent variable of particle mass, showed similar results, as depicted in Figure 4. The particle masses represent a range of cloth models from one that only slightly deforms under its own weight to one that hangs low to the ground.

Figure 4: The results from the particle mass test showing the time steps sizes that begin to produce oscillation.

The final experiment, the spring strength test, demonstrates that Velocity Verlet is able to handle much larger spring strength constants before showing any signs of oscillation. These results are shown in Figure 5. However, both models are capable of remaining stable for large spring strengths that prevent simple deformations. Therefore, both are suitable in the case of the spring strength test when attempting to model a highly deformable surface, such as cloth.

Figure 5: The results from the spring strength test showing the spring strengths that begin to produce oscillation.

For a simulation to run in real-time with small time step sizes, the number of simulation steps per rendered frame must be increased. The results from the first two tests show that the time step sizes used when modeling cloth with Velocity Verlet must remain quite low. In order to match the speed and visual stability of RK4, repeated position updates per rendered frame are necessary in the Velocity Verlet model. These repeated updates result in a computational cost that exceeds that of the stable and accurate RK4 method. The repeated updates also cause a performance hit, which is undesirable for real-time simulation. Therefore, RK4 is determined to be the more suitable integration technique for modeling cloth with a system of interconnected particles in real-time. These results are significant for anyone designing physics systems for simulations involving interconnected particles. The results also provide the empirical background for choosing the right integration technique based on the needed level of accuracy and speed. While Velocity Verlet does cause a performance hit with repeated simulation steps per frame, this cost may be determined negligible for simulations that are not rendered in real-time. In this case, the benefit of Velocity Verlet’s ease of programming may outweigh that of RK4’s speed. In addition to the experiments conducted, the interface created in support of this project can be used to further experiment with the mass-spring cloth. Its extensibility has been demonstrated with extensions that include cloth tearing using the elastic limit of springs, and an interface for importing 3D models that are reconstructed using the mass-spring particle model to create custom deformable objects. The interface will soon be available on the web to allow others to experiment with and extend the mass-spring particle cloth model.

References:

[1] Breen, D. A particle-based model for simulating the draping behavior of

woven cloth. PhD thesis, Troy, NY, USA, 1993.

[2] Kaldor, J. M. and James, D. L., Marschner. Simulating knitted cloth at the

yarn level. In SIGGRAPH ’08: ACM SIGGRAPH 2008 papers, pages 1 – 9,

New York, NY, USA, 2008 ACM. Doi: http://doi.acm.org/10.1145/1399504.

1360664.

[3] Provot, X. Deformation constraints in a mass-spring model to describe rigid

cloth behavior. In Graphics Interface ’95, Wayne A. Davis and Przemyslaw

Prusinkiewicz, editors, pages 147–154. Canadian Human-Computer

Communications Society, 1995.

[4] Reynolds, C. W. Flocks, herds and schools: A distributed behavioral model.

In SIGGRAPH ’87: Proceedings of the 14th annual conference on Computer

graphics and interactive techniques, pages 25–34, New York, NY, USA,

1987. ACM.

[5] Song, M. and Grogono, P. A framework for dynamic deformation of uniform

elastic two-layer 2d and 3d objects in OpenGL. In C3S2E ’08: Proceedings of

the 2008 C3S2E conference, pages 145–158, New York, NY, USA, 2008.

ACM.

[6] Swope, W., Anderson, H., and Berens, P. A computer simulation method for

the calculation of equilibrium constants for the formation of physical clusters

of molecules: Application to small water clusters. The Journal of Chemical

Physics, Vol. 76, No. 1, 1982 pages 637 – 649, 1982.

[7] Verlet, L. Computer “experiments” on classical fluids. i. thermodynamical

properties of Lennard-Jones molecules. Phys. Rev., Vol. 159, No. 1, 1967,

pages 98 - 103, July 1967.

[8] Weil, J. The synthesis of cloth objects. SIGGRAPH Comput. Graph., Vol.

20, No. 4, pages 49–54, 1986.

[9] Zink, N. and Hardy, A. Cloth simulation and collision detection using

geometry images. In AFRIGRAPH ’07: Proceedings of the 5^th international

conference on computer graphics, virtual reality, visualisation, and interaction

in Africa, pages 187 – 195, New York, NY, USA, 2007. ACM. ISBN 978-1-

59593-906-7. doi: http://doi.acm.org/10.1145/1294716.