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?

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?