Sign in to follow this  

15 separating axis optimization

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
[quote name='Darkbouncer4689' timestamp='1313188638' post='4848443']
... 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.
[/quote]
Unless they aren't. Any two boxes can have an arbitrary relative orientation: the only axes that are [i]guaranteed[/i] 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 this post


Link to post
Share on other sites
[quote name='LorenzoGatti' timestamp='1313334767' post='4848990']
Unless they aren't. Any two boxes can have an arbitrary relative orientation: the only axes that are [i]guaranteed[/i] 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.
[/quote]


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 this post


Link to post
Share on other sites
[list][*]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.[/list]Please post code.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this