Octrees and Scenegraphs... how do they work together?
Hi,
Previously in my little game projects I've used an Octree to organize the static geometry and a simple list to keep track of anything movable.
I've been looking into using a scene-graph to organize everything for rendering, but I can't figure out how the scenegraph and Octree work together so that I can use the Octree for culling.
I've had a look through the Ogre source code and started implementing some basic (empty, non-functional) classes based on that. So at the moment I have a SceneNode class to which I can attach other SceneNodes or Entitys. And I've got an empty Octree class, and a basic SceneManager class which contains the root SceneNode...
I understand completely how the SceneNodes work together but I can't figure out how Ogre uses the Octree in this.
I can see that the SceneNode hierarchy will allow me to neatly manage the scene, and the Octree will provide efficient culling, collision etc. for the scene, but I just can't figure out how to tie it together, can anyone explain this to me?
Having never used it I can't speak for Ogre.
One common approach is to make the octree a node in the scene-graph, if necessary other scene-graph nodes can contain pointers to the leaf-nodes of the octree representation.
There's actually a wealth of info about this topic on GDNet, here's one of them.
Combining scene-graph with spatial partitioning structures seems to be somewhat of a dark art and the best method is a rather subjective issue.
One common approach is to make the octree a node in the scene-graph, if necessary other scene-graph nodes can contain pointers to the leaf-nodes of the octree representation.
There's actually a wealth of info about this topic on GDNet, here's one of them.
Combining scene-graph with spatial partitioning structures seems to be somewhat of a dark art and the best method is a rather subjective issue.
I think some engines update objects' positions in the spatial data structures whenever they move. In a scene graph, any objects that are children of an object that was moved will also need to update their position in any spatial data structures they are in.
Another way is to keep a list of all the objects that have moved during the current update cycle and then go down that list updating their position in the data structures. This avoids calculating an object's position in other data structures more than once per frame, but it also means the data structures won't necessarily have current information until the updates are run. For rendering this is fine since you don't render states that exist during an incomplete update. For collision detection this could be an issue depending on how you are handling collisions.
Another way is to keep a list of all the objects that have moved during the current update cycle and then go down that list updating their position in the data structures. This avoids calculating an object's position in other data structures more than once per frame, but it also means the data structures won't necessarily have current information until the updates are run. For rendering this is fine since you don't render states that exist during an incomplete update. For collision detection this could be an issue depending on how you are handling collisions.
Hmm, OK I've been thinking about this all day and I just can't decide on the best approach. If I use an Octree I need to be able to know about the static geometry of the world so I can build the tree.
If I add the octree to the scenegraph I need to attach the static geometry to it first before adding it to the graph, that's not a problem, but then I should really sort the polygons in the world into a scene graph to manage materials etc. So the only solution to that I can think of is that each octree node has a mini scenegraph just for the static geometry.
Then I'd need to attach the movable entities to the main scene graph so now I have something like this:
But now the Octree stuff seems a bit specific. To me the Octree doesn't even seem like it should be in the scenegraph at all.
So if I separate it, now we have something like:
So now imagine I have the scenegraph and the octree which is built around the static geometry. The objects in the scenegraph have pointers to the octree nodes that they are contained in. But how do I traverse the nodes?? Would I just traverse the whole scenegraph, then if the linked octree node is visible I draw it?
This seems to make sense to me. Is this a good approach?
If I add the octree to the scenegraph I need to attach the static geometry to it first before adding it to the graph, that's not a problem, but then I should really sort the polygons in the world into a scene graph to manage materials etc. So the only solution to that I can think of is that each octree node has a mini scenegraph just for the static geometry.
Then I'd need to attach the movable entities to the main scene graph so now I have something like this:
root / | octree movableentities / octreeNode etc. / textureNode / staticPolygon
But now the Octree stuff seems a bit specific. To me the Octree doesn't even seem like it should be in the scenegraph at all.
So if I separate it, now we have something like:
octree root / \ / | octreeNode octreeNode etc. staticent movableent / | staticPolygon monster
So now imagine I have the scenegraph and the octree which is built around the static geometry. The objects in the scenegraph have pointers to the octree nodes that they are contained in. But how do I traverse the nodes?? Would I just traverse the whole scenegraph, then if the linked octree node is visible I draw it?
This seems to make sense to me. Is this a good approach?
Traversing everything in the scene graph to determine which objects are visible and need to be drawn defeats ones of the main purposes of using an octtree. Using the scene graph like this will require looking at every object and won't scale well as the number of objects increases.
The octtree scales better because you only traverse the objects that are in the visible nodes. The number of objects to inspect will be proportional to the number of objects that are actually visible.
From an octree node you should be able to find the geometry that node contains. Octtrees aren't particularly good for dynamic geometry; you should look into a more suitable method like a uniform grid or a "loose" octree (which are almost the same thing).
The octtree scales better because you only traverse the objects that are in the visible nodes. The number of objects to inspect will be proportional to the number of objects that are actually visible.
From an octree node you should be able to find the geometry that node contains. Octtrees aren't particularly good for dynamic geometry; you should look into a more suitable method like a uniform grid or a "loose" octree (which are almost the same thing).
The scenegraph is primarily (or at least generally) only interested in dynamic entities. Though it is common to have a node that represents an octree for example which houses all the scenes static geometry.
From the link I posted before take a look at Yann's prototype scenegraph:
Notice that he has a node for a quadtree and a node for an octree.
The exact implementation of, lets say, the octree is hidden from the scene-graph. It may well contain a separate tree of (octree)nodes, each leafnode may then have one or more buffers of vertices grouped by material. A bit like your first diagram except that everything after octree isn't part of the scene-graph, they're specialised nodes for the octree implementation (and my implementation and your's might differ considerably but we could plug them into the same scenegraph)
Putting static objects (likes trees and rocks) as individual nodes in the scenegraph isn't overly useful, you can have all your static geometry within one or more spatial partitioning structures and each structure is a single node on the scene-graph.
You may want to have some sort of spatial partitioning applied to the dynamic entities (that you do have individual nodes for), in which case these scenegraph nodes probably need to somehow reference the spatial structure (loose-octree or whatever). Note that since the scenegraph is the higher level structure that it references 'downwards' into the spatial structure, the spatial structure is at a lower level and requires no knowledge of the scenegraph above it.
From the link I posted before take a look at Yann's prototype scenegraph:
Quote:ROOT | |--- terrain node (geomipmapped quadtree) | |--- geometry of the village (static, octtree) | |--- Player (deformable skinned mesh) | | | |--- Torch (solid 3D object) | | | |--- Flame (volume renderer) | | | | | |--- Smoke (particle system) | | | |--- torch Lightsource | | | |--- torch shadow projector | |--- Big bad guy behind the player (skinned mesh) | |--- Big battle axe in the hand of the bad guy | |--- Dripping blood from the axe (particle system)
Notice that he has a node for a quadtree and a node for an octree.
The exact implementation of, lets say, the octree is hidden from the scene-graph. It may well contain a separate tree of (octree)nodes, each leafnode may then have one or more buffers of vertices grouped by material. A bit like your first diagram except that everything after octree isn't part of the scene-graph, they're specialised nodes for the octree implementation (and my implementation and your's might differ considerably but we could plug them into the same scenegraph)
Putting static objects (likes trees and rocks) as individual nodes in the scenegraph isn't overly useful, you can have all your static geometry within one or more spatial partitioning structures and each structure is a single node on the scene-graph.
You may want to have some sort of spatial partitioning applied to the dynamic entities (that you do have individual nodes for), in which case these scenegraph nodes probably need to somehow reference the spatial structure (loose-octree or whatever). Note that since the scenegraph is the higher level structure that it references 'downwards' into the spatial structure, the spatial structure is at a lower level and requires no knowledge of the scenegraph above it.
Hello
In OGRE, scene graph is a tree, which organize object aggregation. Octree is just another separate tree, which do space partition, culling etc. You can find “Octree”, “OctreeNode” class in OctreeSceneManager project. A scene graph node with mesh object will be attached to an OctreeNode. When the scene graph node have moved, OctreeSceneManager move it to the other OctreeNode, you can find the code in OctreeSceneManager::_updateOctreeNode(). SceneManager is just a manager class for both scene graph and octree.
In OGRE, scene graph is a tree, which organize object aggregation. Octree is just another separate tree, which do space partition, culling etc. You can find “Octree”, “OctreeNode” class in OctreeSceneManager project. A scene graph node with mesh object will be attached to an OctreeNode. When the scene graph node have moved, OctreeSceneManager move it to the other OctreeNode, you can find the code in OctreeSceneManager::_updateOctreeNode(). SceneManager is just a manager class for both scene graph and octree.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement