Jump to content
  • Advertisement
Sign in to follow this  
NickGravelyn

Octree vs. Scene Graph

This topic is 4422 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

In a 3d game situation, which system is better for arranging data for effective rendering? My main goal is a capable engine that can handle things from first person shooters to larger RPG style areas (think a less attractive, but still as vast Oblivion world). I like how scene graphs are set up with parent nodes affecting attributes of the children, but the system doesn't seem to make much sense in culling compared to octrees. In an octree, if a parent node isn't visible, none of the children are. This is not true, however, in a scene graph. What are the opinions around GameDev.net about the two systems? What are some logical comparisons between advantages and disadvantages of the two? Any good links to both theory and implementation of the systems? Thanks for answering any of my questions.

Share this post


Link to post
Share on other sites
Advertisement
I would say (in my opinion, of course) that octrees are best used for static geometry... your static world geometry, for example, could be placed in the scene graph, but could simultaneously be stored in some hierarchical bounding volume (like an octree) to aid in culling when it is rendered.

Scene graphs are good for managing all of the geometry, including the dynamic stuff, with state changes, etc... I think that the two actually can complement one another, and aren't mutually exclusive.

Share this post


Link to post
Share on other sites
In my opinion the two aren't comparable. A scene graph is a way to represent relations between nodes in a scene. An octree is a culling technique. You can have a scene graph that has octree nodes to render larger geometry.

Quote:

I like how scene graphs are set up with parent nodes affecting attributes of the children, but the system doesn't seem to make much sense in culling compared to octrees. In an octree, if a parent node isn't visible, none of the children are. This is not true, however, in a scene graph.


If you are using the scene graph to cull, why would the children of a non-visible node be visible?

I would personally use the scene graph, and then use have an octree node that can take a mesh node and use an octree on it.

Share this post


Link to post
Share on other sites
JohnnyCassil is completely right. A scenegraph is totally independent of an
octree and vice versa. A scenegraph should be able to handle any spatial structure you want be it an Octree, a quadtree, a kd-tree, or even a bsp tree. Ideally an engine will support multiple spatial partitioning systems, because there is no be-all end-all spatial system that works perfectly in any situation.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Octree! Quick and simple!

Share this post


Link to post
Share on other sites
Just because this issue is close to home for me at the moment... I'm with JohnnyCassil as well. Build a scenegraph that handles relationships between objects in your worldspace, and then build a spatial subdivision structure (octrees are a fine candidate) where each octree node links into an arbitrary scenegraph node. Whether the scenegraph or spatial subdivision structure is actually responsible for holding geometry is up to you, but I personally favor having the scenegraph do it, and pass the transformed geometry into the subdivision mechanism for culling and other operations.

Also note that scenegraphs go exceedingly well with bounding volume hierarchies, which are admittedly not very widely used in polygon-based 3D engines, but can still be highly effective for certain classes of scenes.

Just note that when building your spatial subdivision data structure from the scenegraph-transformed nodes, you have to build from the bottom up: transform all nodes down to the leaves of the scenegraph tree, then work your way back up to determine (in worldspace) the bounding coordinates of each node.

Share this post


Link to post
Share on other sites
It may depend on the type of game and your engine structure, but I always try and split mine into two entities. The scene graph is useful to stick all you game objects into to represent spacial relationships and is easy to render from. Th octree is excellent for trimming down on visibiliy, collision detection, and physics.

Share this post


Link to post
Share on other sites
Luckily, I'm using Newton Dynamics for physics so collisions and such are handled for me.

I like the idea of using multiple systems, but how would I set up a scene graph that uses an octree for culling? Would certain nodes on the scene graph have an octree in them or am I thinking incorrectly?

Share this post


Link to post
Share on other sites
I personally have the nodes in my octree point to their corresponding nodes in the scene graph. For culling, they simply set a visibility flag in the node. Of course, I'm sure there are much better and more elaborate ways to handle it...

Share this post


Link to post
Share on other sites
Quote:
Original post by Sr_Guapo
I personally have the nodes in my octree point to their corresponding nodes in the scene graph. For culling, they simply set a visibility flag in the node. Of course, I'm sure there are much better and more elaborate ways to handle it...


Pretty much how I'd do it, too. I can't think of any benefit to a more complicated approach off the top of my head.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!