In 2004, I needed to write some volume intersection code for a visible surface removal algorithm. Since
RAD Game Tools, where I worked, was right next door to
Valve Software at the time, it was not unusual for me to have lunch with programmers at Valve.
During this time I happened to have lunch with
Jay Stelly, the person who did the original physics integration for
Half Life 2. We talked about intersection testing, and he pointed out how he thought all the papers on
GJK were very bad, and obfuscated the real action of the algorithm. He then proceeded to explain how both
GJK and the
expanding polytope algorithm for convex hulls were both very easy to understand when thought of geometrically.
Jay’s explanation made perfect sense to me, and I found it intuitively obvious how to write a GJK solver from his explanation (unlike most GJK papers, which are violently obtuse). So I went back to the office and wrote one.
As I worked out the cases, I realized that the tests you needed to do for computing GJK, when considered geometrically, were
much simpler than the ones advocated by the papers, which only considered the matter algebraically. This lead to a more optimal formulation, which I would like to call the “Gilbert Johnson Keerthi Stelly Muratori,” or “GJKSM” formulation. Although I generally don’t like naming algorithms after their creators in lieu of a more properly descriptive name, if the original is already an absurd concatenation of names, why not continue the trend?
A few years after this development, I recorded a makeshift video describing the technique:
Since then, the technique was refined further. For example, the 2-simplex case can be reduced to zero checks (like the 1-simplex case) because you already know the point is past the origin. However, the 4-simplex case has yet to be proven to be “fully reduced”, as far as I know, so the jury is still out on how few if’s you can do to select the correct sub-simplex there.
A decade after this talk, I recounted the discovery of the technique again during my lecture at the
2016 Papers We Love conference, where it occupies the last 25 minutes or so of the lecture.
