Implementing GJK (2006)
By Casey Muratori
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.
For more information on my current projects, join the Molly Rocket Mailing List: