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.
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[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, &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, ¢re, 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, ¢re, 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, ¢re, 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, ¢re, 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, ¢re, 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
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
