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.
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 flavor-of-the-month frameworks and frivolous syntactical sugars.|
|Meow the Infinite|
|The feline space opera you’ve been waiting for, presented in serial comic form.|
|A complete, professional-quality game and engine, coded from scratch on a live stream.|
|A fully interactive story about the criminal underworld of 1930s New York City and the prosecutors charged with bringing them down.|