Skip to main content
gamedev.net
🔒 Locked

15 separating axis optimization

Started by Darkbouncer4689 3 replies 2.3k views
Original Post
Darkbouncer4689
Darkbouncer4689
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?
LorenzoGatti
LorenzoGatti

... 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.
Omae Wa Mou Shindeiru
Darkbouncer4689
Darkbouncer4689

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!
LorenzoGatti
LorenzoGatti
  • 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.
Omae Wa Mou Shindeiru
Darkbouncer4689
Darkbouncer4689
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 >_>

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.