How to recalculate axis-aligned bounding box after translate/rotate

Question

When I first load my object I calculate the initial AABB with the maximum and minimum (x,y,z) points. But this is in object space and the object moves around the world and more importantly, rotates.

How do I recalculate the new AABB every time the object is translated/rotated? This happens basically in every frame. Is it going to be a very intensive operation to recalculate the new AABB every frame? If so, what would be the alternative?

I know AABBs will make my collision detection less accurate, but it's easier to implement the collision detection code than OBBs and I want to take this one step at a time.

Here's my current code after some insight from the answers below:

typedef struct sAxisAlignedBoundingBox {
    Vector3D bounds[8];
    Vector3D max, min;
} AxisAlignedBoundingBox;

void drawAxisAlignedBoundingBox(AxisAlignedBoundingBox box) {
    glPushAttrib(GL_LIGHTING_BIT | GL_POLYGON_BIT);

    glEnable(GL_COLOR_MATERIAL);
    glDisable(GL_LIGHTING);

    glColor3f(1.0f, 1.0f, 0.0f);

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[0].x, box.bounds[0].y, box.bounds[0].z);
        glVertex3f(box.bounds[1].x, box.bounds[1].y, box.bounds[1].z);
        glVertex3f(box.bounds[2].x, box.bounds[2].y, box.bounds[2].z);
        glVertex3f(box.bounds[3].x, box.bounds[3].y, box.bounds[3].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[4].x, box.bounds[4].y, box.bounds[4].z);
        glVertex3f(box.bounds[5].x, box.bounds[5].y, box.bounds[5].z);
        glVertex3f(box.bounds[6].x, box.bounds[6].y, box.bounds[6].z);
        glVertex3f(box.bounds[7].x, box.bounds[7].y, box.bounds[7].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[0].x, box.bounds[0].y, box.bounds[0].z);
        glVertex3f(box.bounds[5].x, box.bounds[5].y, box.bounds[5].z);
        glVertex3f(box.bounds[6].x, box.bounds[6].y, box.bounds[6].z);
        glVertex3f(box.bounds[1].x, box.bounds[1].y, box.bounds[1].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[4].x, box.bounds[4].y, box.bounds[4].z);
        glVertex3f(box.bounds[7].x, box.bounds[7].y, box.bounds[7].z);
        glVertex3f(box.bounds[2].x, box.bounds[2].y, box.bounds[2].z);
        glVertex3f(box.bounds[3].x, box.bounds[3].y, box.bounds[3].z);
    glEnd();

    glPopAttrib();
}

void calculateAxisAlignedBoundingBox(GLMmodel *model, float matrix[16]) {
    AxisAlignedBoundingBox box;
    float dimensions[3];

    // This will give me the absolute dimensions of the object
    glmDimensions(model, dimensions);

    // This calculates the max and min points in object space
    box.max.x = dimensions[0] / 2.0f, box.min.x = -1.0f * box.max.x;
    box.max.y = dimensions[1] / 2.0f, box.min.y = -1.0f * box.max.y;
    box.max.z = dimensions[2] / 2.0f, box.min.z = -1.0f * box.max.z;

    // These calculations are probably the culprit but I don't know what I'm doing wrong
    box.max.x = matrix[0] * box.max.x + matrix[4] * box.max.y + matrix[8] * box.max.z + matrix[12];
    box.max.y = matrix[1] * box.max.x + matrix[5] * box.max.y + matrix[9] * box.max.z + matrix[13];
    box.max.z = matrix[2] * box.max.x + matrix[6] * box.max.y + matrix[10] * box.max.z + matrix[14];
    box.min.x = matrix[0] * box.min.x + matrix[4] * box.min.y + matrix[8] * box.min.z + matrix[12];
    box.min.y = matrix[1] * box.min.x + matrix[5] * box.min.y + matrix[9] * box.min.z + matrix[13];
    box.min.z = matrix[2] * box.min.x + matrix[6] * box.min.y + matrix[10] * box.min.z + matrix[14];

    /* NOTE: If I remove the above calculations and do something like this:

             box.max = box.max + objPlayer.position;
             box.min = box.min + objPlayer.position;

             The bounding box will move correctly when I move the player, the same does not
             happen with the calculations above. It makes sense and it's very simple to move
             the box like this. The only problem is when I rotate the player, the box should
             be adapted and increased/decreased in size to properly fit the object as a AABB.
    */

    box.bounds[0] = Vector3D(box.max.x, box.max.y, box.min.z);
    box.bounds[1] = Vector3D(box.min.x, box.max.y, box.min.z);
    box.bounds[2] = Vector3D(box.min.x, box.min.y, box.min.z);
    box.bounds[3] = Vector3D(box.max.x, box.min.y, box.min.z);
    box.bounds[4] = Vector3D(box.max.x, box.min.y, box.max.z);
    box.bounds[5] = Vector3D(box.max.x, box.max.y, box.max.z);
    box.bounds[6] = Vector3D(box.min.x, box.max.y, box.max.z);
    box.bounds[7] = Vector3D(box.min.x, box.min.y, box.max.z);

    // This draw call is for testing porpuses only
    drawAxisAlignedBoundingBox(box);
}

