Figure 1. Our simulation using explicit integration.
3D Cloth Simulation
Aaron Bryden & Eva Schiffer
Problem:
Produce 3D cloth simulation using a variety of approaches.
At least one approach should run well in real time.
Goal:
Learn about the history and current state of cloth simulation.
Implement a system that performs explicit and implicit integration on a modestly sized cloth grid. The system should be able to handle very simple pinning constraints.
Basic Principles:
In this section of our writeup we will discuss the basic principals of the mass springs model as well as explicit and implicit integration very briefly.
The essence of the mass springs model is a particle system representation. The cloth is represented as a mesh of cloth particles (in our case we used a grid to simplify calculations) connected by spring forces to control the behavior of the cloth as it stretches and deforms. Each particle keeps track of its current position and velocity at the current time and can generatively find the forces on it at the current time. The forces on a particle include the spring forces as well a simple gravity force and a simple aerodynamic drag force. The spring forces for a particle are made up of two parts, a force that tries to move the positions of the particles towards the rest length of the spring (-ks (|l| - r) ) and the viscous drag force that tries to counter the velocities of the two particles ( kd (v1 - v2) ).
Explicit integration is basically the act of "guessing" at the next state of the particles in the system, based on the current state and current forces on the particles. It is in essence the act of taking a chunky step forward in what you hope is the correct direction. However, since the systems we are trying to model can have very subtitle complex behaviors, this is not always going to work very well. Notably, if explicit integration is performed with too large of a time step, it overshoots the actual answer that was desired and will over correct on the next time step. The system will then degenerate into chaos as the spring forces try to correct for increasingly large errors in our prediction of the future state. This can be overcome by using a higher viscous drag force in the springs, but this leaves the cloth looking like it is "floating in molasses" as Witkin put it.
The basic method of performing expicit integration is:
1. Calculate the forces at the current time, t0
2. Move the positions of the particles to their next, t1, positions by adding their current velocities (scaled by the time step) to their t0 positions.
3. Calculate the accelerations on the forces at t0 by dividing the particle forces at t0 by the masses of the particles.
4. Move the velocities of the particles at t0 to their t1 state by adding the t0 accelerations (scaled by the time step) to the t0 velocities.
5. Repeat by as many time steps as you like.
The basic method of performing implicit integration is:
1. The step in the implicit method is calculated based on the conditions at the end of the step
2. Perform the taylor expansion of f to say f(x0 + deltax, v0 +deltav) = f0 + df_dx*deltax + df_dv*deltav
3. Substitute the Taylor series expansion of f into the equation defining deltax and deltav
4. This sets up a linear system which after some rearranging is solvable with a conjugate gradient method.
What We Read:
In this section we will give very brief summaries of the papers that we read for this project. Additional, longer, summaries will be handed in in a separate file along with this paper.
"Differential Equation Basics", Andrew Witkin and David Baraff of Pixar Animation Studios, SIGGRAPH 2003 Course Notes.
Summary: This paper discusses the basic strategy of explicit integration and the specific cases of Euler's method and the midpoint method. The paper also touches on how to calculate error in order to estimate adaptive step sizes and some issues to consider when implementing an ODE solver.
"Particle System Dynamics", Andrew Witkin of Pixar Animation Studios, SIGGRAPH 2003 Course Notes.
Summary: This paper discusses the structure of a basic mass springs particle system, the forces that will act on the particles and how to define them, as well as a little information on collision detection and response.
"Large Steps in Cloth Simulation" - David Baraff and Andrew Witkin
Summary: The major contribution of this paper is a system for performing cloth simulation using implicit integration as opposed to explicit integration. This results in far superior performance compared with previous cloth simulation methods.
"Interactive Animation of Cloth-Like Objects for Virtual Reality" - Mathieu Desbrun, Mark Meye, Alan H. Barr
Summary: This is a chapter out of the book "Cloth Modeling and Animation". In
this chapter, they address the problem of interactive animation of
deformable objects in virtual reality systems.
"Simulation of Clothing with Folds and Wrinkles" - Section on Semi-Implicit Integration - R. Bridson, S. Marion, R. Fedkiw
Summary: The part of this paper that we examined defines a system for "Mixed Explicit/Implicit Time Integration." The goal of this system is to combine the advantages of explicit and implicit integration with as few as possible of the disadvantages.
What We Did:
We implemented a basic mass-springs model and set up both explicit (Euler's method) and implicit integration in order to calculate the movement of the model. Our model included simple spring forces, very simple aerodynamic drag, a static downwards gravity force, and simple pinning constraints. We have included more detail about some of the parts of our implementation below.
The mass-springs model was based upon the one presented in the "Particle System Dynamics" section of the SIGGRAPH 2003 course notes. We changed the data structures involved somewhat and added in the force calculations and enforcement for pinning constraints. This same section provided the basic outline of our explicit integration, though our forces and time steps needed a lot of tweaking in order to get a believable resulting animation. We initially mis-interpreted the spring force equation and had to later rework our implementation to better match the model presented in the course notes.
We based our implementation of implicit integration off of Hamilton Chong's implementation ( see http://www.people.fas.harvard.edu/~hchong/cs276r/index.html ). In particular we used his Modified Conjugate Gradient solver and his definition of the first and second derivatives of the constraint equation in order to calculate df_dx and df_dv.
Example Results:
Our results indicate that as expected implicit integration ran dramatically faster than explicit. For instance, Eva's laptop was able to run grids 4 times as large in real time using implicit integration as opposed to explicit.
As far as interesting behavior we discovered that the cloth behaves dramatically wrong if too large of time steps are used in explicit integration, the springs basically overcompensate more and more each time step and eventually just go completely crazy. In addition we discovered that this could be solved by either relaxing the springs more or greatly increasing the damping factor, but doing these things resulted in unrealistic looking cloth.
Given are two screen shots, 1 of explicit integration running and 1 of implicit.
What We Learned:
In terms of our understanding of cloth simulation we advanced our understanding to the point where we understand the spring forces involved as well as their first and second partial derivatives as well as the damping forces. We also got the point where we understand the manipulation of the equation defining the change in velocity based on the forces at the next time step, as well as how to set up the matrix and vector used to solve for deltav. What we are still having some trouble with is understanding exactly how the conjugate gradient
solver was modified and also understanding exactly how semi-implicit integration is performed.
In terms of what we learned about project planning, we learned that we need to be more conservative in our estimation of learning times. We were pretty cramped to get this done in the time available because it took us a good deal of time just to get our understand of linear algebra and ODEs to the point where we were able to grasp the Baraff and Witkin paper.
For the Future:
Our initial plan for project 2 is to get our system to the point where it can be used to demonstrate and help people understand the differences between explicit, implicit, and semi-implicit integration. This will involve both updating the user interface so the various constants can be set interactively, and improving the stability of the simulation in general, as well as providing a interface for saving the results of the computations over time so we
can set the parameters, perform the calculations and play it back. As part of this we will ensure that our system works on a larger grid, tentatively 50X50.
We also intend to prepare the notes required for the April 3ed lecture on advanced topics in cloth simulation. This will include a detailed presentation on implicit and semi-implicit methods as well as some background on the math to get folks up to speed. This presentation will incorporate our updated cloth simulation tool to show examples of the various resulting properties of the cloth systems solved in different ways and with different constants and other force properties.