Will Perone

Calculating the Axis Aligned Bounds of a Rotated Rectangle (aka generating AABB from OBB)


So we have a rectangle that represents the oriented bounding box (OBB) of some object in our game and we need to check collision with hundreds maybe thousands of other game objects. Off the bat we think QuadTree but even after putting that we still want to have some sort of trivial rejection before doing complex collision-response calculations on the objects thus regular old bounding box checks would be great for this. But, how do we get the bounding box?

This is a question I commonly ask in interviews and is important to know how to do correctly and efficiently to perform trivial rejection on objects in the world before you start processing real collision with them. This is especially important in Flash because getBounds is very slow because it does checks for lots of different things that we don't need in this scenario.

There are 2 ways to approach this problem, with trig and with linear algebra.

Trig Approach

We can form 2 right triangles on the bottom there after making the realization that the angle 'a' at the bottom is the same thing as the angle the object is rotated by. We also can deduce that b = 180 - 90 - a = 90 - a
Our 2 bottom segments then become:
h*cos(b) and w*cos(a)
Let's call the total bounding box width w' = h*cos(90 - a) + w*cos(a)
Making a bit of a leap of faith (or just using Google or actually analyzing it mathematically) we can figure out that cos(90 - a) = sin(a) so we end up with:
w' = h*sin(a) + w*cos(a)
h' = h*cos(a) + w*sin(a)
But wait, does that really always work? Check out the scenario below:

When our rectangle is rotated more than 90 degrees, what are our 2 bottom segments?
Our left side becomes w*cos(180-a) and the right side is now h*cos(180-a-90) = h*cos(90-a) = h*sin(a)
If you draw a cosine graph you can quickly realize that cos(180-a) = -cos(a) so now we have a problem:
if (a < 90) use w*cos(a) else use -w*cos(a)
So what does this mean? Is there a way to optimize this further? What about the sin(a) component?

If you look at the graph of cosine you will notice that it goes negative at 90 degrees, essentially what the equation above means is we need to take the absolute value of cos(a). If you run through more cases like a > 180 and a > 270 you will realize this happens for the sine and cosine components, ie. if (a > 180) use -h*sin(a).
Using this we arrive at:
w' = h*abs(sin(a)) + w*abs(cos(a))
h' = h*abs(cos(a)) + w*abs(sin(a))
This is correct and pretty fast as it is BUT there is still more we can do... We really don't want to calculate sin/cos twice and Math.abs is slow in AS3 because it calls a function to do a fundamental operation and functions sadly do not inline in AS3. Extracting out sin/cos in AS3 we get:
s= Math.sin(a);
c= Math.cos(a);
wn= h*Math.abs(s) + w*Math.abs(c);
hn= h*Math.abs(c) + w*Math.abs(s);
Getting rid of the slow Math.abs call:
s= Math.sin(a);
c= Math.cos(a);
if (s < 0) s= -s;
if (c < 0) c= -c;
wn= h*s + w*c; // width of AABB
hn= h*c + w*s; // height of AABB

Linear Algebra Approach

Immediately we see this is a rotation operation. We know there are 4 vertex points but since the rectangle is rotated around it's center, those points are all symmetric:
[-w/2,-h/2], [w/2,-h/2], [-w/2,h/2], [w/2,h/2]
We just need to rotate one of them to figure out the other 3:
[w/2]   [cos(a)  -sin(a)]   [w*cos(a)/2 - h*sin(a)/2]
[h/2] * [sin(a)   cos(a)] = [w*sin(a)/2 + h*cos(a)/2]
Doing this for all 4 points we will get the same result just with +/- in all the fields, to find the extents of the box though we want the find the maximum of all of these transformed points so we end up with:
[w*max(cos(a),-cos(a))/2 + h*max(sin(a),-sin(a))/2]
[w*max(sin(a),-sin(a))/2 + h*max(cos(a),-cos(a))/2]
Of course we make the same realization we did with the trig approach: max(sin(a),-sin(a)) and max(cos(a),-cos(a)) is the same thing as the absolute value. Substituting and factoring out the 1/2 we get:
[w*abs(cos(a)) + h*abs(sin(a))] / 2
[w*abs(sin(a)) + h*abs(cos(a))] / 2
At this point we make the same steps above as we did in the trig method but there is a fundamental difference in this approach. Using linear algebra we end up finding the extents and not the dimensions so this will be exactly 1/2 of the trig version:
s= Math.sin(a) / 2;
c= Math.cos(a) / 2;
if (s < 0) s= -s;
if (c < 0) c= -c;
ex= h*s + w*c;  // x extent of AABB
ey= h*c + w*s;  // y extent of AABB
Which is more useful? We have to take a step back and see what we are using this for again: to do fast bounding box checks before we calculate collision. The center of the rectangle is going to be its position in world space so our checks are going to have to take that into consideration. We will need to know the left,top,right and bottom bounds to do the actual bounding box checks and to do that we will need to add and subtract some value from the position of the rectangle. Because of this, the linear algebra solution is better:
if (x-ex < otherObjectRight && x+ex > otherObjectLeft &&
    y-ey < otherObjectTop && y+ey > otherObjectBottom) collide();

More Optimizations

If you know 0 <= a <= 360, you can branch on a instead of doing 2 absolute values
const pi:Number= Math.PI;
const pi2:Number= Math.PI/2;
const pi32:Number= Math.PI*3/2;

s= Math.sin(a) / 2;
c= Math.cos(a) / 2;
if (a < pi2)  ex= h*s+w*c, ey= h*c+w*s; else
if (a < pi)   ex= h*s-w*c, ey= w*s-h*c; else
if (a < pi32) ex= -h*s-w*c, ey= -h*c-w*s; else
                 ex= w*c-h*s, ey= h*c-w*s;

Also, we don't need to calculate the extents every time we check the collision; we only need to do this when the rectangle is rotated. If you have a bunch of rectangles rotating all the time, you may consider constructing a 3d lookup table indexed by angle, width and height.

Bigger Picture

Taking a look at the 10000 ft perspective again, think about what we are trying to accomplish here. We are trying to trivially reject objects from colliding. Maybe we don't need this level of accuracy? Chris Birke has pointed out to me that instead of even doing a rotation calculation, just rough estimate the extents as a square with it's dimensions being max(w,h)*(some feathering constant, maybe sqrt(2)). Whether you use this super simplified approach mainly depends on the actual objects themselves. If you have very long objects in the mix this approach would not work well, if you know everything is similar to a square in shape then this could be used.
1 Comment
Rangle 2011/12/31 Contact Me4 1
I'm shcoekd that I found this info so easily.

<- for private contact