Separating Axis Theorem

Hello,

I have looked everywhere for a real, decent, sensitive explanation  of the Separating Axis Theorem, and I just cannot find anything that makes any sense.  I can't visualize what it is talking about.

I want to be able to detect and extract information from a collision between two Orientated Boxes, it say severywhere to use this Theorem but says nowhere about how it works, or what it is.

Please help me out. Thanks.
epirocksAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

sunnycoderCommented:
http://www.flipcode.com/cgi-bin/msg.cgi?showThread=00009404&forum=3dtheory&id=-1
http://citeseer.nj.nec.com/context/605523/0  (check the links)
ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/sig96.pdf
some explanation is on the acm site but it needs a member account for accessing ... citeseer looks like best bet
0
epirocksAuthor Commented:
None of those are very clear at all.

Just seems like every article I look at does it's best to confuse me.
If you can tell me the difference between edge directions and face directions that would be great. But even besides this, it does not explain step by step.

I probably need that degree in Mathematics.

0
bcladdCommented:
Have you looked in Akenine-Moller and Haines _Real-time Rendering_? Chapter 13 covers intersection test methods and the gang here seemed to get most of the information from their treatment.
van den Bergen's _Collision Detection in Interactive 3D Environments _ was published this week. It looks to cover much of the same material with a few more proofs and some additional concepts (I haven't read it, just drooled over the table of contents of a colleague's copy).

Both of these books have copious citations so you can look for papers/technical reports underlying the material presented.

Hope this helps, -bcl
0
Cloud Class® Course: MCSA MCSE Windows Server 2012

This course teaches how to install and configure Windows Server 2012 R2.  It is the first step on your path to becoming a Microsoft Certified Solutions Expert (MCSE).

KashraCommented:
The Gottshalk reference above is probably the best one on OBB collision detection. That's where I learned about it from, anyway. I'll do my best to describe it here.

Let's start in 2D. The first thing you have to understand is how to project objects onto a line (an axis) in space. You can imagine this, visually, by placing a spotlight directly over the objects and watching where their "shadows" would fall on the line. (The virtual spotlight should be oriented so that it shines directly onto the line; its light rays should be perpendicular to the line) The shadows are the projection of these objects on the line.

If you don't know how to mathematically find the projection of one vector onto another, then you should take a course or read a book on vector math, dot and cross products, etc. I'll assume you know how to do this.

Anyway, imagine two boxes in quadrant I of a 2D space. Let's use the x-axis as our "line" for simplicity's sake. Now imagine the projection of these boxes onto the line. If the projections don't overlap (you have two distinct projections with some separating region between them), then the boxes cannot be colliding and you have found the "separating axis". If they were colliding in any way, then the shadows/projections would overlap.

Keep in mind that if the shadows/projections DO overlap, that doesn't mean that the boxes are colliding. It just means you can't tell yet. You have to try another axis. Try the y-axis. Still overlapping? How about the line formed by one of the box-edges? The Gottschalk paper describes the minimum number of such tests required to find a separating axis. If you exaust all of those tests and still can't find a separating axis, then the boxes must be colliding.

In 3D, the same analogy applies. Imagine the shadows of the boxes on some arbitrary plane (since we've added a dimension, we're looking for a separating plane now). If they don't overlap, then you know the boxes can't be touching each other. If they do, then you have to try another plane.

Ultimately, it turns out you have to try, at most, 15 such tests before you can be sure that the boxes are colliding. The paper describes a lot of simplification in the math that makes these tests a lot faster computationally. I also think it does a great job explaining it. You just need to slow down and take it one step at a time.

Good luck!
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
bcladdCommented:
Despite the original poster's qualms, sunnycoder gave a great number of very good resources. I gave some books that might help.

Maybe an 80/20 split sunnycoder and I?

-bcl
0
KashraCommented:
Or you could give credit to the person who actually answered the question?
0
sunnycoderCommented:
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Game Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.