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.