Sign in to follow this  
shaobohou

what to do after GJK?

Recommended Posts

I been researching collision detection for a small game that me and a group of friends are developing. I looked at GJK and some of the other distance computation techniques, one thing papers for these fails to mention is what to after you detected a collision (distance threshold), in particular how to calculate the data needed for collision response such as point of collision (assuming that non-penetration constraint is enforced, this could be midpoint of the shortest path from surface of A to surface ofB) and the the normal to the collision surface. hopefully someone can point me in the right direction.

Share this post


Link to post
Share on other sites
GJK detects intersections between convex objects. So, if you have non-penetration constraints that work, then yeah, you can use GJK to find the separation plane when the objects are contacting (very close to each other).

When you look for that plane, GJK walks on the two surfaces of the objects, evaulates two support points A and B, until |AB| is the minimum distance.

Those points on each objects are your contact points, or take the mid-point as the singular contact point, as you said. The normal is basically calculated within the GJK min-distance search, and should be, in the end in the direction of [AB].

If you do allow intersections, then there is an extention to the GJK algo which calculates the intersection depth and points, in a kind of similar way to the GJK search. It's a bit complicated for a post.

a list of papers.
http://www.win.tue.nl/~gino/solid/gdc2001depth.pdf
http://www.iis.sinica.edu.tw/LIB/TechReport/tr2001/tr01013.pdf
http://www.merl.com/reports/docs/TR97-05.pdf
http://www.csis.hku.hk/GraphicsGroup/project/Collision3.pdf

Another algorithm that could be useful, if the V-Clip (TR97-05.pdf), or voronoi clip algo, but works only on polyhedrons (polygonal convex hulls).

the first doc explains in simpler terms, how to compute the penetration depth using GJK. It's another paper from Gino VDB, who's kind of THE reference on that subject.

Share this post


Link to post
Share on other sites
GJK is supposedly faster. I don't know really. I'd probably use the easiest and the one I understand the most, rather than the fastest. They should be similar in speed, and collisions, although expensive, aren't a bottleneck in games, so as long as it is not stupidely slow, I'd go with the one I am most confortable with.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this