void drawObjectPlayer(void) {
    static float mvMatrix[16];

    if(SceneCamera.GetActiveCameraMode() == CAMERA_MODE_THIRD_PERSON) {
        objPlayer.position = SceneCamera.GetPlayerPosition();
        objPlayer.rotation = SceneCamera.GetRotationAngles();

        objPlayer.position.y += -PLAYER_EYE_HEIGHT + 0.875f;

        /* Only one of the two code blocks below should be active at the same time
           Neither of them is working as expected. The bounding box doesn't is all
           messed up with either code. */

        // Attempt #1
        glPushMatrix();
            glTranslatef(objPlayer.position.x, objPlayer.position.y, objPlayer.position.z);
            glRotatef(objPlayer.rotation.y + 180.0f, 0.0f, 1.0f, 0.0f);
            glCallList(gameDisplayLists.player);
            glGetFloatv(GL_MODELVIEW_MATRIX, mvMatrix);
        glPopMatrix();

        // Attempt #2
        glPushMatrix();
            glLoadIdentity();
            glTranslatef(objPlayer.position.x, objPlayer.position.y, objPlayer.position.z);
            glRotatef(objPlayer.rotation.y + 180.0f, 0.0f, 1.0f, 0.0f);
            glGetFloatv(GL_MODELVIEW_MATRIX, mvMatrix);
        glPopMatrix();

        calculateAxisAlignedBoundingBox(objPlayer.model, mvMatrix);
    }
}

But it doesn't work as it should... What I'm doing wrong?

Alecto

Answer 1

Simply recompute the AABB of the transformed AABB. This means transforming 8 vertices (8 vertex - matrix multiplications) and 8 vertex-vertex comparisons.

So at initialisation, you compute your AABB in model space: for each x,y,z of each vertex of the model, you check against xmin, xmax, ymin, ymax, etc.

For each frame, you generate a new transformation matrix. In OpenGL this is done with glLoadIdentity followed by glTransform/Rotate/Scale (if using the old API). This is the Model Matrix, as lmmilewski said.

You compute this transformation matrix a second time (outside OpenGL, for instance using glm). You also can get OpenGL's resulting matrix using glGet.

You multiply each of your AABB's eight vertices by this matrix. Use glm for matrix-vector multiplication. You'll get your transformed AABB (in world space). It it most probably rotated (not axis-aligned anymore).

Now your algorithm probably only work with axis-aligned stuff, hence your question. So now you approximate the new bounding box of the transformed model by takinf the bounding box of the transformed bounding box:

For each x,y,z of each vertex of the new AABB, you check against xmin, xmax, ymin, ymax, etc. This gives you an world-space AABB that you can use in your clipping algorithm.

This is not optimal (AABB-wise). You'll get lots of empty space, but performance-wise, it's much much better that recomputing the AABB of the whole mesh.

---

As for the transformation matrix, in drawObjectPlayer:

