Hi there,

I'm having a hard time with this AABBs and despite lots of more topics on this board about the same subject, I still had to register and post my own question as I can't make it work... Hopefully someone here can guide me in fixing my problems and tell me what am I doing wrong.

I can easily calculate the max/min vertex of some object and create the bounding box of that object. It's also easy to move that box when the object moves; I just need to sum max/min with the object position and that's it. But when it comes to rotations, I'm finding it really hard to calculate the AABB. And I probably need to take a different approach. From what I've read, I need to multiply the modelview matrix by the max/min vector or maybe the 8 vertices of the bounding box (it's probably the same, converting from one to the other is trivial).

But that's exactly my problem... I just can't calculate the AABB after rotating the object and I have no idea what I'm doing wrong. The object I'm trying to create the AABB for is the player, which starts at the world's origin. With my current code, if I don't move the player and just rotate, the bounding box starts shrinking/enlarging but not correctly. If I move the player a bit and then rotate, the bounding box starts shrinking/enlarging as before but it will also rotate around some arbitrary point and I don't know why that happens. Bottom line is, my code is not working as I want it...

[source lang="cpp"]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);
}
}[/source]

The first thing I'd suggest is to consider whether you really need to update the AABB in this way, or if you could just use a sphere or AABB that encompasses the object in all orientations and be done with it. (The latter would be quite a bit easier.)

The second thing I'd say is that any time you find yourself writing something like this:

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];
It's time to refactor. These sorts of operations should be wrapped up in operators or functions with meaningful names. This will make debugging easier (because you can test functionality in isolation and, once tested, remove it from consideration as a source of error - ideally at least), and will also make it easier to reason about the algorithm at a high level.

As for building an AABB from a rotated AABB, it can be done without transforming the corners or anything like that. A rotated AABB is essentially an OBB, and you can easily compute the orthogonal projection of an OBB with respect to an arbitrary axis. By projecting the OBB (the rotated AABB) onto the cardinal axes (which can be treated as a special case), you can compute a new AABB that encompasses the rotated AABB.

Again though, it's probably worth considering whether this is really worth the trouble.

(...)or AABB that encompasses the object in all orientations and be done with it

I don't know what that means, could you clarify please?

It's time to refactor. These sorts of operations should be wrapped up in operators or functions with meaningful names. This will make debugging easier (because you can test functionality in isolation and, once tested, remove it from consideration as a source of error - ideally at least), and will also make it easier to reason about the algorithm at a high level.

Sure, but if I waste too much time refactoring code like that and then end up with code that doesn't work or doesn't do what I want and need to recode everything, then I wasted precious time refactoring. First I'm trying to make things work as I want it, then I refactor and wrap code like that in a proper function.

As for building an AABB from a rotated AABB,(...)

This is confusing me... The problem is that I don't think I have a "rotated AABB". I only have one AABB, the original one. Then I translate/rotate my object and that AABB no longer has any meaning, it needs to be recalculated. That's what I'm trying to achieve...

A rotated AABB is essentially an OBB, and you can easily compute the orthogonal projection of an OBB with respect to an arbitrary axis. By projecting the OBB (the rotated AABB) onto the cardinal axes (which can be treated as a special case), you can compute a new AABB that encompasses the rotated AABB.

Ok, you lost me there...

Again though, it's probably worth considering whether this is really worth the trouble.

I'm actually trying to work with bounding spheres now and see whether they are enough for most objects but I'm afraid they won't suffice for some other objects, that's why I'm trying to get AABB to work and then pick the ones that work better with each specific object.

