//The big grid
//MAP_DIM==256
bounding[0] = 0;
bounding[1] = MAP_DIM-1;
bounding[2] = MAP_DIM*(MAP_DIM-1);
bounding[3] = MAP_DIM*MAP_DIM-1;
void CQuadtree::CreateNodes(int* bounding, int iParentID, int iNodeID, TERRAINVERTEX* verts, LPDIRECT3DDEVICE9 &pDevice){
static int iTotalTreeID = 0;
qtType type;
int width, height, i, j;
width = bounding[1]-bounding[0]+1;
height = floorf((bounding[2]-bounding[0])/256)+1;
if(width==iMinSize || height==iMinSize)
type = LEAF;
else
type = NODE;
QT_NODE* pNode = &pNodeList[iNodeID];
pNode->uiID = iNodeID;
pNode->uiParentID = iParentID;
for(i=0; i<4; i++)
pNode->vBoundCoords[i] = verts[bounding[i]].vPos;
pNode->iType = type;
if(type==LEAF){
//stuff
}
else{
int newBounding[4];
//Top left
iTotalTreeID++;
pNode->uiBranches[0] = iTotalTreeID;
newBounding[0] = bounding[0];
newBounding[1] = bounding[0]+floorf(((bounding[1]-bounding[0])/2.0f));
if(newBounding[1]==128)
newBounding[1]--;
newBounding[2] = ((newBounding[1]-newBounding[0])*iMaxSize+newBounding[0]);
newBounding[3] = newBounding[2]+(newBounding[1]-newBounding[0]);
CreateNodes(newBounding, iNodeID, iTotalTreeID, verts, pDevice);
//**************************************************************************
//Top right
iTotalTreeID++;
pNode->uiBranches[1] = iTotalTreeID;
bounding[0]++;
bounding[2]++;
newBounding[0] = bounding[0]+ceilf(((bounding[1]-bounding[0])/2.0f));
newBounding[1] = bounding[1];
newBounding[2] = ((newBounding[1]-newBounding[0])*iMaxSize+newBounding[0]);
newBounding[3] = newBounding[2]+(newBounding[1]-newBounding[0]);
CreateNodes(newBounding, iNodeID, iTotalTreeID, verts, pDevice);
//**************************************************************************
//Bottom left
iTotalTreeID++;
pNode->uiBranches[2] = iTotalTreeID;
bounding[0]+=iMaxSize;
bounding[1]+=iMaxSize;
bounding[2]--;
newBounding[0] = ((bounding[2]-bounding[0])/2);
newBounding[1] = newBounding[0]+floorf(((bounding[1]-bounding[0])/2.0f));
newBounding[2] = bounding[2];
newBounding[3] = newBounding[2]+((bounding[3]-bounding[2])/2);
CreateNodes(newBounding, iNodeID, iTotalTreeID, verts, pDevice);
//**************************************************************************
//Bottom right
iTotalTreeID++;
pNode->uiBranches[3] = iTotalTreeID;
int wTemp = bounding[3]-bounding[2];
bounding[0]+=(iMaxSize+1);
bounding[1]+=iMaxSize;
bounding[2]++;
newBounding[0] = (bounding[2]/2.0f)+(bounding[0]/2.0f)+ceilf(wTemp/2.0f);
newBounding[1] = newBounding[0]+floorf(wTemp/2.0f);
newBounding[2] = newBounding[3]-floorf((wTemp/2.0f));
newBounding[3] = bounding[3];
CreateNodes(newBounding, iNodeID, iTotalTreeID, verts, pDevice);
}
}
//------------------------------------------------------------------------------------------------------
The great logician Bertrand Russell once claimed that he could prove anything if given that 1+1=1. So one day, some fool asked him, "Ok. Prove that you're the Pope." He thought for a while and proclaimed, "I am one. The Pope is one. Therefore, the Pope and I are one."
[edited by - Sfpiano on September 21, 2003 11:21:04 AM]
Splitting a quadtree
I've been working on this for a few days now, and it's really, really annoying me. I'm trying to write the code to create the quadtree's bounding boxes, but the numbers aren't comign out quite right. Let me explain how I see it in my head. My full grid is 256x256, and I want the leaves to be 64x64. I'm also using a linear array because I'm using this data in accordince with my indx buffer. So since this is an array, it really goes from 0-255. So the upper left quadrant from the first division would have x from 0 to 127, and y from 0 to 32512 (127*256). Then the upper right quadrant from have x of 128 to 255, and y from 0 to 32512. So on and so forth. I believe the first division works out ok, but then things start to fall apart.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement