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

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

## Recommended Posts

Is GJK the best choice for distance computation? I did not do any tests with GJK yet but btw it seems to be the faster one. What do you think?! Thanks._.

##### Share on other sites
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 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 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 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 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.

1. 1
2. 2
3. 3
Rutin
16
4. 4
5. 5
JoeJ
13

• 9
• 14
• 10
• 25
• 9
• ### Forum Statistics

• Total Topics
632645
• Total Posts
3007629
• ### Who's Online (See full list)

There are no registered users currently online

×