Octree for dynamic objects

Well the best behaviour depends on the typical speed of objects vs octree nodes, number of dynamic objects in the scene, density of objects in the scene, the size of the scene and various other factors. Firstly if you know the objects will not move that much, you don't actually have to place them back in the tree from the root, you can potentially reinsert it from the parent node of wherever it currently is (this can save time when the tree is very deep). It's quite possible to have a suboptimal octree for dynamic objects integrated with an optimal octree for static parts of the scene, that's to say the dynamic objects always sit at a certain depth in the tree that is considered minimal... eg every branch of the tree has a depth of 4 and those depth 4 elements are the only place that dynamic objects are placed (like a fixed grid) but static scene elements may be placed much deeper in the structure to provide more optimal culling. Basically you can't say generically which will be best, you just have to decide. If you have more specific info about the nature of the application, then maybe you can get some more specific advice.

Dan

Quote:

It's quite possible to have a suboptimal octree eg every branch of the tree has a depth of 4 and those depth 4 elements are the only place that dynamic objects are placed

So I must allocate all the 4-th level nodes including empty ones at octree creation time. Yes?
And, say me please, how to determine nodes which contains specified object (bruteforce, node pointers list in object class or any better way?).

Quote:

If you have more specific info about the nature of the application, then maybe you can get some more specific advice.

Yes, I can say several things more about my application. It's non-professional engine that's developing for outdoor RPG. So:

speed of objects and the size of the scene - Hmmm... Let the scene will be 1000*1000*200 (x*y*z) units and object's size is near 2*2*2 - 10*10*10. Movement speed will be varying from really small values up to 5-15 units\sec, but teleportation is possible too (in fact it's not a movement, and it's a bit confusing me).

number of dynamic objects in the scene - I think, up to 200, but now I can't say exactly. 200 seems to be more than enough now (excluding static animated geometry)

density of objects in the scene - up to 25-30 objects in group (dynamic, nearly placed), but groups from 1 to 7-8 will be much more common. These groups are at least 10 units from each other. If you need static objects density too, than add up to 25 static objects (eg trees in the forest) to the values above. I hope you can imagine what I try to describe.

If it's not enough, ask me more and I'll try to answer.

Thanks.

Here's how I do it for my physics engine. I use a few things to dramatically speed up the re-appropriation of objects to nodes every frame.

1. keep a pointer to it's current node for each object, as well as it's index in the node (for quick removal).
2. each node has a pointer to it's parent node.

here's the initial insertion algorithm:
1. add object to a node
2. node checks to see if it can completely contain object
3. if not, it adds the object to it's parent node
4. if yes, then we see if this node has any other objects children
5. if it has no objects or children, then we can stop subdividing as place the object in this node
6. if not, then we see if the object can be entirely contained by any of it's children
7. if yes, then we add the object to the child which could contain it.
8. if not, then we add it to this node.

here's the re-appropriation algorithm:
1. check to see if an object is contained by it's current node
2. if yes, then we check to see if it needs to be added to a child (step 6 from above), then stop if not.
3. if not, then we go one level up the hierarchy and see if the parent can contain it.
4. this ends either when we run out of parent nodes or when we find a parent which contains it.
5. after we find a parent which contains the object, we then make sure we can't add it to a different child

the effect of this algorithm is that objects travel the shortest path in the hierarchy to be a correct state. generally, objects will go up a level of the hierarchy, and then be place in children of that higher level.

the beauty of this system is that there is only one copy on an object in the tree at any one time, which makes for fast removal, and that object re-appropriation is very fast.

heres how fast this is: i get an average time to re-appropriate 1000 objects in close proximity of 0.4ms on my machine (2.16ghz Macbook pro) running on only one core. for 10000 objects running in the same space, it takes 9ms. Of course, this is only for the re-appropriation. Doing actual collision detection is much slower.

Quote:

Original post by Aressera the beauty of this system is that there is only one copy on an object in the tree at any one time, which makes for fast removal, and that object re-appropriation is very fast.

Thanks a lot. I understood your algorithms and will try to implement it. One question. Do you use standard or loose octree?

Hej folks !

I would like to hint you to a GPU-based quadtree generator, see:
http://www.mpii.de/~gziegler

I am currently aobut to crank it up to an Octree version, which I haven't yet released - but I am pretty sure you figure a bit of it reading the Quadtree version ;)

Let me know what you think !

-Gernot (real-time graphics researcher)