GJK
The incomprehensible little screenshot at the right is my first GJK implementation running in test mode. I'm actually kind of disappointed in how straightforward the algorithm is once you drill past some poor notation in the standard papers. I remember that I put off playing around with GJK a couple years ago because I had the impression that it was High Voodoo. Apparently, not so. Gino van den Bergen's paper is a comprehensive account of what you need to know to implement the core of the algorithm, especially when augmented by examination of FreeSOLID, but the notation makes me groan.
Once you get past that, the idea is really quite elegant and straightforward. I especially like the way the underlying representation of the hull is completely opaque to the inner loop. Quadrics, boxes, polymeshes, whatever. If it's convex, toss it in and it Just Works. Sweet. Want to sweep out linear motion? Twiddle the return value of one of the support points based on the dot product of the direction of motion and the support vector. Done.
The depressing part, of course with all object interference detection is the messy reality of implementing such a nice, clean, algorithm in dirty, nasty, single-precision floats. This stuff isn't currently very robustinated against precision problems, I'll eventually do that if I ever figure out what I'm going to use this for.