Jump to content
  • Advertisement

Archived

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

jollyjeffers

(C++) generating quadtrees for terrain

This topic is 5560 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, I''ve been trying to generate a trivial quadtree for my game engine, I have a 2^n square grid (32x32, 64x64 etc..) and just want to recursively sub-divide it down to 1x1 leaves. here''s my code:
  
Gfx3D::quadtreeNode* Gfx3D::CreateQuadTree( int lX, int lY, int uX, int uY ) {
	//we use simple recursion to generate this node and then its next 4 children

	
	char* pMsgBx = new char[ 100 ];
	sprintf( pMsgBx, "CreateQuadTree : [%d,%d]->[%d,%d] = (%dx%d) %s", lX,lY,uX,uY,(uX-lX),(uY-lY), (uX-lX)== 1 ? "LEAF!" : " ");
	MessageBox( NULL, pMsgBx, "Status", MB_OK );
	delete pMsgBx;

	quadtreeNode *n = new quadtreeNode;
	n->vLow.x  = ( float ) lX;
	n->vLow.y  = ( float ) lY;
	n->vHigh.x = ( float ) uX;
	n->vHigh.y = ( float ) uY;

	//if the current node is ONLY 1x1 in size then it''s a leaf.

	n->bLeaf = ( ( n->vHigh.x - n->vLow.x ) <= 1.0f ) && ( ( n->vHigh.y - n->vLow.y ) <= 1.0f );

	//quadtree nodes must be square

	if ( ( uX - lX ) != ( uY - lY ) ) {
		char* pMsg = new char[ 100 ];
		sprintf( pMsg, "Quadtree: node is not of same height and width : [%d,%d,%d,%d] = (%dx%d)\nLeaf = %s", lX,lY,uX,uY,(uX-lX),(uY-lY),n->bLeaf ? "Yes" : "No");
		throw Gfx3DException( pMsg );
		delete pMsg;
	}

	n->NextNode[0] = n->bLeaf	? NULL 
								: CreateQuadTree( lX,			lY,				(uX / 2),		(uY / 2)	);	//top-left

	n->NextNode[1] = n->bLeaf	? NULL 
								: CreateQuadTree( (uX / 2),		lY,				uX,				(uY / 2)	);	//top-right

	n->NextNode[2] = n->bLeaf	? NULL 
								: CreateQuadTree( lX,			(uY / 2),		(uX / 2),		uY		);	//bottom-left

	n->NextNode[3] = n->bLeaf	? NULL 
								: CreateQuadTree( (uX / 2),		(uY / 2),		uX,				uY		);	//bottom-right

	
	//return the fully constructed node

	return n;
}
  
it may look a little cryptic - but I know roughly whats causing the problem - variables. notice that lX,uX,lY,uY are parameters to the function, and these are re-used when recursively calling the function. is this okay? on debugging, the program generates the first branch correctly, but starts to screw up when generating the second branch (ie, it goes down to 1x1 by sub-div the top-left square, but goes wrong when searching the top-right square(s)). is it "safe" to use the same variables over and over again? is there any chance that my variables are going to be confused/mixed up? any ideas? In theory, I cant see ANYTHING wrong with my code much appreciated, Jack DirectX 4 VB: All you need for multimedia programming in Visual Basic Formula 1 Championship Manager, My Game Project.

Share this post


Link to post
Share on other sites
Advertisement
Because you are passing by value, the recursion will not affect the variables (ie within each invocation they are each copies of the values passed in).

The reason it is failing is (I'm almost certain) because you are using ints. Use floats for the parameters and it will all work.

[edited by - JuNC on April 2, 2003 8:33:30 AM]

Share this post


Link to post
Share on other sites
quote:

is it "safe" to use the same variables over and over again? is there any chance that my variables are going to be confused/mixed up?



Yes. Recursion wouldn''t work otherwise.

While I can''t say for certain what your problem is (since I''m not going to write a program around it), I''d say its the way you are splitting your quad tree.

Here''s how I''m splitting my QT in my current project


  
if(xmax - xmin <= 1 && zmax - zmin <= 1)
{
block = terrain.getBlock(xmin,zmin);
//LogError("Grabbed block " << xmin << " " << zmin);

}
else
{
q1 = new QuadTreeNode();
q2 = new QuadTreeNode();
q3 = new QuadTreeNode();
q4 = new QuadTreeNode();
int xmid = (xmin + xmax) / 2;
int zmid = (zmin + zmax) / 2;
q1->build(xmin,xmid, zmin,zmid, terrain);
q2->build(xmid,xmax, zmin,zmid, terrain);
q3->build(xmin,xmid, zmid,zmax, terrain);
q4->build(xmid,xmax, zmid,zmax, terrain);
}


In mine, I''m taking the middle of xmin and xmax (your lX and uX), not just dividing it by 2. Otherwise your lX for the top-right never changes.

And if I''m not mistaken, the memory allocated for your exception is never freed, leading to a memory leak.

Hope that helped

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!