collision detection in 3D

Quote:

Original post by daniel_i_l I'm thinking on using the SAT to do collision detection in 3D. my question is, after detecting a collision, how do i find the exact collision point so that i can respond to the collision? Thanks.

First of all, what's the context? As straightforward as SAT is, sphere coldet is still much, much easier to implement. Also, if you only need a static (discrete) test, you could add capsules to the mix; spheres and capsules together would be quite manageable (you just need the appropriate closest-point support functions).

If you're fixed on using the SAT, are you thinking OBBs, or arbitrary polytopes? The SAT doesn't scale very well, so I wouldn't advise the latter. In any case, the SAT test (discrete or continuous) can be extended to provide a contact manifold between the two objects in question. How to do so has been discussed ad infinitum on these boards and elsewhere, so some googling might be in order. I just tried it and googling for 'separating axis gamedev' turns up some relevant threads (I guess you could use the site search engine also).

Thanks, the context is a physics simulation so i need to know exaclty were the OBB's touched eachother. Would it be easier to do it by checking all the corners and edges of one of the bodies against the sidesw of the other one? then using the intersection points it would be that hard to get the relevant collision points. Is there a better way?
Thanks.

Quote:

Original post by daniel_i_l Would it be easier to do it by checking all the corners and edges of one of the bodies against the sidesw of the other one?

Conceptually, maybe, but practically, no.

Quote:

Is there a better way?

Yup, the aforementioned extended SAT method. If you're interested in implementing this, I'd start by finding every article and thread on the topic that you can and gather them together. Look for old threads in this forum, and be sure to check the articles section here, and also geometrictools.com. If you can afford a book, pick up Christer's 'Real-Time Collision Detection'. I think some folks on this forum have even made available complete source code for OBB coldet, so if you can find that, that would be a good reference as well.

I would also recommend implementing the OBB test in 2D first, as it is somewhat more simple and will give you an opportunity to get the concepts down. Then, if you run into problems or have specific questions about the algorithm, post back.

There are two types of collisions. The first type is when the objects are initially sperated and fly into one another during the next frame. In that case all SAT can tell you is that the objects where separated initially, but won't find any collision features/points. You'll need to do some moving point/plane intersection to do that as well as two moving lines.. SAT is more useful when objects are overlapping initially, in that case there is no impact collision, and you must find a penetration depth or more precisely the shortest vector to separate the two objects. Hope that helps and good luck.

--Bart

Quote:

Original post by bpj1138 There are two types of collisions. The first type is when the objects are initially sperated and fly into one another during the next frame. In that case all SAT can tell you is that the objects where separated initially, but won't find any collision features/points. You'll need to do some moving point/plane intersection to do that as well as two moving lines.. SAT is more useful when objects are overlapping initially, in that case there is no impact collision, and you must find a penetration depth or more precisely the shortest vector to separate the two objects.

You can extend the SAT to return contact information for the continuous test just as with the discrete test; there should never be any need to perform separate swept feature-feature tests as you describe.

I'll just put a list of code samples, and a link to the original thread. Too tired to go through an explanation or format the links but anyway, see if it helps...

original thread
http://www.gamedev.net/community/forums/topic.asp?topic_id=346956

2D
http://members.gamedev.net/oliii/satpost/BoxBoxIntersect.cpp
http://members.gamedev.net/oliii/satpost/BoxBoxCollision2.cpp
http://members.gamedev.net/oliii/satpost/BoxBoxCollisionAndMTD.cpp
http://members.gamedev.net/oliii/satpost/ConvexPolygonCollision.cpp

3D
http://members.gamedev.net/oliii/satpost/OrientatedBoxesCollision.cpp
http://members.gamedev.net/oliii/satpost/3DBoxPolygonCollision.cpp

spheres and polys
http://members.gamedev.net/oliii/satpost/3DSpherePolygonCollision.cpp
http://members.gamedev.net/oliii/satpost/SpherePolygonCollision.cpp

some extra files
http://members.gamedev.net/oliii/satpost/DXInputs.cpp
http://members.gamedev.net/oliii/satpost/DXInputs.h

