Sign in to follow this  

Frustum Culling with AABB Please help with image

This topic is 2813 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 all. I'm trying to put my terrain chuncks into a quad tree and using a AABB frustum cull the section I dont see with the cammera, But it seam there is a problem some where, I just cant see where it is. The image contains some terrain with missing chunks. The chunks move around depending on the cameras position and view direction. Im not sure if the problem is in the quad tree or its just the AABB's of each node. Ill post some code on how I create the AABB and how I subdevide the tree. And a frustum aabb test it may be here thats the problem. //the yellow meshes are the quad trees leaf nodes that contain terrain chunks the wire mesh. description of your image AAbb Frustrum test


bool Visible(AABB *box)
{
	// Test assumes frustum planes face inward.

	D3DXVECTOR3 P;
	D3DXVECTOR3 Q;
	//Q = box->extent();//center();
	//P = Q - _pos;
	//p = _pos - box->center;
	//we can quick cull if we use the fog distance ?????
	//if(D3DXVec3Length(&P) > 300)
	//	return false;//out of rang

	//      N  *Q                    *P
	//      | /                     /
	//      |/                     /
	// -----/----- Plane     -----/----- Plane    
	//     /                     / |
	//    /                     /  |
	//   *P                    *Q  N
	//
	// PQ forms diagonal most closely aligned with plane normal.

	// For each frustum plane, find the box diagonal (there are four main
	// diagonals that intersect the box center point) that points in the
	// same direction as the normal along each axis (i.e., the diagonal 
	// that is most aligned with the plane normal).  Then test if the box
	// is in front of the plane or not.
	for(int i = 0; i < 6; ++i)
	{
		// For each coordinate axis x, y, z...
		for(int j = 0; j < 3; ++j)
		{
			// Make PQ point in the same direction as the plane normal on this axis.
			if( FrustumPlanes[i][j] > 0.0f )
			{
				P[j] = box->minPt[j];
				Q[j] = box->maxPt[j];
			}
			else 
			{
				P[j] = box->maxPt[j];
				Q[j] = box->minPt[j];
			}
		}

		// If box is in negative half space, it is behind the plane, and thus, completely
		// outside the frustum.  Note that because PQ points roughly in the direction of the 
		// plane normal, we can deduce that if Q is outside then P is also outside--thus we
		// only need to test Q.
		if( D3DXPlaneDotCoord(&FrustumPlanes[i], &Q) < 0.0f  ) // outside
			return false;
	}
	return true;
}//end  Visible
///////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////



//splitting the quad tree you pass in 0, 0, width, height map bound size //the subgrids and tree are in 3d world coords



//------------------------------------------------------------------------
//this will return a allocated node set with default values and the rect
//passed in is its bounds
//------------------------------------------------------------------------
QuadNode *CreateNode(RECT *rect, D3DXVECTOR3 *centre,
	int halfmapwidth)
{
	//we need to creat our first node and set the bounds
	QuadNode *newnode = new QuadNode();
	if(newnode == NULL)
		return NULL;//error no memory or some thing

	//set the nodes boundary
	newnode->Bounds = (*rect);


	//new code
	//set up the nodes bounding box
	//we need the half width and depth of this node and using the centre in 3d world coord
	//we can make our aabb 
	int hwidth	= (newnode->Bounds.right - newnode->Bounds.left) * 0.5f;
	int hdepth	= (newnode->Bounds.bottom - newnode->Bounds.top) * 0.5f;
	newnode->m_BndBox.minPt.x = centre->x - hwidth;
	newnode->m_BndBox.minPt.y = 0.0f;
	newnode->m_BndBox.minPt.z = centre->z - hdepth;

	newnode->m_BndBox.maxPt.x = centre->x + hwidth;
	newnode->m_BndBox.maxPt.y = 10000.0f;
	newnode->m_BndBox.maxPt.z = centre->z + hdepth;

	return newnode;

}//end CreateNode
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////









