Jump to content
  • Advertisement
Sign in to follow this  
daniel_i_l

collision detection in 3D

This topic is 4390 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

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 this post


Link to post
Share on other sites
Advertisement
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).

Share this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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...

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!