Advertisement Jump to content
Sign in to follow this  
cozzie

Understanding my AABB / OBB code

This topic is 1755 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

Hi,

 

Before I continue to implement collision detections etc. in my 3d engine, I'm trying to fully understand (and improve where possible) my code on handling AABB's and OBB's of my dynamic mesh instances and renderables. Keeping in mind that for now I want to support both OBB and worldspace AABB.

 

To explain this a bit more, here's the approach I'm doing with a few code snippets below.

 

INITIAL LOADING

For each mesh instance & renderable:

- create AABB in modelspace

- resulting in 10 vectors: 8 corners, size, and center

- setup OBB worldSpace corners (8) by multiplying the 8 AABB modelspace corners with worldMatrix

- setup OBB worldSpace center, by multiplying AABB modelspace center with worldMatrix

- OBBsize = AABB modelspace size

- setup/ calculate AABBworldsize, by finding (and substracting) max/min XYZ of 8 OBB corners

 

PER UPDATE

For each dynamic mesh instance & renderable:

- update OBB worldspace corners and center, by multiplying AABB corners and center with worldMatrix

- update AABBworldsize, by finding min/max XYZ of 8 OBB corners

 

And also for each dynamic mesh instance:

- check if childs (renderables) OBB exceeds parent (mesh instance) OBB, if so:

** update 8 OBB corners and size, by checking parent/child min/max XYZ, create 8 new OBB corners and OBBsize

Note: now OBBsize is in worldspace (was in modelSpace).

Therefore OBBsize is now multiplied by the worldMatrix of the meshinstance

 

 

The functional end result is as expected/ OK, but I 'feel' I'm doing some unnecessary steps to get there.

Any input is appreciated.

typedef struct BOUNDINGBOX
{
	D3DXVECTOR3 AABBmodelCenter;
	D3DXVECTOR3 AABBmodelSize;
	D3DXVECTOR3 AABBmodelCorners[8];

	D3DXVECTOR3 OBBsize;

	D3DXVECTOR3 OBBworldCenter;		// OBB in worldspace now
	D3DXVECTOR3 OBBworldCorners[8];
	
	D3DXVECTOR3 AABBworldSize;	// AABB in worldspace, uses P/N-vertex 

	bool		created;

	BOUNDINGBOX():created(false) { };
} BOUNDINGBOX;

// my culling functions

int CD3dcam::OBBInFrustum(const BOUNDINGBOX &pBoundingBox, const D3DXMATRIX &pWorldMatrix) const
{
	D3DXVECTOR3				mAx, mAy, mAz;
	int _result = 99;

	mAx = D3DXVECTOR3(pWorldMatrix._11, pWorldMatrix._12, pWorldMatrix._13);
	mAy = D3DXVECTOR3(pWorldMatrix._21, pWorldMatrix._22, pWorldMatrix._23);
	mAz = D3DXVECTOR3(pWorldMatrix._31, pWorldMatrix._32, pWorldMatrix._33);

	float d, s;

	for(int i=0;i<6;++i)
	{
		d = D3DXPlaneDotCoord(&mFrustumPlane[i], &pBoundingBox.OBBworldCenter);

		s = fabs	(D3DXVec3Dot(&mAx, &D3DXVECTOR3(mFrustumPlane[i].a, mFrustumPlane[i].b, mFrustumPlane[i].c)) * pBoundingBox.OBBsize.x / 2.0f) +
			fabs	(D3DXVec3Dot(&mAy, &D3DXVECTOR3(mFrustumPlane[i].a, mFrustumPlane[i].b, mFrustumPlane[i].c)) * pBoundingBox.OBBsize.y / 2.0f) +		// AABBsize
			fabs	(D3DXVec3Dot(&mAz, &D3DXVECTOR3(mFrustumPlane[i].a, mFrustumPlane[i].b, mFrustumPlane[i].c)) * pBoundingBox.OBBsize.z / 2.0f);

		if(d < -s) return OUTSIDE;
		if(d+ -s < 0) _result = INTERSECT;	
	}
	if(_result == INTERSECT) return INTERSECT;
	else return INSIDE;
}

