SIMD for Collision

Summary

In a previous post SIMD Matters I discussed the big wins I got from graph coloring to make the contact solver faster. That same approach exists in Box3D. I like to call this approach “wide SIMD”. The idea is to process multiple work units at the same time. In the contact solver this means solving four contact points at the same time. This is different from “narrow SIMD” where a 3-vector (xyz) is put into a SIMD register and then standard vector math is expressed as SIMD intrinsics. Narrow SIMD can be useful, but the gains are not as obvious. In 3D there is an opportunity for using wide SIMD that doesn’t exist in 2D. Consider the convex pile benchmark ported from PEEL. This benchmark drops 5120 convex hulls, each with 32 points. Box3D treats boxes as hulls and many of the benchmarks use boxes. The performance with boxes has been good and typically most of the cost is not in the narrow phase. But the 32 point hull is a different beast. Let’s call it “boulder”. The table below shows the hull details for a box compared to the boulder. Hull Vertices Faces Edges Box 8 6 12 Boulder 32 59 89 Box3D uses the Separating Axis Test for collision detection. This is abbreviated as SAT. Using SAT I can find the best features to use for pushing the shapes apart and precisely how far apart they need to be pushed to remove overlap. Furthermore, I use these results to compute the contact normal and the contact points. Other physics engines may use the distance algorithm GJK instead with an overlap fallback such as the Expanding Polytope Algorithm, also known as EPA. I’m a big fan of SAT for convex hull collision because it doesn’t require a collision margin. Shapes can rest directly on each other. The GJK and EPA combo usually tries to keep shapes slightly separated to make keep the shapes in the GJK region, which is faster. This can lead to visual gaps. Also, EPA can be numerically brittle and often physics engines will need a fallback if EPA fails: a fallback for the fallback. EPA is...