23

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?

5 Answers 5

20

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?

9
  • 1
    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.
    – rfgamaral
    May 19, 2011 at 11:17
  • 1
    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...
    – rfgamaral
    May 19, 2011 at 15:46
  • 1
    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)
    – Calvin1602
    May 19, 2011 at 21:24
  • 2
    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)
    – Calvin1602
    May 19, 2011 at 21:30
  • 1
    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?
    – rfgamaral
    May 19, 2011 at 23:02
12

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 mix / max, which is described by Christer Ericson in Real-Time Collision Detection (photo).

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

1
  • 4
    This should be the accepted answer. It's what is used in real code. Thanks for references.
    – vehsakul
    Jul 31, 2020 at 14:42
2

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.

7
  • 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.
    – rfgamaral
    May 19, 2011 at 11:12
  • 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. May 19, 2011 at 11:30
  • To transform object space coordinates to world space multiply them by model matrix. May 19, 2011 at 11:30
  • enlarge by sqrt(2) and using bounding spheres only helps if the pivot point is the center of the sphere or bbox.
    – Frunsi
    May 19, 2011 at 12:33
  • 2
    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. May 20, 2011 at 6:00
1

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.

-7

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.

2
  • 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 Jan 1, 2022 at 16:20
  • 1
    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.
    – Ad N
    Apr 7, 2022 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.