gLLoadIdentity();
glTranslatef(objPlayer.position.x, objPlayer.position.y, objPlayer.position.z);
glRotatef(objPlayer.rotation.y + 180.0f, 0.0f, 1.0f, 0.0f);
glGetFloatv(GL_MODELVIEW_MATRIX, mvMatrix);
// Now you've got your OWN Model Matrix (don't trust the GL_MODELVIEW_MATRIX flag : this is a workaround, and I know what I'm doing ^^ )

gLLoadIdentity(); // Reset the matrix so that you won't make the transformations twice
gluLookAt( whatever you wrote here earlier )
glTranslatef(objPlayer.position.x, objPlayer.position.y, objPlayer.position.z);
glRotatef(objPlayer.rotation.y + 180.0f, 0.0f, 1.0f, 0.0f);
// Now OpenGL is happy, he's got his MODELVIEW matrix correct ( gluLookAt is the VIEW part; Translate/Rotate is the MODEL part
glCallList(gameDisplayLists.player); // Transformed correcty

I can't explain it further than that... as said in the comments, you had to do it twice. You wouldn't have these problems and ugly workarounds in OpenGL 3, btw, because you'd be fully responsible of your own matrices. Equivalent in OpenGL 2:

glm::mat4 ViewMatrix = glm::LookAt(...);
glm::mat4 ModelMatrix = glm::rotate() * glm::translate(...);
// Use ModelMatrix for whatever you want
glm::mat4 ModelViewMatrix = ViewMatrix * ModelMatrix;
glLoadMatrix4fv( &ModelViewMatrix[0][0] ); // In OpenGL 3 you would use an uniform instead

Much cleaner, right?

Cyclometer

I'm sorry, but I have no idea how to do that. That's exactly my question. And can't I just work with the max/min (x,y,z) instead of 8 vertices? I can calculate those 8 vertices with the max/min if I have to, but the question is how to convert them into world-space after translation and rotations. – Alecto

Much less confusing now, thanks. However, I would like to avoid using the GLM library for this, I would prefer to do the matrix calculations myself. But that's where I'm failing... – Alecto

Everything you do, matrix multiplication included, looks good, except this : glGetFloatv(GL_MODELVIEW_MATRIX, mvMatrix), which returns ViewMatrix * ModelMatrix. Sadly, this is old-school OpenGL, and there is no mean to only get the model matrix. Workaround : loadIdentity, translate, rotate, getfloat (now you have ModelMatrix), loadIdentity, gluLookAt, translate, rotate (now opengl is happy with its modelviewmatrix) – Cyclometer

oh, and there is a mistake (not crucial now). According to how you rotate your model, box.max can really become the minimum on some axis, so at the end of calculateAxisAlignedBoundingBox, you need something like box = computeAABB ( box.bounds ) (more or less) – Cyclometer

But I already do that to get the model matrix, the only thing is that I do it the other way around: loadIdentity, gluLookAt, translate, rotate, loadIdentity, translate, rotate, glGetFloat. It's in the code I posted, in attempt #2. Shouldn't this be enough? – Alecto

Re-read my comment :) You need to do it twice, one for you (ModelMatrix only) and one for OpenGL (ViewMatrix * ModelMatrix) – Cyclometer

Looking at the code I posted, wouldn't that be the same as enabling both code blocks (in the order they currently are) but removing the glGetFloatv from the first code block? If not, then maybe I don't understand (or know how) to do it just for the ModelMatrix and then another for ViewMatrix * ModelMatrix. Isn't the first code block VM * MM and the second just the MM? Do I need to swap them? Again, removing the unneeded glGetFloatv from one of the code blocks. – Alecto

Hum, as far as I can see it, my problem is on gluLookAt and the matrix I need to use on my object-space to world-space calculations is simply the Model Matrix and not the ViewMatrix * ModelMatrix, correct? In other words, to calculate the AABBs, I need to do the transformations twice and one of them must be before gluLookAt, correct? Other than that, my vector-matrix multiplications are correct? – Alecto

More or less. You need ModelMatrix; OpenGL needs ModelViewMatrix. You compute ModelMatrix, get your own copy, reset (glLoadIdentity), recompute ModelView, and let it to opengl. And your vector-matrix multiplication seems ok, yes. – Cyclometer

Answer 2

Yep, you can transform the eight corner vertices and do min/max on the results, but there is a faster way, as described by Jim Arvo from his chapter in Graphics Gems (1990).

