Jump to content
  • Advertisement

Archived

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

Sfpiano

Splitting a quadtree

This topic is 5378 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

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]

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
bump

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!