Jump to content
  • Advertisement
Sign in to follow this  
minionx

When collisions fail...

This topic is 4909 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

Hi there, I'm having a problem with my collision detection as usual... I'm writing in c++ and opengl, and i've actually *nearly* successfully implemented several different collision detection schemes: point-polygon sphere/elipsoid-polygon and now, AABB-polygon However, regardless of the type of collisions i'm trying to do, inevitably, I find that they all have a tendency to *sometimes* fail. I can't quite put my finger on the cause of the problem, and the failed collisions are somewhat infrequent. The only thing I can come up with is this: Will collisions sometimes fail due to the limited accuracy of the variables i'm using? And if so, do most people have to write code that will handle a situation where a collision has failed? Any feedback/advise is appreciated

Share this post


Link to post
Share on other sites
Advertisement
Collision code can be riddled with special cases to handle, well, fails. These fails can be the consequence of several factors, but usually, floating point innaccuracies and divisions by 0 or close to 0. Especially if you do a lot of intersection code (so a lot of divisions). The best way in my opinion is to minimise the special cases and the divisions, and handle minute numbers carefuly if you gonna use them in divisions. So basically, implement thresholds carefully.

Minimising branching is also a good idea, so the code will be a lot clearer, and less specific. This is where the SAT (separation axis theorem) is superior to other intersection based approached. As long as your set is valid (box with non-zero size, non-degenerate triangles, ... and even then, I'm not even sure if it would actually fail). Virtually no special case, little branching, code fragmented into simple functions which are iterated several times, no divisions (for the overlap test), works for a buttload of geometry proxies (from single triangle to convex hulls).

That's what I found the most annoying when doing collison code. Special cases drive me nuts. Ahrr...

Share this post


Link to post
Share on other sites
Ok, excellent... thanks...

I'm looking into the separating axis thing now... I played around with that a bit in 2d once.

So would you say then, if a separating axis collision scheme was carefully implemented, that it could fail 0% of the time? or is there always some rate of failure for any system?

Share this post


Link to post
Share on other sites
It's considered the most robust test. and also probably the fastest (especially if you do careful optimisations for each specific axes, like for boxes) for simple simplices.

you can also extend it further to do 'swept' tests, meaning predicting collisions forward in time, not just when an intersection occurs.

The algorithm in itself is very simple. It only involves basic vector maths, and no divisions (when not doing the swept test).

you can see an example here

it's got a whole set of demos, building up to an example of a 2D rigid body demo, and the docs to explain the steps one by one. Starts of wth intersection detection, moves on to swept tests, then contact point calculations derived from the SAT results, then using those contact points to generate collisoin impulses to integrate into a simple rigid body dynamics framework. or something. have a look.

the 3D version is here

I'm now working on removing the need to test the extra SAT axes for the swept test.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
This is where the SAT (separation axis theorem) is superior to other intersection based approached. [...] Virtually no special case [...]


The special case that SAT has is quite serious though. The edge-edge case, being O(n^2), dominates the axes tested. Because those axes are the result of a cross product, they will exhibit robustness problems when the axes become (near) parallel and the cross product result becomes the (near) zero vector.

If that is not handled correctly you can have situations where two clearly intersecting polytyopes are incorrectly deemed nonintersecting on one of these (near) zero vectors. That's b-a-d! (And pretty much all the SAT code that I see posted on the web fail to deal with this case.)

Share this post


Link to post
Share on other sites
if the SAT test involves no divisions as you say, then there must be a method of projecting a point onto a plane without using a division? is this true? all the ray->plane intersection code i've seen has involved a division.

Share this post


Link to post
Share on other sites
Oops, I may have spoken too soon without doing my google work. :)

http://www.euclideanspace.com/maths/geometry/elements/plane/

Seems to have some information on using translation matricies to place a point on a plane.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
if the SAT test involves no divisions as you say, then there must be a method of projecting a point onto a plane without using a division?


SAT doesn't involve any such projections. Perhaps you are confusing it with something else?

Share this post


Link to post
Share on other sites
ah, your're right, I didn't quite understand the process. So I've had a look at oliii's 2d tuts (very informative by the way), and I can see how a future collision between 2D convex polygons can be predicted, and how the distance to the collision can be calculated. But i'm not clear on how this can be accomplished in 3d.

There must be a way to use the SAT to find distance to collision for 3d convex objects as well, yes?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!