Sign in to follow this  
lotusEater

3D collision detection algorithm choice for convex to convex polytopes

Recommended Posts

lotusEater    100
Hello,

I apologize for the length of this post.

I've been browsing this subforum, looking at recommended articles and books on different 3d collision detection algorithms. While i understand i could always implement some sort of open-source physics engine, i would much rather program my own, for at least simply the learning experience. Keep in mind this is for narrow-phase, convex to convex polytopes.

I planned on implementing the GJK-SAT algorithm with EPA for depth. It seemed quite popular and very efficient. However, after reading numerous threads over the frustrations of GJK and especially implementing EPA, im very hesitant to go this route. From what i've read there are robustness issues with GJK-SAT such as infinite looping, precision errors (these may only have to do with the original GJK, not GJK-SAT) and or false positives (i read that casey's implementation from molly rocket causes these)?

Next on my list would have to be XenoCollides MPR algorithm. I've only be able to find [url="http://www.google.ca/url?sa=t&source=web&cd=14&ved=0CC0QFjADOAo&url=http%3A%2F%2Fuu.diva-portal.org%2Fsmash%2Fget%2Fdiva2%3A343820%2FFULLTEXT01&rct=j&q=3d%20Minkowski%20portal%20refinement&ei=AOtATq6KAoavsALjuaHkCQ&usg=AFQjCNEAmyVegOF3NG780B9-A9OUC7ko1Q&cad=rja"]a single article[/url] on this algorithm in 3D and am worried that it may be plagued by the rame robustness issues as GJK as they are quite similar. The article i've linked doesnt go over any robustness issues aside from when computing depth, which it states are only heuristic estimates and in some cases can be quite far off. This was discouraging to hear.

I also came across the Chung Wang Separating-vector Algorithm, i've only come across it in Christer Ericson's Realtime Collision Detection. Its apparently twice as fast as GJK, has anyone succesffuly implemented this algorithm?

Aside from which algorithm i use to detect whether a collision takes place, im still stuck trying to find how to obtain penetration depth. Are there any good algorithms aside from EPA which seems to be more trouble than its worth?

I would love to hear anyones input!

Cheers

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