//------------------------------------------------------------------------
//this will create the quadtree pass in the total size of the map to start it
//------------------------------------------------------------------------
bool CreateTree(RECT *rect, //the maps size eg. left,top = 0; bottom left right
					 int stopwidth,
					 int halfmapwidth)//used so we can convert the bounds to 3d world coords for the aabb/when our rectangle width gets to this size we stop
{
	//start the recursion
	float wyval = 0.0f;//
	D3DXVECTOR3 centre;//we calculate this and give it to create node so we can tranlate the box to its world coords

	//we need to set the offsets here used later to in the recursion
	//so we can trans form the cube we make
	Offsetx = -(rect->right -  rect->left) * 0.5f;
	Offsetz = -(rect->bottom - rect->top ) * 0.5f;

	//create the centre point for this mesh box
	centre.x = (rect->left + ((rect->right -  rect->left)* 0.5f) + Offsetx);
	centre.y = wyval;
	centre.z = (rect->top + ((rect->bottom - rect->top )* 0.5f) + Offsetz);

	//we need to creat our first node and set the bounds
	StartNode = CreateNode(rect, &centre, halfmapwidth);
	if(StartNode == NULL)
		return false;//error no memory or some thing

	TCHAR buff[MAX_PATH];
	
	
	//add a message to that dialogbox on the main window
	//ErrorReport.AddErrorMessage(buff, false);



	//add a message to that dialogbox on the main window
//	ErrorReport.AddErrorMessage(buff, false);




	CreateTreeRecursion(StartNode,//c//the node
						NULL,//the parentnode
						stopwidth,//when our rectangle width gets to this size we stop
						halfmapwidth);



	return true;//all ok
}//end CreateTree
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////




