Sign in to follow this  

When collisions fail...

This topic is 4692 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
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
Quote:
There must be a way to use the SAT to find distance to collision for 3d convex objects as well, yes?

Yes. The principle is the same, but whereas in 2D the axes to test are simply the normals to the edges, in 3D they are the normals to the faces, as well as the cross products of each edge from object A with each edge from object B.

SAT is invariant under axis length and sign (i.e. v and -v are equivalent). So for, say, oriented bounding boxes, where edges and face normals are colinear, the number of axes to test can be reduced considerably. For arbitrary polytopes, however, the number of edge cross product tests required can be prohibitive.

Also, as Christer mentioned, 3D introduces the problem of degenerate axes resulting from near-colinear edges, and the resulting numerical problems.

Share this post


Link to post
Share on other sites
Quote:
in 2D the axes to test are simply the normals to the edges, in 3D they are the normals to the faces


With SAT in 2d, the 2d shapes are projected into one dimension, where the intervals are analyzed.

So in 3D, wouldn't the 3d objects be projected into TWO dimensions (ie, on a plane)? where they're silhouettes can be analyzed? You said in 3d, the normals to the faces are used. I don't see how a 3d object's interval can be projected onto the normal.

Share this post


Link to post
Share on other sites
Ah, I see. No, in 3D you still project the objects to 1D, i.e. along a single axis.

The formulation of the projection is the same in 2D and 3D, and in fact any dimension. The dot product of two n-dimensional vectors is always a scalar. Geometrically, it is also the length of the projection of one of the vectors onto the other, scaled by the length of the second vector.

For a shape in any dimension, the maximum of the projected interval on an axis A is max(Dot(v[i], A)), where v[] are the vertices of the object. Similarly for the minimum.

Anyway, 'hope that clears things up a little. If you're looking for a good reference on the topic, try Dave Eberly's .pdf - you can find it on his Magic Software site.

Share this post


Link to post
Share on other sites
Quote:

The dot product of two n-dimensional vectors is always a scalar. Geometrically, it is also the length of the projection of one of the vectors onto the other, scaled by the length of the second vector.


Holy shnikies!!!
I had no idea what the hell you were saying with that, but the I tried it. Thats amazing how that works. Ya know, I just thought I was kindof getting on top of all the uses for a dot product and here you go and give me a brand new one.

Boy, that makes the projection onto the vector a snap, doesn't it.

Thanks everyone, I think I actually have enough to put this into action now.

Share this post


Link to post
Share on other sites
Just out of curiosity, isnt SAT very innefficient in 3d? i mean a cube-cube (assuming you dont detect paralell planes) requires you to deal with 12 planes right?, i dunno, maybe im crazy :-p, maybe it is alright... but for meshes, it could become unwieldy in my opinion

my two cents
-Dan

Share this post


Link to post
Share on other sites
Quote:
Just out of curiosity, isnt SAT very innefficient in 3d?

It's not necessarily innefficient for AABBs, OBBs, triangles, linear components, and maybe some other things I'm not thinking of.

Quote:
i mean a cube-cube (assuming you dont detect paralell planes) requires you to deal with 12 planes right?

Yes, plus the edge cross products. So without optimizations, you have 12 face normals + 12 edges * 12 edges, for a total of 156 axes to test.

Quote:
but for meshes, it could become unwieldy in my opinion.

Yes.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ademan555
but for meshes, [SAT] could become unwieldy in my opinion

Well, SAT is only applicable to convex solid geometry and because an (arbitrary) mesh is neither convex nor solid, SAT typically does not apply to meshes.

Share this post


Link to post
Share on other sites
Quote:
Well, SAT is only applicable to convex solid geometry and because an (arbitrary) mesh is neither convex nor solid, SAT typically does not apply to meshes.

Oops - I probably should have pointed that out in my previous post. I guess I just assumed he was referring to convex objects.

Share this post


Link to post
Share on other sites

This topic is 4692 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.

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