Finding contact point in GJK-based collision detection

_oisyn 101 Nov 27, 2009 at 17:11

I was reading up on some papers regarding collision detection using the Minkowski sum A-B of convex objects A and B and their support mappings. Gino van den Bergen has a paper on collision detection of moving (but nonrotating) objects by doing a ray cast on A-B based on the famous GJK algorithm, which would report the time of collision, the hit point and the normal at that hit point.

In short, two convex objects A and B intersect if and only if the origin is included in their (also convex) Minkowski sum A-B. This is easy to prove intuitively: A-B is the set of all points of A subtracted by all points of B. For the objects to intersect, there exists a point p which is both in A and in B. Which means that one of the points in A-B is the result of p-p = (0, 0, 0).

The geometry of A-B can be read using a support mapping sp(v), which returns one of the points on A-B that is most extreme in the direction of v. It can be shown that the support mapping spA-B(v) for Minkowski sum A-B can be calculated by spA(v) - spB(-v). So, basically, all you need to know to intersect two objects is what their support mapping are, which opens up a whole class of convex objects (boxes, polyhedrae, spheres, ellipses, cones, cyllinders, etc.) which can be tested for intersection against eachother using a single general algorithm.

The raycasting method proposed by Van den Bergen works by iteratively following a ray cast from the origin in the direction of movement of B relative to A, until it hits A-B. For each iteration, it determines the closest point and normal to the current position of the ray in A-B. Using that point and normal, you can construct a plane and then advance the ray until it hits that plane. You know you can’t have passed through A-B as A-B is convex and therefore everything in front of the plane is not in A-B. Then, the resulting point is either on A-B (in other words, a hit), or there exists a new point on A-B that is closest to the new ray’s position. Naturally, if the ray moves parallel to or away from the plane you would have a miss.

Unfortunately, his paper is a bit vague. First of all, he does not mention where the ray should start and what it’s direction should be, although it’s obvious that it should start at the origin and move in direction of object B’s movement relative to A: here’s a webpage that contains an applet that draws A-B given A and B. You can drag around A and B to see what happens. It is clear that as you drag B towards A, that A-B moves towards the origin. Also, he reports the final intersection point of the ray with A-B as “the intersection point”, but that is a point in A-B configuration space. The problem I’m having is converting that point to world space. Of course, I could use the individual support mapping functions of A and B to to get a point that is most extreme in the direction of the contact normal, but the fact to the matter is that the support mapping may not yield a unique point. For example, the most extreme points of a box might be the set of all the points on a face, even though the contact point itself might have been unique.

Does anyone have any experience in using GJK or this method in a physics engine, and if so, what have you done to resolve the contact points?

1 Reply

Please log in or register to post a reply.

_oisyn 101 Oct 18, 2010 at 09:29

Thanks Mr. Spammer for reminding me of this thread :D