Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Separating Axis Theorem

Posted on 2003-11-04
9
Medium Priority
?
1,314 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
Learn how to optimize MySQL for your business need

With the increasing importance of apps & networks in both business & personal interconnections, perfor. has become one of the key metrics of successful communication. This ebook is a hands-on business-case-driven guide to understanding MySQL query parameter tuning & database perf

 
LVL 3

Accepted Solution

by:
Kashra earned 1000 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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

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

Artificial Intelligence comes in many forms, and for game developers, Path-Finding is an important ability for making an NPC (Non-Playable Character) maneuver through terrain.  A* is a particularly easy way to approach it.  I’ll start with the algor…
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
Sometimes it takes a new vantage point, apart from our everyday security practices, to truly see our Active Directory (AD) vulnerabilities. We get used to implementing the same techniques and checking the same areas for a breach. This pattern can re…
We’ve all felt that sense of false security before—locking down external access to a database or component and feeling like we’ve done all we need to do to secure company data. But that feeling is fleeting. Attacks these days can happen in many w…

715 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