Sign in to follow this  

How to efficiently update AABB on scaling/translating?

This topic is 411 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

AABB says to recalculate the box if rotation change on the base model. So if I scale, or translate the model, I don't need to recalculate.

I've calculated the min/max values from local space so far, and when I wanted to check intersection, I asked for the model's scale and transform information, and transformed the box to world space.

 

As it turns out to get the min/max values on a rotated model, I have to apply world transformation to the vertices, and save those min/max values in world space.

 

The question is: if I do a translation or a scale, how should I calculate the new min/max values of the box, without iterate through the vertices in world space. I fell I may lack some math knowledge here, or miss something trivial.

 

Share this post


Link to post
Share on other sites

Rotate the box with the object. Find the min/max values of the corners. Adjust the AABB's box corners to fit. It sounds stupid but in reality it works. I came up with this terrible trick when I was looking at an action figure inside a plastic container. It won't be completely accurate. But you should use your original BB as the item to recompute your new BB to help reduce some errors.

 

If the object animates however, you need to do it the hard way. But if the animation is periodic and is not very dynamic (trees bending and bowing in blowing wind. You can save yourself the trouble and just expand the bounding box a bit to encompass the entire animation. You can do this with player models as well.

 

The other stupid trick is if the animation is not too dependent on blending and has a lot of variations, you can just animate the bounding box to fit the model. Then the rotation trick I mentioned will still work.

Edited by Tangletail

Share this post


Link to post
Share on other sites

Here is the fastest method that I am aware of, this uses 4D SIMD vectors to implement, but you can just swap out for your own Vector3f/Vector4f. It involves taking the local-space AABB, translating it to the origin, rotating according to the transformation, computing the extents along each axis, finding the min/max in world space, then translating the box according to the position offset of the transform. It should compile to about 30 instructions with SSE.

class ALIGN(16) Transform
{
	class ALIGN(16) Basis
	{
		// Scaled X, Y, Z columns of rotation matrix.
		SIMDFloat4 x;
		SIMDFloat4 y;
		SIMDFloat4 z;
	};
	
	Basis basis;
	SIMDFloat4 position;
};

SIMDFloat4 Transform:: transformPoint( const SIMDFloat4& point )
{
	return position + basis.x*point[0] + basis.y*point[1] + basis.z*point[2];
}

void Transform:: transformAABB( const SIMDFloat4& aabbMin, const SIMDFloat4& aabbMax,
								SIMDFloat4& transformedMin, SIMDFloat4& transformedMax )
{
	// Move the box to the origin and scale it.
	const SIMDFloat4 center = (aabbMin + aabbMax)*SIMDFloat4(0.5f);
	const SIMDFloat4 localMin = aabbMin - center;
	const SIMDFloat4 localMax = aabbMax - center;
	
	// Compute the extents along each world axis.
	SIMDFloat4 aX = basis.x*localMin[0];
	SIMDFloat4 bX = basis.x*localMax[0];
	SIMDFloat4 aY = basis.y*localMin[1];
	SIMDFloat4 bY = basis.y*localMax[1];
	SIMDFloat4 aZ = basis.z*localMin[2];
	SIMDFloat4 bZ = basis.z*localMax[2];
	
	// Start at the world-space center of the box.
	transformedMax = transformedMin = this->transformPoint(center);
	
	// Update the final AABB.
	transformedMin += (math::min( aX, bX ) + math::min( aY, bY ) + math::min( aZ, bZ ));
	transformedMax += (math::max( aX, bX ) + math::max( aY, bY ) + math::max( aZ, bZ ));
}
Edited by Aressera

Share this post


Link to post
Share on other sites

Adding some more stupid tricks I remembered doing.

For fully animated objects with IK, I did not actually recalculate based on each vertex. This would be rediculously expensive as it needs to be animated per frame.

Instead I did a really rough estimation based on the object's skeleton.

The skeleton would hold a very very tiny point cloud. Usually no more than maybe about 15-30 points.

These points would be attached to only the parts of the skeleton that would actually have a major impact over the Bounding Box.

So the hip, a few locations on the back. One locked onto the forearm and streatching out from the elbow to the full length of the hand. The elbow. Four on the head. The knees, the feet.

It basically looked like a dude wearing a mocap suit.

When the object animates, the Bounding box is based off of those points, and not the actual mesh. The result is a roughly fitted bounding box.

 

I did these tricks because no matter what people say, a f*cking phone is not that powerful.

Edited by Tangletail

Share this post


Link to post
Share on other sites

This topic is 411 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this