I have a variety of geometry types in my 2d game, but i need to test for collision between them. One of the most tricky is the convex hull. Convex hull vs. Point is easy enough - checking the point against each plane to see whether it is inside or not. However I''m not sure how to extend this to include Convex Hull vs. Circle and Convex Hull vs. Convex Hull. Circle vs convex hull at first seems like a variation on a point test, just change the point to have a radius and check the distance from the planes. However I think that corners that are very pointy (internal angle smaller than ~90) this will cause inaccurate ''hit'' results.. I think for convex hull vs. convex hull I need to find a separating plane.. So if i test every plane from one hull against the points of all the others vertices, and then the plane separates the two if all the points are outside. Is this correct or is there some special cases i''ve forgotten about?

There is the GJK algo, which tries to find a separation axis between the two convex shapes. It works in 2D as well as in 3D. The maths are quite simple, all you need is a function that returns the minimum or maximum vertex of a convex shape along an axis, which is trivial. It works for polytopes or more generic volumes (cones, spheres, cylinders, boxes, single triangles).

http://citeseer.nj.nec.com/vandenbergen99fast.html
(top left corner of the page are the docs in various formats).

Another method is to clip one of the convex hull with the over convex hull, like you''d do for raster clipping. See what''s left. The advantage is, you''ll get a better idea of the regions that intersected, and you can apply some kind of collision response.

Ok, i've been looking into the GJK method (from here. If I get this right:

The Minkowski difference is the set of points from one hulls points to the others. Does this create a new bounding hull from the first two (effectivly rubber-banding the original two hulls)?

And v(C) is just the point on a hull 'C' nearest to the origin, which is pretty simple.

But I don't get this 'support mapping'. It seems to be using the v(C) in some weird way:

sC(p) ? C ? p . sC(p) = max{ p . x | x ? C }

Can anyone clarify what this actually means? I can see the first half before the 'and' defines that 'p' needs to be within C (p is the input point?).

[edited by - OrangyTang on October 6, 2003 2:19:03 PM]

the support mapping is just a fancy word for a simple thing. Damn academics

the support mapping function return the point on the each of the hulls that is the max (or min) along along an axis.

example, for a triangle, given axis N, the max support point would be

Vector Triangle::GetMaxSupportPoint(const Vector& N)
{
float dmax = (V[0] * N);
Vector Support = V[0];

float d1 = (V[1] * N);
if (d1 > dmax)
{
Support = V[1];
dmax = d1;
}

float d2 = (V[2] * N);
if (d2 > dmax)
{
Support = V[2];
dmax = d2;
}

return Support;
}


for a sphere, it''s even simpler

MaxSupportPoint = Sphere.Centre + N * Sphere.Radius;

for the min support point, well, it''s the opposite.


For the minkowski difference, on one hull, you find the max support point, and on the other hull, the min. (max - min) will give you the point V(c) on the minkowski hull. That''s support mapping.

So you don''t really need to construct the minkowski difference, just call min and max to get a new point V(c) on the minkowski hull, and build new potentialy separating axes from that.