//------------------------------------------------------------------------
//this will create the quadtree its a recursive function
//------------------------------------------------------------------------
void CreateTreeRecursion(QuadNode *node,//the node
									QuadNode *parent,//the parentnode
									int stopwidth,//when our rectangle width gets to this size we stop
									int halfmapwidth)//for the offsets
{
	//get the width
	int width = node->Bounds.right - node->Bounds.left;
	int hieght = node->Bounds.bottom - node->Bounds.top;

	
	
	

	//ok we can go for more 
	node->m_pParentNode = parent;

	//see if we can stop the deviding
	if(width <= stopwidth)
	{
		//we are a leaf node 
		node->NodeType = QuadNode::LEAF_TYPE;
		node->LeafCount++;

		return;//end recursion
	}

	//ok we need to split up this rect from node and give it to its branches
	RECT rect;
	int hwidth	= width  * 0.5f;
	int hhieght = hieght * 0.5f;

	float wyval = 0.0f;//
	D3DXVECTOR3 centre;//we calculate this and give it to create node so we can tranlate the box to its world coords

	
	

	//------------------------------------------------------------------------------------------------
	//for the first childnode
	rect.left	= node->Bounds.left;
	rect.top	= node->Bounds.top;
	rect.right	= rect.left + hwidth;
	rect.bottom	= rect.top + hhieght;

	//create the centre point for this mesh box
	centre.x = rect.left + (hwidth*0.5f) + Offsetx;
	centre.y = wyval;
	centre.z = rect.top + (hhieght*0.5f) + Offsetz;

	node->ChildNode[0] = CreateNode(&rect, &centre, halfmapwidth);
	if(node->ChildNode[0] == NULL)
	{
		//ErrorReport.AddErrorMessage("Error Failed To Create NEW NODE", false);
		return;//error
	}

	
	

	//add a message to that dialogbox on the main window
	//ErrorReport.AddErrorMessage(buff, false);


	//do recursion
	CreateTreeRecursion(node->ChildNode[0],//the node
						node,//the parentnode
						stopwidth, halfmapwidth);//when our rectangle width gets to this size we stop
	//-----------------------------------------------------------------------------------------------------


	//------------------------------------------------------------------------------------------------
	//for the second childnode
	rect.left	= node->Bounds.left + hwidth;
	rect.top	= node->Bounds.top ;
	rect.right	= rect.left + hwidth;
	rect.bottom	= rect.top + hhieght;

	//create the centre point for this mesh box
	centre.x = rect.left + (hwidth*0.5f) + Offsetx;
	centre.y = wyval;
	centre.z = rect.top + (hhieght*0.5f) + Offsetz;

	node->ChildNode[1] = CreateNode(&rect, &centre, halfmapwidth);
	if(node->ChildNode[1] == NULL)
	{
		//ErrorReport.AddErrorMessage("Error Failed To Create NEW NODE", false);
		return;//error
	}


	
	//add a message to that dialogbox on the main window
	//ErrorReport.AddErrorMessage(buff, false);


	//do recursion
	CreateTreeRecursion(node->ChildNode[1],//the node
						node,//the parentnode
						stopwidth, halfmapwidth);//when our rectangle width gets to this size we stop
	//-----------------------------------------------------------------------------------------------------



	//------------------------------------------------------------------------------------------------
	//for the third childnode
	rect.left	= node->Bounds.left;
	rect.top	= node->Bounds.top + hhieght;
	rect.right	= rect.left + hwidth;
	rect.bottom	= rect.top + hhieght;

	//create the centre point for this mesh box
	centre.x = rect.left + (hwidth*0.5f) + Offsetx;
	centre.y = wyval;
	centre.z = rect.top + (hhieght*0.5f) + Offsetz;


	node->ChildNode[2] = CreateNode(&rect, &centre, halfmapwidth);
	if(node->ChildNode[2] == NULL)
	{
		//ErrorReport.AddErrorMessage("Error Failed To Create NEW NODE", false);
		return;//error
	}

	

	
	//add a message to that dialogbox on the main window
	//ErrorReport.AddErrorMessage(buff, false);


	//do recursion
	CreateTreeRecursion(node->ChildNode[2],//the node
						node,//the parentnode
						stopwidth, halfmapwidth);//when our rectangle width gets to this size we stop
	//-----------------------------------------------------------------------------------------------------



	//------------------------------------------------------------------------------------------------
	//for the 4th child node
	rect.left	= node->Bounds.left + hwidth;
	rect.top	= node->Bounds.top + hhieght;
	rect.right	= rect.left + hwidth;
	rect.bottom	= rect.top + hhieght;

	//create the centre point for this mesh box
	centre.x = rect.left + (hwidth*0.5f) + Offsetx;
	centre.y = wyval;
	centre.z = rect.top + (hhieght*0.5f) + Offsetz;


	node->ChildNode[3] = CreateNode(&rect, &centre, halfmapwidth);
	if(node->ChildNode[3] == NULL)
	{
		//ErrorReport.AddErrorMessage("Error Failed To Create NEW NODE", false);
		return;//error
	}


	//add a message to that dialogbox on the main window
	//ErrorReport.AddErrorMessage(buff, false);

	//do recursion
	CreateTreeRecursion(node->ChildNode[3],//the node
						node,//the parentnode
						stopwidth, halfmapwidth);//when our rectangle width gets to this size we stop
	//-----------------------------------------------------------------------------------------------------


}//end CreateTreeRecursion
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////



Share this post


Link to post
Share on other sites
Does it work correctly if you don't use frustum culling?

Also, you should use a loop instead of duplicating the construction code for each child.

Share this post


Link to post
Share on other sites
They all render when I zoom the camera out so all quadtree is with in the frustum.
could it be my near and far planes.
// Initialize the projection matrix45.0f

D3DXMatrixPerspectiveFovLH( &Projection, ( float )D3DX_PI * 0.5f , ( FLOAT )Width / ( FLOAT )Height, 100.1f, 100000.0f );

Share this post


Link to post
Share on other sites
Got it working I was using the quad trees leaf nodes aabb for the Visible check
and the quad trees nodes are a bit out from what the terrains sub grids are, and that was the cause of the poping terrain.

Share this post


Link to post
Share on other sites

This topic is 2813 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.

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