I spent about a year struggling with GJK back in the 1990s.
It's useful for collision detection in 3D, and it can also be used as a closest-points algorithm. As a closest-points algorithm, it's easy to understand the basics. You have two convex solids. Start with a random point on each, and get the distance between those points. On each solid, try to improve the distance by advancing along each edge from the current point. Pick the new closest point. Repeat.
This stops working when the closest point is no longer a vertex. That's when the "simplex" concept is needed. The closest points can be vertex-vertex, vertex-edge, vertex-face, edge-edge, edge-face (no unique solution) and face-face (no unique solution). The simplex thing is really doing a case analysis of those cases.
Lots of things go wrong in practice. If you are doing a physics engine, objects will often settle into face-face contact. A single-point collision model will then result in vibration or incorrect movement. Also, as positions settle into face-face contact, the GJK algorithm runs into a small difference of large values problem that can result in a complete loss of floating point significance.
The termination condition can also cause infinite looping.
In theory, this is an elegant solution, but it's a difficult numerical analysis problem.
Despite that, it's probably the fastest approach to the problem. It's O(log N) in normal cases, and O(1) for situations where the positions are closest to the previous positions and you use the last solution as the starting point.
The late Prof. Steven Cameron at Oxford did a lot of work on getting GJK right.
I used GJK in "Falling Bodies", the first commercial 3D ragdoll system, in the late 1990s.
Couldn't agree more. One thing to note is that once you have that contact, you almost certainly want to do something with it. In most cases doing something useful involves knowing the actual overlap information. Working that out is actually _worse_ numerically - you start with the simplex that GJK generates and expand out the way, and do triangle subdivision along the way. It's a total nightmare to do performantly.
It's useful for collision detection in 3D, and it can also be used as a closest-points algorithm. As a closest-points algorithm, it's easy to understand the basics. You have two convex solids. Start with a random point on each, and get the distance between those points. On each solid, try to improve the distance by advancing along each edge from the current point. Pick the new closest point. Repeat.
This stops working when the closest point is no longer a vertex. That's when the "simplex" concept is needed. The closest points can be vertex-vertex, vertex-edge, vertex-face, edge-edge, edge-face (no unique solution) and face-face (no unique solution). The simplex thing is really doing a case analysis of those cases.
Lots of things go wrong in practice. If you are doing a physics engine, objects will often settle into face-face contact. A single-point collision model will then result in vibration or incorrect movement. Also, as positions settle into face-face contact, the GJK algorithm runs into a small difference of large values problem that can result in a complete loss of floating point significance. The termination condition can also cause infinite looping.
In theory, this is an elegant solution, but it's a difficult numerical analysis problem. Despite that, it's probably the fastest approach to the problem. It's O(log N) in normal cases, and O(1) for situations where the positions are closest to the previous positions and you use the last solution as the starting point.
The late Prof. Steven Cameron at Oxford did a lot of work on getting GJK right. I used GJK in "Falling Bodies", the first commercial 3D ragdoll system, in the late 1990s.