Bullet Physics is an open source physics engine that is sometimes used for games and movies.
It supports many near phase collision types such as spheres, boxes, capsules, triangle meshes and convex hulls.
None of these were a good match for my signed distance fields(SDF).
Triangle meshes might seem like a solution, but they have two obvious issues.
- No volume which leads to penetration issues and bad collision detection
- Uses lots of memory to store the mesh
Convex hulls might also seem like a solution, but also have a downsides
- They only work with convex data. To work with concave data you must generate multiple hulls and stick them together.
- Not very accurate representation of the original shape unless you stitch many of them together, this would be infeasible for the world/terrain shape which is many kilometres in size
So I decided to extend bullet to directly support SDF vs SDF collision.
As everything in my game world is represented by an SDF, I do not need any of bullets built in collision types and only use SDF vs SDF collision.
Collision Algorithm
The solution I went with is based on generating a point hull for the SDF, a point hull is a list of points that lie within the shapes negative space. In my implementation all points in a given hull uses the same radius.
To perform collision detection between two SDFs, you treat one of them as a point hull and the other as an SDF. You transform each point in the point hull into the space of the SDF and sample the SDF. If the distance to the negative space is <= the point hulls radius, you have a collision.
I decide which object will act as the point hull based on who has the smaller point hull radius, this ensures consistent collision, and allows for the smaller object to collide against the larger objects full SDF.
For the world/terrain shape I disable the point hull generation pass, it is always treated as the SDF when colliding.
For points that are found to be colliding, a second pass is run to generate the normal and collision depth, and to reduce the number of impact points down to four(this is the number of points bullet wants fed to it).
Result
SDF vs SDF supports both convex and concave shapes.
It also has fewer issues with penetration than triangle meshes since SDFs have proper volume, even if a small object penetrates into a larger one, it will still be pushed out in the correct direction.
Here is a shape for which we will generate a point hull
And here is a visualization of the point hull.
Optimizations sometimes known as midphase
There are numerous ways to optimize this, but here are some that I use. The underlying SDF algorithms are already all SIMD, so this is focused on algorithmic optimizations.
Surface Approximate
Instead of sampling the full SDF against all of the points, I first run a pass that only samples eight points on the point hulls AABB within the SDF. It then uses those eight points to perform a quick rejection of points that incapable of colliding because they are too far away. This often eliminates >90% of the points, so we can skip full SDF evaluation.
Temporal Collision Frame
This is a frame that is specific to a given object vs object collision, it records a rough approximation of the previous collision attempt between the two shapes. If not enough movement or rotation has occurred it can early out and skip performing the full near phase–the previous contact points are reused.
Handling SDFs with broken distance formulas
Otherwise known as Lipschitz continuous– we want gradients whose magnitude is as close to 1 as possible.
Some SDFs do not have euclidean correct distances, for these cases I run a fix up step which calculates a correction factor based on the rate of change in the local space of the SDF.
My correction algorithm takes the distances calculated for the AABB of the point hull projected into the SDFs space, and compares the true distance between the points against the distance returned by the SDF. It compares all of the points against each other, and uses the largest ratio of (sdf distance/true distance) as the correction factor.
This allows for colliding against fractals and other complex formulas, which often have incorrect distance formulas.
Performance Notes
In scenes with many moving & colliding objects:
Initially my SDF near phase and Bullets solver were about equal in cycle usage.
After adding various optimizations to reduce the time spent in the SDF near phase, the solver is now the primary waster of cycles.
Bullets solver has a few SSE based implementations, but they are AoS not SoA based, so the performance gain is minimal.
Bullet has a few inefficiencies in how it works, it loves to iterate over every single CollisionObject just to access a single bool, while this is not a problem for small scenes, it does not scale to the number of physics objects I plan to use.
I plan to rework this part of Bullet in my local copy, and have already rewritten/removed a few passes Bullet was performing that I did not need.
Pseudo Continuous Collision Detection
Bullet has some support for CCD(Continuous Collision Detection), but I’m using my own pseudo CCD instead.
My CCD solution is very simple:
Calculate the maximum distance an object can travel in a given physics tick based on its current velocity, and expand the point hulls radius to incorporate it.
At high speeds this causes expansion, but I cannot visually tell that this is happening.
I run physics at 120 hertz, but I did test it at 60 hertz and it seemed to work fine there also.
I’m not currently incorporating angular velocity, but I will probably add that at some point.
Future Work
- The algorithm for placing points within the hull could always use more work.
- It might also be worth looking into storing a per point radius, this will allow for less points in some situations
- Angular Velocity for CCD