Solved

Separating Axis Theorem

Posted on 2003-11-04
9
1,292 Views
Last Modified: 2007-12-19
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.
0
Comment
Question by:epirocks
  • 2
  • 2
  • 2
  • +1
9 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9679429
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
 

Author Comment

by:epirocks
ID: 9679650
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
 
LVL 11

Expert Comment

by:bcladd
ID: 9687694
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
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 3

Accepted Solution

by:
Kashra earned 250 total points
ID: 9726937
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
 
LVL 11

Expert Comment

by:bcladd
ID: 10120493
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
 
LVL 3

Expert Comment

by:Kashra
ID: 10123592
Or you could give credit to the person who actually answered the question?
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 10127226
0

Featured Post

Active Directory Webinar

We all know we need to protect and secure our privileges, but where to start? Join Experts Exchange and ManageEngine on Tuesday, April 11, 2017 10:00 AM PDT to learn how to track and secure privileged users in Active Directory.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
This video shows how to quickly and easily add an email signature for all users on Exchange 2016. The resulting signature is applied on a server level by Exchange Online. The email signature template has been downloaded from: www.mail-signatures…
A short tutorial showing how to set up an email signature in Outlook on the Web (previously known as OWA). For free email signatures designs, visit https://www.mail-signatures.com/articles/signature-templates/?sts=6651 If you want to manage em…

830 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question