GJK vs. SAT performance-wise.
Author
Hi,
The title says it all I guess.
What kind of speed difference would there be between good implementations of both this algorithms (caching and precalculating what can be (eg. unique edges/normal per convex, last separating axis, etc...)).
I'm asking because I'm real lazy and I already have a working SAT. :)
not much gain, I would think. GJK is more about flexibility. SAT is only for small polytopes. if you restrict yourself to simplices like small convex hull and boxes. Besides, the implementation is complex.
Author
Quote:Original post by oliii
not much gain, I would think. GJK is more about flexibility. SAT is only for small polytopes. if you restrict yourself to simplices like small convex hull and boxes. Besides, the implementation is complex.
(edit: sorry I just realised you mentioned small convex hull... so the question is, how big is a small convex hull? :))
Yep that's my fear... spending a lot of time for not much.
But indeed, I was not clear enough. I'm speaking of say convexes with about 20 vertice... that seems a good typical convex that make sense.
With SAT I transform B unique edges/normals into A space then it's just a bunch of dots and cmp per axis (granted the number of axis to test grows real fast). The continuous detection is also very easy to add.
If I was to extend my current SAT to general convex, I would probably split the SAT elements in octant to cut down the number of potential edge/normal forming a separating axis (so that's at least half less elements and somewhere around a quarter of the total axis to test edit: correct me if I'm overlooking something).
With temporal coherence and close proximity configuration the SAT would exit real fast... How would GJK fair in comparison? >2x?
[Edited by - b34r on July 30, 2005 8:54:37 AM]
I haven't completed a GJK implementation, so the following is mostly speculation. But if you're talking about multiple arbitrary polytopes of 20+ vertices, that may be pushing the limits of SAT a little. Even a pair of arbitrary 6-side polytopes would require, um, 156 axis tests? Also, determining non-intersection with SAT is cheap with appropriate caching - it's determining intersection that can get expensive when the polytopes are complex.
Anyway, I would implement continuous SAT and get it working before thinking about GJK. Continuous SAT is pretty simple to implement, and then you can see how it performs in practice with complex polytopes. You might find that it's adequate for your needs.
If not, or if you want to introduce more complex shapes such as capsules, cones, cylinders, and ellipsoids, GJK may be required. But be forewarned: the implementation is not trivial!
Quote:If I was to extend my current SAT to general convex, I would probably split the SAT elements in octant to cut down the number of potential edge/normal forming a separating axis (so that's at least half less elements and somewhere around a quarter of the total axis to test edit: correct me if I'm overlooking something).I've never heard of anything like this, and it's not immediately clear to me how it would work. Can you elaborate on what you mean exactly?
Anyway, I would implement continuous SAT and get it working before thinking about GJK. Continuous SAT is pretty simple to implement, and then you can see how it performs in practice with complex polytopes. You might find that it's adequate for your needs.
If not, or if you want to introduce more complex shapes such as capsules, cones, cylinders, and ellipsoids, GJK may be required. But be forewarned: the implementation is not trivial!
Author
Quote:Original post by jyk
I've never heard of anything like this, and it's not immediately clear to me how it would work. Can you elaborate on what you mean exactly?
Yep, note that I'm thinking of continuous SAT only but that should work for discrete SAT too... I guess.
Basically split the polytope features (side/edge) in eight nodes.
Then simply cull opposite nodes when determining the separating axis set.
That would be useless for a cube since all edges and faces are redundant across all the octants but for say, a rock like hull, there's great chances that all faces and edges are unique. So, there's a good number of them that can be culled away as they will certainly not lead to a least penetrating axis...
Quote:
Anyway, I would implement continuous SAT and get it working before thinking about GJK. Continuous SAT is pretty simple to implement, and then you can see how it performs in practice with complex polytopes. You might find that it's adequate for your needs.
That's done. And it works (well ok, not continuous but it's not like it's going to be a big problem) fast and fine, that's why I'm more for avoiding the GJK headaches.
Quote:If not, or if you want to introduce more complex shapes such as capsules, cones, cylinders, and ellipsoids, GJK may be required. But be forewarned: the implementation is not trivial!
Ok... Cylinders and elipsoids would be nice... indeed. And yes, it's not trivial but I'm over paranoid when it comes to collision detection so I'll proceed carefully if I'm to try implementing GJK. That wouldn't make it easier, but I'm warned ;).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement