Sign in to follow this  
Spa8nky

How to construct an OBB/AABB from the following 6 planes?

Recommended Posts

I have the following 6 planes:
            position = centre;
            normal = normal_Surface;

            Vector3 binormal = Vector3.Cross(normal, tangent);   //up=tangent?

            //=============================================
            //------- [Calculate Boundary Planes] ---------
            //=============================================

            float d = Vector3.Dot(centre, tangent);
  
            plane_Left = new Vector4(tangent, width * 0.5f - d);        // Left Plane (As Vector4)  
            plane_Right = new Vector4(-tangent, width * 0.5f + d);      // Right Plane  

            d = Vector3.Dot(centre, binormal);

            plane_Bottom = new Vector4(binormal, height * 0.5f - d);    // Bottom
            plane_Top = new Vector4(binormal, height * 0.5f + d);       // Top

            d = Vector3.Dot(centre, normal);

            plane_Front = new Vector4(-normal, depth + d);              // Front
            plane_Back = new Vector4(normal, depth - d);                // Back
The problem is that if I want to convert the combination of the planes into a bounding volume for testing against triangles how would I find the rotation needed for a OBB, or would an AABB suffice. Both the OBB and AABB are constructed via a central point (which I can take from the centre paramter in above code) and Extents (width/2.0f, height/2.0f/, depth2.0f). For the AABB it should be easy enough to use the provided width, height and depth to create an AABB. However, in the case of the OBB it also requires a rotation matrix. How do I obtain the rotation matrix using the above case? The OBB will be used to determine which triangles intersect it for displaying a decal on a curved surface. If it is not necessary to use an OBB in this case please let me know.

Share this post


Link to post
Share on other sites
Just some ideas:

Assuming the only transformations are rotation/translation then each plane pair (opposite sides) is the transformed version of either x/y, x/z, y/z planes.

You could get each corner point of the box by solving for the intersection of 3 planes (left, bottom, back intersection would give that corners point). Once you have those you could use 3 of the co planar ones (say 3 points on the left plane) along with that planes normal to work out a basis matrix.


This makes some assumptions that might not be true. Lets say where you say "left plane" you know that that plane will be the z/y plane with minimum x value. You can use the point, bottom, left, near to bottom, left, far to determine the direction of the z axis in your transformed space. Do the same thing to get the y axiz (you already know the x axis, it is the plane normal).

Those 3 vectors now should form an orthogonal basis (providing no scaling was used) which is pretty much a rotation matrix.

If you don't know which plane represents which side of your box then there are any number of rotation matrices that could be the right one. Can't think of how to get that down to a unique solution.

Share this post


Link to post
Share on other sites
Quote:
How do I obtain the rotation matrix using the above case?
You already have it (the basis vectors are the normal, binormal, and tangent vectors in your example code).

