#### Archived

This topic is now archived and is closed to further replies.

This topic is 5548 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.
//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]

bump

##### Share on other sites
I find it extremely no one here knows how to split up a quadtree. I have tried going over this countless times, and I cannot get the math to work. Will someone please help me.

1. 1
2. 2
3. 3
Rutin
20
4. 4
khawk
14
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633656
• Total Posts
3013190
×