Sign in to follow this  
NickGravelyn

Octree vs. Scene Graph

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
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
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
Quote:
Original post by Cote-Duke Tech
Then what? Go through entire scene-graph and render objects with visibility flag set to true? That's not the best way :)


If it suits one to completely overcomplicate the entire affair; When one sets the flag to true, they can also push a pointer to said object onto a "Please Render" stack at the same time.

However, that is pure overkill when a for-loop or container iterator (allows for easy depth sorting) would do just fine like suggested above.

And besides, if an object isn't to be even considered for rendering, what the heck is it doing in the scene graph in the first place? This is why these things are "disabled" temporarily, or completely removed altogether if it's a dynamically instantiated object.

Share this post


Link to post
Share on other sites
Oh, well. There is no strong definition for Scene Graph itself. But usually,
Scene Graph used to represent entire scene, not just visible part.

Now, since scene may contain fairly big amount of reneder assets, going
through entire scene graph each frame to render just some nodes (the visible part) is not the best solution. Think of the overhead.

Best way is to separate. Culling is one thing and Scene Graph is another.
While you cull (via Octree, BSP, whatever you like) it's good to fill out
render queue on the place, so you'll end up with a list of objects to render.

This list should be much lighter than Scene Graph to iterate through.

Share this post


Link to post
Share on other sites
Most important points have been covered for you to consider, I'll just stick in a little extra info.

I'd go with separating the scene graph with any spatial information, meaning that the internals of your, say, octree is totally invisible to the scene graph. The octree is simply another node in the graph. This will help if you want to stuff in some other spatial information.

Using vis-flags for every single node will work well as long as the number of octree-nodes is rather small. Oblivion-sized landscapes, now these are not small [smile]. When it's time to render and you traverse your scene graph, at one point you will bump into a node which the scene graph is not really sure about, the octree. The scene graph tells the node "if you wanna get rendered, start working". Now the octree kicks in and does its "traversing and putting nodes into renderer queue thingie". Unaware of what just happened, the scene graph goes to the next node, tells it the same thing and on it goes.

Share this post


Link to post
Share on other sites
I keep hearing this suggestion of making a quad/oct-tree simply a node of the scene graph, but this introduces a huge problem as far as culling/collision efficiency goes. An object that lives outside of the quad/oct-tree (anything else in the scene graph according to this proposed method) looses the benefits of spatial locality that would otherwise be available if objects existed inside the quad/oct-tree's heirarchy. Instead, you propose to search from the root of the octtree heirarchy for every query. Thats seems absurdly inefficient to me.

Take the example of very large terrain implemented via geomipmapping (a good choice considering how well suited a quad-tree struture is to the algorithm for collision/culling purposes). Suppose this terrain is covered in various objects such as trees, fences, small buildings, furniture, potted plants, trash cans, vehicles, etc. Each object lies on a terrain patch. Why not place these objects in the same quadtree structure as the terrain. If a peice of furniture is flung into the air by an explosion, its most likely to hit a piece of terrain nearby. By simply stepping up the quad tree, spatial locality ensures a fast collision query most of the time (except when queries cross quad boundaries at higher levels in the hierarchy.)

Alternatively, in your approach, every object lives outside the quad tree. A collision query would involve both the spatial subdivision struture that objects exist in (such as a seperate bounding volume heirarchy) and the quad tree structre...starting from the root. As I said before, the terrain could be very large, and hence the quad-tree structure would be very deep.

If your argument is that dynamic objects are never stored in the same structure, then at least part of my argument would still apply. A query would always involve both the quad-tree as well as whatever other seperate spatial subdivision structures were used. While it makes sense to nest spatial structures inside each other, a quad/oct-tree is an exception because it is usually employed to subdivide things that have a massive span across the game world. (As opposed to a building which is relatively small and could efficiently be subdividied using say... a BSP tree). As a result seperating them severely inhibits culling/collision efficiency.

With modern games having more and more of a dynamic nature, where most things can moved and changed in various ways, is a structure that establishes an abstract relationship between objects in a scene valuable at all? The most classic example i see is books on a bookshelf, where the books are children of the shelf. Who cares what shelf the book "belonged to" if you can rip it off the shelf, carry it with you, sell it, or place it on another bookshelf miles away for where you originally found it. It seems like spatial structures are by far the most useful for most aspects of a game's functioning.

Of course, these are only my opinions and observations. I would love to get some crtiticism on this and see what other propose, and possibly some new alternatives. I suspect to often, information is propagted that sounds good in theory, but is wildly different in applicaiton. Does anyone have some hard-core experience and the tales of woe that go along?

And before you go and say, "Your missing the point, a scene graph is a seperate thing.. bla bla", tell me then was the point of putting a spatial structure in the scene graph at all if its "a seperate thing". Ultimately, the goal at hand is finding an efficient way to combine, nest, or otherwise use different spatial structures at the same time.

Share this post


