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