Axis aligned boxes and rotations

Pilepllon · 2016-01-02T16:58:44

I implemented frustum culling in my framework. It takes the 6 planes of the camera frustum and checks against all the models' AABBs. This worked great, even when I applied transformations to the scene nodes. Here's the important code runs every time a scene node is transformed. SceneNode.cpp void SceneNode::setTransformation(const glm::mat4 &transformation) { _transformation = transformation; //update _toRootTransformation for this node and all its children _updateToRootTransformations(); if(!_aabb) _aabb = new Aabb; *_aabb = _untransformedAabb->getTransformed( _toRootTransformation ); } Aabb.cpp void Aabb::applyTransformation(const glm::mat4 &transformation) { glm::vec3 min = glm::vec3( transformation * glm::vec4(_min, 1.0f) ); glm::vec3 max = glm::vec3( transformation * glm::vec4(_max, 1.0f) ); this->reconstructAabb(min, max); } Aabb Aabb::getTransformed(const glm::mat4 &transformation) const { Aabb aabb = *this; aabb.applyTransformation(transformation); return aabb; } I store an un-transformed AABB (called "_untransformedAabb") for each scene node, and when a transformation is applied, I set "_aabb" using the "_toRootTransformation" matrix. Now I came to realize that when applying rotations, the AABB gets broken, and the techniques that rely on valid AABBs break as well. After debugging I understand that this happened because the AABB's "min" and "max" numbers were mixed, meaning for example that min.x could be bigger than max.x. To fix this I added 3 lines to Aabb::applyTransformation(): void Aabb::applyTransformation(const glm::mat4 &transformation) { glm::vec3 min = glm::vec3( transformation * glm::vec4(_min, 1.0f) ); glm::vec3 max = glm::vec3( transformation * glm::vec4(_max, 1.0f) ); //to make sure that rotations won't ruin our aabb glm::vec3 temp = min; min = glm::min(min, max); max = glm::max(temp, max); this->reconstructAabb(min, max); } At first it looked like I solved my problem, but after checking how the AABB actually looks in the game I saw that it didn't. At some points in time, the AABB has a volume of 0. Can you think of any solution for my problem?

Math and Physics Programming

Started by Pilpel November 21, 2015 01:05 PM

31 comments, last by Alundra 8 years, 5 months ago

CacheMiss

194

December 15, 2015 08:18 PM

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;
}

Pilpel

564

Author

December 16, 2015 12:52 AM

@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

18,997

December 16, 2015 04:21 AM

@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.

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

Pilpel

564

Author

December 16, 2015 11:22 AM

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?

swiftcoder

18,997

December 16, 2015 04:31 PM

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.

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

Alundra

2,326

December 16, 2015 06:20 PM

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.

CacheMiss

194

December 16, 2015 09:07 PM

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?

Pilpel

564

Author

December 16, 2015 09:16 PM

Yes

CacheMiss

194

December 16, 2015 09:30 PM

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

Pilpel

564

Author

January 02, 2016 04:11 PM

@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?

Axis aligned boxes and rotations

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Axis aligned boxes and rotations

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines