Talk:Gilbert–Johnson–Keerthi distance algorithm

The description of the algorithm isn't quite right. It only works for convex polyhedra (or, in theory, polytopes in N dimensions). And "enhanced" versions of the algorithm which use edge information, not just a point cloud, are used in practice, because they're much faster.

I've fixed the links and added a link to the best implementation. It's actually quite hard to implement this algorithm properly; the termination condition is subtle. The Stephen Cameron paper gets it right. (And that took some work back in the late 1990s.)

This is a tough algorithm to understand. It's widely used in video games, so it's of practical interest. It's hard to implement correctly. So a really good Wikipedia article, with pictures of what the "simplex" does, and a discussion of what can go wrong, would be useful. I don't have time to write it, though. It would be a nice project for a grad student in computational geometry.

On the other hand, a good explaination of what it does, when it's used, and how to get more information is probably enough for Wikipedia.

So I'm leaving this as a stub, but with good links to the key papers.

--Nagle 19:28, 9 March 2006 (UTC)[reply]

http://citeseer.ist.psu.edu/cache/papers/cs/17667/ftp:zSzzSzftp.inrialpes.frzSzpubzSzsharpzSzpublicationszSzsundaraj:etal:iros:00.pdf/sundaraj00new.pdf That paper actually describes a few problems with GJK. I had this problems also in practice. Should maybe mentioned. -- 62.134.229.57 13:10, 14 November 2006 (UTC)[reply]

Amusingly, that paper cites my posting to comp.graphics.algorithms as identifying the problem. The Steven Cameron paper cited in the article has some of the answers. That needs a better cite; the link is to the IEEE repository, which is, annoyingly, a pay site. --John Nagle 04:35, 20 June 2007 (UTC)[reply]

Probably a redirect from GJK algorithm should be added. -- Vftdan (talk) 18:55, 24 April 2022 (UTC)[reply]

Nice pictures

Some pictures were added. But they show collisions, not distances. GJK is normally a distance algorithm for non-intersecting polyhedra, but there are extensions for "negative distance", i.e. interpenetration.

For the distance between two convex polyhedra, there are four main cases - vertex/vertex, vertex/edge, vertex/face, and edge/edge, plus the ambiguous cases edge/face and face/face, where the objects are parallel and there is no unique closest-points vector. See the Cameron paper. The ambiguous cases are troublesome. In practice, in physics engines, they come up frequently, since as objects come to rest they tend to settle into a face/face configuration. This can lead to roundoff error problems in collision detection and is often a statically indeterminate system in a physics engine. --John Nagle (talk) 03:46, 15 February 2011 (UTC)[reply]