Performance-wise, Arvo's method is roughly equivalent to two transforms instead of eight and basically goes as follows (this transforms box A into box B)

// Split the transform into a translation vector (T) and a 3x3 rotation (M).

B = zero-volume AABB at T
for each element (i,j) of M:
   a = M[i][j] * A.min[j]
   b = M[i][j] * A.max[j]
   B.min[i] += a < b ? a : b
   B.max[i] += a < b ? b : a
return B

One variation of Arvo's method uses center / extent representation rather than min / max, which is described by Christer Ericson in Real-Time Collision Detection (photo).

Complete C code for Graphics Gems article can be found here.

Twin

This should be the accepted answer. It's what is used in real code. Thanks for references. – Bronchopneumonia

Note that this unfortunately does not work with non uniform scaling – Rapine

Answer 3

To quote a previous response on AABB @ Stack Overflow:

"Sadly yes, if your character rotates you need to recalculate your AABB . . .

Skurmedel

---

The respondent's suggestion, and mine, is to implement oriented bounding boxes once you have AABB working, and also to note you can make aabb's of portions of a mesh to fudge collision detection with greater accuracy than one enormous box for each object.

Objection

Answer 4

To do that you have to loop over every vertex, calculate its position in the world (multiply by modelview) and find the minimum / maximum vertex coordinates within every object (just like when you compute it for the first time).

You can scale your AABB a bit, so that you don't have to recalculate it - it is enough to enlarge it by factor sqrt(2) - your rotated object then always fits in AABB.

There is also a question in which direction you rotate(?). If always in one then you can enlarge AABB only in that direction.

Optionally, you can use bounding spheres instead of AABBs. Then you don't care about rotation and scaling is not a problem.

Stutz

The question is how do I do that? I already have the max/min (x,y,z) in object space. I also have the exact (x,y,z) position of the object in world space. My question is how to calculate the AABB with this info. – Alecto

You need max/min in world space, not object space. Maybe I don't understand you correctly but as I said - you need to iterate over all vertices. For each vertex compute it's (x,y,z) in world space. From these world space coordinates choose min and max in each axis to get AABB. – Bozeman

To transform object space coordinates to world space multiply them by model matrix. – Bozeman

enlarge by sqrt(2) and using bounding spheres only helps if the pivot point is the center of the sphere or bbox. – Jacindajacinta

@lmmilewski I know that I need max/min in world space, that's what this question is about and that's what I'm trying to do. I have them in object space and I need to know how to convert them to world space. That's my problem. I'm trying to multiple them by the model matrix but I'm not doing it right as it's not working... I think I'll have to post a sample of my current code. – Alecto

I see you are still using the old API. You don't maintain model matrix yourself - I always did. In your code you don't multiply by MODEL matrix but by MODELVIEW (which is model and view matrices multiplied). You can either compute the model matrix or push opengl modelview matrix, load identity, do all transformation/rotation/scaling stuff and get modelview matrix, then pop the matrix - that way view matrix is identity in modelview, so you get only model matix. I'd choose implementing model matrix myself - It's usefull to hove one accessible in your program. – Bozeman

So, in other words, are you're saying that I should leave botch code blocks active, removing glGetFloatv from code block #1 cause it's not needed there and change code block #2 accordingly to the procedure you just described? Or am I misunderstanding any of it? – Alecto

Answer 5

Why not use your GPU? Today I implimented a solution of this problem by rendening a couple of frames.

1. Temporary place your camera over the object, above it, pointing down at the object.
2. Render only your object, with out lights or anything.
3. Use orthographic projection too.
4. Then read the frame buffer. Rows and columns of black pixels means the model isn't there. Hit a white pixel - you hit one of the model AABB borders.

I know this isn't a solution for all the cases, but with some prior knowledge, this is very efficient.

For rendering off screen see here.

Moreland

This could technically work but I'd doubt if it would be any efficient due to the drawing and especially the reading the framebuffer part – Emphasize

You also need the bounding box of your object before doing this (otherwise, how do you know you are projecting the whole object on the render target). A solution which is slower in both development time and runtime performance. – Huambo