int CD3dcam::AABBInFrustum(const BOUNDINGBOX &pBoundingBox) const
{
	D3DXVECTOR3	_pvtx, _nvtx;
	bool		intersect = false;
	float		dist;

	for(int i=0;i<6;++i)
	{
		// find the nearest and farthest point along normal direction
		_pvtx.x = pBoundingBox.OBBworldCenter.x + (pBoundingBox.AABBworldSize.x / 2.0f) * mFrustumPlaneSign[i].x;
		_pvtx.y = pBoundingBox.OBBworldCenter.y + (pBoundingBox.AABBworldSize.y / 2.0f) * mFrustumPlaneSign[i].y;
		_pvtx.z = pBoundingBox.OBBworldCenter.z + (pBoundingBox.AABBworldSize.z / 2.0f) * mFrustumPlaneSign[i].z;

		_nvtx.x = pBoundingBox.OBBworldCenter.x - (pBoundingBox.AABBworldSize.x / 2.0f) * mFrustumPlaneSign[i].x;
		_nvtx.y = pBoundingBox.OBBworldCenter.y - (pBoundingBox.AABBworldSize.y / 2.0f) * mFrustumPlaneSign[i].y;
		_nvtx.z = pBoundingBox.OBBworldCenter.z - (pBoundingBox.AABBworldSize.z / 2.0f) * mFrustumPlaneSign[i].z;

		// check positive vertex; further along the normal's direction
		dist = D3DXPlaneDotCoord(&mFrustumPlane[i], &_pvtx);
		if(dist < 0) return OUTSIDE;		// wrong side of plane, completely outside

		// check negative vertex; less far along the normal's direction
		dist = D3DXPlaneDotCoord(&mFrustumPlane[i], &_nvtx);
		if(dist < 0) intersect = true;
	}
	if(intersect) return INTERSECT;
	return INSIDE;
}

Nb.: I plan to keep doing the frustum checks in worldSpace (not move frustum to modelspace and do checks in modelspace)

Edited by cozzie

Share this post


Link to post
Share on other sites
Advertisement

Why are you using AABB and OBB? Are you using one for pre culling and the other for more fine culling?

 

You maybe able to just use one depending on what your objects are doing. Also if your shapes are not deforming then you shouldn't need to modify the OBB that much, just updates its position and rotation.

 

It seems you might be keeping a hierarchy of volumes. Depending on whats happening there you could make the hierarchy just be the AABB which are faster to compute the bounds of say the children and save the OBB for the last visibility test. And then your not having to recompute new OBB which are probably not optimal anymore.

Share this post


Link to post
Share on other sites
Thanks. I actually only update the OBB's for dynamic objects. But it made me think, I will try to find out how to eliminate the 2x 8 corners (aabb and obb) and go with center and size, this might work.

That way I only have to update it's position, using the world matrix combined with position for culling.

Share this post


Link to post
Share on other sites

this is actualy AABS, axix aligned bounding sphere. A very awesome thing your implementation should not miss, as objects should carry both, AABB and AABS information.

Share this post


Link to post
Share on other sites

I've decided to go for keeping the AABB modelspace and OBB corners.

Because in the end I also need AABB worldspace min and max for collision detection.

 

I've also managed to solve updating the parent AABB if a child's OBB exceeds the 'size' of the parent.

Although the result is fine and tested, it still feels a bit 'overkill'/ possibly unnecessary much effort.

 

I've pasted the function below, any input on how to to this more efficiently is appreciated.

/**************************************************************************************/
/***							UPDATE AABB PARENT									***/
/*** ==> usage: to update the AABB if another/ child AABB impacts the parent		***/
/*** ==> compares OBB's, transforms back to AABB and updates parent's AABB			***/
/**************************************************************************************/

