• Advertisement

Archived

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

Quadtree question

This topic is 5805 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 read several articles on quadtrees and I''m implementing one myself now. I just can''t see in what order I construct the quadtree. 1. I check south and east vertices if they should be enabled. 2. and then ????? If both edge vertices are enabled should I treat the SE quadrant as a new quad square (new node) ? But then the middle vertex of this quadrant isn''t enabled. Or should I first check if the SE needs subdivision before treating it as an separate (new) quad square. Can somebody explain the general lines of the quadtree algorithm? Thanks, Edo

Share this post


Link to post
Share on other sites
Advertisement
Just take Octree algorithem ( there is a bunch of tutorials one the net ) and use only 2 dimensions

There are more worlds than the one that you hold in your hand...

Share this post


Link to post
Share on other sites

What exactly are you using the quadtree for?

My powers of telepathy tell me that you are using a quadtree as an level of detail terrain algorithm. If so, then this Gamasutra article will probably give you lots of tips:

http://www.gamasutra.com/features/20000228/ulrich_pfv.htm

Cheers

Keef

-----------------------
glDisable(WORK);
glEnable(GL_CODING);

Share this post


Link to post
Share on other sites
blueEbola: I do


------------------------------------------------------------
Email
Website

"If you try and don''t succeed, destroy all evidence that you tried."
------------------------------------------------------------

Share this post


Link to post
Share on other sites

Keef, I read the article on gamedev, and although it is pretty detailed in certain areas, it fails to make me clear what the precise procedure is on subdividing quads.

Yes, I''m using the quadtree for terrain LOD. BlueEbola: do you somewhere have pseudo-code description of your demo (or some site with your demo).

Thanks for the replies.

Edo

Share this post


Link to post
Share on other sites
I can probably upload it to my site tomorrow (I don't want to log into geocities and get involved with there bad interface right now)

but basically for my quadtree I define the size of the tree (as in the dimensions of the heightmap) and it with one call it builds the whole tree (using recursive function calls). In the function I set the bounding box for the node and then I check to see if its width is at my specified leaf size; if so, make it a leaf, otherwise it becomes a node. When its a node, it has children, when its a leaf, it doesnt. Heres what the function looks like (pseudo code):

  

#define LEAF_WIDTH 16

void CreateNode(QuadtreeNode *quadnode,int xstart,int xwidth,int ystart,int yheight)
{

// Define the bounding box here (I'm not going to write

// all the code for this sorry) :(


quadnode->Leaf = FALSE;

if (xwidth == LEAF_WIDTH)
{
// Define all the vertices inside this leaf

quadnode->Child[0] = NULL;
quadnode->Child[1] = NULL;
quadnode->Child[2] = NULL;
quadnode->Child[3] = NULL;

quadnode->Leaf = TRUE;
}
else
{
quadnode->Child[0] = new quadnode;
quadnode->Child[1] = new quadnode;
quadnode->Child[2] = new quadnode;
quadnode->Child[3] = new quadnode;

CreateNode(quadnode->Child[0],xstart,xwidth/2,ystart,yheight/2);
CreateNode(quadnode->Child[1],xstart+xwidth/2,xwidth/2,ystart,yheight/2);
CreateNode(quadnode->Child[2],xstart+xwidth/2,xwidth/2,ystart+yheight/2,yheight/2);
CreateNode(quadnode->Child[3],xstart,xwidth/2,ystart+yheight/2,ywidth/2);
}

}



Thats basically how you can construct the quadtree. The QuadtreeNode structure could look like:

  
typedef struct _quadnode
{
BOOL Leaf;
Vertex3f BoundingBox[4];
Vertex3f Vertices[LEAF_WIDTH][LEAF_WIDTH];
_quadnode *Child[4];
}


I don't store the actual vertices in my quadtree structure though, I store indices which point into an array. I hope this helps a bit

Edited by - blueEbola on February 28, 2002 9:25:48 PM

Share this post


Link to post
Share on other sites

  • Advertisement