Link to post
Share on other sites
Introduction:
Good points samgzman, I can't say I have rock-solid experience on this and I won't discuss this thing with terminology and definitions in focus.

And now the discussion:
Most games will probably benefit from reusing spatial data structures, which saves memory, retraversing overhead and the lot you described. This is the most straightforward solution and it will work most of the time.

The reason I don't do it this way is that I'm working on a general-purpose plugin kernel (which doesn't even know what rendering is) where I prefer not to have a clue at all what will be put into the scene. Number of objects, object clustering, object sizes, nothing. For a particular application, I could probably write a custom scene graph to take care of it, but a general solution would be much easier in the long run. I also aim at rather scalable results so the "minor issues" with objects going amok high up in spatial structures isn't really minor. There are ways which are rather complicated but I won't get into that here...

You're right in that logical relationships start to lose meaning as games become more open and dynamic. I wouldn't bind books into a bookshelf in my scene graph as that relationship is doomed to be messed up by the player as fast as he sees the opportunity. My scene graph is simply a container of objects that exist in the scene and due to the plugins, there will probably be very few exposed parent-children relationships which instead will be taken care of "in the dark" by the plugins. The scene graph still gives a feeling of confidence in scene managing as everything is automatically handled.

This approach takes time and it's really hard work. But, as it's only a serious hobby of mine and not in my line of study, I got the time to live out my dreams [smile]

Share this post


Link to post
Share on other sites
Putting the scenegraph "into" the spatial subdivision structure (or whatever) is obviously silly. That's not a good approach. What's been suggested is to have totally separate structures, except with one pointing to nodes in the other to retrieve things like geometry meshes. That method does solve efficiency problems, does preserve logical groupings, does promote clean code design, and does make effective use of storage resources.


Subtleties in terminology may be small, but that doesn't mean they are not important.

Share this post


Link to post
Share on other sites
I often get into these discussions with misinterpretations [smile]. I generalized from old threads a bit.
Transforming every geometry node in the scene graph belonging to the octree/quadtree/ultratree is heavy and looping through them all to check vis-flags breaks the idea of trees. If the tree is use to remove things for processing, do it before anything else ("inverse" query in the octree, then only work on the geometry considered relevant).

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
... pointing to nodes in the other to retrieve things like geometry meshes ... does promote clean code design...


Not necessarily, lets assume a typical implementation by doing this you've introduced a dependency with a particular scene graph, this makes your spatial data-structures tightly coupled with the particularities of your scene graph.

Whether this is acceptable or not depends on the context and is another story.

Share this post


Link to post
Share on other sites
Sure, there's coupling, but coupling is not always evil. Sometimes things make sense coupled. In any case, this is still a very loose coupling; it's still very easy to program to an interface and not an implementation. Honestly, if linking the two structures leads to a coupling to the actual implementation of either data structure, then the programmer has broken something by introducing a poor design. That doesn't necessarily mean that the design concept (separate, linked structures) is at all to blame.

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
Sure, there's coupling, but coupling is not always evil. Sometimes things make sense coupled.


As i said already whether this is acceptable or not depends on the context.

Quote:
Original post by ApochPiQ
In any case, this is still a very loose coupling; it's still very easy to program to an interface and not an implementation. Honestly, if linking the two structures leads to a coupling to the actual implementation of either data structure, then the programmer has broken something by introducing a poor design.


I wouldn't quite call it loosely coupled because really it isn't, obviously it's better to depend on an interface than an implementation i'm not debating that but the fact of the matter is you've still tied it to one particular interface, in this context some abstract scene graph node. One cannot reuse this spatial data structure any where else.

There are various methods to make them more/less loosely coupled all with different levels of abstraction and/or levels of indirections and all with different trade-offs.

Quote:
Original post by ApochPiQ
That doesn't necessarily mean that the design concept (separate, linked structures) is at all to blame.


I'm not saying that, all i'm saying it isn't quite as "clean" or loosely coupled as you make it out to be but one has to eventually make a choice and it all depends on your requirements.

Share this post


Link to post
Share on other sites
Eh, fair. I guess the degree of looseness to the coupling is partially subjective. But yes, it does introduce some dependencies between the two systems.

Really, though, that's more or less academic, since the two systems are fundamentally interrelated by nature.

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
Really, though, that's more or less academic, since the two systems are fundamentally interrelated by nature.


I wouldn't call it academic, it all depends on the context and requirements and i wouldn't say there "fundamentally" interrelated yes maybe indirectly but a scene graph is not a fundamental concept in the problem domain of spatial data structures.

Spatial data structures are data structures that deal with multidimensional data. The algorithms which build these structures take geometry as input, there typical is no notion of scene graphs in there definition.

Share this post


Link to post
Share on other sites
Yes, but we're talking about game graphics engines here. If you refrain from inflating the problem domain to arbitrary scopes, then spatial subdivision and scenegraph structures are closely interrelated, because they solve nonorthogonal problems within the domain of building the graphics engine [wink]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this