How often in games and animations do we have objects interacting with each other? Almost constantly right? Characters walk over grass. They hit things with swords, maybe kick a ball, or swing on a rope. And what could be more infuriating than playing a game and seeing something horribly unrealistic – like when you’re driving a car and suddenly it get launched into the sky. In the end, all of this comes down to having a good dynamic systems simulation. And well, physics is hard, but surely we can do better.
Prior to Position Based Dynamics by Matthias Müller et al. [2006], simulation of dynamical systems in computer graphics was all force based. This means that at each time-step, internal and external forces are calculated and then transformed into accelerations using density distributions or vertex masses. Finally, the accelerations are turned into velocities and the velocities into positions through some integration scheme.
And while this works well enough, things are not always easy. It meant you have to use implicit integration methods and have sparse system solvers which can get quite complicated. And what if you want to control the positions of your object in some more direct way – for example, interacting with objects that are animated with keyframes. Using a force based method would make that very difficult.
In this paper, a position based method is proposed. And it’s fast. In 2006, it was able to do simulation of cloth, rigid-soft body interactions, handle self-collision, tearing, etc. in real time! And as the icing on the cake, it’s unconditionally stable, which is a great improvement compared to the previous methods which required all kinds of messy numerical intergration schemes. Müller has a youtube video showcasing this capability:
It’s no wonder then that Nvidia acquired Ageia which was the company that developed the Position Based Dynamics method and implemented it on a special physics processing unit chip. Now, the method is built into Nvidia graphics cards and is used in the PhysX engine.
But how does position based dynamics work? It’s not too complicated.
First, we have to be able to represent an object. This is done as a set of vertices and constraints. The vertices are straightforward. Each has a position $x$, mass $m$, and velocity $v$. A constraint is a bit more abstract. It represents how things are attached together and how strongly that attachment is. This is done by defining a function $C(\{x_i\})$ that maps vertex positions to a value. There are both equality and inequality constraints – the equality constraints are satisfied if $C(\{x_i\}) = 0$, and the inequality when $C(\{x_i\}) \geq 0$. The constraints are modelled effectively as springs, and have an associated stifness parameter.
Now, lets take a look at the algorithm:
1. initialize all vertices and constraints, set timestep $\Delta t$
2. calculate external forces
3. for all vertices $i$, calculate the new velocities with a simple forward Euler method: $v_i(t) = v_i(t-1) + \frac{\Delta t}{m_i}f_{ext}(x_i)$
4. damp velocities if necessary
5. update positions using simple kinematics: $x_i(t) = x_i(t-1) + \Delta t v_i$
6. get any new constraints needed due to collisions
7. move $x_i$ so that they satisfy all constraints while conserving linear and anguluar momentum
8. update the velocity since we moved around the positions to satisfy the constraints: $v_i(t) = \frac{x_i(t)-x_i(t-1)}{\Delta t}$
9. goto step 2 while we are still simulating.So in effect, at each timestep we have to: use external forces to update vertex velocities, then use the new vertex velocities to update positions. Next, we ensure all constraints are satisfied, and finally update the velocity again to account for the constraint enforcing step.
See – it’s really not so bad at its core!
Of course, the devil is in the details. We’ve glossed over how to do the scarier things like dealing with collisions and ensuring the constraints are satisfied while adhering to momentum conservation laws. If you’re really interested, here is a quite long video that gets into the weeds:
And if not, now you at least have a cursory level understanding of Position Based Dynamics. With that, we can happily go back to thoroughly appreciating its applications in video games and animation tools!