Talk:Gilbert–Johnson–Keerthi distance algorithm

Mathematics Stub‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

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]

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]