When collisions fail...

Started by
16 comments, last by Zakwayda 19 years, 2 months ago
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.
Advertisement
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.
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, 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.
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.
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
When General Patton died after World War 2 he went to the gates of Heaven to talk to St. Peter. The first thing he asked is if there were any Marines in heaven. St. Peter told him no, Marines are too rowdy for heaven. He then asked why Patton wanted to know. Patton told him he was sick of the Marines overshadowing the Army because they did more with less and were all hard-core sons of bitches. St. Peter reassured him there were no Marines so Patton went into Heaven. As he was checking out his new home he rounded a corner and saw someone in Marine Dress Blues. He ran back to St. Peter and yelled "You lied to me! There are Marines in heaven!" St. Peter said "Who him? That's just God. He wishes he were a Marine."
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.
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.
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.

This topic is closed to new replies.

Advertisement