Comment by Animats
2 days ago
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 that detected cycling, and Prof. Stephen Cameron at Oxford finally fixed the numerical math to behave.[2]
(You can get his code from his web site, there's a substantial license fee for commercial use, and he died years ago. I licensed the code back in the 1990s, but can't sublicense or release it. If someone really wants it, they'll need to find his heirs and negotiate.)
You also need "good" convex hulls. Your options are hulls with polygonal faces that won't be perfectly flat due to numerical precision limits, or hulls with triangular faces that are sometimes coplanar. Using a convex hull generator which can enforce a minimum break angle of about 1 degree, with polygonal faces, seems to work best.
Now there's OpenGJK.[3] Haven't looked at that. Hopefully they've dealt with all these problems. I was doing this back in the stone age of game physics, when nothing worked out of the box.
[1] https://www.youtube.com/watch?v=5lHqEwk7YHs
There was an even better version of GJK published around 2017 which made it more numerically robust: the Signed Volume Method (https://dl.acm.org/doi/10.1145/3083724) OpenGJK is written by the same author, and is based on that paper.
In addition to writing Box2D, the author of this article was the lead physics programmer at Blizzard for 15 years. He also wrote an evaluation harness called Solver2D where he has pitted many solvers against each other. I suspect that he has solid reasons for choosing to exhaustively test for collisions.
In fact, if you listen to his recent podcast episode with Łukasz Ściga (which I linked in another comment), he mentions some properties that his current project (The Legend of California) relies on like determinism and reversibility. He also put up an earlier blog post with accompanying videos that show how Unreal’s built-in physics engine fails to resolve important collisions in their game correctly: https://box2d.org/posts/2026/06/announcing-box3d/
GJK is a cool algorithm but:
- Collision using simple shapes is very optimized and fast
- GJK's complexity scales linearly with the complexity of the support function, while checking pairs scales quadratically, which is a big advantage of GJK
- GJK imposes a convexity requirement, so non-convex shapes need to be decomposed somehow, this is a non-trivial problem if your shapes are dynamically generated and you need to decompose them dynamically. An absolutely nontrivial problem.
- Physics engines have a 'broadphase' where they detect collision pairs using approximate shapes much more efficiently. For a fully general algorithm, this is needed for GJK as well, because of said decomposition. This gets rid of much of the quadratic behavior of simpler algorithms.
- GJK doesn't give you penetration distance which simple algorithms do - this needs additional work, but it might be tractable since that only happens after a collision was found
- A nice thing about GJK is that it generalizes easily to continuous collision detection
- In video games, developers can 'cheat' and design their objects to be easily represented by (composites of) simple shapes - cubes, cylinders, spheres etc.
So in all, GJK imo, is a 'mini-broadphase' and not separate technique (in that it forwards the actual query to the support function).
So if OBB-OBB collision is inherently 5x faster, and SIMD gives you another 6x speedup, you need 30 collision evaluations to break even. The nature of 2D vs 3D space is that crowding in 2D is much less feasible.
You need a coarse level of collision detection above GJK, of course. Axis-oriented bounding boxes and spheres both work.
Generating good convex polygons is indeed a problem. I used QHull for that. QHull is overkill; it can generate convex hulls in N dimensions. But you can specify such things as minimum break angle, to avoid near-coplanar faces.
It would be interesting to look at some of the newer algorithms for approximate convex decomposition. These decompose a non-convex object into multiple convex hulls that can overlap slightly. Decomposing a non-convex object into multiple convex hulls perfectly tends to generate a lot of small parts you don't really need. Think about what happens at an elbow. I tried some academic code for that last year, but it wasn't very robust.
Simple shapes are not necessarily a win over convex hulls, because even a cube means testing 12 edges against 12 edges.
At one time I used a separating vector algorithm as a preprocessor for GJK, but the performance got worse.
Collision detection is such a fascinating subfield with so many approaches based on what representation you end up going with, and what sort of domain you are working in.
> It would be interesting to look at some of the newer algorithms for approximate convex decomposition. These decompose a non-convex object into multiple convex hulls that can overlap slightly.
I wonder if you involve the broadphase in this, you could make an even cheaper decomposition - if you used something like BSP (which is a collision detection algo in of itself) that constrained nodes spatially, like BSPs, so if the convex decomposition nodes were to 'spill out' of the original model, those points would be rejected by the broadphase so they wouldn't matter.
Right now, most algorithms discard all the information built up by the broadphase.
Needing SIMD is hardly a problem though, especially if you only need the completely ubiquitous versions, and in using it, can avoid a good amount of fussy stuff.