To compute an AABB from an OBB, you can simply compute the projection of the OBB onto the cardinal axes. (Don't have time to post the details at the moment, but post back if you have questions about this.)

Share this post


Link to post
Share on other sites
I thought I might be making this too hard.

So is the rotation matrix as follows :

Matrix rotation = (tangent, binormal, normal)

Or is local space different to tangent space for rotation?

Quote:

To compute an AABB from an OBB, you can simply compute the projection of the OBB onto the cardinal axes.


I'm not sure I am going to need an AABB but can't I just ignore the rotation matrix for an AABB, or is the projection method the only option?

Thanks for your help.

Share this post


Link to post
Share on other sites
Quote:
I thought I might be making this too hard.

So is the rotation matrix as follows :

Matrix rotation = (tangent, binormal, normal)
Yes, that should be right, assuming you've placed the right vectors in the right columns/rows.

(There is the question of whether it should be 'binormal' or 'bitangent', but that's another issue.)
Quote:
I'm not sure I am going to need an AABB but can't I just ignore the rotation matrix for an AABB, or is the projection method the only option?
If you simply ignore the rotation, the AABB may not fully enclose the clipping volume (draw some example diagrams if you're unsure why this is the case).

AFAIK at least, the projection method is the fastest and most straightforward way to compute an AABB from an OBB.

Share this post


Link to post
Share on other sites
Quote:

Yes, that should be right, assuming you've placed the right vectors in the right columns/rows.


Well the matrices in XNA are row-major matrices.

So therefore:


rotation.M11 = tangent.X;
rotation.M12 = tangent.Y;
rotation.M13 = tangent.Z;

rotation.M21 = binormal.X;
rotation.M22 = binormal.Y;
rotation.M23 = binormal.Z;

rotation.M31 = normal.X;
rotation.M32 = normal.Y;
rotation.M33 = normal.Z;



Where a 4x4 row-major matrix =

11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44

Is this correct or should I arrange them in columns?

EDIT: If I wanted to get the yaw, pitch and roll from this rotation matrix, how would that be found?

Share this post


Link to post
Share on other sites
It looks like you have some of your terminology confused.
Quote:
Well the matrices in XNA are row-major matrices.

So therefore:
            rotation.M11 = tangent.X;
rotation.M12 = tangent.Y;
rotation.M13 = tangent.Z;

rotation.M21 = binormal.X;
rotation.M22 = binormal.Y;
rotation.M23 = binormal.Z;

rotation.M31 = normal.X;
rotation.M32 = normal.Y;
rotation.M33 = normal.Z;
That doesn't have anything to do with whether the matrices are row major or column major. It does however show that your matrices are set up to work with row vectors rather than column vectors.

Quote:
Where a 4x4 row-major matrix =

11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
And that doesn't relate in any way to majorness or vector notation convention :) (AFAIK at least, matrices in linear algebra are always indexed by row and then column.)
Quote:
Is this correct or should I arrange them in columns?
That depends on the conventions of the math library you're using. I haven't used XNA, but the DirectX math library uses row-major storage and row vectors, so if XNA uses the same conventions as DirectX, then you're good.

Quote:
If I wanted to get the yaw, pitch and roll from this rotation matrix, how would that be found?
First, the usual question: what do you need the Euler angles for?

You certainly can extract them if needed, but it's kind of a pain (you have to get all of the conventions right - including rotation axis order - or the results will likely be incorrect).

Also note that Euler-angle triples can alias one another (that is, two sets of Euler angles can produce the same orientation), so the Euler angles you get out won't always be the same as the angles you put in.

Share this post


Link to post
Share on other sites
Quote:

First, the usual question: what do you need the Euler angles for?


I don't sorry, it seems I just needed to use a Quaternion.CreateFromRotationMatrix() method which I overlooked by mistake.

If I want to compute a tight AABB from a rotation matrix and a central point, how would I go about doing that correctly?

This currently works for non rotated OBBs but I get the feeling it is not correct as you mentioned a projection method being involved:


public static CD_AxisAlignedBoundingBox ComputeFromRotationMatrix(Matrix rotation, Vector3 centre)
{
CD_AxisAlignedBoundingBox aabb_New = new CD_AxisAlignedBoundingBox(centre, 0, 0, 0);

// +ve halfwidth extents = radius
aabb_New.Extents.X += Math.Abs(rotation.M11);
aabb_New.Extents.X += Math.Abs(rotation.M12);
aabb_New.Extents.X += Math.Abs(rotation.M13);

aabb_New.Extents.Y += Math.Abs(rotation.M21);
aabb_New.Extents.Y += Math.Abs(rotation.M22);
aabb_New.Extents.Y += Math.Abs(rotation.M23);

aabb_New.Extents.Z += Math.Abs(rotation.M31);
aabb_New.Extents.Z += Math.Abs(rotation.M32);
aabb_New.Extents.Z += Math.Abs(rotation.M33);

return aabb_New;
}

Share this post


Link to post
Share on other sites
Quote:
If I want to compute a tight AABB from a rotation matrix and a central point, how would I go about doing that correctly?
You would need a set of extents in addition to a center point and rotation matrix (which I think you already know).

All you really need is a function to project an OBB onto an axis. No guarantee I'll get this right, but:
float center = dot(box.center, axis);
float radius =
abs(dot(box.axis[0], axis)) * box.extents[0] +
... ditto for index '1' ... +
... ditto for index '2';
min = center - radius;
max = center + radius;
Now, using this function, you simply project the OBB onto the three cardinal axes to yield the min and max extents of the AABB. (If performance is a concern, you can optimize the projection function to take advantage of the fact that the input axis is always a cardinal basis vector.)

Share this post


Link to post
Share on other sites
Thanks jyk,

Is the following method what you meant:


public static CD_AxisAlignedBoundingBox ComputeFromOBB(CD_OrientedBoundingBox obb)
{
CD_AxisAlignedBoundingBox aabb_New = new CD_AxisAlignedBoundingBox(Vector3.Zero, 0, 0, 0);

aabb_New.Centre.X += Vector3.Dot(obb.Position, GameConstants.WORLD_X_AXIS);
aabb_New.Centre.Y += Vector3.Dot(obb.Position, GameConstants.WORLD_Y_AXIS);
aabb_New.Centre.Z += Vector3.Dot(obb.Position, GameConstants.WORLD_Z_AXIS);

// Compute the projection interval radius of obb onto world x axis
float r_X = obb.Extents_HalfWidth.X * Math.Abs(Vector3.Dot(GameConstants.WORLD_X_AXIS, obb.Axis_X)) +
obb.Extents_HalfWidth.Y * Math.Abs(Vector3.Dot(GameConstants.WORLD_X_AXIS, obb.Axis_Y)) +
obb.Extents_HalfWidth.Z * Math.Abs(Vector3.Dot(GameConstants.WORLD_X_AXIS, obb.Axis_Z));

// Compute the projection interval radius of obb onto world y axis
float r_Y = obb.Extents_HalfWidth.X * Math.Abs(Vector3.Dot(GameConstants.WORLD_Y_AXIS, obb.Axis_X)) +
obb.Extents_HalfWidth.Y * Math.Abs(Vector3.Dot(GameConstants.WORLD_Y_AXIS, obb.Axis_Y)) +
obb.Extents_HalfWidth.Z * Math.Abs(Vector3.Dot(GameConstants.WORLD_Y_AXIS, obb.Axis_Z));

// Compute the projection interval radius of obb onto world z axis
float r_Z = obb.Extents_HalfWidth.X * Math.Abs(Vector3.Dot(GameConstants.WORLD_Z_AXIS, obb.Axis_X)) +
obb.Extents_HalfWidth.Y * Math.Abs(Vector3.Dot(GameConstants.WORLD_Z_AXIS, obb.Axis_Y)) +
obb.Extents_HalfWidth.Z * Math.Abs(Vector3.Dot(GameConstants.WORLD_Z_AXIS, obb.Axis_Z));

aabb_New.Extents = new Vector3(r_X, r_Y, r_Z);

return aabb_New;
}



I project the obb onto the world x,y,z axes and then obtain the tight fighting AABB from that.

Is this method sound, I have tried optimizing it as best as I could?

Share this post


Link to post
Share on other sites
That looks right - have you tried it?

It's not optimized though (if that matters). The optimizations come from the fact that each element of the input axis is either zero or one. If you do the math longhand, many of the calculations drop out, leaving you with simpler, faster code.

(Again, though, whether the gain in performance would matter or not depends entirely on the circumstances.)

Share this post


Link to post
Share on other sites
It works perfectly but the following two methods produce different results:

ComputeFromOBB() [as above]

and

ComputeFromRotationMatrix() [below]


public static CD_AxisAlignedBoundingBox ComputeFromRotationMatrix(Vector3 centre, float width, float height, float depth, Matrix rotation)
{
CD_AxisAlignedBoundingBox aabb_New = new CD_AxisAlignedBoundingBox(Vector3.Zero, 0, 0, 0);

aabb_New.Centre.X += Vector3.Dot(centre, GameConstants.WORLD_X_AXIS);
aabb_New.Centre.Y += Vector3.Dot(centre, GameConstants.WORLD_Y_AXIS);
aabb_New.Centre.Z += Vector3.Dot(centre, GameConstants.WORLD_Z_AXIS);

Vector3 x_Axis = new Vector3(rotation.M11, rotation.M12, rotation.M13);
Vector3 y_Axis = new Vector3(rotation.M21, rotation.M22, rotation.M23);
Vector3 z_Axis = new Vector3(rotation.M31, rotation.M32, rotation.M33);

width /= 2.0f;
height /= 2.0f;
depth /= 2.0f;

// Compute the projection interval radius of obb onto world x axis
float r_X = width * Math.Abs(Vector3.Dot(GameConstants.WORLD_X_AXIS, x_Axis)) +
height * Math.Abs(Vector3.Dot(GameConstants.WORLD_X_AXIS, y_Axis)) +
depth * Math.Abs(Vector3.Dot(GameConstants.WORLD_X_AXIS, z_Axis));

// Compute the projection interval radius of obb onto world y axis
float r_Y = width * Math.Abs(Vector3.Dot(GameConstants.WORLD_Y_AXIS, x_Axis)) +
height * Math.Abs(Vector3.Dot(GameConstants.WORLD_Y_AXIS, y_Axis)) +
depth * Math.Abs(Vector3.Dot(GameConstants.WORLD_Y_AXIS, z_Axis));

// Compute the projection interval radius of obb onto world z axis
float r_Z = width * Math.Abs(Vector3.Dot(GameConstants.WORLD_Z_AXIS, x_Axis)) +
height * Math.Abs(Vector3.Dot(GameConstants.WORLD_Z_AXIS, y_Axis)) +
depth * Math.Abs(Vector3.Dot(GameConstants.WORLD_Z_AXIS, z_Axis));

aabb_New.Extents = new Vector3(r_X, r_Y, r_Z);

Console.WriteLine("RotMethod " + x_Axis);

return aabb_New;
}



The problem is the rotation matrix.

When creating an OBB I use the following to set the orientation of the OBB:


Quaternion Orientation = Quaternion.Identity; // Orientation of OBB (Rotation matrix is derived from this)

.......

public CD_OrientedBoundingBox(Vector3 centre, float width, float height, float depth, Matrix rotation)
{
Quaternion additionalRot = Quaternion.CreateFromRotationMatrix(rotation);
Orientation *= additionalRot;
Rotation = Matrix.CreateFromQuaternion(additionalRot);

Centre = centre;
Extents = new Vector3(width / 2.0f, height / 2.0f, depth / 2.0f);
}



Now because the rotation matrix is derived from a Quaternion each time, the results differ drastically when compared to just using rotation as in the ComputeFromRotationMatrix().

So my question is this, is the rotation matrix still correct when computing the OBB this way, or is the ComputeFromRotationMatrix() method incorrect?

Thanks again.

Share this post


Link to post
Share on other sites

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