Archived

This topic is now archived and is closed to further replies.

PyroBoy

A couple easy spacial subdivision questions

Recommended Posts

First off, apologies for asking a question that''s probably been asked before, but the forum search is timing out... Anyway, I''m getting into spacial subdivision culling, using quadtrees/octrees, and I''m pretty familiar with the basics - divide the world up, placing objects into different areas of the tree, depending on their position in that world, and recursively traverse the tree to grab what needs rendering and toss out what doesn''t quickly. Nifty. A couple questions though: 1. What do you do about moving objects? Eventually they''re gonna cross over a subdivision boundry, and the data(pointer to that object, sitting in the tree I''d assume) is going to need to be moved... Isn''t it? What do you do about it? Does an object''s place in the tree have to be updated every time they move? Wouldn''t that involve a trip through the tree to find the new spot? Wouldn''t that be pretty slow with a lot of moving objects per frame? 2. Assuming there''s a minimum size of sub-division, what do you do if an object is sitting right on a boundry? Do you put the object into 2 "cells" of the tree at the same time? And wouldn''t updating *that* for a moving object be a pain to implement correctly? And assuming that minimum subdivision size is smaller than some objects in your world, what do you do about objects that are bigger than the smallest subdivision?

Share this post


Link to post
Share on other sites
Most of the time people seem to store only their static geometry in an oc-tree, and store it at the polygon level.

However, there''s a few things that I have found helpful when adapting the oc-tree structure to work with dynamic objects. Most importantly, sort things into your tree with bounding spheres or some other simple representation that can be tested rapidly against the node division planes.

When re-adding an object after it has moved, I find it quicker to traverse UP the tree from the object''s ''old'' node to the first node which contains the object in its new position, then recurse back DOWN the tree in the normal fashion to find its new home. This will slow down the algorithm if an object suddenly jumps to the opposite side of the world, but will be much faster for cases when objects simply move to a neighboring node.

As far as your second point, you can eliminate this issue by adding objects only to the smallest node that wholly contains them. This evades the multi-node issue, but presents the possibility of many very small objects sitting on the boundary plane of the root node, which would damage your ability to frustum cull accurately.
On the other hand, you can set a maximum number of nodes that an object may fall into (certainly less than 8 or you might as well add it higher up), and store pointers to those nodes with the object itself. I haven''t tried this version yet, or thought about how this approach will work with the shortcut re-add function described above, but it''s an idea .

-Matt

Share this post


Link to post
Share on other sites