Axis aligned boxes and rotations

Started by
31 comments, last by Alundra 8 years, 3 months ago
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.

peotIij.gif
Can you think of any solution for my problem?
Advertisement

You have to transform the 8 corners of the original AABB and find the new min/max using these 8 new corners.

I see...

What about OBBs? Should I use them here? I never worked with them before.

What's the popular approach for this kind of things?

AABB and Sphere are the common approach for frustum culling.

If you want to use the OBB you will have to convert the frustum to OBB space and do the test like a classical AABB.

Then what are OBBs used for? Are they represented by an AABB with a transformation?

You definitely answered my question, if you could only link me to a good article about OBBs it would be great. I read the OBB section Real-Time Rendering but I didn't grasp it well.

Don't use OBB for broadphase culling, waste of your time.

What Alundra is saying that you need to transform the 8 corners of the AABB and build a new AABB using those 8 vectors is totally wrong, not sure why he gets upvoted for this wrong suggestion. You are already on the right track by just transforming the min and max vectors of the AABB and recomputing the AABB with just these two.

I think your problem is that glm::min and ::max probably do something else than you think it does, like maybe it just compares lengths of the 2 vectors and returns the lowest vector in the case of ::min. What you need is something like this:


AABB& AABB::recompute() {
    Vector3 newMin, newMax;

    if( min.x < max.x )
    {
        newMin.x = min.x;
        newMax.x = max.x;
    }
    else
    {
        newMin.x = max.x;
        newMax.x = min.x;
    }

    if( min.y < max.y )
    {
        newMin.y = min.y;
        newMax.y = max.y;
    }
    else
    {
        newMin.y = max.y;
        newMax.y = min.y;
    }

    if( min.z < max.z )
    {
        newMin.z = min.z;
        newMax.z = max.z;
    }
    else
    {
        newMin.z = max.z;
        newMax.z = min.z;
    }

    min = newMin;
    max = newMax;

    return *this;
}
Then what are OBBs used for? Are they represented by an AABB with a transformation?

OBB is simply a center, half extents and a rotation matrix (or rotation quaternion), can be like that :


struct TOBB
{ 
  CVector3 Center;
  CVector3 HalfExtents;
  CQuaternion Rotation;
};

They are used for animation when you want to find an AABB based on bones, in physics, and other places.

What Alundra is saying that you need to transform the 8 corners of the AABB and build a new AABB using those 8 vectors is totally wrong, not sure why he gets upvoted for this wrong suggestion. You are already on the right track by just transforming the min and max vectors of the AABB and recomputing the AABB with just these two.

This is trivially incorrect. If you take only the min and max corners, and rotate them by 45 degrees, then at least one of their coordinates will be equal, leading to a zero-width AABB.

Try it out with paper and pencil if you don't believe me.

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

Alundra said the only correct answer here

If you transform a mesh you need to recompute the AABB from its transformed vertices. This can be unnecessarily expensive for broaphase culling (e.g. in physics or visibility). A simple way to conservatively transform a given AABB is this:


rnVector3 TransformedCenter = Transform * Bounds.Center;
rnVector3 TransformedExtent = rnAbs( Transform.Rotation ) * Bounds.Extent;

Here the rotation part of the transform is a 3x3 matrix and rnAbs() builds the absolute value of each element of the matrix. This formula doesn't give you the best fit AABB like transforming each vertex, but it is conservative and will contain your transformed mesh (e.g. it can be larger than necessary and yield false positives). Note that I used the center/(half)extent form of the AABB here, but it is trivial to transform from/to the min/max form. I would also not worry about the performance if you need to transform between the two!

Conceptually this formula transforms the original AABB (which now becomes an OBB) and then builds its AABB.

HTH,

-Dirk

This topic is closed to new replies.

Advertisement