SAT vs GJK

There's a lot that could be said about this! I've only got a few minutes though, so I'll just outline it a little.

1. The GJK algorithm calculates the distance between two objects by operating on their CSO (configuration space obstacle). The CSO is the Minkowski difference of the objects, A - B. (Note that this is sometimes also refered to as the Minkowski sum, A + -B.) The Minkowski difference for two point sets A - B is the set of all points a - b, where a is a point from A and b a point from B. Consider that the distance between A and B is min(|a - b|). Since the CSO is all a - b, the distance between the objects is also the distance between the CSO and the origin. If the CSO contains the origin, the objects intersect. (Ok, I guess there is no such thing as a 'short outline' of GJK.)

2. This solution can be evaluated directly by finding the convex hull of A - B and calculating its distance from the origin. This is too expensive in real time though, so in practice GJK samples the CSO using support functions for the objects, where a support function returns the maximal point v along a direction d.

3. There's a lot more too it, and honestly a robust implementation is pretty involved. For everything you ever wanted to know about GJK and more, get Gino van den Bergen's book 'Collision Detection in Interactive 3D Environments'. Christer Ericson also discusses it in his new book.

4. AFAIK GJK is mainly suited for static intersection, and with some work can return the depth of penetration of two convex objects. Theoretically there is a way to find the first time of contact between two moving objects using GJK, but it involves raycasting against a sampled CSO, and I'm not sure if that is a solved problem.

5. On Gino's SOLID site, he mentions that SOLID 4.0 will include 'shape casting', which I assume will be swept collision for arbitrary convex polyhedra. I'm *extremely* curious to know what approach he will be using for this.

6. SAT handles static and moving interection equally well. It's great for 2D, and works well for AABBs, OBBs, and triangles in 3D. For arbitrary polyhedra the number of edge cross products to test is exponential and SAT quickly becomes unfeasable.

7. Finally, I'm currently very interested in the problem of continuous collision detection between arbitrary convex polyhedra, so I'll be curious if anyone else has anything to say about that.

Well, sorry that was long! But that was about the shortest summary I could come up with...

[Edit: I just read Gino's paper on CSO raycasting, which I had overlooked. So I'm guessing CSO raycasting will be the continuous collision detection method employed in SOLID 4.0.]

[Edited by - jyk on February 2, 2005 10:13:23 PM]

A good summary from jyk. I just wanted to add some short comments.

Quote:

2. This solution can be evaluated directly by finding the convex hull of A - B and calculating its distance from the origin. This is too expensive in real time though, so in practice GJK samples the CSO using support functions for the objects, where a support function returns the maximal point v along a direction d.

Sampling the CSO using support functions is actually more powerful than having the convex hull in that you can easily spherically extend the polyhedra by modifying the support functions to add in a "radius". The support functions also allow the GJK algorithm to be modified to deal with continuous collision queries (through an interval halving approach).

Quote:

4. AFAIK GJK is mainly suited for static intersection, and with some work can return the depth of penetration of two convex objects. Theoretically there is a way to find the first time of contact between two moving objects using GJK, but it involves raycasting against a sampled CSO, and I'm not sure if that is a solved problem.

As you noted later on, Gino has a recent paper on doing the ray cast (which he is also presenting at GDC'05) for doing GJK on moving objects. Also, in my book I discuss an alternative modification to GJK for moving objects, based on interval halving (as I mentioned above). So, no, GJK is suited for contiuous intersections too.

Quote:

6. SAT handles static and moving interection equally well. It's great for 2D, and works well for AABBs, OBBs, and triangles in 3D. For arbitrary polyhedra the number of edge cross products to test is exponential and SAT quickly becomes unfeasable.

Small nitpick: not exponential but quadratic. (Quadratic is bad enough!)

Quote:

7. Finally, I'm currently very interested in the problem of continuous collision detection between arbitrary convex polyhedra, so I'll be curious if anyone else has anything to say about that.

In addition to the two methods already described (GJK, SAT) it is also possible to solve the problem as a mathematical optimization problem (quadratic programming), but for most practical purposes I would stick with GJK or SAT.