# Looking for more quad tree tuts

This topic is 4587 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
Quote:
 Original post by ZealousEngineMaybe 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 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 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_Sstruct 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 treeNode 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 treevoid 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 visiiblevoid 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 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 recursionif(cursize == minleafsize)return;pnodes = new quadtree[4];//for each pnodepnode->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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 15
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
634150
• Total Posts
3015808
×