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

## Recommended Posts

Newbie question time (all my questions seem to be rather noobish don't they?) I understand the concept of using a Quadtree or Octree for Frustrum culling. What I don't quite understand is what you sort that tree by? I've been pouring over Google searching for explanations and nothing I have found so far explains what your trees are sorted by.

##### Share on other sites
I dont think you sort them per-se. What you do is take the top node(that every other node is in), and check if its visible. If it is, you check the 4/8 child nodes, and if theyre visible, check their children, recursively. Once you get to a node with no children, you draw that node. If a node isnt visible, that means none of its children are visible, which allows you (supposedly) to remove them faster, since you dont have to do so many checks. In personal testing, which I assume isnt the case always, I found that is was faster to make a uniform grid(all the same size), and recursively check the node the camera is in, then the 4 nodes around it, then the four nodes around each of them, etc. Im sure there are other optimizations you could do for this, of course. Make sure to check it out, you might find its faster.

Unless I completally misunderstood your question. Is there some other part of dealing with quadtrees that you are calling sorting?

##### Share on other sites
To my understanding there has to be some kind of sorting going on. If you reach a node that isn't viewable then you know that every child of that node is also not viewable right? If so then there has to be something determining that if A isn't viewable then B, C, and D are not viewable either. If a node isn't in the FOV but one of it's children is then that defeats the purpose of the whole thing.

##### Share on other sites
All the children of a Node HAVE to be within the node, so if the node isnt visible, its impossible for any of its children to be visible. The children of a node are the 4/8 equal nodes inside of it (that split it up)

##### Share on other sites
Indeed, if for example a box isn't in your field of view, all the contents inside of that box can't be seen as well. The same applies to the children of quads that fall outside. Those can be skipped as their parent isn't visible as well. This can save you a lot of time by not rendering any objects in those quads.

##### Share on other sites
Alright then I guess my understanding of this was a little more lacking then I thought...

So I guess my question now is how do I generate this quadtree/octree?

##### Share on other sites
In the simplest case, you can just choose a cutoff, which can be adjusted on the fly to find the best settings (note to self: adjust automatically based on FPS? Must go implement!). So first, you have your game world, which is a square (Im doing quadtrees). Now, you have a function:
[code]
void recursiveNodeHandler(vec2 pos,vec2 size,int level)
{
if(level>THRESHOLD || box of size at pos is completally visible)
drawStuffInNode();
if(box of size at pos is partially visible)
{
recursiveNodeHander(pos,size/2,level+1);//upper left
recursiveNodeHander(vec2(pos.x,pos.y+size.y/2),size/2,level+1);//lower left
for each of the 4 quarters of the current node
}
}[/code]
then you just call it with
level=0
pos=the top left of your world,

This will split the world in to 4 separate sections, and then test each one, going THRESHOLD levels deep, and once it reaches that many levels, it just draws the stuff, but if at any level a node isnt visible, it stops.

##### Share on other sites
Just to elaborate a little better here.

Each node of the tree can be in one of three states:
[list][*]Fully outside the frustum[*]Fully inside the frustum[*]Intersecting the frustum[/list]As all child nodes are enclosed by the volume of their parent, the rules become:
[list][*]If a node is fully inside the frustum then all of it's children are also fully inside the frustum and don't need to be tested (trivial accept).[*]If a node is fully outside the frustum then all of it's children are also fully outside the frustum and don't need to be tested (trivial reject).[*]If a node intersects the frustum then it's children may be in any one of the three states, so you need to test them all.[*]The top node will always intersect the frustum as it contains all of your geometry.[/list]The first and the second above can be further refined - as there are 6 frustum planes, if a node is in a given state for each of those planes, then all of it's children can be guaranteed to also be in the same state for the same plane. (Depending on your frustum layout you may not need to check the front plane - can you see why?)

Pseudocode might look like this:
[code]void TraverseQuadTree (node *n, int frustumcheck)
{
// if this has been cleared then the node's parent was fully inside the frustum
if (frustumcheck)
{
for (int planenum = 0; planenum < 6; planenum++)
{
// the parent node was fully inside the frustum on this plane so don't check
if (!(frustumcheck & (1 << planenum))) continue;

// we don't yet know...
int sidestate = UNDEFINED_UNKNOWN;

// ...so check; if it's fully outside we reject this node and all of it's children
if ((sidestate = FrustumPlaneTest (n, planenum)) == FULLY_OUTSIDE_FRUSTUM) return;

// if the node was fully inside the frustum on this plane all of it's children are
// also fully inside on this plane, so clear this plane from the list to check for them
if (sidestate == FULLY_INSIDE_FRUSTUM) frustumcheck &= ~(1 << planenum);
}
}

// do stuff here

// traverse child nodes
}

// check all 6 planes for the top node (63 == 111111)

##### Share on other sites
Right, I get the theory there. What I don't get is how you build the tree from objects with x,y,z coords.

##### Share on other sites
Buliding it from objects is one way, but it might be a bit complex. Instead what you can do is something like this:

You know the dimensions of your world, say it's 8192 units in each direction. This becomes your top node.
Divide this into 4 (for a quadtree) or 8 (for an octree) roughly equal sized areas; these are your top node's children.
Divide each of these recursively until you hit your threshold beyond which you don't divide any more.

So now we've got an empty tree structure that we need to populate. In order to do this we go through each object in the scene and figure which node it belongs in (Google for "octree insertion" for lots on info about this; also look for "loose octrees" which is a useful technique), then add it to a list of objects for that node.

In general terms you'll have three types of object:

[list=1][*]Static (unmoving) objects which just get added once (at load time); once you've added them you don't need to worry about them any more so far as this part of the job is concerned.[*]Dynamic (moving) objects which need to be added every frame (or every time they move) and removed from their previous node (if they moved).[*]Objects which you're not going to bother using the tree for because you've profiled and determined that it's faster to just draw them all; this might include particles.[/list]
So now you come to draw. This is just a simple node traversal, perhaps using code like that I posted earlier, and each time you traverse a node you check it to see if there are any objects to be drawn in it. If so, draw them.

##### Share on other sites
[quote name='mhagain' timestamp='1309353086' post='4829058']
The top node will always intersect the frustum as it contains all of your geometry.[/quote]
I'm a little bored and this is only a minor correction to the otherwise excellent explanation above:
The top node will of course not always intersect the frustum, but it should always be evaluated in order for one to determine whether anything in the tree is visible. Obviously, mhagain suggests that if we need to check if a state is one of the 3 mentioned states, the root node could be set to the intersect state before every tree evaluation, to simplify things.

##### Share on other sites
I guess I'm just not getting this. I understand checking the tree against the view frustrum. I'm not understanding how you build this tree.

[quote]You know the dimensions of your world, say it's 8192 units in each direction.[/quote]

I'm guessing this means that if my world is a giant box 10k*10k*10k then that's what I split my nodes up into? Split that up into consecutively smaller sections of 4 (or 8)? So if a node is within my view frustrum it gets drawn and all it's children nodes get checked and drawn (if visible) until we run out of nodes or the nodes are no longer visible? Is that right?

##### Share on other sites
[quote name='SuperVGA' timestamp='1309365653' post='4829135']
[quote name='mhagain' timestamp='1309353086' post='4829058']
The top node will always intersect the frustum as it contains all of your geometry.[/quote]
I'm a little bored and this is only a minor correction to the otherwise excellent explanation above:
The top node will of course not always intersect the frustum, but it should always be evaluated in order for one to determine whether anything in the tree is visible. Obviously, mhagain suggests that if we need to check if a state is one of the 3 mentioned states, the root node could be set to the intersect state before every tree evaluation, to simplify things.
[/quote]

Absolutely correct, maybe something like "the top node is treated as if it intersects all 6 frustum planes"?

##### Share on other sites
[quote name='Ahl' timestamp='1309367339' post='4829147']
I guess I'm just not getting this. I understand checking the tree against the view frustrum. I'm not understanding how you build this tree.

[quote]You know the dimensions of your world, say it's 8192 units in each direction.[/quote]

I'm guessing this means that if my world is a giant box 10k*10k*10k then that's what I split my nodes up into? Split that up into consecutively smaller sections of 4 (or 8)? So if a node is within my view frustrum it gets drawn and all it's children nodes get checked and drawn (if visible) until we run out of nodes or the nodes are no longer visible? Is that right?
[/quote]

That sounds roundabout right. Your top node will enclose a 10k*10k*10k volume, and (assuming an octree) each child at the next level is 5k*5k*5k.

The key bit of info that I skipped over above is that you test bounding boxes of nodes against the frustum, not bounding boxes of objects. The bounding box of an object is just used for inserting the object into the correct node, and from there you'll have groups of multiple objects in each node. By testing node bounding boxes you get to accept or reject multiple objects in one fell swoop.

##### Share on other sites
I was sitting in my Linear Algebra class and in dawned on me how this whole thing works. I think I get it now, but I still have a few questions:

1: This one you already answered to a degree. What do you do with large objects? You (mhagain) said use an objects bounding box to determine the correct node to insert it in. That makes sense for objects whose centers are outside of view frustrum but protrude into the visible scene anyways. It makes sense that you'd want your largest models in your largest nodes. I'll get to my question for this is a second...

2: I can see how Quad-tree/Octree frustrum culling would be great for large static scenes. How about scenes with a LOT of moving objects? Unless there is a method here I'm not seeing, rebuilding your tree every frame would get expensive in a hurry and undo whatever optimization you might otherwise get.

I guess that pretty much sums it up for now; How do you handle your trees with a constantly changing scene?

##### Share on other sites
You'd just build the tree once (at load time) and then insert objects into the correct nodes during runtime. Yeah, it's potentially expensive with lots of objects, but that's a tradeoff versus the savings you make by not having to draw them (and by being able to trivially reject huge numbers of them in one fell swoop). In general terms the tradeoff works on the side of higher performance, but sometimes it doesn't (I mentioned particles as a possible case where it doesn't above, there are very probably others). That's where knowing your program, and pofiling it to determine where the bottlenecks are, comes in.

Large objects are a special case; with a traditional octree they tend to "bubble up" to larger nodes which reduces the effectiveness of the octree. Loose octrees ([url="http://anteru.net/2008/11/14/315/"]good description here[/url]) are a solution to this. They're also good for your last question - moving objects - as inserting an object into a node is faster than with a traditional octree.

##### Share on other sites
It seems the trade off is in whether the CPU or the GPU does the culling (my understanding is that the GPU does do culling on its own?) I guess I'll have to play with it to see what I can do...