Advertisement Jump to content
Sign in to follow this  

quad tree leaf width problem

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

Alright, when splitting a heightmap into a quad tree you continue recursively until you get a bounding box for a node that when split up will be a certain width known as the leaf width. Now, I wrote everything in the idea that the leaf width could be adjusted. I've never bothered to change it off of 4 tho until testing is done. Well I decided to test it, and 2 doesn't work, neither does 8 or 16, so I stopped there. Posting code for this is not something any is goona wanna debug, so I guess my question is should this be adjustable? I've been debugging for hours, I cannot seem to see why it won't work but the recursive to build the tree goes to far, it doesn't stop when it should.

Share this post

Link to post
Share on other sites
It should]/i] be adjustable in the sense that otherwise it doesn't work as designed - who knows what other problems this might cause when the leaf size = 4? I would want it to be variable so you can test performance/memory consumption at differnt values. I would think 4 is actually too small - most people seem to use 16-64 and I find 32 is fastest - 4 means a lot of extra work on the huge number of leaves.
Are you sure the leaf size isn't hard-coded in some places but settable in others? And what goes wrong - a crash or what?

Share this post

Link to post
Share on other sites
Well sort of.
When I set to any value a power of 2 that isn't 4 I get a problem.
The problem is an invalid memory access during the recursive that builds the tree. It attempts to read a node that hasnt been allocated.

I believe I have found the problem but have no solution. CalcNodeNum I belive is calculating an incorrect number of nodes for anything but 4, but since the numbers on 4 have been debugged to $#!* and they are confirmed to be right in code and on paper.

This is how I calculate the final number of neccessary nodes:

//Store the important coordinates
m_iNumLeaves = (pHeightmap->Width() / iLeafWidth) * (pHeightmap->Height() / iLeafWidth);
m_iNumNodes = CalcNodeNum(m_iNumLeaves, iLeafWidth);
m_pNodes = new NODE[iNumNodes];

Calculate how many nodes we need for this tree
int cQuadTree::CalcNodeNum(int iNumLeaves,int iLeafWidth)
int iCounter=0;

iCounter += iNumLeaves;
iNumLeaves = iNumLeaves / iLeafWidth;

if(iNumLeaves <= 1) break;

return iCounter;

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!