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 2simplex case can be reduced to zero checks (like the 1simplex case) because you already know the point is past the origin. However, the 4simplex 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 subsimplex 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.
— Casey
PS. If you like my blog and want to see what I’m working on these days, here are some links to my current projects:

Star Code Galaxy 
A complete course that focuses on the fundamentals of programming that apply to all programs in all languages, rather than flavorofthemonth frameworks and frivolous syntactical sugars. 

Meow the Infinite 
The feline space opera you’ve been waiting for, presented in serial comic form. 

Handmade Hero 
A complete, professionalquality game and engine, coded from scratch on a live stream. 

1935 
A fully interactive story about the criminal underworld of 1930s New York City and the prosecutors charged with bringing them down. 