Solved

Separating Axis Theorem

Posted on 2003-11-04
9
1,266 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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
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

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

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 …
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…
It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…

758 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

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now