Comment by torginus
2 days ago
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.