• Advertisement
Sign in to follow this  

Looking for more quad tree tuts

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

Ive been reading a couple quad tree tuts, but all seem to be lacking in some way (or maybe its ME thats lacking!). Anyway I just read... http://www.gamedev.net/reference/articles/article1303.asp It started out great, then he lost me when he started introducing 'the size of the leaf' and 'how many verts/triangles were in the leaf', ... Seems like it would have been a better idea to start with SPACE (ie make a single leaf represent a single cell, screw whats inside it). And even then after everything was over, he never showed how you actually USE this nifty tree you just spent hours writing. Lets say I want to tell if cell '12,15' is visible or not, how do I do that? So does anyone have any other beginner tutorials that are worth viewing? *Edit And maybe im thinking about this in the wrong way.. when I think of how youd "use" a quad tree, I think of something like...
for ( int x = 0; x<16; x++ ) {
for ( int z = 0; z<16; z++ ) {
 if ( isQuadTreeLeafInView(x,z) == true ) do blah blah...
}}


Maybe the 'proper' way to use a quad tree is to travel THROUGH it, starting at the root, hiding/showing terrain chunks as you go. In all the tutorials ive come across, ive yet to find one that even TOUCHES on this question (it seems pretty key too). [Edited by - ZealousEngine on July 2, 2006 7:19:41 PM]

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by ZealousEngine
Maybe the 'proper' way to use a quad tree is to travel THROUGH it, starting at the root, hiding/showing terrain chunks as you go.
It is pretty much always the case that a tree structure (whether quadtree, BSP-tree, k-d tree, or whatever) is traversed recursively from the top.

For example, if you want to render geometry stored in the leaves of a quadtree, you would do the following (untested pseudocode):


void RenderQuadtree(Viewport &view, Quadtree &node)
{
if (IsLeaf(node)) {
...render contents of leaf...
} else {
if (VisibleInView(view, node.GetBoundingVolume())) {
for (int i = 0; i < 4; i++)
RenderQuadtree(view, node.GetChild(i));
}
}
}


If you're having problems with tree structures you may want to get a textbook on basic data structures. They all pretty much talk about different trees and how to perform operations on them and a quadtree is really no different from any other tree (of up to four children at each node).

As for testing if a bounding volume is partially visible in the view volume, well there are also several books and plenty of articles that talk about how to do that. Simply think of the problem as a collision detection test between the bounding volume and the view volume. For such a test, if you want an exact (as opposed to an approximate) test, you can use what is known as the separating axis test (documented in many places).

Share this post


Link to post
Share on other sites
Quote:
It is pretty much always the case that a tree structure (whether quadtree, BSP-tree, k-d tree, or whatever) is traversed recursively from the top


Hmm thats what I was starting to think. So it sounds like ill have to re write all my 'for loops', and just travel the tree everytime I want to do any 'visibility' chekcs.

However, I want to be able to use this tree (containing 'sector' visibility culled by the frustum) for multiple systems, not just for my terrain. I was thinking the best way to do this would be, rather than stroing DATA (terrain chunks/geometry) in a node, it would be better to store 'coordinates'/space.

In other words, each node would have a flag that represented the nodes visibility (completely in view, partially in view, ect), but also a xStart, zStart and size variable that represented the area of the node. Then you use this 'area' data to run a traditional 'for loop' on that scope of data. This of course assumes your geometry (or whatever) data is broken up into areas, like mine is. This way you could use a single quad tree for LOTS of different systems, not just 'objects'.

What think?

Share this post


Link to post
Share on other sites
Well I wrote a little test program this morning (havent actually tested it, but it LOOKS like it would work). What I plan to do is create a quad tree (with a 16x16 leaf resolution), then I will frustum cull my scene and store the results inside the quadtree. Now, I dont want to link any actually objects/geometry to the quad tree ( i plan to use it for more than just that ), so instead what I did (or tryed to do) is record the 'leaf area' of each node. Then I use that area to run a simple for loop, which hides/shows my terrain chunks.

