# 15 separating axis optimization

This topic is 2532 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey all,

So I'm working on the 15 separating axes theorem for OBB/OBB intersection detection. I actually have it working, but it's the brute force method that just computes dot/cross products everytime. I wan't to make use of the extensive optimization that can be done by getting rid of dot products that will always be 1 or 0.

So since we know we are dealing with orthogonal axes, the dot product of any axis with one of it other axes will be 0 since they are perpendicular.

Also the dot product of an axis with itself will be 1 (but) only when we are dealing with a unit vector such as (1, 0, 0), (0, 1, 0), (0, 0, 1).

This is the part that is messing me up as the axes of my OBB's are not unit vectors.

I'm assuming there is some type of rotation that needs to be done in order to change the axes of both OBB's we are testing to unit vectors in order for the optimization to work? How can this be done without messing up the orientation of the OBB's?

##### Share on other sites

... the extensive optimization that can be done by getting rid of dot products that will always be 1 or 0.
So since we know we are dealing with orthogonal axes, the dot product of any axis with one of it other axes will be 0 since they are perpendicular.

Unless they aren't. Any two boxes can have an arbitrary relative orientation: the only axes that are guaranteed to be perpendicular are those of a single box. Detecting perpendicular vectors amounts to computing the dot products you want to skip, so it is completely pointless.

##### Share on other sites

Unless they aren't. Any two boxes can have an arbitrary relative orientation: the only axes that are guaranteed to be perpendicular are those of a single box. Detecting perpendicular vectors amounts to computing the dot products you want to skip, so it is completely pointless.

Hey Lorenzo,

Thanks for the post. You are correct, the only axes that are guaranteed to be perpendicular are the axes of the same box. Thus for axis test Au, Ay, Az, Bu, By, Bz we could save computing 2 dot products for each of these separating axes tests as the vectors will be perpendicular.

However there are a lot more optimizations to be made. One being if we are dealing with unit vectors the dot product of a vector with itself will be 1.

Also for the separating axes tests that deal with cross products, if we make use of the property

sA dot (B X C) = sC dot (A X B)

there are considerable optimizations to be made for those 9 tests as well. Could you please elaborate as to why these optimizations are unimportant?

Also, back to my original post, the part I am hoping to get some advice on would be how to convert the axes of the OBBs to unit vectors in order to optimize the algorithm.

Thanks!

##### Share on other sites
• The axes of your boxes can be defined by rotation and translation of the axes of a reference box: unit vectors remain unit vectors, you only need to store box height, width and depth separately. I suspect you are representing your boxes in some less convenient way.
• There are no clever data-dependent optimizations, only the special messy case of parallel axes.
• You aren't going to compute dot products or cross products between axes of the same box, nor of any vector with itself.Please post code.

##### Share on other sites
Solved. I got owned by storing some the absolute values of some variables that weren't suppose to have their absolute value for certain calculations >_>

1. 1
2. 2
3. 3
Rutin
22
4. 4
JoeJ
16
5. 5

• 14
• 29
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631774
• Total Posts
3002287
×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!