Sign in to follow this  

Computing the distance between convex polyhedras. Is GJK the best/faster algorithm?

This topic is 3928 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

It depends on the properties of your input set, and there is never a best algorithm in the real world. GJK is, however, known to be pretty fast.

Yet, it seems to me that you might be asking the wrong questions: what is important is, is GJK the best algorithm for your program? Or, to say it differently, would the improvements provided be worth time spent incorporating GJK into your program, as opposed to a simpler algorithm or a third-party solution?

Share this post


Link to post
Share on other sites
Thanks for reply. What I usually do is detect collisions between convexpolyhedras (or concave polyhedras represented by some covexpolyhedras glued together) by finding the closest points. My input set are the triangles with their vertex positions. Then, what do you recommend?!

Thanks

Share this post


Link to post
Share on other sites
Profile. Is your distance function the bottleneck of your collision detection system? Is the collision detection system the bottleneck of your game? If the bottleneck is somewhere else, you should probably spend more effort correcting that instead.

Share this post


Link to post
Share on other sites
Since your input set is triangles one posible solution is to compute triangle mesh collision (triangle vs triangle) and posibly optimize that by axis aligned box tree (it depends on how many triangles your collision model have).

If you still desire to use GJK, your in a world of hurt. The part of the GJK that does not have to do with distance computation (penetration depth) is actualy very nice and not so hard to understand and implement. But the distance computation is very painful and there is no best solution yet (expanding polytope and suport vector sampling are 2 of them).

Share this post


Link to post
Share on other sites
I thought it was the other way round, that the MTD computation was hard, but the distance computation not so much (apart from the expanding terahedron stuff).

Something I haven't tried, but using the SAT, you can find the minimum distance between the polyhedras, along the SAT planes (face normals, cross product of edges).

Granted, that is not necessary your closest distance, but using the supporting features along that 'MTD', then you can simplify the problem with a plane/edge, plane/point, edge/edge or edge/point distance check.

Share this post


Link to post
Share on other sites

This topic is 3928 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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