Constrained Particle Dynamics

For our second assignment in my physically-based modeling and simulation course we were given the task of implementing a particle system capable of imposing constraints upon the particles. An example of a constraint would be requiring two particles to always stay a fixed distance apart. The trick is getting the particles to obey physics while also obeying all constraints imposed upon them. How do we define the particles' behavior to accomplish this?

It turns out a good way to do this is through the use of constraint forces, which are directly-calculated forces that cancel out all illegal accelerations, thereby only allowing the particles to move in a way that maintains their constraints. When I say the forces are directly calculated I mean that the force calculations are done before the particles have violated their constraints, in effect never allowing them to do so. This is in contrast to the penalty method which applies restorative forces after the particles have already violated their constraints (such as in the collision response of the mass-spring system I did earlier).


There's an excellent reference on the internet by Andrew Witkin of Pixar that explains constrained particle dynamics and how to use them. Because his article is basically what I used to learn about the topic, I'm not going to give any kind of lengthy explanation about the math or implementation of the system, since I would essentially just be repeating what he's already said. And besides, I'm sure his explanations are better anyway. The article can be found here.

One aspect of Witkin's method that makes it ideal for interactive applications is the treatment of constraints as individual objects that can be inserted and deleted from the system as needed. Each constraint object is responsible for calculating and filling in its own portions of the required matrices. What this means is that you don't have to hard-code the linear system of equations that need to be solved, which allows for an interactive simulation that can add and remove particles, and their constraints, at will. If you have no idea what I'm talking about, then I refer you to the reference above. =)

The video below shows my implementation of Witkin's system, using 18 particles constrained to a ring. The top-most particle is constrained to remain in place, the bottom-most particle is constrained to remain on the ring, and every particle is constrained to remain a fixed distance from its neighbors. External forces are applied interactively through keyboard input. There's also no collision (by design), because the 3D-ness of everything is just meant as a visual aid to help "see" the constraints. And just like the first assignment, this too is written in C/C++ and OpenGL.

Deformable Objects Via 3D Mass-Spring Systems

This semester I'm taking a course on physically-based modeling and simulation, a topic that sounded interesting when I signed up for it but one that I didn't know too much about. So far it's turning out to be very interesting indeed, and challenging and fun too. I'd say it's the best course I've taken yet.

For our first assignment we had to simulate a deformable jello cube that moves around within a bounding box under an arbitrary non-uniform force field, bouncing off any plane it comes into contact with. The jello cube itself is modeled as a 3D mass-spring system: the cube is discretized into a grid of mass points that are all connected to their neighbors with springs. The springs are what maintain the cube's shape but at the same time allow jello-like deformity.


It turns out just having each mass point connect to each of its six direct neighbors isn't enough to maintain the cube's shape - the grid of points can shear while still allowing the springs to remain at rest, resulting in a collapsed (i.e. flattened) cube of jello. There are actually three different types of springs needed to keep the cube from losing its form:

1) structural springs (direct neighbor links, defines the shape of the cube)
2) shear springs (diagonal neighbor links, prevents shearing)
3) bend springs (direct 2nd-neighbor links, prevents folding)

Ok, that's not entirely true. The bend springs aren't strictly necessary for a cube shape because the other two types will keep the cube from folding over anyway. However, a 2D simulation such as cloth would need all three types (assuming you didn't want to allow the cloth to fold over on itself).

The cube in our assignment consists of 512 mass points in total (8x8x8) resulting in 6,220 springs in the system. In contrast, a system consisting of just 8 points (2x2x2) would have 28 springs. As you can see, the number of springs grows exponentially with the number of mass points. This can make finely-grained modeling of large objects using mass-spring systems not very feasible. The screenshot below shows just the surface points and connected structural springs of the jello cube.


The elastic forces exerted by the springs are found by using Hook's Law, F = -kx. In addition to these forces there also needs to be a damping force that always opposes the motion. Without any kind of damping the springs would oscillate indefinitely and eventually the simulation would fail. Damping forces are modeled similarly to elastic spring forces, except they depend on the velocity: F = -kv. Note that the value of k is different for damping than it is for springs. The two forces are added together to obtain a spring's overall force contribution.


Collision with a plane is handled via the penalty method. Once a mass point has been found to be colliding with the plane, an artificial collision spring is placed perpendicularly between the plane's surface and the mass point. This new spring will push/pull the mass point backwards and away from the colliding plane. As you might expect, collision springs have their own elasticity and damping coefficients, just like ordinary springs.


The final piece of the simulation is the external force field which causes the jello cube to move around within the bounding box. The field's resolution (i.e. the number of force points in the field) can be arbitrary, and the cube is constantly moving, so trilinear interpolation is used to find the exact force at each mass point.


So what does all of this add up to? Using Newton's 2nd Law, F = ma, the acceleration of each mass point can be calculated as follows:


Combining the equations together for all the mass points gives us a system of ODEs (ordinary differential equations), which can be solved numerically using integrators. Examples of such integrators are Euler, Runge-Kutta 2nd-order (RK2, a.k.a. midpoint method), and Runge-Kutta 4th-order (RK4). I won't go into how they work here; that's a topic unto itself. Deciding which integrator to use is usually a tradeoff between accuracy and computational cost. For example, the Euler method is computationally inexpensive but very inaccurate. Very small timesteps are needed to keep it stable which doesn't allow for fast simulations, so it's rarely used in practice. The Euler and RK4 methods were both implemented for the assignment.

The first video below clearly shows the deformations of the jello cube as it bounces off the walls. The second video is the simulation I turned in for the assignment. Different values for the spring and damping coefficients were used to achieve the different effects. And for those who are wondering, the simulation is writtin in C/C++ and OpenGL.