culling, renderables and scaling

Started by
21 comments, last by cozzie 10 years ago

Implemented with succes, from the point of view of the result that is :)

LSpiro (and others); any feedback is appreciated.


bool CD3dmeshInst::UpdateBVWorldSpace()
{
	// WORLD MATRIX should be already updated
	if(!mDynamic) return false;

	// FULL mesh
	if(mIsMoved || mIsRotated || mIsScaled)
	{
		// Update bounding sphere
		D3DXVec3TransformCoord(&mSphereCenterWorldspace, &mSphereCenterModelspace, &mMatWorld);
		mSphereBoundingRadius = mSphereBoundingRadiusBase * mScale;

		// Update OBB - stays unchanged if no renderables 'exceed'
		for(int i=0;i<8;++i) D3DXVec3TransformCoord(&mBoundingBox.OBBcorners[i], &mBoundingBox.AABBcorners[i], &mMatWorld);
		UpdateAABBWorld(&mBoundingBox);
		
		D3DXVec3TransformCoord(&mBoundingBox.OBBcenter, &mBoundingBox.AABBcenter, &mMatWorld);

		// Update bounding volumes of all renderables + update Bounding Volume of parent/ instance
		for(size_t obj=0;obj<GetNrRenderables();++obj)
		{
			auto &renderable = mRenderables[obj];
			renderable.UpdateBVWorldSpace();

			if(renderable.GetDynamic())
			{
				// UPDATE sphere radius is needed
				float dist = CoordToCoordDist(renderable.GetSphereCenterWorld(), mSphereCenterWorldspace);
				if(dist + renderable.GetSphereBoundingRadius() > mSphereBoundingRadius)
					mSphereBoundingRadius = dist + renderable.GetSphereBoundingRadius();

				// Update OBB and AABB if needed
				if(UpdateOBB(&mBoundingBox, renderable.GetBoundingBox()))
				{
					UpdateAABBWorld(&mBoundingBox);
				}
			}
		}
	}
	return true;
}

// updating an OBB if needed

/**************************************************************************************/
/***								UPDATE OBB										***/
/*** ==> usage: to update the OBB if another/ child impacts the OBB 				***/
/*** ==> compares parent and child OBB and updates parent if child exceeds parent	***/
/**************************************************************************************/

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

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

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

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

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

		if(pChildBox.OBBcorners[vtx].x > childOBBmax.x) childOBBmax.x = pChildBox.OBBcorners[vtx].x;
		if(pChildBox.OBBcorners[vtx].y > childOBBmax.y) childOBBmax.y = pChildBox.OBBcorners[vtx].y;
		if(pChildBox.OBBcorners[vtx].z > childOBBmax.z) childOBBmax.z = pChildBox.OBBcorners[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->OBBcorners[0].x = newOBBmin.x;
		pParentBox->OBBcorners[0].y = newOBBmin.y;
		pParentBox->OBBcorners[0].z = newOBBmin.z;

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

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

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

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

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

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

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

		pParentBox->OBBsize.x = newOBBmax.x - newOBBmin.x;
		pParentBox->OBBsize.y = newOBBmax.y - newOBBmin.y;
		pParentBox->OBBsize.z = newOBBmax.z - newOBBmin.z;

		pParentBox->OBBcenter = newOBBmax - (pParentBox->OBBsize / 2.0f);
		return true;
	}
	return false;
}

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

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

Advertisement
I was optimizing UpdateOBB() when I realized you store your OBB’s as 8 corners.
A bounding box is not (ever) stored as 8 corners.
Store it as 3 axes with non-normalized length values and a center point.
If maintaining and working with an OBB is too complex, use an AABB instead.


L. Spiro

I restore Nintendo 64 video-game OST’s into HD! https://www.youtube.com/channel/UCCtX_wedtZ5BoyQBXEhnVZw/playlists?view=1&sort=lad&flow=grid

Thanks LSpiro.

Here's a bit more background on what I do;

- per mesh instance (parent) and renderable I keep track of an OBB with 8 corners + X/Y/Z size AND of an AABB in worldspace.

(below the code I use)

- my camera class can cull either a point, a sphere with radius, an OBB or an AABB in worldspace

(below also the code)

I actually do that you say when I cull an OBB against the frustum, but my definitions are a bit confusing. I use the 8 'OBB' corners to calculate the AABB in worldspace.
If you have some advice on where my definitions are off and how to clean it up a bit, would be very appreciated. I want to keep the availability of checking against an OBB and AABB (world) and keep track of both of them (per renderable and mesh instance).


