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 acutally describes a few problems with GJK. I had this problems also in practise. Should maybe mentioned. -- 62.134.229.57 13:10, 14 November 2006 (UTC)