And since you mentioned bounding spheres, I'm having a tiny little problem with them and I'm not sure what I'm doing wrong. Again, the problem I'm having is with the calculation and it's basically finding the the radius and better fits the whole object. I've tried 2 different approaches (which I'll post below).

The first one, depending on the object, does not completely enclose it in a sphere. For instance, a cube will have it's corners outside of the bounding sphere. The second one is creating bouding spheres much larger than what they should be but I can't understand where my calculations are failing. What I'm doing wrong?

First approach with tight bounding spheres:[color="#010001"]
[source lang="cpp"]
glmDimensions(objPlayer.model, objDim);

objDim[0] /= 2.0f, objDim[1] /= 2.0f, objDim[2] /= 2.0f;
maxRadius = MAX(objDim[0], MAX(objDim[1], objDim[2]));
[/source]
Second approach with big bounding spheres:
[color="#010001"][source lang="cpp"]
glmDimensions(objTower[0].fireModel, objDim);

objDim[0] /= 2.0f, objDim[1] /= 2.0f, objDim[2] /= 2.0f;
vAux.SetValue(objDim[0], objDim[1], objDim[2]); // Vector (x,y,z)
maxRadius = vAux.Magnitude();
[/source]

The problem is that I wanted to completely enclose the object in the bounding sphere (keep the cube corners inside) but I don't understand why my second approach is giving me pretty large bounding spheres for some objects.

I don't know what that means, could you clarify please?

I just mean that regardless of how the object is oriented, the AABB or bounding sphere will still completely contain it. (This way, you don't have to recompute the bounding volume when the object rotates.)

Sure, but if I waste too much time refactoring code like that and then end up with code that doesn't work or doesn't do what I want and need to recode everything, then I wasted precious time refactoring. First I'm trying to make things work as I want it, then I refactor and wrap code like that in a proper function.[/quote]
You're looking at it the wrong way (IMO). Although most things in software development have a degree of subjectivity to them, it's pretty close to an objective fact that refactoring is a critical part of the software development process, and will almost always improve software quality and make writing, testing, and debugging of code easier. (Maybe someone will offer a different opinion, but I think most developers would agree with this.)

You're not wasting time by refactoring; you're saving time by streamlining the development process. The process you describe - 'making it work, and then refactoring' - is more or less the opposite of what's generally accepted.

One of the key benefits of refactoring is making it easier to determine code correctness, which in turn makes it easier to 'make your code work'. That's why 'making it work and then refactoring' is backwards; refactoring is (in part) how you make it work.

A related concept is unit testing. Let's say you have a function that multiplies a vector by a matrix. Ideally, you would implement this function, then test it in isolation until you're fairly certain it's correct. Then, you can use that function instead of writing out the multiplication by hand, and be fairly certain that the source of any problems you might encounter is not in the multiplication code itself.

As your code is now though, the bug could be anywhere; it's hard for you to debug it, and it's hard for someone else to read over your code and try to help you diagnose the problem.

There's a lot more that could be said about this, but I'll offer one more rationale for refactoring. Ideally, code that implements an algorithm should read like a high-level description of the algorithm. If the algorithm involves transforming a vector by a matrix, there should (ideally) be a single statement that performs this operation. That way, you can read through the code and easily follow the algorithm, step-by-step. Cluttering the code with the low-level details of each individual operation makes it hard to see the 'big picture' and to evaluate the correctness of the algorithm at a high level.

In summary, I strongly suggest reconsidering your approach. Refactoring should come first, not last; refactor early and often, and you'll find that your code will be much easier to work with and of much higher quality.

This is confusing me... The problem is that I don't think I have a "rotated AABB". I only have one AABB, the original one. Then I translate/rotate my object and that AABB no longer has any meaning, it needs to be recalculated. That's what I'm trying to achieve...[/quote]
By 'rotated AABB', I just mean that if you have an object with an AABB, and then you rotate that object, you then have a rotated AABB.

The use of the term 'AABB' in this context may be confusing, since obviously after being rotated, the AABB is likely no longer axis-aligned. The point though is that the AABB is axis-aligned in the local space of the object; it's only in world space that it's (possibly) not axis-aligned. This rotated AABB can however be used to generate a new world-space AABB that fully contains the object.

Ok, you lost me there...[/quote]
I wouldn't worry about that part unless you really need to compute a new AABB for the rotated object. (Basically though, the projection process is the same as is used in the SAT.)

I just mean that regardless of how the object is oriented, the AABB or bounding sphere will still completely contain it. (This way, you don't have to recompute the bounding volume when the object rotates.)

Oh, that... Well, I don't think it would make sense to use AABB that way, I would rather use a Sphere instead (what I'm currently doing). If I choose to go with AABB, I want it to be as tight as possible on all axis.

About the refactoring discussion, it's your opinion (and I'm sure others) and I respect it, but I don't fully agree with it. I think it all comes down on you and how you are more productive. I'm more productive if I refactor in the end. Specially when I don't know exactly what I'm doing and I'm just trying really hard to make things work, experimenting. IMO, it's pointless to keep refactoring the code in a situation like this. But like I said, this is just me, I achieve better results like this. Everyone should do what's best for them

By 'rotated AABB', I just mean that if you have an object with an AABB, and then you rotate that object, you then have a rotated AABB.

I still don't get it... Where is the rotated AABB? Where are the values for the box 8 corners? I understand that a rotated AABB is basically a OBB, but how do I get the values that define that AABB/OBB after the object rotation then?

This rotated AABB can however be used to generate a new world-space AABB that fully contains the object.

That's exactly what (I think) I'm trying to do by extracting the modelview matrix and generating the new world-space AABB that fully contains the object. That's the problem, is not working. The question now is, what I'm doing wrong? Or maybe I'm doing everything wrong and the question becomes, how do I do it then?

Oh, that... Well, I don't think it would make sense to use AABB that way, I would rather use a Sphere instead (what I'm currently doing). If I choose to go with AABB, I want it to be as tight as possible on all axis.

