Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
30 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to Math and Physics

Strange rotation sympton, aabb extents (with video)

Started by
26 comments, last by cozzie 11 years ago

Hi,

I have a strange problem with calculating my AABB extents, min and max.

For testing I places 2 small cubes in my scene, which constantly take over the AABB's min and max vertices as a world position.


This perfectly illustrates the sympton.

Only with 90, 180, 270 or 360 degrees rotation the extents match the real min and max points of the rotating object.


Here's the video:

">

Below are the related code parts.

This is what I do:

- calculate the AABB initally with untransformed, not rotated verticies

- the 8 corners are stored in a 'base' vertex array

- every frame where the object is moved or rotated, I transform the 8 base vertices with the new matrix

- then I find the min/ max extents to use for AABB culling

Can someone help me out?


// initial creation of the AABB

void CreateAABB(TVERTEX *pVtxArray, DWORD pStart, DWORD pNr, BOUNDINGBOX *pBox)
{
	// MIN and MAX vertices
	pBox->min.x = pVtxArray[pStart].position.x;
	pBox->min.y = pVtxArray[pStart].position.y;
	pBox->min.z = pVtxArray[pStart].position.z;

	pBox->max.x = pVtxArray[pStart].position.x;
	pBox->max.y = pVtxArray[pStart].position.y;
	pBox->max.z = pVtxArray[pStart].position.z;

	for(DWORD vc=pStart;vc<pStart+pNr;++vc)
	{
		if(pVtxArray[vc].position.x < pBox->min.x) pBox->min.x = pVtxArray[vc].position.x;
		if(pVtxArray[vc].position.x > pBox->max.x) pBox->max.x = pVtxArray[vc].position.x;

		if(pVtxArray[vc].position.y < pBox->min.y) pBox->min.y = pVtxArray[vc].position.y;
		if(pVtxArray[vc].position.y > pBox->max.y) pBox->max.y = pVtxArray[vc].position.y;

		if(pVtxArray[vc].position.z < pBox->min.z) pBox->min.z = pVtxArray[vc].position.z;
		if(pVtxArray[vc].position.z > pBox->max.z) pBox->max.z = pVtxArray[vc].position.z;
	}
	
	// FULL 8 vertices of the AABB		
	pBox->boxArrayBase[0].x = pBox->min.x;
	pBox->boxArrayBase[0].y = pBox->min.y;
	pBox->boxArrayBase[0].z = pBox->min.z;

	pBox->boxArrayBase[1].x = pBox->max.x;
	pBox->boxArrayBase[1].y = pBox->max.y;
	pBox->boxArrayBase[1].z = pBox->max.z;

	pBox->boxArrayBase[2].x = pBox->max.x;
	pBox->boxArrayBase[2].y = pBox->max.y;
	pBox->boxArrayBase[2].z = pBox->min.z;

	pBox->boxArrayBase[3].x = pBox->min.x;
	pBox->boxArrayBase[3].y = pBox->max.y;
	pBox->boxArrayBase[3].z = pBox->min.z;

	pBox->boxArrayBase[4].x = pBox->min.x;
	pBox->boxArrayBase[4].y = pBox->min.y;
	pBox->boxArrayBase[4].z = pBox->max.z;

	pBox->boxArrayBase[5].x = pBox->max.x;
	pBox->boxArrayBase[5].y = pBox->min.y;
	pBox->boxArrayBase[5].z = pBox->max.z;

	pBox->boxArrayBase[6].x = pBox->max.x;
	pBox->boxArrayBase[6].y = pBox->min.y;
	pBox->boxArrayBase[6].z = pBox->min.z;

	pBox->boxArrayBase[7].x = pBox->min.x;
	pBox->boxArrayBase[7].y = pBox->max.y;
	pBox->boxArrayBase[7].z = pBox->max.z;

	for(int i=0;i<8;++i) pBox->boxArray = pBox->boxArrayBase;
	pBox->created = true;
}

// updating the AABB

