• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
cozzie

culling, renderables and scaling

22 posts in this topic

Hi,

Happy as I am having renderables implemented with success (render per renderable instead of whole mesh instances), I've ran into a challenge/ question. My situation is the following:

 

- a mesh is loaded

- several instances of the mesh are created

- each mesh instance consists of 'x' renderables

- the 'parent': mesh instance has a world matrix

- each renderable has a transformation matrix

(it's worldmatrix = local transform * parent world matrix)

- when culling I check if the mesh instance is inside the frustum (simple sphere check)

- if not, all renderables are not visible, if so, cull the individual renderables

 

This all works fine, until I scale one or more individual renderables, up to an amount where the bounding radius of a renderable is larger then the radius of it's parent (whole mesh instance).

 

Although I'm not sure if this scenario is realistic, I'd like to have my engine flexible smile.png

 

The result now is that the parent might be  outside the frustum and therefor renderables which might be inside (because of their radius), not checked and marked !visible.

 

I've thought of a few solutions:

1 - simply always cull all renderables (don't cull based on full mesh instance)

2 - update the bounding radius of the parent (mesh instance) based on checking the max radius of all it's renderables

3 - assume that this situation is not likely to occur and don't change anything

 

What solution would go for? Or might you have a 4th solution?

(all of the above ofcourse only goes for dynamic meshes, static meshes are no issue)

Any input is appreciated.

Edited by cozzie
0

Share this post


Link to post
Share on other sites

Well, generally if the parent bounds all the children, if the children get bigger, the parent sill needs to bound the children, so an update to the parent is required.

So you might

- do a pass over the objects, and update transforms. If child transforms, scale, rotate (maybe not rotate with spheres, but aabbs ) or translate, then the parent bound is potentially invalidated

- do a pass that transforms a unit bound, or recalc some how, for each object, any parents bound the updated child bounds

- do culling

- draw

2

Share this post


Link to post
Share on other sites
Thanks. I thought about what you said and will try the following:
- my mesh instance function which updates the world matrix, calls an update function for the transformation per renderable
- I will let that function of my renderable class return if something is changed, and if so, update the parent. Maybe I could even let it returns the bounding radius so I can check if it's larger then the mesh instance radius, if so, adapt that one
0

Share this post


Link to post
Share on other sites

- a mesh is loaded
- several instances of the mesh are created
- each mesh instance consists of 'x' renderables
- the 'parent': mesh instance has a world matrix
- each renderable has a transformation matrix
(it's worldmatrix = local transform * parent world matrix)
- when culling I check if the mesh instance is inside the frustum (simple sphere check)
- if not, all renderables are not visible, if so, cull the individual renderables

So far this is the correct process, but you can gain a lot of performance by not culling the individual renderables if the parent instance is entirely inside the frustum. While there will be objects partially inside the frustum, most are either fully in or fully out.


Or might you have a 4th solution?

As mentioned above, the parent’s bounding volume is meant to encapsulate all those beneath it. It should always be made to do so.



L. Spiro
2

Share this post


Link to post
Share on other sites

I'd like to point out that usually in renderers (Ogre, Unity etc.) the sub-renderables or submeshes don't have their own transform, rather any per-submesh transformation is "baked" into the vertex buffer data, and when rendering, they all get the same transform of the whole mesh instance (the Entity's scene node in Ogre, or the Transform component from the same gameobject in Unity)

 

But in your case, just merge their bounding boxes to the mesh instance bounding box on demand (ie. whenever their transform changes.)

 

This is quite similar problem as what you will encounter with skinned meshes, if you want to update the bounding box in real time based on animation. In that case you could have a bounding box or sphere on each of the bones, and use those to compute the whole skinned mesh instance's bounding box.

1

Share this post


Link to post
Share on other sites
Thanks. This helps, I'll implement 2 changes:

1. If the mesh instance is fully inside the frustum I'll skip checking all the renderables
(simple sphere check should do I think?)
2. When a renderable transforms I'll update the bounding volumes of the parent mesh instance

@agentc: how does ogre or unity then handle transforms on submeshes/ renderables?
In my case the basic "frame" of a indoor scene (building) might be a instance of 1 relatively big mesh, where I want to have the possibility to change transforms on specific renderables
(another option would be to have individual meshes that make up the "frame" of the indoor scene/ building)
0

Share this post


Link to post
Share on other sites

In those systems you have to make a separate scenenode or gameobject for the part that needs to be transformed individually.

 

Unity, for example, will import a complex object from a modeling program as several meshes + several gameobjects, if it's not merged into one. This process also preserves parent-child relationships if there are any. But at this point the meshes in the child gameobjects have no knowledge any more that they're part of a greater whole, instead they're just culled individually.

0

Share this post


Link to post
Share on other sites

Thanks. I understand. Good so see how other engines handle things, so I can decide what to adapt/ not to adapt in my own engine.

I've made some changes, which already shows some improvement (not profiled yet though). I had to change checking the mesh instance with sphere radius to OBB, because I need to distinguish inside/outside and intersect.

 

Below is the result.

 

Next thing todo is update the OBB of the mesh instance if one of it's renderables are transformed (scaled > 1.0, moved or rotated).

Have to think about how to do that efficiently, for example keeping track of the renderables that are dynamic and will/ can actually transform.

bool CD3d::CullObjects(const CD3dcam &pCam)
{
	if(mD3dscene == NULL || !mRenderQueueCreated) return false;

	/********* TODO here; introduce tree - spatial culling etc.	 ********/

	/** CULL MESH INSTANCES AND RENDERABLES AGAINST FRUSTUM, VISIBLE YES/NO				**/
	for(size_t mi=0;mi<mRenderQueue.GetNrMeshInst();++mi)
	{
		auto &inst = mD3dscene->mMeshInst[mi];
		int cull = pCam.OBBInFrustum(inst.GetBoundingBox(), inst.GetWorldMatrix());
			//int cull = pCam.AABBInFrustum(inst.GetBoundingBox());
			//int cull = pCam.SphereInFrustum(inst.GetSphereCenterWorld(), inst.GetSphereBoundingRadius());

		switch(cull)
		{
			case INSIDE:
				inst.SetVisible(true);
				inst.SetAllRenderablesVisible(true);
				++mInstInSceneVisible;
				break;

			case OUTSIDE:
				inst.SetVisible(false);
				inst.SetAllRenderablesVisible(false);
				break;

			case INTERSECT:
				inst.SetVisible(true);
				++mInstInSceneVisible;

				for(DWORD obj=0;obj<inst.GetNrRenderables();++obj)
				{
					if(pCam.OBBInFrustum(inst.GetRenderable(obj).GetBoundingBox(), inst.GetRenderable(obj).GetWorldMatrix()) != OUTSIDE)
			//		if(pCam.AABBInFrustum(inst.GetRenderable(obj).GetBoundingBox()) != OUTSIDE)
			//		if(pCam.SphereInFrustum(inst.GetRenderable(obj).GetSphereCenterWorld(),inst.GetRenderable(obj).GetSphereBoundingRadius()) == INSIDE)
					{
						inst.SetRenderableVisible(obj, true);
					}
					else inst.SetRenderableVisible(obj, false);
				}
				break;
		}
	}
	return true;
}

Edited by cozzie
0

Share this post


Link to post
Share on other sites

No problem, here it is:

/**************************************************************************************/
/***									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;
}

0

Share this post


Link to post
Share on other sites

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;
}
0

Share this post


Link to post
Share on other sites
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 Edited by L. Spiro
0

Share this post


Link to post
Share on other sites

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


0

Share this post


Link to post
Share on other sites

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;
0

Share this post


Link to post
Share on other sites
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? :)
0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

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;
}
0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

The performance is really good but the main point with the algorithm is the simplicity and versatility. It work also for world/view space aabb and child nodes. It's also does not depend your camera code. Also its more accurate than AABB methods. For static objects you can calculate world space AABB and save matrix matrix mul.

 

For special purpose case like voxel engine you can even optimize it even more. You can use matrix that include voxel size and center offset from 3d index so you precalculate extent part and result is frustum vs aabb test that cost same amount than normal frustum vs point.

0

Share this post


Link to post
Share on other sites

@Kalle; just a short update, I've managed to save quite some 'bytes' per bounding box.

Some vectors were just waste (AABBsize == OBBsize), and some are only necessary when creating the AABB, so now I simply created them on the stack.

 

The 8 AABB corners and OBB corners I still got in place, because I don't know how to 'save them'. Because per frame I transform the AABB corners to OBB corners, to determine the worldpace AABB size. I could probably save that, only if I would cull in local/ modelspace as you suggested.

typedef struct BOUNDINGBOX
{
	D3DXVECTOR3 AABBcenter;
	D3DXVECTOR3 AABBsize;
	D3DXVECTOR3 AABBcorners[8];

	D3DXVECTOR3 OBBcenter;		// OBB in worldspace now
	D3DXVECTOR3 OBBcorners[8];
	
	D3DXVECTOR3 AABBworldsize;	// AABB in worldspace, uses P/N-vertex 

	bool		created;

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

0

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  
Followers 0