Implementing an Octree, seeking some advice

    This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

    • Implementing an Octree, seeking some advice

      Hi all,

      I've been working further on my scene-graph, and decided to implement an Octree to keep track of the static geometry in my scene.

      Rougly, my scene currently looks like this:

      RootNode
      - staticGroup
      -- octreeRootNode
      --- 8 child octreeNodes, which can contain 8 child nodes again, also each octreeNode has a vector of MeshInstanceNodes
      - dynamicGroup
      - skyGroup
      - invisibleGroup
      This hierarchy is based off the one described in the book, and I'm also basing it off of this discussion: gamedev.net/topic/110342-terrain-and-scene-graphs/ (post number 6 by Yann L)

      Basically I've created my own Octree structure that plugs in perfectly with the scene graph. The OctreeRootNode does the overlaying management of checking visibility of the MeshInstanceNodes in the child octreeNodes, and then renders these efficiently.

      However I'm not entirely sure how I want my octree to be set up initially, and how inserting new meshInstanceNodes should affect the Octree's structure. I'll describe my current algorithm a bit, and its shortcomings:
      - The octree has a limited depth, let's call it DEPTH_LIMIT (say 10 levels of child octree nodes), and a limited amount of mesh instances that each child octree node can contain which I'll call MESH_LIMIT.
      - Initially there is only one Node, that of the root node.
      - When a new meshInstanceNode wants to be inserted, first a test is done to see if the mesh will physically fit inside the octree node. If succesful, a test is done to see if the octree node has enough room in its vector (comparison with MESH_LIMIT), the node will then add this mesh instance to its list if the limit isn't exceeded. However, if the limit is exceeded, the node is split into 8 child nodes (if allowed by the DEPTH_LIMIT), all the nodes are re-distributed into the child nodes, and an attempt is done to add in the new mesh Instance Node into one of the new child nodes.
      - The addChild method is recursive, as the previous sentence roughly describes.
      - If the attempt to add the mesh instance to the child node failed for any reason, it is simply left in the parent node of those children.

      There's a few other tidbits, but they're not as important to the discussion :)

      Hopefully my description is somewhat understandable to get the gest of what I'm doing. The drawbacks of this approach are:
      - you only do any node splitting on insertion of nodes
      - my last point in the algo description means that I'm left with "dangling" mesh instances in some parent nodes, and that not all the leaf nodes contain all the mesh instances per sé.

      My questions to you are:
      - should I already initially split up my octree into several sections, rather than starting off with just one node? If so, how "deep" should the octree be initialised?
      - would it be better to push all meshInstances as deep as possible into the octree, and for overlapping meshes keep duplicate pointers to them? Also, when doing visibility and rendering, how do you determine a distinction between these duplicates? (perhaps a flag in each MeshInstanceNode: detectedForRendering ?)
      - when should I split an octreeNode to create child nodes?

      I look forward to your feedback and suggestions! Thought it was best to get this important part of my scene graph done "right" from the start :)

      Oh btw, in the book you mentioned this neat debug-camera feature in which you could have a "backstage pass" into the game's mechanics. I also implemented this and am finding it very useful :D[list]
      [/list]
      Cheers and beers from Belgium!
    • RE: Implementing an Octree, seeking some advice

      Originally posted by L0d3man
      - should I already initially split up my octree into several sections, rather than starting off with just one node?

      You can do it either way, it depends on what the octree is really being used for. I usually set it up initially.


      If so, how "deep" should the octree be initialised?

      This completely depends on your game and the level you're building. The unsatisfying answer is "deep enough, but not too deep". This is one of those things you have to play with to get right. Often times, each branch on an octree or quadtree can have different depths. See the example here for quadtrees:
      en.wikipedia.org/wiki/Quadtree


      - would it be better to push all meshInstances as deep as possible into the octree, and for overlapping meshes keep duplicate pointers to them? Also, when doing visibility and rendering, how do you determine a distinction between these duplicates? (perhaps a flag in each MeshInstanceNode: detectedForRendering ?)

      By definition, a quadtree or octree shouldn't have anything in a non-leaf node. Duplicating pointers for meshes that overlap a boundary and having a flag is the most straight-forward way of handling this issue. Another way is making the algorithm that builds the initial octree setup smart enough to never split on a mesh boundary. This would cause each branch to be at a different depth, but that's usually fine. This can also cause a lot of issues if you happen to have geometry splitting in inconvenient places. I'd stick with the duplicated geometry and flag.


      - when should I split an octreeNode to create child nodes?

      At initialization time, usually.

      One piece of feedback I have is that I wouldn't attach an octree directly to the scene. I would organize my objects (static and dynamic) into an octree or quadtree independent of the scene. As objects move around, they'd reinsert themselves into the tree. The whole point of something like an octree is to be able to find objects that are close to some point or within some box. You can ask the question: what objects are within 10 meters of me? With an octree or quadtree, you only have to search a few nodes to find that answer. It can control rendering as well since you're asking the same question. What objects are within this frustum?

      I'm also not convinced you want an octree. Most of the time, you actually just want a quadtree because most games are pretty flat. If you pull the camera all the way back, most games take place on a plane, or a series of planes (especially outdoor games). If you pull back and your level looks like a cube, an octree is the way to go. A space fighter simulation is a good example of this type of game. If you're game is mostly flat, a quadtree is probably best. This is true even in 3D games. For example, we use quadtrees on The Sims.

      -Rez
    • Thanks for your feedback.
      The unsatisfying answer is "deep enough, but not too deep".

      Ironically the answers provided about octree initialisation/duplicates were satisfying to me :)

      The reason I wanted to include my octree into the scene graph was so I could merge the hierarchical representation of my objects via the scene graph, with the spatial partitioning benefits of octrees/quadtrees. This means that even static geometry could have hierarchical relations in the scene graph, for example a static tree could have a static apple. The MeshInstanceNode class is set up to have child-nodes. But for actor finding, collision detection, I could still just have a look in the scene's octree as: scene->getOctree()->findActor(id);

      I was going to keep a seperate octree for static objects, a seperate one for dynamic objects, and for my terrain I wanted to use a quadtree to contain the terrain patches. Our game will have flying entities as well, therefore I think at least in the dynamic case an octree would be a good choice. The terrain will also be dynamic, so it can range from flat valleys to hilly vistas. Therefore the scenery on the terrain would be arranged more "cube-like" rather than flat on a plane.

      That said I am of course also always interested in your comments upon such a merging of hierarchical scene graphs with spatial partitioning systems. I personally don't really see what's bad about plugging it into the scene-graph/why I should keep it seperately :)
      Cheers and beers from Belgium!
    • When I say cube-like, I mean in density. A lot of games have flying creatures, but they make up a small amount of the total geometry. Ignoring Y and just splitting on the X/Z plane is usually the correct choice. Still, it's easy enough to change to go with your instincts and see how full your leaf nodes are.

      The way you're plugging in the octree just seems a bit wonky. If it were me and I decided to use an octree, I wouldn't bother with the scene graph the way it is. I would just use the octree for everything and have each leaf contain the appropriate scene node (which can each contain children for attached geometry, of course). I'm not sure how much win you're getting by separating everything.

      Still, as I said, follow your instincts and refactor where necessary.

      -Rez
    • Seems to me that using the oct or quad tree structure would be somewhat helpful in visibility culling and level of detail calculation for groups of objects, especially for detailed environments - depending on how the environments were structured.
      Mr.Mike
      Author, Programmer, Brewer, Patriot
    • Originally posted by rezination
      follow your instincts and refactor where necessary.

      -Rez


      Will do. Again, thanks for the input! Look forward to showing some of the progress once it's reached a more mature state :)
      Cheers and beers from Belgium!

      The post was edited 1 time, last by L0d3man ().