Computing the distance between convex polyhedras. Is GJK the best/faster algorithm?
Author
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._.
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?
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?
Author
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
Thanks
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.
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).
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).
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
