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.