When collisions fail...
Author
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
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...
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...
Author
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?
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?
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.
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.
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.)
Author
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.
Author
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.
http://www.euclideanspace.com/maths/geometry/elements/plane/
Seems to have some information on using translation matricies to place a point on a plane.
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?
Author
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?
There must be a way to use the SAT to find distance to collision for 3d convex objects as well, yes?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
