Last year, after I moved back to Australia from the UK, I spent a lot of time working on a variety of small projects to find my feet again. I was super burned-out after my last job turned from a games tech company into a cryptocurrency cult and just needed some time to recalibrate.
For a while I’d been entranced by simulations like these:
There are a few youtube channels that specialise in them, simulating them offline with Bullet and rendering them offline with Blender. I find these to be absolutely enchanting, and wanted to be able to interact with something this detailed in real-time in VR.
Knowing nothing about physics simulation whatsoever, and with a copy of the XPBD Rigid Bodies paper in my hand, I proceeded to naively begin programming a physics engine using compute shaders in Unity.
Collision Detection is Hard #
At the time, I was no stranger to one of the key components of collision detection in physics: the broad phase. In the broad phase, you cheaply cull all your colliders to pairs of likely colliders. So, having implemented a neat and tidy spatial hashing algorithm and some simple sphere collision to start, I was feeling pretty good about having a big stack of colliding spheres simulating nice and fast on my Laptop 3070 (my desktop still being on a container ship).
(Rendered using the old sphere imposter trick.)
So, onto collision detection for every other shape. How hard could it be?
I quickly discovered the hard way that the internet is full of “garden path” articles and videos about collision detection. To review, there are a few levels of “collision detection” algorithm.
- Boolean: did two things collide or not?
- Directional: what is the separating plane and distance?
- Point: what was one of the collision points?
- Manifold: what are a stable manifold of collision points?
A quite upsetting number of resources give you the first one or two and no more. Many others give you the rest for 2D then hand-wave on 3D. I went down a few paths, including just implementing GJK and EPA, but those are extremely branchy algorithms that grinded the GPU to a halt, not to mention that they need a few frames to build a full manifold. I’m not going to call out specific articles. But suffice to say, don’t trust anyone who hasn’t shipped a physics engine (so don’t trust me!).
It was a long road of dealing with baffling bugs like this:
Though, as a small consolation, though it was wrong it was fast and wrong.
Dirk to the Rescue #
After going back to google, I finally found Dirk Gregorius’ fantastic GDC Talks, which cover methods of doing proper one shot manifold generation, which was a much better fit (though still not perfect) for GPU collision detection. I could explain them here for exposition but honestly you should watch those talks if you need the information.
After that, I finally had something that was starting to look right:
But as lovely as the collisions looked, and as fast as it ran… it just wasn’t stable.
Solvers are Hard #
If you look at the videos above you’ll notice that the towers look quite bouncy. They shouldn’t.
Transferring XPBD to the GPU meant going from using Gauss-Seidel iteration as in the paper (which to put it simply solves local constraints sequentially) to using Jacobi iteration. Jacobi iteration solves all the constraints concurrently, adds up all the changes from those solves, then applies them at once. As a result, long chains of constraints (like a tower) propagate very slowly, and interpenetration happens.
The taller the tower, the worse the bouncing, to the point it collapses. The whole point of the game I was working on was to spend hours meticulously building a structure so that you could have the joy of knocking it down, hardly fun if a physics bug beats you to it! In reality this is why most game physics engines use Gauss-Seidel (or technically “Projected” Gauss-Seidel, or PGS), in addition to some direct solvers here and there.
But at the time I wanted something I could ship, and this had already been too much of a research project for my liking. I decided to try and salvage what I could for something smaller… simpler.