Jump to content
  • Advertisement
Sign in to follow this  
Promit

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

This topic is 4748 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

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


Link to post
Share on other sites
Advertisement
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 this post


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


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


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


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


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

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!