Heres what I wrote, please let me know what I screwed up, this is my first attempt! Any advice appreciated!

test



#ifndef Node_S
struct Node {
bool isLeaf; //is this node a leaf flag
int visible; //0 completely out of view, 1 partially in view, 2 completely in view
int x,z; //location of bottom left leaf (add size to get a range for looping)
int size; //size of this node (in leafs)
int parentId; //position (array index) of the parent
int nodeId; //position (array index) of this node
int childId[4]; //position (array index) of the 4 children
};
#define Node_S
#endif

//declare the quadtree (i precalculated the final size, should be right...)
//16x16 quad tree
Node qt[341];

//====
//MAIN
//====
void main () {

//build the quad tree (only done once obviously)
addNode( 16, 0, 0 );

//frustum cull the scene (lets assume this already works)
//cullScene()

//use the quad tree to hide/show terrain objects (with simple for/next loops)
cullTerrain( 16, 0, 0 );

}

//*********
//Functions
//*********

//==========
//ADD NODE()
//==========
//builds the quad tree
void addNode ( int size, int parentId, int nodeId ) {

static nodeCtr = 0;

//whats an easy way to determine x and z (the bottom left leaf)?
qt[nodeId].x = 0; qt[nodeId].z = 0; //this is temp! not 0! help!
qt[nodeId].size = size;

qt[nodeId].parentId = parentId; //position (array index) of the parent
qt[nodeId].nodeId = nodeId; //position (array index) of this node

//stop at the leaf level
if ( size == 1 ) {

qt[nodeId].isLeaf = true;

} else {

qt[nodeId].isLeaf = false;

//add 4 more nodes
size /= 2;
for ( int i = 0; i < 4; i++ ) {
nodeCtr++;
qt[nodeId].childId = nodeCtr;
addNode( size, nodeId, nodeCtr );
} //next i

} //end if

} //end addNode()

//==============
//CULL TERRAIN()
//==============
//determines which terrain chunks (terObj[16][16]) are visiible
void cullTerrain ( int size, int parentId, int nodeId ) {

//grab the bottom left 'leaf' for this node
int xStart = qt[nodeId].x; int zStart = qt[nodeId].z;

//if we are at the leaf level
if ( qt[nodeId].isLeaf == true ) {

//if this node is at least partially in view, show the object
if ( qt[nodeId].visible > 0 ) showObject( terObj[xStart][zStart] );
else hideObject( terObj[xStart][zStart] );

} else {

//if this node is completely out of view, hide all children
if ( qt[nodeId].visible == 0 ) {
for ( int x = xStart; x < xStart+size; x++ )
for ( int z = zStart; z < zStart+size; z++ )
hideObject( terObj[x][z] );
return;
}

//if this node is completely in view, show all children
if ( qt[nodeId].visible == 2 ) {
for ( int x = xStart; x < xStart+size; x++ )
for ( int z = zStart; z < zStart+size; z++ )
showObject( terObj[x][z] );
return;
}

//otherwise, check all 4 children
size /= 2;
for ( int i = 0; i < 4; i++ )
cullTerrain( size, nodeId, qt[nodeId].childId);

} //end if

} //end cullTerrain()

//*/






[Edited by - ZealousEngine on July 3, 2006 10:45:30 AM]

Share this post


Link to post
Share on other sites
http://www.gamedev.net/community/forums/topic.asp?topic_id=395546

[source lang=cpp]
void quadtree::subdivide(float minleafsize,min, max)
{
//stop recursion
if(cursize == minleafsize)
return;

pnodes = new quadtree[4];
//for each pnode
pnode->subdivide(minleafsize,newmin,newmax);
}




for a simple renderer you can do it as suggested above, for more complex implementations you will need some sort of visible scene management where you sort by shaderid, statechanges, texture ids

this would look like this

a) get visible objects from quadtree and insert the references into a sorted list
b) render the list

Share this post


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

  • Advertisement