Sure, what makes sense depends on the specifics of your application, and maybe orientation-independent AABBs aren't the optimal choice in your particular case. But, they're used quite often, and can be a good choice where the simplicity that's gained is more important than having the highest possible accuracy.

About the refactoring discussion, it's your opinion (and I'm sure others) and I respect it, but I don't fully agree with it. I think it all comes down on you and how you are more productive. I'm more productive if I refactor in the end. Specially when I don't know exactly what I'm doing and I'm just trying really hard to make things work, experimenting. IMO, it's pointless to keep refactoring the code in a situation like this. But like I said, this is just me, I achieve better results like this. Everyone should do what's best for them[/quote]
Well, that's one of the nice things about programming for yourself - you can do things however you want :)

But, I think it's worth noting that your approach is basically the opposite of standard practice and what most software developers (I suspect) would recommend.

Also, it's not only about what works best for you. When you post code to the forum for others to help you with, at that point, it starts to matter what the code looks like. You may not care that much one way or the other, but refactoring will make it easier for other people (like your fellow forum members) to help you. So, if you don't want to refactor for yourself, you might at least consider doing it for others who might end up reading your code (like us :).

Also, moving stuff like matrix-vector multiplication into its own function is barely even refactoring; it's just basic code organization.

I still don't get it... Where is the rotated AABB? Where are the values for the box 8 corners? I understand that a rotated AABB is basically a OBB, but how do I get the values that define that AABB/OBB after the object rotation then?[/quote]
I might be misunderstanding the question, but there's a couple of different ways to represent an AABB. The first (and probably most common) way is as a 'min' vector and a 'max' vector. The second (and somewhat more general) way is as a center point, and a set of extents (the box's half-dimensions along each cardinal axis).

An OBB takes the latter representation (center and extents) and adds to that an arbitrary orientation. In this sense, an AABB is simply a special-case of an OBB; that is, it's an OBB with an identity orientation.

You can convert back and forth between the min-max and center-extents AABB representations easily. If you convert to the center-extents representation and then factor in the object's orientation, you then have an OBB. (Again, the canonical representation for an OBB is a center point, an extent for each axis, and an orientation, usually represented by three orthonormal basis vectors.)

That's exactly what (I think) I'm trying to do by extracting the modelview matrix and generating the new world-space AABB that fully contains the object. That's the problem, is not working. The question now is, what I'm doing wrong? Or maybe I'm doing everything wrong and the question becomes, how do I do it then?
[/quote]
Without digging into your code, I can't really say where the problem is exactly. Have you tried stepping through the code in the debugger?

I'm not saying I don't agree with you completely, you have some valid points but I don't agree with them all. But I'm not going to discuss the refactoring issue any longer, it's not relevant to my problem. Although I think you're making a big fuss out of nothing. It's not like the code I posted is unreadable or hard to understand because I didn't move a matrix-vector multiplication into it's ow function. That's nothing to compared some atrocities I see on other topics (not necessarily this forum). I'm always really careful when I post topics such as this in forums (or StackOverflow which I use more often). I compose my topic carefully and as easy to understand as possible, text and code wise. The better and more clear I make my post, the easier and faster someone will help me out. Basically, I help people help me.

I might be misunderstanding the question, but there's a couple of different ways to represent an AABB. The first (and probably most common) way is as a 'min' vector and a 'max' vector. The second (and somewhat more general) way is as a center point, and a set of extents (the box's half-dimensions along each cardinal axis).

Yes, that's what I have, a min and max vector (that's in box.max and box.min).

