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
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?
Please log in or register to post a reply.
Thanks Mr. Spammer for reminding me of this thread :D