Solved

Separating Axis Theorem

Posted on 2003-11-04
9
1,299 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
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 is a high-level webinar that covers the history of enterprise open source database use. It addresses both the advantages companies see in using open source database technologies, as well as the fears and reservations they might have. In this…
Michael from AdRem Software outlines event notifications and Automatic Corrective Actions in network monitoring. Automatic Corrective Actions are scripts, which can automatically run upon discovery of a certain undesirable condition in your network.…

734 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