bool UpdateAABB(BOUNDINGBOX *pBox)
{
	if(!pBox->created) return false;

//	8 AABB corners need to be transformed by the latest world matrix
//	now find the 2 extents

	pBox->min.x = pBox->boxArray[0].x;
	pBox->min.y = pBox->boxArray[0].y;
	pBox->min.z = pBox->boxArray[0].z;

	pBox->max.x = pBox->boxArray[0].x;
	pBox->max.y = pBox->boxArray[0].y;
	pBox->max.z = pBox->boxArray[0].z;

	for(int vc=0;vc<8;++vc)
	{
		if(pBox->boxArray[vc].x < pBox->min.x) pBox->min.x = pBox->boxArray[vc].x;
		if(pBox->boxArray[vc].x > pBox->max.x) pBox->max.x = pBox->boxArray[vc].x;

		if(pBox->boxArray[vc].y < pBox->min.y) pBox->min.y = pBox->boxArray[vc].y;
		if(pBox->boxArray[vc].y > pBox->max.y) pBox->max.y = pBox->boxArray[vc].y;

		if(pBox->boxArray[vc].z < pBox->min.z) pBox->min.z = pBox->boxArray[vc].z;
		if(pBox->boxArray[vc].z > pBox->max.z) pBox->max.z = pBox->boxArray[vc].z;
	}
	return true;
}

// update the world matrix

bool CD3dmeshInst::UpdateWorldMatrix()
{
	if(!mDynamic) return false;
	if(!mIsMoved && !mIsRotated && !mIsScaled) return false;

	if(mIsMoved)
	{
		D3DXMatrixIdentity(&mMatTranslate);
		D3DXMatrixTranslation(&mMatTranslate, mWorldPos.x, mWorldPos.y, mWorldPos.z);
	}
	if(mIsRotated)
	{
		D3DXMatrixIdentity(&mMatRotateX);
		D3DXMatrixRotationX(&mMatRotateX, D3DXToRadian(mRot.x));
		D3DXMatrixIdentity(&mMatRotateY);
		D3DXMatrixRotationY(&mMatRotateY, D3DXToRadian(mRot.y));
		D3DXMatrixIdentity(&mMatRotateZ);
		D3DXMatrixRotationZ(&mMatRotateZ, D3DXToRadian(mRot.z));
	}
	if(mScale)
	{
		D3DXMatrixIdentity(&mMatScale);
		D3DXMatrixScaling(&mMatScale, mScale, mScale, mScale);
	}

	mMatWorld = (D3DXMATRIXA16)(mMatScale*mMatRotateX*mMatRotateY*mMatRotateZ*mMatTranslate);

	D3DXMatrixInverse(&mMatWorldInv, NULL, &mMatWorld);
	D3DXMatrixTranspose(&mMatWorldInvTransp, &mMatWorldInv);
	return true;
}

// update the bounding volume based on new world matrix

bool CD3dmeshInst::UpdateBVWorldSpace()
{
	// WORLD MATRIX should be already updated

	if(!mDynamic) return false;

	// FULL mesh
	if(mIsMoved || mIsRotated || mIsScaled)			// TO BE SPECIFIED LATER
	{
		mBoundingRadius = mBoundingRadiusBase * mScale;
	
		for(int i=0;i<8;++i) D3DXVec3TransformCoord(&mBoundingBox.boxArray, &mBoundingBox.boxArrayBase, &mMatWorld);	
		
		if(!UpdateAABB(&mBoundingBox)) return false;

	}
	return true;
}

Rotation, translation etc. of the mesh all work fine, I use the same updated mMatWorld matrix for rendering the mesh through my shaders without problems. Maybe something wrong with updating/ transforming the boundingbox corners/ extents? radians and degrees?

Help );

Crealysm game & engine development: http://www.crealysm.com

Looking for a passionate, disciplined and structured producer? PM me

Advertisement

Video looks correct for a local AABB to world space AABB conversion, and the code looks correct. If you draw lines to define the AABB, you'll quickly that it matches the min/max extents just fine. I suspect your confusion is because you have created a world space AABB, but were expecting to see an OBB rather than the AABB you're getting back.

Hi rob.

