# collision detection in 3D

This topic is 4087 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

##### Share on other sites
Quote:
 Original post by daniel_i_lI'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).

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by daniel_i_lWould 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.

##### Share on other sites
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

##### Share on other sites
Quote:
 Original post by bpj1138There 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.

##### Share on other sites
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...

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 :)

##### Share on other sites
Quote:
Original post by jyk
Quote:
 Original post by bpj1138There 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

##### Share on other sites
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).

##### Share on other sites
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).

##### Share on other sites
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.

##### Share on other sites
Hey Oliii, can you remember if that paper only delt with OBB's?

##### Share on other sites
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...

void Intersect(A, B, &N, &d){    bool test = true;    int axiscount=0;        while (...)    {        Vector D = ...some separation axis between A & B...        float mina, minb;        float maxa, maxb;        GetInterval(A, D, mina, maxa);        GetInterval(B, D, minb, maxb);         float d0 = maxb - mina;        float d1 = maxa - minb;           // intervals dont intersect.        // => objects separated.        // no intersection!        if(d0 < 0 || d1 < 0)        {             N = D; // that's a separation axis that separates the objects             return false;        }        float d2 = D.DotProduct(D); // square length of axis.        float axisd = (d0 < d1)? -d0 / d2 : d1 / d2;        if(axiscount == 0 || fabs(axisd) < d)        {            N = D;            d = axisd;        }        axiscount++;    }    return true;}

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

##### Share on other sites
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.

Vector N;float d;if(Intersect(A, B, &N, &d)){    N.Normalise(); // normalise    if (N.DotProduct(B.pos - A.pos)) < 0.0f) // make sure N points A -> B        N = -N;    C_SupportFace supportFaceA;    C_SupportEdge supportEdgeA;    C_SupportVertex supportVertexA;    C_SupportFeatureA* pSupportA = NULL;           if(FindSupportFace(A, -N, &supportFaceA))    {         pSupportA = &supportFaceA;    }    else if(FindSupportEdge(A, -N, &supportEdgeA))    {        pSupportA = &supportFaceA;    }    else     {        FindSupportVertex(A, -N, &supportVertexA); // always true        pSupportA = &supportVertexA;    }    C_SupportFace supportFaceB;    C_SupportEdge supportEdgeB;    C_SupportVertex supportVertexB;    C_SupportFeatureA* pSupportB = NULL;           if(FindSupportFace(B, N, &supportFaceA))    {         pSupportB = &supportFaceB;    }    else if(FindSupportEdge(B, N, &supportEdgeB))    {        pSupportB = &supportFaceB;    }    else     {        FindSupportVertex(B, N, &supportVertexB); // always true        pSupportB = &supportVertexB;    }    C_ContactPoints contactPoints;    CalculateContactPoints(pSupportA, pSupportB, &contactPoints);}

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....

##### Share on other sites
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).

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by daniel_i_lThanks 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?

##### Share on other sites
Yes that helped a lot! thanks

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
There are a 2 steps, as the others already mentioned:

1) calculating the separating vector (normal+signed distance, where negative distance implies penetration)
2) gathering all contact points, potentially using information from step 1