Let's say I load an object and draw it on screen without any translation/rotation. The object will be drawn at the origin and if I draw a box with the max/min vectors, everything is fine and looks good. The problem is that when I translate the max/min doesn't translate along, in other words, the max/min are in object space (like the object is at the origin) and I need them in world-space. That's easy to fix, when I need the translated AABB I just need to add the object's current position to max and min vectors. It gets tricky when we are talking about a rotation instead of translation. That's my problem. I don't know how to convert the max/min object-space vectors into world-space ones.

Let me give an example...

Let's say I have a cube of size 1.0 on all sides. Then max will be (0.5, 0.5, 0.5) while min will be (-0.5, -0.5, -0.5). Drawing a box around the object with these values is easy, I just need to calculate the 8 points of the box and draw it. If I translate along the x axis by 2. drawing a box around the object is still easy. I just need to add that to max and min, which will now be (2.5, 0.5, 0.5) and (-2.5, 0.5, 0.5) respectively.

Again, with rotations is where it gets tricky. For simplification let's assume I didn't translate, just rotated, by 45º along the Y axis. Since this is a cube of size 1.0 on all sides, I know that the new max and min will be around (0.7, 0.5, 0.7) and (-0.7, -0.5, -0.7) respectively. How do I know that, well, rotating 45º on the Y axis makes the cube diagonals aligned with the X and Z axises and so I have to use those to calculate the new max and min. And the diagonal will be SQRT(1^2 + 1^2) = 1.4, which gives 0.7 when diving by 2 for the max/min vectors.

But this doesn't work (or I don't know how to make it work) when the object is not a cube (but a rectangle instead, in other words, different sizes for all axises) and when the rotated angle is something different, like 30º. With 45º we have the diagonals aligned with the X and Z axises which is what we need for a good AABB. But rotation something different doesn't give us aligned diagonals and so we can't use them (or I don't know how to use them to make it work).

Understand better my problem now? It's a little confusing and since English is not my main English, it can be hard for me sometimes to explain exactly what I want to say...

Although I think you're making a big fuss out of nothing.[/quote]
On the forums I frequent at least, it's fairly common for issues not directly related to the stated question to be addressed by those who reply. Quite often someone will ask about X while posting code with problem Y, and as part of answering the question, people will address problem Y as well as responding to question X. Once you've spent a little time on the boards, I think you'll see this is not at all uncommon, and while it may not always be well received, in most cases at least, the intent is to be helpful (maybe just not in the exact way that the poster was expecting).

Whether the forums should work this way is up for debate, I suppose, but for better or for worse, it's generally the way they do work.

As for 'making a fuss', I tend to be fairly detailed in my replies, and when I have a point to make, I'll sometimes devote a fair amount of attention to said point. Perhaps this seems like 'making a fuss' to you; if so, fair enough, I suppose. But, I stand by the emphasis I've placed on the issue.

It's a little confusing and since English is not my main English, it can be hard for me sometimes to explain exactly what I want to say...[/quote]
I may not be fully understanding the question, but if so, it's certainly not due to your writing (which is very clear and easy to understand :).

In your post above, it sounds to me like you're just asking how to compute the corners of the box once it's been rotated - is that correct?

If so, the answer is to transform the local-space corners of the box by the same transform you're using for the object. How to do this depends on what information you have available. How is the transform represented? (You may have already answered this question, but I can't remember at the moment.) A position vector and a quaternion? A 4x4 matrix? Something else?

In any case, you can always build a matrix representing the transform and then transform the local-space corners using a matrix-vector multiplication (using a 4-d vector with the 'w' element set to 1) or a special-case 'point transform' function.

Well, this is getting confusing lol...

I appreciate your help but I don't care about this any longer (at least for now). This university project is due tomorrow and I can't be bothered with this problem anymore, I still need to finish the report about the whole thing (which I haven't started yet). I decided to go with bounding spheres, they seem to work just fine for this project.

However, someone helped me out over at StackOverflow and I believe his answer does exactly what I want but I don't have time to test it and see if it really works. But I suppose it does so I'll just leave a link here for anyone else interested:
http://stackoverflow.com/questions/6053522/how-to-recalculate-axis-aligned-bounding-box-after-translate-rotate

Again, thank you for your time.

Regards.

However, someone helped me out over at StackOverflow and I believe his answer does exactly what I want

The general method described in the accepted StackOverflow answer is similar to the method I described earlier, only less efficient (although the difference in performance is unlikely to matter in this case).

But, I'm sorry we weren't able to help. I never quite got what the specific question was, but that was probably my failing.

Anyway, good luck with the project.