• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Ahl

Quadtree/Octree question...

17 posts in this topic

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

Share this post


Link to post
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?
0

Share this post


Link to post
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.
0

Share this post


Link to post
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)
0

Share this post


Link to post
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.
0

Share this post


Link to post
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?
0

Share this post


Link to post
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,
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.
0

Share this post


Link to post
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
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);[/code]
1

Share this post


Link to post
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.
0

Share this post


Link to post
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.
0

Share this post


Link to post
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.
1

Share this post


Link to post
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?
0

Share this post


Link to post
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"?
0

Share this post


Link to post
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.
0

Share this post


Link to post
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?
0

Share this post


Link to post
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.
0

Share this post


Link to post
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...
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0