SAT and GJK provide solutions for step 1 (GJK doesn't calculate penetration, it relies on another approach)
Olivier Renault (oliii's) SAT tutorial called Cube3d.zip is a good starting point.

At http://bullet.sf.net I provide an open source collision detection and rigid body dynamics library, Bullet, that includes solutions for 1 and 2, using GJK and SAT. The CcdPhysicsDemo shows stable stack of cylinders.

For 2, by default Bullet has a complex contact point reduction algorithm, so it works with implicit shapes like cylinder, cones as well as convex polyhedra, boxes, spheres etc, all using GJK. Therefore, instead of calculating all points in one go, it collects them over several frames and performs reduction. Alternatively Bullet provides a direct contact clipping approach for polyhedra, that calculates all contact points based on the separating normal and the most parallel features. (this is not enabled by default, and the sources are in 'Extras/SATCollision'). This is similar to oliii's approach.

In Bullet, I prefered to use GJK and contact caching/reduction, so one code path can solve all combinations. However, Bullet allows to register collision algorithms for each pair, so it is easy to compare SAT with GJK, and contact caching/reduction with direct clipping. The constraint solver stores extra information in the cached contact points, like the previous frames solution (warm starting).

Hope this helps,
Erwin Coumans
http://continuousphysics.com

##### Share on other sites
Thanks everyone,
i have a question about getting the actual collision points after finding the supports. lets say that i have a face-face collision, instead of clipping would it work to check if the vertices of each face are in the other body - this is very fast to check, then after finding a vert inside a body (lets call it A), i'd just have to move along the MTD inorder to find the point on body B.
What do you guys think?
Thanks.

##### Share on other sites
Point in poygon tests wont be enough I'm afraid.

/*             -----            |     |             |     |             |     |      -------------------    |                   |    |                   |     -------------------            |     |             |     |             |     |              -----*/

That wouldn't work for example.

Also, you would be missing 'supports' on the intersections, which will improve the stability.

And yes, you can use the MTD by finding the other pairing point on the other object.

Clipping isn't that expensive really. Remember that face / face collisions should only be a minor occurence. Most of the collisions you will encounter will be point-face. Also, as soon as you do have objects resting on top of each others, the physics system should have a clever way to stop testing collisons and 'rest' the objects.

##### Share on other sites
Thanks, but i really have no clue how the clipping works, do you think that you could provide some links or an explanation?
Thanks.

##### Share on other sites
Quote:
 Original post by daniel_i_lThanks, but i really have no clue how the clipping works, do you think that you could provide some links or an explanation?
Just as a side note, be aware that implementing robust collision detection and response at the level under discussion here is non-trivial. If you're pursuing it out of interest by all means do so, but if this is more in the service of a particular game or project, you might consider either a less complicated collision detection and response scheme, or perhaps a third-party library. Just something to think about.

As for your question, the type of clipping that will be required depends on the support feature pair, that is, the two support features, one from each box, along the minimum axis. The possible support feature pairs and clipping types are:

1. vertex-vertex

Obviously no clipping is required here (or the clipping is trivial, depending on how you want to look at it). This case will hardly ever, if ever, occur in practice.

2. vertex-edge

Similarly, this case is very unlikely; the point of contact is trivially the vertex.

3. vertex-face

Again the point of contact is trivially the vertex; this will probably be the most common type of contact.

4. edge-edge

This type of contact may be fairly common, depending. In most cases the edges will be skew with respect to one another, in which case the contact point can be computed as the average of the pair of closest points between the two line segments. The algorithm for finding this pair of points is well documented and is described and implemented at geometrictools.com, in Graham's article in GPG, and many other places. Googling 'closest point line segments' will probably also turn it up.

In the exceedingly rare case where the edges are parallel or nearly parallel (not so rare, I suppose, if the boxes have one axis that has a consistent alignment), the line segments must be clipped together to find the pair of points that describes the contact manifold. Robustness issues are introduced here, as an appropriate tolerance must be used for detecting the parallel case, otherwise the closest-points algo may fail. The clipping can be done by projecting the endpoints of one segment onto the other segment, and finding the set intersection in the parametric space of the second segment. Not entirely trivial, but pretty easy, especially compared to...

5. edge-face

In an environment where no particular orientation or set of orientations is favored, this will be rare. Here you actually have to perform 'real' clipping of the line segment against the extruded planes of the face. Robustness is again an issue here, since the segment may be parallel or nearly parallel to one or more face planes (well, exactly two in the case of an OBB).

6. face-face

Again, fairly uncommon, and requires the same attention to detail with respect to clipping. Here you apply the Sutherland-Hodgman clipping algorithm to one of the faces against each of the extruded planes of the other face in sequence. Be aware that the SH clipping algo is not always presented in the same way, and some implementations are less robust than others. For an excellent discussion of this (and many other things relevant to this topic) check out Christer Ericson's book.

Now although I described some of these cases as rarely occuring, if your environment includes gravity, and you wish for objects to stack and/or come to rest, those cases will move from the 'rare' category to the 'inevitable' category. In this case your edge-face and face-face clipping functions will get a workout.

Anyway, that's a brief summary of at least one way you can go about it. As shown in previous posts there are several different approaches and algorithms you can bring to bear on the problem. Alas, none of them is trivial, and once you get your coldet working you still have the physics to contend with!

##### Share on other sites

This topic is 4087 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.