This goal of this project is to demonstrate a mass-spring cloth simulation suitable for real time applications. In particular, this project explores the trade-offs between accuracy and speed inherent in building high performance graphical applications.
One of the more common approaches to building a physics-based simulation for cloth is to treat the cloth as a grid of nodes at which all the mass of the cloth is assumed to be concentrated, and then to model the interactions of the nodes with each other. The particular method used here is to connect this grid with a series of linear springs designed to resist forces pulling the fabric apart. This mass-spring model uses three types of springs to maintain the cloth shape:
These springs are used to set up a system of differential equations to solve for the position of the nodes. At any time t, the forces applied to each node can be calculated from the spring forces and other external forces like gravity and wind. In addition, it is also possible (although this technique is not used here) to detect potential collisions in the grid and apply a restitution force to prevent the cloth from intersecting itself. The position can then be derived through a simple Euler method integration:
where mu is the mass of the particles, and dt is the (discrete) time step. Care must then be taken as to the size of the time step. A too-large time step will lead inevitably to unstable behavior. When this model is run, for example, with a time step of 0.1s, then the magnitudes of the velocities of the particles quickly diverge from the correct behavior, and the grid becomes chaotic:
This behavior can be avoided by using a smaller time step, with the tradeoff that more steps will be required for the same length of animation. This is the same model, with a time step of 0.01s:
Although the system is now well behaved, a new problem is apparent: the top corners of the mesh show springs that are extended far past double their initial length. This behavior is not present in most textiles, which would rip or tear (behaviors not modeled here!) long before they could be stretched to these lengths. One solution to this problem would be to increase the spring constant of the springs in the model. However, the maximum effective time constant is inversely proportional to the spring stiffness; as the stiffness increases, smaller and smaller time steps must be used.
For the purposes of real-time animation, this is clearly not always feasible. One solution to this problem is laid out in [Provot 95], and allows for very large time steps to be used by applying a series of constraints to the springs after the integration has occured. The key idea in these constraints is to consider the direction the springs are moving to be correct, but to limit the deformation of each spring to a value consistant with empirical observations of actual cloth. A reasonable value for the maximum deformation of textiles if 105-110% of their original length. Therefore, this method iterates over all the springs in the model, and if they have exceeded the maximum deformation, moves the nodes at the ends of the springs closer together.
This method is not without disadvantages. First of all, by stepping away from the strictly physics-based simulation, the solutions will only be qualitatively correct. In addition, the procedure is not proven to work in all cases; worse yet, it is dependent on the order the springs are examined, and correcting one spring may overextend another, and there is never gauranteed to be a correct traversal order. The procedure works in most cases because often the result of shortening one spring and lengthening another is to propagate deformations throughout the cloth structure, but nevertheless, over-extended springs can still manifest. The results are better when the procedure is run multiple times in a row, but despite the assertions of the author of the method, the process was not found to always converge to a completely non-extended state, even in common situations.
However, this method is coupled with powerful advantages. Despite the caveats, this method does produce realistic-looking output in most cases. In addition, not only does the time constant of the system need not be reduced to match higher spring constants, the constraint process also always the time step to be set to a value at which the system would otherwise be unstable. This often means an order of magnitude larger time step. The same simulation shown above running at .1s, and becoming unstable, and then running at 0.01s, and remaining stable but showing overextension, can be compared to a simulation of the same mesh run at a 0.1s time step, with the constraint process applied:
The cloth mesh now shows almost no over-extension, with 10 times fewer time steps required. According to the author of the paper, in most cases this method leads to a 90% reduction in the running time of the simulation. Thus this model sacrifices a tolerable amount of accuracy for a dramatic speed improvement.
The first condition is handled by this simulation by the first constraint process; the velocity of the nodes is always limited by the maximum deformation rate. The second and third conditions can be met with a triangle grid small enough to be simulated in real time on modern hardware. There are still serious disadvantages to this method - sliding contact will never be correctly handled, and if a node position oscillates between outside and inside the repulsion distance, it will visibly and unrealistically jitter. In addition, this process is still fundamentally an O(n^2) algorithm, although its cost is reasonable for the meshes used here, and can be reduced through the use of bounding box hierarchies. However, for several common sitations, like determining the 'drape' of fabric, this simple method is good enough.
Many improvements can be added to this system. Better collision detection systems are possible to implement in real time using novel reductions in the number of computations needed. One such system is presented in [Provot 97] in which the convexity of the cloth is determined quickly through a hierarchical series of bounding cones, such that if an area of the cloth can be determined to be convex, no intersection calculations between nodes in that area are carried out. Collision with other objects is a natural area to expand into in order to model a wider variety of situations.
Commands: