Sign in to follow this  

Separating Axis Theorem - Point of Collision

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

Hello,

 

so I have implemented the SAT in my programm, which simulates colliding convex Boxes in 3D.

Right know the Collision-Detection is working completely perfect, the Boxes aren't overlapping at all, but just touching each other.

 

The next step is to find the Point of Collision to go on with the Collision-Response. Therefor I googled like hell, but sadly only found very difficult solutions. An approximation of the Point of Collision is acceptable as well.

Numerous Threads said using the MTV (Minimum Translation Vector) combined with the SAT will give me the Point of Collision, but I wasn't able to understand how.

I prefer theoretical explanations due to the fact that this is a more mathematical/physical problem.

I hope you can help me with a simple solution.

PS: Sorry for my bad English, but I'm from Germany.

Share this post


Link to post
Share on other sites

you should define what is a "convex box" and wheather it differs from "convex geometry" at leas somehow, other than it is a box, or cube? In case of perfect optimization, if you are counting only with "convex box"-es , define "convex box", it will move you front...

Share this post


Link to post
Share on other sites

Oh I haven't thought this causes trouble, I just mentioned the word "convex" because the SAT only works with convex bodies. By a "convex box" I just mean a normal "box" with 6 planes looking like this: http://www.medienwerkstatt-online.de/lws_wissen/bilder/22080-1.jpg

But how do I get the Point of Collision? Any Ideas?

Share this post


Link to post
Share on other sites

I gave a presentation about the SAT this year at GDC which also talks a bit about contact creation: You can download the presentation and sample code here: https://code.google.com/p/box2d/downloads/list

 

The usual way to compute the contact points is:

- Compute the axis of minimum penetration (using SAT or whatever you prefer)

 

If the axis of minimum penetration is defined by a face normal

- The associated face defines the reference face

- The most anti-parallel face on the other shape defines the incident face

- Clip the incident face against the side planes of the reference face

- Keep all point below the reference face

 

If the axis of minimum penetration is defined by two edges

- Compute the closest points between the two edges and use the centroid as contact point

 

I also recommend downloading the GDC 2007 presentation by Erin Catto from the same link above. It talks about contact manifolds. There is also a GDC presentation Erwin Coumans which you can download here: https://code.google.com/p/bullet/downloads/list

 

This should get you started. If you look for examples I recommend looking at Bullet, Box2D and in the ODE at a routine called dBoxBox().

 

HTH,

-Dirk

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites

First of all thank you very much for this detailed post, but there are some questions left I need to take care of.

1. The axis of minimum penetration, is it just the axis defined by the orientation of the Minimum-Translation-Vector? If not, how do I get it?

2. By saying "If the axis of minimum penetration is defined by a face normal" you mean the 6 axes defined by the 2 boxes and by saying "If the axis of minimum penetration is   defined by two edges" you mean the 9 axes defined by the crossproduct of the 6 axes, don't you?

 

Thanks a lot for the link to all this helpful presentations, they will surely help me understanding the sub-points of your explanation!

If there are any further questions I will post them here, maybe you can answer them for me :)

Till then have a nice day!

Share this post


Link to post
Share on other sites

If you test all possible separating axes between two overlapping convex shapes you can keep track of the largest negative projection for this axis. This is called the axis of minimum penetration.

 

I also recommend looking into Christer Ericson's book: "Real-Time Collision Detection"

 

And yes, sure ask your questions here or on the Bullet forums... :)

Share this post


Link to post
Share on other sites

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