/**************************************************************************************/
/***								CREATE AABB										***/
/*** ==> usage: after meshinstance loading, before rendering						***/
/*** ==> creates AABB in modelspace, untransformed. corners, center etc.- INITAL	***/
/**************************************************************************************/

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

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

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

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

		if(pVtxArray[vc].position.z < pBox->AABBmin.z) pBox->AABBmin.z = pVtxArray[vc].position.z;
		if(pVtxArray[vc].position.z > pBox->AABBmax.z) pBox->AABBmax.z = pVtxArray[vc].position.z;
	}

	pBox->AABBsize.x = pBox->AABBmax.x - pBox->AABBmin.x;
	pBox->AABBsize.y = pBox->AABBmax.y - pBox->AABBmin.y;
	pBox->AABBsize.z = pBox->AABBmax.z - pBox->AABBmin.z;

	pBox->AABBcenter = pBox->AABBmax - (pBox->AABBsize / 2.0f);

	// FULL 8 vertices of the AABB - modelspace
	pBox->AABBcorners[0].x = pBox->AABBmin.x;
	pBox->AABBcorners[0].y = pBox->AABBmin.y;
	pBox->AABBcorners[0].z = pBox->AABBmin.z;

	pBox->AABBcorners[1].x = pBox->AABBmax.x;
	pBox->AABBcorners[1].y = pBox->AABBmax.y;
	pBox->AABBcorners[1].z = pBox->AABBmax.z;

	pBox->AABBcorners[2].x = pBox->AABBmax.x;
	pBox->AABBcorners[2].y = pBox->AABBmax.y;
	pBox->AABBcorners[2].z = pBox->AABBmin.z;

	pBox->AABBcorners[3].x = pBox->AABBmin.x;
	pBox->AABBcorners[3].y = pBox->AABBmax.y;
	pBox->AABBcorners[3].z = pBox->AABBmin.z;

	pBox->AABBcorners[4].x = pBox->AABBmin.x;
	pBox->AABBcorners[4].y = pBox->AABBmin.y;
	pBox->AABBcorners[4].z = pBox->AABBmax.z;

	pBox->AABBcorners[5].x = pBox->AABBmax.x;
	pBox->AABBcorners[5].y = pBox->AABBmin.y;
	pBox->AABBcorners[5].z = pBox->AABBmax.z;

	pBox->AABBcorners[6].x = pBox->AABBmax.x;
	pBox->AABBcorners[6].y = pBox->AABBmin.y;
	pBox->AABBcorners[6].z = pBox->AABBmin.z;

	pBox->AABBcorners[7].x = pBox->AABBmin.x;
	pBox->AABBcorners[7].y = pBox->AABBmax.y;
	pBox->AABBcorners[7].z = pBox->AABBmax.z;

	pBox->created = true;
}

// OBB CORNERS = AABB CORNERS * WORLD MATRIX OF MESH/ RENDERABLE

/**************************************************************************************/
/***								UPDATE AABB WORLD								***/
/*** ==> usage: when updating the bounding volume AABB in worldpace					***/
/*** ==> uses OBB corners to find min max and size to define AABB in worldspace		***/
/**************************************************************************************/

bool UpdateAABBWorld(BOUNDINGBOX *pBox)
{
	if(pBox == NULL) return false;

	// MIN and MAX vertices - modelspace
	pBox->AABBworldmin.x = pBox->OBBcorners[0].x;
	pBox->AABBworldmin.y = pBox->OBBcorners[0].y;
	pBox->AABBworldmin.z = pBox->OBBcorners[0].z;

	pBox->AABBworldmax.x = pBox->OBBcorners[0].x;
	pBox->AABBworldmax.y = pBox->OBBcorners[0].y;
	pBox->AABBworldmax.z = pBox->OBBcorners[0].z;

	for(int j=0;j<8;++j)
	{
		if(pBox->OBBcorners[j].x < pBox->AABBworldmin.x) pBox->AABBworldmin.x = pBox->OBBcorners[j].x;
		if(pBox->OBBcorners[j].x > pBox->AABBworldmax.x) pBox->AABBworldmax.x = pBox->OBBcorners[j].x;

		if(pBox->OBBcorners[j].y < pBox->AABBworldmin.y) pBox->AABBworldmin.y = pBox->OBBcorners[j].y;
		if(pBox->OBBcorners[j].y > pBox->AABBworldmax.y) pBox->AABBworldmax.y = pBox->OBBcorners[j].y;

		if(pBox->OBBcorners[j].z < pBox->AABBworldmin.z) pBox->AABBworldmin.z = pBox->OBBcorners[j].z;
		if(pBox->OBBcorners[j].z > pBox->AABBworldmax.z) pBox->AABBworldmax.z = pBox->OBBcorners[j].z;
	}
	pBox->AABBworldsize = pBox->AABBworldmax - pBox->AABBworldmin;
	return true;
}

// CULLING FUNCTIONS OF CAMERA CLASS

/**************************************************************************************/
/***									OBB IN FRUSTUM 						  CONST	***/
/*** ==> usage: before rendering, in scenegraph										***/
/*** ==> checks a OBB against the current frustum planes							***/
/**************************************************************************************/

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.OBBcenter);

		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) +
			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;
}

