Here is the webpage from the collision paper I was trying to replicate:-
It features a presentation almost identical to my own! Haha.
http://www.cs.unc.edu/~geom/DEEP/I have realized a better what though to solve the problem. Um, Instead of projecting the guass representations onto a planar subdivision, represent the guass map as a 3D sphere cut by planes. Use these planes as the deliminators of a BSP tree and assign the guass representation's features within the BSP tree, this can all be done upfront once. Then, when it comes to comparing the two representations you can use the BSP to quickly lookup opposite features by spacial positions. The main bulk of the algorithm remains the same (i.e. walk along the features until you can't get an improvement in your penetration depth) but it cuts out the planar subdivision part which has degeneracies associated (and its also quite hard to implement a fast planar subdivision algorithm as I have found out).
Thats what I was thinking currently. I have not got time to do it though :-(
The article seems to be very promising

They very mentioning a constant complexity, I actually can't think how this should work ... hmm they were mentioning s.th. about a good heuristic for a starting point - hmm if they use the point, that was the deepest last step, it really can work pretty fast.
it seems they are also able to calculate the penetration direction - nice

My idea with the simplex algorithm was to use it to find the closest point (better: plane going through that point) to the other object (or an optimum if you want it that way

) and then do the same with the other object. And then calculate the distance between the two planes - and voila you would get some kind of penetration distance.
But I've realized, that there are situations, where it would return a penetration distance, where the objects don't even intersect!
So it's probably not so wise to use this approach
