Jump to content
  • Advertisement
Sign in to follow this  
Halsafar

quad tree leaf width problem

This topic is 4821 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
Advertisement
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;

while(1)
{
iCounter += iNumLeaves;
iNumLeaves = iNumLeaves / iLeafWidth;

if(iNumLeaves <= 1) break;
}
iCounter++;

return iCounter;
}

Share this post


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

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!