/**************************************************************************************/
/***								AABB IN FRUSTUM 						  CONST	***/
/*** ==> usage: before rendering, in scenegraph										***/
/*** ==> checks a AABB in worldspace against frustum planes, using pos/neg vertex	***/
/**************************************************************************************/

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.OBBcenter.x + (pBoundingBox.AABBworldsize.x / 2.0f) * mFrustumPlaneSign[i].x;
		_pvtx.y = pBoundingBox.OBBcenter.y + (pBoundingBox.AABBworldsize.y / 2.0f) * mFrustumPlaneSign[i].y;
		_pvtx.z = pBoundingBox.OBBcenter.z + (pBoundingBox.AABBworldsize.z / 2.0f) * mFrustumPlaneSign[i].z;

		_nvtx.x = pBoundingBox.OBBcenter.x - (pBoundingBox.AABBworldsize.x / 2.0f) * mFrustumPlaneSign[i].x;
		_nvtx.y = pBoundingBox.OBBcenter.y - (pBoundingBox.AABBworldsize.y / 2.0f) * mFrustumPlaneSign[i].y;
		_nvtx.z = pBoundingBox.OBBcenter.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;
}


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

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

Addition:


typedef struct BOUNDINGBOX
{
	D3DXVECTOR3 AABBmin;		// AABB in modelspace
	D3DXVECTOR3 AABBmax;
	D3DXVECTOR3 AABBcenter;
	D3DXVECTOR3 AABBsize;
	D3DXVECTOR3 AABBcorners[8];

	D3DXVECTOR3 OBBcenter;		// OBB in worldspace now
	D3DXVECTOR3 OBBsize;
	D3DXVECTOR3 OBBcorners[8];
	
	D3DXVECTOR3 AABBworldmin;	// AABB in worldspace, P/N-vertex now stored in CD3dcam class
	D3DXVECTOR3 AABBworldmax;
	D3DXVECTOR3 AABBworldsize;

	bool		created;

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

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

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

304bytes for AABB.

Yes, for now that's the case because I want support both obb and aabb. Maybe I could decrease the bytes a bit by doing some calculations in the obb/aabb check functions itself rather then during updating. Is that what you implicitly meant? :)

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

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

Yes, for now that's the case because I want support both obb and aabb. Maybe I could decrease the bytes a bit by doing some calculations in the obb/aabb check functions itself rather then during updating. Is that what you implicitly meant? smile.png

Everything more than 24bytes is wasting. I support only OBB's by doing frustum culling at object space and I only store static mesh AABB at once(not per instance). Memory usage and bandwith is minimal but frustum culling is very accurate and fast.

OK, I'm not sure if I'd make it with 24bytes for both the obb and aabb :)

Can you explain a bit more on what you mean;

- do you only have a OBB on 'mesh instance' level? (both static and dynamic)

- and on renderable level only a aabb, also for collisions?

(not sure what your/ the definition of object space is)

I understand that an improvement would be, that I just have a AABB (worldspace) for static mesh instances and renderables. Without the memory wasting this is exactly what I do, I only update the bounding volumes for dynamic mesh instances (defined per renderable). It feels a bit like a waste to define 2 structs/classes; one for dynamic boundingbox and one for static (just to save the bytes).

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

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

For each mesh that I load I have calculated also AABB in that space where its modelled. I never transform these to anywhere and there is just single AABB per mesh.

When I do frustum culling I have viewProjection matrix, mesh static AABB and object matrix. First I calculate modelViewProjection matrix and use that to extract frustum planes. This will give me frustum that is defined in object space so I basically do OBB vs frustum culling.


bool static extentSignedTest(const Vector4f& p, const Vector3f& center, const Vector3f& extent)
{
        return (dot(Vector3(p), center) + dot(abs(Vector3(p)), extent) < -p.w);
}
 
bool static isAABBInFrustumReference (const AABB& box, const Matrix44& frustumMatrix)
{                      
        const Vector4f  rowX                    = frustumMatrix.getRow(0);
        const Vector4f  rowY                    = frustumMatrix.getRow(1);
        const Vector4f  rowZ                    = frustumMatrix.getRow(2);
        const Vector4f  rowW                    = frustumMatrix.getRow(3);
       
        const Vector3f& center =  box.getCenter();
        const Vector3f& extent =  box.getExtents();
 
        // Left and right planes              
        if (extentSignedTest(rowW + rowX, center, extent))
                return false;
 
        if (extentSignedTest(rowW - rowX, center, extent))
                return false;
 
        // Bottom and top planes
        if (extentSignedTest(rowW + rowY, center, extent))
                return false;
 
        if (extentSignedTest(rowW - rowY, center, extent))
                return false;
       
        // Near and far planes
        if (extentSignedTest(rowW + rowZ, center, extent))
                return false;
 
        if (extentSignedTest(rowW - rowZ, center, extent))
                return false;
 
        return true;
}

Ah ok, I get it. You don't transform the AABB to worldspace/ an OBB using it's world matrix, you do it the other way around. Frustum to modelspace.

That explains why you need a lot less vector3 per mesh / instance / renderable.

On the performance side I'm not sure if there's much benefit, because with both approaches you have to go from one space to another, for the object OR for the frustum.

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

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

This topic is closed to new replies.

Advertisement