I was thinking of building a 3D engine beased on octrees - mainly because it's fairly easy to implement, and useful for visibility testing, collision detection, ray intersection testing, etc. However, I also realised that managing dynamic/moving objects in octrees is a real pain. Basically you'd have to update parts of the octree in real-time when the object moves. I was wondering if there is a efficient method for doing this? The scenery will be both indoors and outdoors.
It shouldn't be too difficult... all you need to do is go up one (or two if you don't want to worry about passing the node's boundary) nodes and re-test it. As long as your testing isn't slow this should be fine :)
I have some nifty octree code around here somewhere, I'll see if I can find it. IIRC Kalin has done this stuff as well, I'll see if I can get him to post some stuff too :)
If you want to use OctTrees or QuadTrees in a highly dynamic environment I would suggest using the "loose" variety, this means that each node size if double of what it usually is, and the nodes overlap somewhat. There was an article about this in the first Game Programming Gems book.
The looseness helps in a dynamic environment because objects would tend to migrate between nodes less frequently as each node's size is doubled at least. I would try and explain more of it now but it's late and I've just gotten home from New Years celebrations.
It really depends on the complexity & mechanics of your world. Even with an extremely fast subdivision algorithm things can slow down very quickly if you have too many objects moving at once.
Provide yourself with some flexibility; Not all objects need affect the tree. I've written different octtree implementations and one of them was designed with a static octtree and was only affected by static geometry within the scene (Once, at runtime). Dynamic objects used these nodes for world/object & object/object collision/physics testing and the node's PVS was used to determine object visibility.
This example worked well in the context I needed it for but might not suit your needs, especially if you remove the PVS system; Then you're left with a straight Object/Frustum test, resulting with an O(n) complexity.
I've got quadtree code I've written where I use a map (or you could write your own hash map if you don't like map's performance) to convert from object id's to node numbers (or pointers if you're so inclined) - so I can do a test to see if the moved object is still within the quadtree node, if it's not, I remove and reinsert into the quadtree.
Lots of optimisations one can do from there, but see how it performs first.