Implementing GJK

Implementing GJK

Here is a video that describes how to quickly and efficiently implement the Gilbert Johnson Keerthi algorithm for determining whether or not two convex solids intersect (among other things).

Apologies as always for the poor quality, lack of rehearsal, etc., etc.

One thing I noticed when watching the video myself was that I failed to articulate precisely why the Minkowski difference of A and B must contain the origin in the case where A and B intersect. It is extremely simple to prove: for any point in A, if I try subtracting all the points in B, I will only get 0 if there is a point in B that exactly equals the point in A. Ai - Bj = 0 only when Ai = Bj. Thus, if the two shapes share any points, they will necessarily have some point in the Minkowski difference that equals 0, because we try subtracting all points in B from all points in A.

Now, in GJK, we are only actually operating on the convex boundary of A and B, but fortunately that doesn't matter for convex solids, because the convex boundary of the Minkowski difference will obviously still maintain that property. However, if we were to use concave solids, this would no longer be the case, which is just one of the reasons why you can't throw a concave solid at GJK and have it work.

Recommend this page on: Twitter, Digg, Delicious, StumbleUpon, Reddit, Facebook