GJK in C#

While I was working for Microsoft, they were busy working on this kick-ass video game SDK for the hobbyists that you might have heard about : The XNA framework. Managed code is a pleasure to work with. This is just the type of thing to get me back into coding in my spare time. After attending GDC2006, I felt inspired to write my own implementation of the GJK collision detection algorithm, natively in C#.

For reference, I used Gino Van Den Bergen's paper on the subject (http://www.win.tue.nl/~gino/solid/jgt98convex.pdf). He was the presentor of the GDC talk. He has one of the most complete treatments i've seen of the nastiest problem that the algorithm has: numerical instability.
Christer Ericson's "Real time collision detection" book was also useful in explaining how this algorithm works.
Now I won't feel guilty of not explaining it here, and I'll just jump to some pictures!



Here we see two boxes that are candidates for the intersection test. I'll direct your attention to the small white dots on the screen. These are the edges of the configuration space volume. It's a naive representation for debugging only, and all n^2 vectors are shown. The configuration space volume is defined by the convex hull around these points. The shape of this space varies as the relative orientation of the two objects changes.

The algorithm supports any convex shape that can be represented by a support function s(v). v is a direction vector, s(v) giving the farthest point on that convex in the direction v.

It just happens that it's easier to draw boxes, and debug them ;) So in theory, you could get any other sort of convex shape working here.

I managed to get this algorithm to work almost exclusively with floating point vectors. The idea is that these are the more compact, and therefore are more amenable to SIMD optimizations. The only place I couldn't skimp on was the determinant calculations in the closest point on simplex calculations.
With this setup, my current implementation of the algorithm is stable with face ratios of up to 1:100.



See the cluster of white points off in the distance? there're four of them near each end of the big surface box. This is fundamentally what causes instabilities in the GJK algorithm. The candidate simplex can be formed of a few points close together, and one way in the distance. This creates very long triangle surfaces that are difficult to solve because of high numerical imprecision.