Don't know if I understand you correct. I try to update the world space AABB when a object is rotated or moved, to achieve that the min/ max extents of the bounding box stay the same relative to the object itself. Maybe that's an OBB then :)

I understand what you mean that the extents you see in the demo/ video are the extents which will count for any rotation (sort of max. independent of rotation).

Do you know how I can achieve that the extents are matched with the rotation?

I thought I would do that by transforming the 8 corners from local space into worldspace, using the World Matrix where I both applied transformation (pos) and rotations, which should bring me to new world space 8 corners (including rotation). Or am i overseeing something?

Crealysm game & engine development: http://www.crealysm.com

Looking for a passionate, disciplined and structured producer? PM me

Addition;

Here's a static image where I rotated the object 30 degrees on the Y-axis.

Showing the AABB extents, this means that's is culled quite a bit later then going out of the frustum (which I try to get more accurate).

It's a bit confusing because I understand that the extents are correct when I want rotation independence.

static.jpg

Here's the same situation, where the object is not rotated/ Y rot = 0

static2.jpg

Crealysm game & engine development: http://www.crealysm.com

Looking for a passionate, disciplined and structured producer? PM me

Don't know if I understand you correct. I try to update the world space AABB when a object is rotated or moved, to achieve that the min/ max extents of the bounding box stay the same relative to the object itself. Maybe that's an OBB then smile.png


Yup, that's an OBB.

There is a simple way of doing this, although for some reason, most people overcomplicate things. To construct an OBB from an AABB + transform, do this:


// just because it explains how I think about the world....
struct Matrix
{
  Vec3 x;
  Vec3 y;
  Vec3 z;
  Vec3 w;
};
 
// 'inputs' to your function...
const Vec3 minBound; //< AABB Points in local space (w == 1)
const Vec3 maxBound;
const Matrix worldTransform; //< of your mesh
 
// compute the extents. Note this is a vector quantity, not a Point! (w == 0)
Vec3 extents = maxBound - minBound;
 
// and OBB is just a matrix in effect.
Matrix OBB;

// transform minBound into world space.
OBB.w = minBound * worldTransform;
 
// scale transform axes by extents.
OBB.x = worldTransform.x * extents.x;
OBB.y = worldTransform.y * extents.y;
OBB.z = worldTransform.z * extents.z;
 
// Ok. At this point, you can test this worked by drawing a single unit length cube ([0,0,0] to [1,1,1]) using 
// OBB as the transform. It should match your local space OBB exactly. If not, you've got a bug 
// (or my tired eyes have got the maths wrong)

// Storing an OBB like this is however useless for most people.

// So, invert the OBB....
OBB = invert(OBB);

// now, given some world space point:
Vec3 P;
 
// transform it by the matrix
Vec3 P1 = P * OBB;
 
// is it inside the OBB?
if( P1.x <= 1.0f && P1.x >= 0 && P1.y <= 1.0f && P1.y >= 0 && P1.z <= 1.0f && P1.z >= 0 )
{
  // inside the unit lengthed cube, therefore it's inside the OBB
}


ray intersections and the like, can simply be performed against a unit lengthed cube ([0,0,0] to [1,1,1]), by transforming the Ray/Frustum/Whatever into the local space of the box. You could modify the code to center the OBB on the center of the AABB (and test against the cube [-0.5,-0.5,-0.5] to [0.5,0.5,0.5]), but that will just come down to personal preference. Some people prefer having a Min/Max bound along with the transform, but I can't see the point in that personally.... (well, i suppose it would reduce the data required to just the same data that you're already storing, the local space AABB bounds + the world matrix)

Thanks Rob. As soon as I understand it, it'll solve my problem :)

Just kidding.

I'm trying to understand it, and tried to write it out step by step.

What I do now, initially:

1 - find min and max vertices(bounds?) in local space, no rotation etc.

2 - define 8 corners based on local space min and max vertices (save in 'base array')

updating:

3 - update worldmatrix of the mesh

4 - transform the 8 base vertices (corners) with world matrix of the mesh.

Now the 8 corners are in world space. Is this where I have then created an OBB?

