17 replies to this topic

[Ahl]

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.

Thanks in advance...

[zacaj]

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?

[Ahl]

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.

[zacaj]

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)

[jeroenb]

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.

[Ahl]

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?

[zacaj]

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:

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

then you just call it with
level=0
pos=the top left of your world,
and size=size 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.

[mhagain]

Just to elaborate a little better here.

Each node of the tree can be in one of three states:

• Fully outside the frustum
• Fully inside the frustum
• Intersecting the frustum

As all child nodes are enclosed by the volume of their parent, the rules become:

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

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:

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
	TraverseQuadTree (n->children[0], frustumcheck);
	TraverseQuadTree (n->children[1], frustumcheck);
	TraverseQuadTree (n->children[2], frustumcheck);
	TraverseQuadTree (n->children[3], frustumcheck);
}



// check all 6 planes for the top node (63 == 111111)
TraverseQuadTree (topnode, 63);

[Ahl]

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

[mhagain]

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:

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

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.

[SuperVGA]

The top node will always intersect the frustum as it contains all of your geometry.

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.

[Ahl]

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.

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

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?

[mhagain]

The top node will always intersect the frustum as it contains all of your geometry.

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.

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

[mhagain]

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.

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

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?

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.

[Ahl]

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?

[mhagain]

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 (good description here) 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.

[Ahl]

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

[Ahl]

In terms of bounding boxes... Would it be better/easier to use a bounding sphere? Would axial aligned bounding boxes be better? Just a generic bounding box?