some more samples (3D cubes and contact point calculations)
http://uk.geocities.com/olivier_rebellion/Cube3D.zip

I'll sort the links out some time later :)

Quote:

Original post by jyk Quote: Original post by bpj1138 There are two types of collisions. The first type is when the objects are initially sperated and fly into one another during the next frame. In that case all SAT can tell you is that the objects where separated initially, but won't find any collision features/points. You'll need to do some moving point/plane intersection to do that as well as two moving lines.. SAT is more useful when objects are overlapping initially, in that case there is no impact collision, and you must find a penetration depth or more precisely the shortest vector to separate the two objects. You can extend the SAT to return contact information for the continuous test just as with the discrete test; there should never be any need to perform separate swept feature-feature tests as you describe.

Sorry for the delayed response. I remembered reading something to that effect in Eberly's paper, but I couldn't remember why I rejected the idea. Well, I was digging through my garbage today and found the paper, so I took a quick glance. The first sentence in the "extended SAT" section states that the objects are moving with "constant velocity". I took this to mean without rotations. I glanced a little further, and found no mention of angular velocity or individual vertex velocities. Is this correct?

Then while I was reading this thing, I decided to look over the pseudocode for the 2D SAT. It didn't look right to me, and after some thought, it seemed to me Mr. Eberly didn't implement his test right. He's got this function WhichSide() which returns three values -1 for points inside edge, +1 for points outside edge, and 0 for a mix. The thing is, the calling function is only interested in the +1 case (points outside), so why not exit WhichSide() early if 0 or -1, he only seems to do this for 0. Furthermore, he doesn't check for the dot product being zero (this might not be a huge problem, but it bothers me nonetheless).

Oh well, I thought I'd shoot this over here, I'm sure you guys can double check this.

--Bart

I seem to recall he has a paper implementing SAT with rotations in mind, but it's more complicated. Linear SAT is easy enough though. Obviously, you will not be able to prevent intersections (since the objects rotate and that's not taken into account).

BTW, back to the origiinal question,

When the SAT returns, it will provide two things, The normal of collision, and the time or depth of intersection.

The normal can be used to find the features that 'support' the object during the collision.

Example, dropping a box, flat on a table, the normal will be pointing up.

The polygon on the table that will be considered will be the top quad. For the box, it will be the bottom quad.

Those faces can be easily detected, since they will be parallel to the normal of collision.

That provides you with two polygons that literally collide each others. To find the surface of contact, you just use a standard clipping algorithm, estended to 3D, to find the intersection region. That will also be a convex polygon, and you can use the vertices of that polygon as your contact point.

If you drop the box onto an edge, the same thing apply. You are left with the top quad of the table, and the edge on the box. Then you clip the edge with the polygon, to get the contact vertices.

if you drop the box on a corner, then the corner is simply the contact point.

To find what features contact, you just need a bit of logic to find the face / edge / vertex that support the object along the normal of collision.

then you should be left with a few cases.

1) vertex - face contact.
2) edge - edge contact.
3) edge - face contact.
4) face - face contact.

all these are relatively straight forward. The most complex involve some 3D volume clipping, but even that is easy (since the volumes will be convex).

Thanks, i have a few more questions:
1) how can i use SAT to get the collision normal and depth?
2) after finding the normal, how do i use it to determine exactly what kind of collision occured?
thanks.

Hey Oliii, can you remember if that paper only delt with OBB's?

The SAT can be generalised to convex hulls, although, the number of tests grows pretty quick, since the number of edges multiplies.

If you start with a triangle, that should be the basis for a convex hull test.

The SAT performs 1D interval overlap checks.

So, you have two intervals for two objects along a direction (not normalised).

say you have object A, object B, and axis D, that you test against for overlap.

you will have two intervals [mina, maxa] and [minb, maxb], one for each objects, which are the projection of the objects along that direction.

If the two intervals are not intersecting, then the objects are not intersectin either, and the direction D is one of many separating axes.

Now, if the two intervals intersect, ...

you can calculate the amount of overlap between them, This value tells you how much the object intersect along the direction D.

in the end, once all the potential separation axes are tested, and all intervals intersect, you simply find the smallest amount of overlap, and that gives you both the direction of intersection, and the amount of intersection.
in pseudo code...



