March 24, 2016
Water Shading
September 9, 2015
Balls and Sticks: Simple Polymorphic Constraints for Verlet Particles
A recent class project required me to make a 2D game. Having made some 2D rigid body simulations before, I wanted to make a physics-based game. Looking at some popular physics games, there was a core mechanic that games such as Polybridge, World of Goo and Tiki Towers all shared, called a Verlet particle system.
This very extendable system is actually simple to initially build. By using objects composed of particles with simple rules instead of to rigid body physics, calculations for rotation and torque aren't needed. This takes a lot of complexity out of the implementation. The following code is adapted from Thomas Jakobsen's seminal paper [Jakobsen] and a great implementation tutorial by Jared Counts [Counts]. I'll provide my header files as templates to help you through the implementations discussed in the references.
First off, you create your particle class. I chose to go with a rigorously object-oriented (OO) VerletParticle class but it may be optimal to use arrays for position, previous position and acceleration vectors and iterate over those, as in [Jakobsen]. Regardless of how it's done, the basic idea is that you iterate over some array while performing the Verlet numerical integration method.
If you take only an array of particles and apply some gravity, you could get a great rainfall simulation. That is a tad anticlimactic though. Moving ahead, we need something to force behavior of the particles as the simulation updates. This is realized through a constraint. For this, I used some good ol' fashioned OO interfacing. This will benefit in two ways: firstly, a polymorphic base pointer will keep iteration simple; secondly, the abstraction will allow many different constraints to be built and further extended.
The abstraction of constraints proceeds with the most simple and then a two-body constraint. As in [Jakobsen] and [Counts], you could even have a three-body constraint that provides angular stiffness. I believe this is a great use of abstraction; base class pointers paired with interfaces that guarantee behavior. I figured every constraint needs to be relaxed, which means doing something to the particles so that the constraint is satisfied. Moreover, Boolean checks for whether a constraint still can or needs to be satisfied is necessary for keeping the simulation in a consistent state [Counts]. The ability to check if a certain particle is constrained is very useful for interaction with the particle system in UI or gameplay elements.
Lastly, we need to get the simulation to run. A couple constraints are needed just to get the particles working in a familiar way. A boundary is needed to keep the particles on screen; this is similar to the C1 iteration of [Jakobsen]. Next we need something to hold the particles ("balls") together. For this, I used a class that functions similarly to the C2 iteration of [Jakobsen] and the Link class in [Counts].
The final piece is the particle system itself. It needs to update every frame. First by adding any forces on the particles to get acceleration, then integrating to get the next position of each particle. These new positions then need to be constrained by iterating over the constraints and relaxing them. An important factor in the simulation is the number of relaxation iterations to perform per frame. This is basically a trade-off between performance and accuracy, since more iterations means more constraints are satisfied completely. However, a key observation by [Jakobsen] is that less iterations, even 2-4 can often provide very realistic behavior.
That's it! Your very own particle simulation! A couple OpenGL draw functions, one for "balls" and one for "sticks", make a nice visualization:
Dress it up with a few transformed textures (std::atan2 is your friend) and you get a look very similar to World of Goo:
Until next time,
- Jarrod
[Jakobsen] Jakobsen, Thomas. Advanced Character Physics. 2001. GDC 2001 article. San Jose, California, USA.
[Counts] Counts, Jared. Simulate Tearable Cloth and Ragdolls With Simple Verlet Integration. 2012. Tutsplus article.