Hi everyone, I've been having the exact same issues as the OP so I was hoping I might be able to join the discussion here (if anyone is against this I'll happily make my own thread)? I've been attempting to essentially "rebuild" the 8 corner points of the AABB using the current min/max, then I transform them and lastly I get a new min/max by comparing these 8 transformed corner points with the current min/max. However, when I rotate the object the AABB only ever grows in size and scaling simply doesn't seem to work at all (translation works fine).

// Bounds indexing: 0 = min, 1 = max
void Transform( const glm::mat4x4 &transform ) {
    // Translation	
    glm::vec3 translation( transform[3][0], transform[3][1], transform[3][2] );
    bounds[0] += translation;
    bounds[1] += translation;
		
    // Rotation/scale
    // Recreate the original 8 corner points from the current min/max
    glm::vec4 cornerPoints[8] = {
        // starting from the top left going clockwise; back-face
	glm::vec4( bounds[0].x, bounds[1].y, bounds[0].z, 0.f ), glm::vec4( bounds[1].x, bounds[1].y, bounds[0].z, 0.f ),
	glm::vec4( bounds[1].x, bounds[0].y, bounds[0].z, 0.f ), glm::vec4( bounds[0].x, bounds[0].y, bounds[0].z, 0.f ),
	// front-face
	glm::vec4( bounds[0].x, bounds[1].y, bounds[1].z, 0.f ), glm::vec4( bounds[1].x, bounds[1].y, bounds[1].z, 0.f ),
	glm::vec4( bounds[1].x, bounds[0].y, bounds[1].z, 0.f ), glm::vec4( bounds[0].x, bounds[0].y, bounds[1].z, 0.f ),
    };

    // Create "new" AABB
    for( U32 i=0; i<8; ++i ) {
        cornerPoints[i] = cornerPoints[i] * transform;

	// Try and find new min/max
	if( cornerPoints[i].x < bounds[0].x ) bounds[0].x = cornerPoints[i].x;
	if( cornerPoints[i].y < bounds[0].y ) bounds[0].y = cornerPoints[i].y;
	if( cornerPoints[i].z < bounds[0].z ) bounds[0].z = cornerPoints[i].z;

	if( cornerPoints[i].x > bounds[1].x ) bounds[1].x = cornerPoints[i].x;
	if( cornerPoints[i].y > bounds[1].y ) bounds[1].y = cornerPoints[i].y;
	if( cornerPoints[i].z > bounds[1].z ) bounds[1].z = cornerPoints[i].z;
    }
		
    // Lastly, set center and size
    center = ( bounds[0] + bounds[1] ) / 2.f;
    size = ( bounds[1] - bounds[0] ) / 2.f;
}

@swiftcoder

How else can I propagate transformations hierarchically? Up-to-date books don't mention anything clever... (e.g Real-Time Rendering)

@CacheMiss

Here's the method I came up with

void Aabb::applyTransformation(const glm::mat4 &transformation)
{
	glm::vec3 min, max;
	glm::mat3 t3x3(transformation);
	glm::vec3 translation = decomposeTranslation(transformation);

	glm::vec3 corners[8]; //all 8 corners of the box
	corners[0] = t3x3 * _min;
	corners[1] = t3x3 * glm::vec3(_max.x, _min.y, _min.z);
	corners[2] = t3x3 * glm::vec3(_min.x, _min.y, _max.z);
	corners[3] = t3x3 * glm::vec3(_max.x, _min.y, _max.z);
	corners[4] = t3x3 * glm::vec3(_min.x, _max.y, _min.z);
	corners[5] = t3x3 * glm::vec3(_max.x, _max.y, _min.z);
	corners[6] = t3x3 * glm::vec3(_min.x, _max.y, _max.z);
	corners[7] = t3x3 * _max;

	for(unsigned int i = 0; i < 8; i++) {
		min = glm::min(min, corners[i]);
		max = glm::max(max, corners[i]);
	}

	setMinMax(min + translation, max + translation);
}

@swiftcoder
How else can I propagate transformations hierarchically? Up-to-date books don't mention anything clever... (e.g Real-Time Rendering)

Real-time rendering is a decent book for rendering techniques, but it doesn't go into the nitty-gritty details of performance optimising low-level engine architecture (and I don't know of a book that does).

The answer to your question is that you stop using global transform hierarchies all together. Why on Earth does each object in the world need a base scene nodes that is attached to a global root node in the first place? How often have you actually transformed the world's root scene node?

So now you don't have any hierarchy at a global level, and you can just keep a flat array of transforms of the top-level objects in the world, which don't need to be updated, because they don't have parents. Perfect, not doing work is about as cache friendly as you can get.

Of course, we still need hierarchies. They make hooking up that sword to the player's hand really convenient, and you almost certainly need skeletal animation, which is organised as a transform hierarchy anyway... So for each top-level object you optionally store a local hierarchy.

And the great thing about these local hierarchies, is that the shape of the tree almost never changes - insertions and removals are really rare operations. So you can bake these down into a flat array, sort them by their depth in the tree, and now these can be updated by just iterating over the tree.

And now our scene update loop looks something like this:

foreach (object in world) {
    object.worldTransforms[0] = world.transforms[object]
}

foreach (object in world) {
    foreach (i in [1...object.numNodes]) {
        object.worldTransforms[i] = object.localTransforms[i] * object.worldTransforms[object.parents[i]];
    }
}

Which is entirely composed out of linear iterations over flat arrays, and contains no extraneous branches. I don't think you can make it a whole lot more cache friendly than that.

In here

foreach (object in world) {
    foreach (i in [1...object.numNodes]) {
        object.worldTransforms[i] = object.localTransforms[i] * object.worldTransforms[object.parents[i]];
    }
}

How can you be sure that an object's worldTransform will not be calculated before its parent worldTransform?

How can you be sure that an object's worldTransform will not be calculated before its parent worldTransform?

You keep the array sorted by the depth of each item in the tree.

As long as parents are guaranteed to be before their children in the array, you can safely update them in order.

That avoid to have 2 representations (root array + linear array) in a cost of a shift of array.

Since the AddChild/RemoveChild is not done every frame surely it's a good option.

Take care if you use index and not pointer for parents since the array is not fixed.

Thanks for you response @Pilpel, I apologize if it seems like I'm trying to "hijack" the thread (just trying to keep related questions together). I pretty much have the same solution as you, only when I rotate the object the AABB only ever grows in size (never shrinks). Does you approach work in all cases?

Yes

Thanks, think I have an idea what's up with mine...

@swiftcoder,

I'm having difficulties implementing your approach.

It's all fun and easy when all I need is to update the transformations of each node in the object hierarchy, but I also need to store AABBs for collision detection and culling. What do I do about that?

Also, a normal scene node hierarchy lets the user have many different types of scene nodes attached to one another to get diverse results. This isn't possible with your approach, right?