Jump to content
  • Advertisement
Sign in to follow this  
RandomAxess

When to resize nodes in Dynamic Octree?

This topic is 3968 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everyone, I'm writing a simple dynamic octree. It doesn't split objects, rather has an object threshold and tries to insert objects into the deepest location it can. It generally has the following functions: -InsertObject: will determine if an object lies on a splitting plane in which case inserts into the current node (this is the deepest node it can go into). If not, we insert into the appropriate child -DeleteObject: called from the object itself, to prevent unneccesary polling of the tree. this will remove the object from a node. Now, that's the real basics. here's my problem: When objects get inserted or deleted, the size of the node and all parent nodes might increase or decrease. I want a method of recursively re-sizing when appropriate, and I have come up with a couple ways: Method 1: -WHen calling InsertObject, after insertion, check to see if the node needs resizing. if yes, resize it, then recursively move up to the root, resizing as neccesary. -When calling DeleteObject, similarly delete the object, check if the node needs resizing, and move recursively up to the root. I'm pretty sure these are both O(log(n)) runtime, O(n) if highly unbalanced tree. However, we are going to do this every time an object is inserted/deleted. could be a bit slow... Method 2: -when inserting/deleting, mark if the node needs resizing, continuing to move up to the root as neccesary -have a seperate function, AFTER all inserts and deletes, resizes the marked nodes recursively from root down. Alternatively, load pointers to nodes into an array, check each array if the resize bit is true. if true, resize recursively to root. this memo-ized version could be faster. The benefit here is that we don't re-size everytime we insert / delete, we just do it all at once at the end of all inserts and deletes. So, instead of inserting / deleting 1000 times for 1000 objects, we just do it all in one shot. Which implementation is really "better?" Thanks!

Share this post


Link to post
Share on other sites
Advertisement
I think there may be a problem in your description or in your understanding of quadtrees. Why would a node need to be resized? More importantly, quadtrees tend to be an overcomplicated and inefficent way of organizing dynamic objects.

Share this post


Link to post
Share on other sites
Hi Vorpy,
Yes, typically octrees / quadtrees are used for static data, and they work great. However, there is also implementations for dynamic octrees that work really well for a lot of things: culling, collision detection, etc.

here's a paper describing what i'm trying to do: http://www.cs.nmsu.edu/CSWS/techRpt/2003-004.pdf

surprisingly, dynamic octree isn't as bad as it sounds. it can get very good results if done properly.

what would you suggest instead?

Share this post


Link to post
Share on other sites
For dynamic data, I'm currently partial towards using uniform grids. I guess that dynamic octtrees could potentially have some advantages, such as being able to adjust to more closely fit the data. I don't think I've seen anything before about a quadtree that keeps track of the bounding box of the contents of every node.

I'm pretty sure the method 2 you describe would be better, assuming the objects in the tree were moving around. If two objects in the same node were moved in one frame, you should only need to recalculate the bounding box for that node once. The only way to do this is to keep track of which nodes need to be updated and then updating them after the object updates are complete for that frame.

It might even be possible to compute the AABBs only when needed, since it seems they are used only for the queries, while the splitting planes provide enough information to place objects in the correct nodes. During a visibility query it should be possible to cull sections of the tree based on the parent AABB without even needing to update the marked children nodes, since it is possible for children nodes to be marked incorrect without the parent becoming incorrect as well (such as when an object that was not flush with the side of its parent node's AABB is updated).

Share this post


Link to post
Share on other sites
RandomAxess> well, the thing is, octree nodes don't need "resizing".
you may need to split a node and create its childs, or to merge 8 nodes together and go back to their parent node.
but in an octree, there is no notion of resizing a node. the split planes can't be moved around (as long as we're talking about the common definition of an octree in game programming, that is: all splits are median-splits, unlike, say.. a Kd-Tree, in which you may resize nodes (or more exactly, change the position of split planes))

now, perhaps your implementation of an octree has an additional bounding box for each node, that allows you to refine the tree faster than only with median splits.
but then it isn't a "standard" octree any more (or at least, it isn't what most people here would refer to as an octree)

what you may need to do, instead of resizing, would be to decide, depending on some treshold, and the number of childs in a node and its brothers, wether to split the node, or to merge the node and its 7 brothers into their parent.

EDIT: hm.. 5h30 cross-post, the tab remained opened in firefox, sorry...

method 2 does seem better too.. although it depends on the number of inserts/delets you will usually do per frame... if you only make a few, it'll very likely cost more to walk the whole tree every single time...

(and if you don't resize, but only refine/merge, you don't need to walk up the whole hierarchy each time, you can have an early exit)

[Edited by - momotte on February 3, 2008 10:06:40 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!