I wish to implement a cloth simulator under the assumption that all other geometry is static. This will tie in with my 348b project, which will contain some object (statue, wooden cross, haven't quite decided) draped in cloth. Lacking both the time and artistic ability to model the cloth, but desiring realistic folds and wrinkles, simulation is the answer. While learning more about numerical analysis/physically-based simulation, I will work to implement previous cloth modeling and collision techniques.
-Implicit vs. Explicit Solvers
-Bigger Time Steps via Implicit Methods
-Detecting and Avoid Collisions
- -Collision with Other Objects
- . -Cloth-Cloth Collisions and Proximity
As outlined above, I will make the cloth model and implement the collision detection. This will then be used to render a sheet draped in an otherwise static scene.
Background Cloth is a solid material, which allows for deformations in its shape. Though it can shear, stretch, and bend, it resists those movements. When dealing with cloth, we are typically deal with woven cloth, which while not fully understood, we are able to model to a greater degree than knitted cloth.
We typically model cloth a mass-spring system, though finite element methods exist as well. The motion of cloth is governed by the equation x = M^-1(-dE/dx + F) where M is the matrix of masses, E is the energy of the system and F are external forces. Thus, the governing equation is a partial differential equation, but is solved as though it were an ODE. The internal energy of the cloth has shear, stretch, and bending components.
Thus, in order to determine the position of the cloth at a time t, we need to solve this equation. We accomplish this through numerical integration techniques. The obvious first choice is an explicit method such as forward Euler which is simply: x(t+1) = x(t) + (step size)*x(t, x(t)) However, the forces governing cloth are stiff. For the system to remain stable, we would be forced to take very small time steps. Given that cloth simulation is often used in animation, this is impractical. We would like to take larger time steps without losing stability. Thus, we want a implicit method , which allows for time steps bounding only by accuracy.
The downside of an implicit method is that it requires solving a system of (possibly non-linear) equations each step, which adds a lot of overhead. Luckily,  showed that since the damping forces of most reasonable cloth models are linear in the velocity and only non-linear in the positions, we can use a mixed-scheme to obtain advantages of both the implicit and explicit methods. We can take larger steps thanks to the implicit parts, while not being overcome by the complexity of non-linear equations. Furthermore, since it produces a symmetric definite Jacobian, we can employ a fast conjugate gradient (CG) solve, taking advantage of the sparsity of the system and the lack of need to build a full matrix since no pre-conditioner is employed.
Finally, once we take a step, we need to account for collisions both between the cloth and other objects in the world and between different parts of the cloth. Many different ways exist to deal with these issues and how to resolve collisions and avoid collisions altogether.
Technical For my project, I implemented a simplified cloth simulator. It proved to be a challenge though I believe I learned quite a bit along the way. My simulator uses the shear and stretch forces found in  and the bend forces and integration method found in . It also utilizes the collision resolution techniques found in . I only had time to implement cloth-object collisions, but hope to do cloth-cloth in future work. Since the simulation was being built into the pbrt renderer, all other objects are static. Thus, before the simulation, a kd-tree is constructed for the scene. In each collision step, we check the particle's path against the kd-tree.
A big problem I ran into involved Boost's ublas implementation. In trying to use it with the method of vectors of particle's positions and velocities and a Jacobian of 3x3 matrices, there were problems with the way the Boost library works. Many operations did not work as expected and matrices needed to manually be set to correct sizes and cleared, which subtracted some of the usefulness of a sparse representation.
Another big issue was dealing with zero. Problems arose from both division by in normalizations and worse still, the propagation of close to zero values. I really learned the importance of checking each value to make sure it was set to zero when it was a really small value. This mostly came up when bend forces or velocities would slowly increase until the system became unstable.
Perhaps the biggest difficulty was in effectively testing the system. I found on a number of occasions that I thought I had fixed an issue only to have it reappear when a greater number of particles were used to discretized the cloth. Also, I discovered the importance of checking collisions between triangle and plan to implement that as further work. I believed that I could simply rely upon a large discretization to allow only point checks. However, in doing so I lost the ability to check my system without having to wait for a very long simulation. This was the primary fault of my simulator. It appears to still be somewhat unstable when undergoing collisions when the number of particles is high, but collision is not terribly effective at lower counts both because collisions are missed and because of the large size of the triangles.
Below are some images I rendered as well as the code I wrote for solving the ODE, doing CG and collision resolution.
 Baraff and Witkin 1998  Bridson et. al 2003
Low Particle Test