Wide SIMD Accelerates Complex Collision Detection in Box3D
SIMD for Collision
I explored how wide SIMD techniques significantly boost performance in Box3D's collision detection, specifically for complex convex hulls. By processing multiple edge tests simultaneously, we achieved over twice the speed of scalar code in our convex pile benchmark. While simple shapes like boxes see little gain, this optimization is crucial for handling detailed geometry efficiently without relying on GJK or EPA algorithms.
EPA is essentially an algorithm for computing a convex hull, and the input data can be flat slivers. That is a challenging scenario for convex hull computation. Hence the need for a second fallback.
- Animats
Exhaustively doing all the edge-edge collision tests is working far too hard. That's why he needs SIMD.
I did the first ragdoll physics system about 20 years ago, when we had less compute available.[1] GJK, which the author mentions, is the preferred algorithm for convex hull collisions. GJK is a hill-climber. You start with two points, one on each object, and walk them towards each other along edges, picking the direction that produces the most improvement. This is O(sqrt N) on the number of vertices per object.
That's with two random starting points. If you're doing this repeatedly, as in an animation, you can start from the winning points of the previous round. If the objects are not rotating and moving very fast, the recheck is constant time. If they move a little, it takes slightly longer, of course. Many modern programs don't use the incremental form, but it's much faster.
GJK is a very fussy algorithm numerically. The optimization involves subtracting large numbers and caring about small differences. Loss of significance due to underflow can be a problem, and can cause the termination condition to not terminate, with the optimization cycling between a few near-optimal solutions. The loss of significance problems show up as objects settle into parallel-face contact, which is why this algorithm tended to loop when put inside a physics simulation where objects settled. Passed tests with randomly oriented convex hulls all day.
This was hard to fix. I had a hack solution th […]
- zamalek
Back in the day I was writing a liero clone, and came up with a neat scheme for pixel-perfect collisions (probably serendipitously, no claims it's unique). A 64bit integer can be seen as an 8x8 mask. You can pixel shift it up and down by simply bitshift left or right by 8n bits. Pixel shift left and right required more instructions; if I was to write it today I would probably store an additional rotated version instead (as that would then effectively pixel shift left and right with bit shifts).
You then have the terrain chopped up into these 8x8s too, and can then do a collision test with at most 4 of them with the 1 character/entity mask.
- animal531
My favourite is probably Bepuphysics due to its C# nature: https://www.youtube.com/watch?v=tjtwSq3u6Dg
Unfortunately it was created before Unity could use vectorization and other C# engines were just starting out as well.
The source, a great resource for learning C# SIMD, even though its a few years old by now: https://github.com/bepu/bepuphysics2
- grg0
As a SIMD noob, one thing that wasn't obvious to me is that SIMD can also speed you up if your mem throughput is underutilized by having the CPU load more data per instruction. It isn't just about compute speedups, which is typically what it's advertised for. Using perf on Linux has been very educational for me to get an intuition for modern CPU performance.
- Decabytes
I feel like SIMD has been around for decades. Why has it taken this long to catch on? I feel like I have been hearing it a lot through the past few years. It feels like it’s talked about like some programming silver bullet