If you want the closest point between two convex polyhedra, GJK is useful, but it helps to think about the problem differently. You don't really need the Minkowsky difference, which requires looking at all the points. It's a local hill-climbing problem. You start with a point on each convex polyhedron and walk along the edges to a shorter distance between the points. You still need a simplex, but its geometric interpretation is clearer - it's describing a point-point, point-edge, edge-edge, point-face, edge-face, or face-face closest situation, all of which are possible. So you advance one point of the simplex at a time.<p>Visualize a small cube sitting just above a big cube for the face-face situation. The closest vertices may be much further apart than the faces.<p>Performance is O(sqrt(N+M)). And that's from a cold start. In practice, when simulating moving objects, you start the algorithm from the previous solution. If movement is slow relative to the frame time, it usually takes zero or one improvements to get the new closest points. So that's O(1). This is very good performance.<p>There are some numerical issues. First, you need a convex hull. Which means no coplanar faces. Faces should be flat polygons, not just triangles. Otherwise, you can get stuck on the wrong triangle of a flat face. Of course, polygons are never completely flat in floating point, which creates other problems. A good solution is to require at least a 1 degree break angle at each edge. Convex hull programs can do things like that. This also provides some mesh reduction in case someone puts in something with a huge number of faces.<p>Second, there's a loss of floating point significance if two faces are nearly parallel. This can cause the algorithm to go into an infinite loop, where the termination condition is not satisfied and the algorithm cycles between similar simplexes. If you're building a physics engine, that's what normally happens when one object comes to rest upon another. So that has to be dealt with.<p>I used to do ragdoll physics, back in the 1990s.[1] I used the implementation of the late Prof. Stephen Cameron at Oxford, and discovered the "problem in the termination condition" he mentions.[2] I had a somewhat clunky fix, but his was better.<p>[1] <a href="https://www.youtube.com/watch?v=-DaWIHc1VLY" rel="nofollow">https://www.youtube.com/watch?v=-DaWIHc1VLY</a><p>[2] <a href="https://www.cs.ox.ac.uk/people/stephen.cameron/distances/" rel="nofollow">https://www.cs.ox.ac.uk/people/stephen.cameron/distances/</a>