Talk:Gilbert–Johnson–Keerthi distance algorithm

From Wikipedia, the free encyclopedia

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)

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)

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)