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

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...

I just finished a working quadtree demo (based on NeHe tut 35) if you want it.

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);

blueEbola: I do


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

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

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

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 16void 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