Okay, I'm computing them that way as well; it seems more scalable since the number of transformations for a given candidate pair within GJK seems fairly constant (assuming the algorithm terminates within a known/maximum number of iterations), whereas the total number of vertices between two shapes can be arbitrarily large.

Going further off topic, you mentioned earlier that you use Quadtrees in your engine. How do you like it? I'm still debating what I will use for my broad phase. I've mostly used spatial grids and some custom spin off of sort and sweep in the past. However this time around I'm trying to go for something more flexible / able to handle arbitrary sized regions. It seems some sort of tree implementation may be the way to go, though updating the tree regularly seems like it would be a pain. I'd be interested to hear your opinions.

P.S. I find it funny how this thread has been like a public PM between us two

Haha. It's nice discussing this with someone who has already faced many of these issues. :)

Just had a thought on how to keep the index-cached simplex implementation with curved / non-vertex based shapes. The way my implementation of GJK is set up, the support functions return a single value representing the support point (e.g. the index of the point). There is no reason this can't also be a floating point / scalar. Since shapes in GJK are convex I can simply return the angle of the point (for convex shapes there is only ever one point along a given angle). Since each shape implements its own "get vertex" and "get support" functions, it can easily manage whether it is expecting angle or index. Obviously the disadvantage of this is the overhead in using trig functions. But it seems there are ways to get around that as well (such as via look up tables, etc..).

This would however make circle-circle queries more inefficient than they otherwise would be. But perhaps the cost would be worth it for circle-OBB or circle-polygon queries?

Although, comparing the two implementations:

// Vector-based Support function for a circle
void Support(const Vector2D & dir, Vector2D & out)
{
  float mag = radius / sqrt(dir.x * dir.x + dir.y * dir.y);
  out.x = pos.x + dir.x * mag;
  out.y = pos.y + dir.y * mag;
}

?

// Radial-based Support function for circle
float Support(const Vector2D & dir)
{
   return atan2(dir.y, dir.x);
}

The first has four multiplies, a divide, and a square root. The second has a trig function. What is more expensive? I suppose the real expense comes into getting the vertices. For the first implementation, there is no need to get a vertex because we already have it from the support function. For the second:

// Get point along direction (in radians)
void GetWorldVertex(float angle, Vector2D & point)
{
   point.x = pos.x + radius * sin(angle);
   point.y = pos.y + radius * cos(angle);
}

That's two trigs and two multiplies. So net across both methods we have:

radial-based: 3 trigs, 2 multiplies

vector-based: 4 multiplies, 1 divide, 1 square root

Perhaps a toss-up? Should probably do some benchmarking.

it's not an incorrect way to do things. It'll just make your codebase harder to maintain and keep up with if hacks are built in to the design.

True. It seems though that it does play nicely into abstraction. Let each shape type determine it's own support / vertex query mechanism. The algorithm itself is none the wiser. The support "key" could even be wrapped in something more nicely so it doesn't feel like I'm trying to stuff indices and angles into the same result.

it will come in handy if you move away from discrete collision detection and into more continuous methods.

That's a justifiable reason to change.

I recommend not using GJK for quadric shapes with floating point position since it doesn't work in practice from my experience. Anyway for spheres and capsules you can use a point and segment and add the radius later. Then the simplex caching also works again.

I recommend not using GJK for quadric shapes with floating point position since it doesn't work in practice from my experience

Is that because of numerical robustness? I have been starting to think I'll only use GJK for polygon-polygon tests and then special case the rest as it seems it will likely be more efficient in some cases (e.g circle vs circle in gjk seems overkill). But if there's a robustness issue as well that's good to know.

Yes, GJK has severe numerical issues in 32 bit floating point math. I would not use it for anything else but polyhedra. Both Christers and Ginos books explain the details. For sphere and capsule I use the center point and segment while adding the radius afterwards.

For sphere and capsule I use the center point and segment while adding the radius afterwards.

I'm not sure I understand what this means. For sphere, is this just a point-polygon distance test verifying that distance is greater than radius? Or do you mean that you use GJK to get closest point between point and polyhedral and then do a radius check?