Sign in to follow this  
peter_b

culling moving objects? (quadtrees)

Recommended Posts

Hello. Im currently implementing quadtree view frustum culling for my terrain. Static objects like terrain pieces are easy but what about moving objects? Seems like alot of hassle scaning all objects each frame and removing them from their old node and inserting them into a new one. I havent seen any tutorials that mentions moving objects (i havent looked superhard either). Is there any trick to handeling them? This is still all alittle new to me and maybe im seeing a problem here when there is none? Thanks in advance.

Share this post


Link to post
Share on other sites
Quick lunch-time answer: loose quadtrees. See GPG1 for a discussion. It's not the only solution, but it does enable fast(er) object insertion and removal.

Share this post


Link to post
Share on other sites
I believe that the general approach to this is that you do remove and change the node's parent when it needs to be done. Note that this doesn't, and shouldn't, be done every frame.

Since you already have it partly implemented, I really see no reason to abandon what you currently have done. Quadtrees can be really effective, if done right [smile].

You may want to PM or email namethatnobodyelsetook, if he doesn't see this thread. I know that he implemented a very solid octree system, so he is sure to have a good understanding of it.

Share this post


Link to post
Share on other sites
What I do is perhaps not optimal, but it's easy to code, quick to run, and the non-optimal nature of it affects only a small number of objects. Anyway, what I do is this...

Your quadtree/octtree nodes should have a list of objects they contain. All levels of the tree have this list, not just the deepest level nodes.

When an object is added to the scene, it is added to the deepest node that completely contains the object. This means you only ever add the object to one tree node, rather than all the deepest level nodes it happens to cross.

When an object is moved, I search from it's current location up or down the tree. In most cases the object will move up a level (or a few), down a level(or a few), or up 2 levels, and down a neighbouring level of the one it was on. When moving objects, I remove the object from it's current list, and insert it into the new node's list. You need a list that doesn't own it's nodes. This means there is no new and/or delete operations, just a couple pointer changes. Quite quick, especially if you're using an Amiga style list (ie: has sentinel nodes so you never have to check for head/tail/emptylist conditions).

When doing culling, first you test if the quadtree node is visible, if so, test the objects in the node. As always, you also continue to test each quad-child node if the current one is visible. If you pushed the object into a several child nodes, you'd potentially check it for visibility several times, or require some kind of marking system to avoid the redundant checks.

So, when is this inefficient, or sub-optimal? When crossing the first few mid-points. Consider a 16x16 world. If the object is at, or near, (8,8), or on the line of (n,8) or (8,n) then the object will remain on the top level of the tree. Again, on the 4 and 12 lines it will remain only 1 level deep... However, your world is likely fairly large, and the percentage of time a few objects are stuck on a higher level of the tree than is optimal is probably fairly low. Most objects should lie in one of the deeper levels of the tree.

This is dead simple to write, quick to run. Sure it has some occasional less than optimal positioning, but I'm not convinced many apps would suffer much. Perhaps the effort of loosening nodes would be worth it... perhaps the extra code of a loose tree would slow things down more than a few ill-placed objects. It really depends on your app.

If you approach it right, you can switch between implentations without headaches. I've got my "SceneObjects", which are objects in a scene, independant of the "Scene". This means I can change the current scene object to from QuadTree to OctTree to BSP to a flat linked list and the rest of the game won't care. The return types and argument types will all still match. My API for the objects remains the same. If you do something like this you can try as many varieties of dynamic scene as you like, and the only thing that will change will be your initialization, creating the correct type of scene.

Share this post


Link to post
Share on other sites
Perhaps I'm the only one that's come to this conclusion, but I'll say it anyway.

I've found that for game actors (moving, dynamic objects) movement up / down the scene graph is somewhat redundant, depending on your bounding volumes for that object. Especially if you've thrown a bit more elbo grease into your rendering line.

In my schemes, regardless of bounding volume, an object that spans nodes is a child of both volume nodes. Inheritance of the 'Actor' class ensures that there's only one instance of an object ever sent to the pipeline. I have my SG position updates tied in with the same frames as my physics (IE only key motions)

Difficult objects (Ie, something that can span multiple nodes) is considered 'in' each, but the first one to get to the draw call sets the draw flag. The others just drop out, as the instance has already been handled.

One interesting way to do it:
If your physics system supports 'phantom' objects (ie, 'triggers') subclass your SG bounding volumes to these phantoms. Then, movements between nodes are actually handled as part of your physics processing, which requires a SG walk in and of itself. I created a version of this that worked quite well, all that was needed was a modification of the callbacks from the physics engine to those specific objects, to update the collision location flag. Worked pretty smooth.


~Main

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