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...
Quadtree/Octree question...
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?
Unless I completally misunderstood your question. Is there some other part of dealing with quadtrees that you are calling sorting?
Author
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.
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)
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.
Author
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?
So I guess my question now is how do I generate this quadtree/octree?
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:
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.
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.
Just to elaborate a little better here.
Each node of the tree can be in one of three states:
Pseudocode might look like this:
Each node of the tree can be in one of three states:
- Fully outside the frustum
- Fully inside the frustum
- Intersecting the frustum
- 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.
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);
Author
Right, I get the theory there. What I don't get is how you build the tree from objects with x,y,z coords.
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:
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