bool UpdateAABBParent(BOUNDINGBOX *pParentBox, const D3DXMATRIX &matWorldParent, const BOUNDINGBOX &pChildBox)
{
	if(pParentBox == NULL) return false;

	// first find OBB MIN and MAX
	D3DXVECTOR3 parentOBBmin = pParentBox->OBBworldCorners[0];
	D3DXVECTOR3 parentOBBmax = pParentBox->OBBworldCorners[0];
	D3DXVECTOR3 childOBBmin = pChildBox.OBBworldCorners[0];
	D3DXVECTOR3 childOBBmax = pChildBox.OBBworldCorners[0];

	for(int vtx=0;vtx<8;++vtx)
	{
		// parent
		if(pParentBox->OBBworldCorners[vtx].x < parentOBBmin.x) parentOBBmin.x = pParentBox->OBBworldCorners[vtx].x;
		if(pParentBox->OBBworldCorners[vtx].y < parentOBBmin.y) parentOBBmin.y = pParentBox->OBBworldCorners[vtx].y;
		if(pParentBox->OBBworldCorners[vtx].z < parentOBBmin.z) parentOBBmin.z = pParentBox->OBBworldCorners[vtx].z;

		if(pParentBox->OBBworldCorners[vtx].x > parentOBBmax.x) parentOBBmax.x = pParentBox->OBBworldCorners[vtx].x;
		if(pParentBox->OBBworldCorners[vtx].y > parentOBBmax.y) parentOBBmax.y = pParentBox->OBBworldCorners[vtx].y;
		if(pParentBox->OBBworldCorners[vtx].z > parentOBBmax.z) parentOBBmax.z = pParentBox->OBBworldCorners[vtx].z;

		// child
		if(pChildBox.OBBworldCorners[vtx].x < childOBBmin.x) childOBBmin.x = pChildBox.OBBworldCorners[vtx].x;
		if(pChildBox.OBBworldCorners[vtx].y < childOBBmin.y) childOBBmin.y = pChildBox.OBBworldCorners[vtx].y;
		if(pChildBox.OBBworldCorners[vtx].z < childOBBmin.z) childOBBmin.z = pChildBox.OBBworldCorners[vtx].z;

		if(pChildBox.OBBworldCorners[vtx].x > childOBBmax.x) childOBBmax.x = pChildBox.OBBworldCorners[vtx].x;
		if(pChildBox.OBBworldCorners[vtx].y > childOBBmax.y) childOBBmax.y = pChildBox.OBBworldCorners[vtx].y;
		if(pChildBox.OBBworldCorners[vtx].z > childOBBmax.z) childOBBmax.z = pChildBox.OBBworldCorners[vtx].z;
	}
	
	// check if child 'exceeds' parent
	bool changed = false;
	D3DXVECTOR3 newOBBmin = parentOBBmin;
	D3DXVECTOR3 newOBBmax = parentOBBmax;

	if(childOBBmin.x < parentOBBmin.x) { newOBBmin.x = childOBBmin.x; changed = true;	};
	if(childOBBmin.y < parentOBBmin.y) { newOBBmin.y = childOBBmin.y; changed = true;	};
	if(childOBBmin.z < parentOBBmin.z) { newOBBmin.z = childOBBmin.z; changed = true;	};

	if(childOBBmax.x > parentOBBmax.x) { newOBBmax.x = childOBBmax.x; changed = true;	};
	if(childOBBmax.y > parentOBBmax.y) { newOBBmax.y = childOBBmax.y; changed = true;	};
	if(childOBBmax.z > parentOBBmax.z) { newOBBmax.z = childOBBmax.z; changed = true;	};

	if(changed)
	{
		// update OBB corners
		pParentBox->OBBworldCorners[0].x = newOBBmin.x;
		pParentBox->OBBworldCorners[0].y = newOBBmin.y;
		pParentBox->OBBworldCorners[0].z = newOBBmin.z;

		pParentBox->OBBworldCorners[1].x = newOBBmax.x;
		pParentBox->OBBworldCorners[1].y = newOBBmax.y;
		pParentBox->OBBworldCorners[1].z = newOBBmax.z;

		pParentBox->OBBworldCorners[2].x = newOBBmax.x;
		pParentBox->OBBworldCorners[2].y = newOBBmax.y;
		pParentBox->OBBworldCorners[2].z = newOBBmin.z;

		pParentBox->OBBworldCorners[3].x = newOBBmin.x;
		pParentBox->OBBworldCorners[3].y = newOBBmax.y;
		pParentBox->OBBworldCorners[3].z = newOBBmin.z;

		pParentBox->OBBworldCorners[4].x = newOBBmin.x;
		pParentBox->OBBworldCorners[4].y = newOBBmin.y;
		pParentBox->OBBworldCorners[4].z = newOBBmax.z;

		pParentBox->OBBworldCorners[5].x = newOBBmax.x;
		pParentBox->OBBworldCorners[5].y = newOBBmin.y;
		pParentBox->OBBworldCorners[5].z = newOBBmax.z;

		pParentBox->OBBworldCorners[6].x = newOBBmax.x;
		pParentBox->OBBworldCorners[6].y = newOBBmin.y;
		pParentBox->OBBworldCorners[6].z = newOBBmin.z;

		pParentBox->OBBworldCorners[7].x = newOBBmin.x;
		pParentBox->OBBworldCorners[7].y = newOBBmax.y;
		pParentBox->OBBworldCorners[7].z = newOBBmax.z;

		D3DXMATRIX inverseWorld;
		D3DXMatrixInverse(&inverseWorld, NULL, &matWorldParent);

		for(size_t i=0;i<8;++i) D3DXVec3TransformCoord(&pParentBox->AABBmodelCorners[i], &pParentBox->OBBworldCorners[i], &inverseWorld);

		D3DXVECTOR3 AABBmin, AABBmax;	
		AABBmin.x = pParentBox->AABBmodelCorners[0].x;
		AABBmin.y = pParentBox->AABBmodelCorners[0].y;
		AABBmin.z = pParentBox->AABBmodelCorners[0].z;

		AABBmax.x = pParentBox->AABBmodelCorners[0].x;
		AABBmax.y = pParentBox->AABBmodelCorners[0].y;
		AABBmax.z = pParentBox->AABBmodelCorners[0].z;

		for(size_t vc=0;vc<8;++vc)
		{
			if(pParentBox->AABBmodelCorners[vc].x < AABBmin.x) AABBmin.x = pParentBox->AABBmodelCorners[vc].x;
			if(pParentBox->AABBmodelCorners[vc].x > AABBmax.x) AABBmax.x = pParentBox->AABBmodelCorners[vc].x;

			if(pParentBox->AABBmodelCorners[vc].y < AABBmin.y) AABBmin.y = pParentBox->AABBmodelCorners[vc].y;
			if(pParentBox->AABBmodelCorners[vc].y > AABBmax.y) AABBmax.y = pParentBox->AABBmodelCorners[vc].y;

			if(pParentBox->AABBmodelCorners[vc].z < AABBmin.z) AABBmin.z = pParentBox->AABBmodelCorners[vc].z;
			if(pParentBox->AABBmodelCorners[vc].z > AABBmax.z) AABBmax.z = pParentBox->AABBmodelCorners[vc].z;
		}
		pParentBox->AABBmodelSize = AABBmax - AABBmin;
		pParentBox->AABBmodelCenter = AABBmax - (pParentBox->AABBmodelSize / 2.0f);

		return true;
	}
	else return false;
}

Note: ofcourse this function is only called when renderables are dynamic and moved/rotated and or scaled.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!