5 - from these 8 corners find min and max, so I have updated min/max vertices (bounds?)

From min and max vertices I find the center en size vertices

6 - I check with the frustum planes using center and size vertices

So now I'm probably back to checking an AABB against frustum plains, or not? (where in step 5 I had an OBB)

If the above assumptions are correct, then my change should probably be after step 4.

If it possible that I keep using the checking P and N vertex with the frustum planes, where P/N vertices are following the planes normal direction?

If so, my change would be in step 5, in creating the correct min and max vertices of the OBB.

Sorry for the maybe simple questions, I'm really trying to understand.

Crealysm game & engine development: http://www.crealysm.com

Looking for a passionate, disciplined and structured producer? PM me

You are creating an AABB. To create an OBB, do the same process for a box where the min bound is [0,0,0], and the max bound is [1,1,1]. Once created, this doesn't need to change. Using a matrix (centered at [0,0,0]), you can use scale to change the size, and simply rotate and translate to position and orient the box. Any other object you want to test against the OBB (such as a frustum) can be transformed into the local space of the AABB (the one between 0,0,0 and 1,1,1) by transforming it by the inverse of your OBB transform. You'd need to figure out how to transform a plane by a matrix (which handles the 6 planes of the frustum), or transform the frustum point and regenerate (which is less efficient), but either way it's not too complicated. At that point, if you have code for an AABB/Frustum test, it will work without modification. The advantage is that the frustum is now in the local space of the mesh data, which means any further testing you may need, it pretty trivial (without needing to transform the vertices for example)

If after step 4 you generated plane equations from those points, you would have an OBB (in world space), however that makes the frustum tests somewhat more complicated. The way i suggested doesn't need step 4 (since the points are always the same, as are the 6 planes of the box). I'd probably start with OBB/point, OBB/ray, before moving onto OBB/frustum to be honest - it'll be much easier to get your head around.

You can cull the OBB directly against the frustum without transforming anything.

If the box centre is c, the box axes are ax, ay, az, and the sizes on each axis are sx, sy, sz, then:

d = dot(c, plane)
s = abs(dot(ax, plane)) * sx + abs(dot(ay, plane)) * sy + abs(dot(az, plane)) * sz

If d > s not culled
If d < -s culled
Otherwise intersects.

Thanks both. I think I'm getting it. For for being bit 'slow' on this subject.

I thought about it and come to the following approach:

Initial

- create 8 corners AABB from original vertices (untransformed, not rotated)

- find min, max, center and size vertices

Updating (after rotating/moving etc.)

- transform the 8 original (AABB) corners with world matrix (rotate/translate)

- update min, max, center and size vertices

Check OBB against frustum:

- go through all 6 planes

- d = dot(center, plane)

- s = abs(dot(ax, plane)) * size.x + abs(dot(ay, plane)) * size.y + abs(dot(az, plane)) * size.z

- if d > s inside frustum (stop checking if true for 1 plane)

- if d < -s outside frustum

There's one thing I'm not sure about yet, how do I get ax/ay/az, I assume I need to use my world matrix for this.

Which in this case is an endresult of the scale, rotation and translation matrices.

If I'm overseeing something, any comments are really appreciated.

Crealysm game & engine development: http://www.crealysm.com

Looking for a passionate, disciplined and structured producer? PM me

The box centre is translated by the world matrix. The box size is the size in model coordinates and does not change. ax, ay and az come straight out of the world matrix. The bounding box vertices are not used in the method I described, nor are min and max.

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
AliAbdulKareem
Understanding the wavy-like shape in alpha-testing magnification for text rendering Graphics and GPU Programming
Advertisement

Recommended Tutorials

GameDev.net
How to nurture a holistic, proactive, approach to technology problem-solving Networking and Multiplayer
Myopic Rhino
The P5 Basics, and the New Profiling Registers General and Gameplay Programming
gdarchive
How to Make Accurate Time Estimates Production and Management
Myopic Rhino
Paris GDC Highlights Event Coverage
mrluisp
Simple C++ Event Handling General and Gameplay Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top