# Quickest way to compute a new AABB from an AABB + transform?

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

## Recommended Posts

If we have an AABB defined by min and max points, and a 4x4 matrix transform, that creates an OBB. What is the quickest way to get the AABB of that OBB?

##### Share on other sites
Wellllll.... Transform the 8 vertices of the AABB by the transformation matrix, then find the max and min x, y, and z values and use those as the extrema for the new AABB. Keep in mind, though, that the AABB of a transformed AABB may be significantly larger than the AABB of the transformed object itself. Consider a transformation consisting of a 45 degree rotation, and the AABB for a sphere. The AABB for the transformed sphere should of course be the same (a cube), but the AABB of the rotated cube will be a larger box.

EDIT: If you can represent the original bounding volume not as an AABB but as a union of spheres which bound the object, you can get fairly tight AABBs both for the original object and for rigid transformations and/or uniform scalings of the object, and efficiency will be fairly high. Tell me if you're interested in that approach.

##### Share on other sites
That's the method I thought of too...just wasn't sure if it was the optimal method of doing this.

As for a union of spheres, I'm not too interested as I'm just trying to construct an AABB tree. Definitely an interesting idea, just not what I need right now.

##### Share on other sites
For an AABB to be transformed to an OBB by a 4x4 homogeneous matrix, that means there is no projection and no skewing. I assume you intend that the transformation is rigid: translation and rotation. To illustrate in 2D, represent your AABB as you would for an OBB. A point in the AABB is P = C + u*I + v*J, where I = (1,0), J = (0,1), C = ((xmin+xmax)/2,(ymin+ymax)/2), |u| <= (xmax-xmin)/2, and |v| <= (ymax-ymin)/2.

The points are transformed by a rotation R and translation T by Q = R*P+T. The transformed AABB representation is Q = (R*C+T)+u*R*I+v*R*J, which is an OBB. The projection of this box onto the I direction is an interval centered at the x-value Dot(I,R*C+T) and has radius ((xmax-xmin)/2)*|Dot(I,R*I)|+((ymax-ymin)/2)*|Dot(I,R*J)|. Similar construction for the projection onto J. Note that Dot(I,R*I) = r00, the entry of matrix R in row 0 and column 0. Also, Dot(I,R*J) = r01, Dot(J,R*I) = r10, and Dot(J,R*J) = r11. All this leads to some simple formulas for the min and max values for the transformed AABB.

##### Share on other sites
Straight from one of the graphics programming gems books (can't remember which one, but I've been using this one in our games for years now)

-Steve.

Axis aligned bounding box is defined as follows
(vector3 is an array of 3 floats)
struct bbox
{
vector3 Min;
vector3 Max;
};

Matrix is simply a 4x4 of floats with access operators.

Enjoy.

void bbox::Transform( const matrix4& M ){    vector3 AMin, AMax;    f32     a, b;    s32     i, j;    // Copy box A into min and max array.    AMin = Min;    AMax = Max;    // Begin at T.    Min = Max = M.GetTranslation();    // Find extreme points by considering product of     // min and max with each component of M.    for( j=0; j<3; j++ )    {        for( i=0; i<3; i++ )        {            a = M(i,j) * AMin;            b = M(i,j) * AMax;            if( a < b )            {                Min[j] += a;                Max[j] += b;            }            else            {                Min[j] += b;                Max[j] += a;            }        }    }}

##### Share on other sites
I thought I would write up the details from my previous post in this thread. In the process, I was a bit surprised to find that the method I proposed is not the "fastest" of the ones I could think of. Here "fast" is based on counting operations and comparisons. Let 'm' be number of multiplications, 'a' be number of additions/subtractions, 'c' be number of comparisons, and 'f' be number of absolute value calls (fabs). On a Pentium, cost for 1m is roughly 4 cycles, cost for 1a is roughly 3 cycles, cost for 1c is roughly 4 cycles (plus worried about branch penalties), and cost for 1f is roughly 1 cycle. The fabs essentially changes a high-order bit, so you can do it with integer bit-mask operations. The comparisons in "winning" algorithm are tests for nonnegativity, so you can also do these with integer bit-mask operations (assuming standard IEEE floating-point numbers).

In 2D, the method I proposed costs 14m+10a+0c+2f. An alternate method, which tests the signs of the rotation matrix entries, costs 8m+8a+2c. In 3D, the extension of the method I proposed costs 27m+21a+0c+9f. The alternate method costs 18m+18a+9c. If you literally used the cycle counts I mentioned, in 2D my method is 74 cycles and the alternate is 56 cycles. In 3D, my method is 153 cycles and the alternate is 144 cycles. These numbers are close enough that you really would want to profile the real implementations for an accurate comparison.

##### Share on other sites
if you're not worried about tight fits, why not just make the bounding box large enough to hold the object under any orientation. ie find the bounding box of the bounding sphere. that way you don't even need to transform ever. seems like it would work dandy for realtiviley summetric objects.

Tim

1. 1
2. 2
3. 3
Rutin
14
4. 4
5. 5
khawk
11

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633671
• Total Posts
3013265
×