BTW, the value (N*d) in the end can be combined into one vector, often called the MTD (minimum translation distance).

Oh yeah, and D and N aren't normalised...

As for the features (face, edge, vertex) that needs to be used for contact point caluclations, it's sraignt forward.

N is the direction of the intersection. Simply find the feature that is supporting the object along N.



depending if you have edge->edge, face->edge, face->point, point->face... YOu will have different algorithms to calculate the contacts between the two features.

Find a support face, it's simply finding a face that has (in my case) its normal completly opposite the intersection direction (within a threshold).

ect....

a support edge would be, an edge that when dot producted with the support axis, would return 0 or close (perpendicular to the support axis), and the start point the lowest of all points along the support axis.

a support vertex is simply the lowest vertex on the convex object, along the support axis. You are obviously always guaranteed to find at least one.

you get the two supports of the objects, then you can find the contact points.

Note that, there should not be cases such as...

vertex - vertex
vertex - edge

so you are left with only...

vertex - face : Contact points are simply the vertex, and the projected point on the face (or just take the MTD vector).

edge - face : you will have to clip the edge with the face extrusion (build edge planes and cut down the edge until all edge planes are processed).

edge - edge : It's the closest points on each edges. It's easy to find (look for line distance calculations in 3D).

face - face : You will have to clip one of the face with the other face extrusion. Same algo as with the edge - face problem. It's in the code I've posted. This stuff isn't hard, it's like a standard 2D clipping algo, but in 3D.

if you do get dodgy cases (vertex - vertex), it's easy enough to find where the contact point would be. But really, if your feature detection algo is solid, that should not happpen :)

Of course, you can take many shortcuts once you have something working, and make it really fast. It's up to you.

Also, the process of finding support features and contact points is no more different in a swept test (where you try to find the time of collision, not just intersections).

Thanks a lot for that explanation! i have a few questions though:
1) what do you mean by "a support edge would be, an edge that when dot producted with the support axis, would return 0 or close (perpendicular to the support axis), and the start point the lowest of all points along the support axis."
at the end of the sentence? (the start point)

2)what is the face extrusion? also, how does clipping help me find the collision points?
Thanks.

Quote:

Original post by daniel_i_l Thanks a lot for that explanation! i have a few questions though: 1) what do you mean by "a support edge would be, an edge that when dot producted with the support axis, would return 0 or close (perpendicular to the support axis), and the start point the lowest of all points along the support axis." at the end of the sentence? (the start point)

The dot product being close to zero indicates that the edge is nearly perpendicular to the axis (I think you got that part). If also one of the end points of the edge (the start point mentioned above) projects maximally (or minimally, depending) onto the axis, then the edge is a support feature. If that's not clear, try drawing a diagram of the situation described and I think it'll make more sense.

Quote:

2)what is the face extrusion? also, how does clipping help me find the collision points? Thanks.

The face extrusion is formed from a set of planes, one for each edge of the face, each of which passes through the corresponding edge and is perpendicular to the face plane itself. Basically it's like an infinite prism built around the face.

Imagine an edge-face collision. Also say that the edge is longer in general than the face dimensions, or is situated in such a way that it 'hangs over' the edges of the face. The contact manifold is then a subset of the edge, bounded by the two points where the edge 'crosses over' the edges of the face.

These points can be found by clipping the edge line segment to the previously described extruded planes. The same process can be applied in a face-face collision, with one face being clipped to the extruded planes of the other resulting in an N-gon describing the contact manifold.

Does that help at all?

Yes that helped a lot! thanks

back to the reeeall question.

if what you really want is the direction and shortest length of the for the collided object to be in non collision state. try gjk.

Ta jyk :) That clipping, support point malarkey is in the demo Rigid3D.zip somewhere.

The reeeall question was, how to use SAT to find contact point. As for GJK, it's another bag of problems. GJK would be for convex hulls, and convex objects not being polytopes (cylinders, cones, even spheres, or convex blobs like a soft body...).

Also, the SAT is useless for distance quesries, unless objects intersect. GJK can provide that.

GJK is another step after the SAT.