I've lately noticed that Tom Forsyth has registered to these forums or at least so it seems as not much can be told from a username. There has been numerous discussions here on Scene Graphs. I've seen references to that article here and there, most of which also complain why an alternative is not presented if scene graphs are to be completely left out. It's working for a lot of people anyway. I am curious as to what alternatives he suggests and thought now that he has registered to these forums, it might be a good time to put this to discussion. It would be nice if you could shed some light on this, Tom. It would be even nicer if other people participate and see what we would get out of it. Thanks

My guess would be that the alternative is an immediate-mode drawing paradigm, in which per-frame scene bucketing comes from the objects themselves, as opposed to their scene graph representations.

Quote:Original post by Promit
This design mixes three unrelated structural ideas into one. First is the hierarchical culling structure. Second is the transformation hierarchy. Third is the optimal rendering order (for batching etc). These are three different trees, which are going to have different arrangements and different structures.

This is absolutely true, and having a single "scene graph" is nonsense for this reason alone. I did a term of full-time research related to scene graphs and graphics engine design and can say definitively that "traditional" scene graphs are a dead end.

That doesn't change the fact that you need some accelerator structures to do things efficiently of course, but one should always remember that they are just that: accelerators for specific tasks! In particular, a spatial accelerator is needed almost universally for doing things like culling and collision detection. Similarly it's often desirable to have a transform hierarchy, both for design and computational efficiency reasons. Often a unique scripting "view" of the game/scene is desirable as well, and the list goes on.

Thus what you need at the very least, is multiple "views" that "index" your scene "database". Indeed scene management starts to look more and more like a DBMS (although a full-blown one is certainly not required for typical games yet). Indeed it may be desirable to even have a *relational* structure for certain views, which certainly follows the typical data management pattern of things starting hierarchical and becoming more relational as they get more complicated, and more complex queries are required.

Usually, however, only a few simple trees or DAGs are required for a typical graphics engine. At the very least one will want "transform" and "spatial" views, but any number of views can be created that all index data that exists conceptually outside of any of these indices.

Incidentally this design avoids many common pitfalls of "uber scene graphs" when it comes to object orientation and polymorphism. People should have gotten the hint when they had to dynamic_cast stuff everywhere or create virtual functions that only make sense for a few classes in the hierarchy, but alas they did not. That's a particular pet peeve of mine in that people need to understand *why* a programming language is designed as it is, and *why* some things are hard to do. Often when you're writing awkward, brittle or inefficient code it's because you have a bad design to begin with...

Quote:Original post by Jason Z
The term 'Scene Graph' has so many definitions and permutations that you need to be very precise when you describe what you are talking about.

I think it has been made pretty clear that we're talking about a monolithic single-graph that is used for tasks that are largely unrelated (spatial culling and hierarchical transformations were cited both by myself and Promit). Performer is a good example of this, although OpenSceneGraph also suffers from it to a lesser degree. Often newer engines like OGRE actually separate out transform and spatial information nicely.

Quote:Original post by Jason Z
In any case, it doesn't make any sense to make a blanket statement that using a scene graph is 'awkward, brittle, or inefficient'. A graph is good at doing things that benefit from known graph based algorithms.

I didn't say the former at all - that was in the context of bad designs (in particular, scene graphs like Performer and so forth). I certainly agree with that latter; I said pretty much the same thing:

Quote:Original post by AndyTX
That doesn't change the fact that you need some accelerator structures to do things efficiently of course [...] accelerators for specific tasks!

Quote:Original post by Jason Z
As it turns out, the same graph can be used for culling since all of the information needed to transfrom a bounding volume is inherently included in the transformation hierarchy.

On this point I disagree, and I believe so would Promit and Tom Forsyth (among others). Even if a scene is very hierarchical in transformations, there is no reason to assume that *geometry* referenced by that graph is similarly coherent or in any way represented by the same structure as the transformations. Only the final "object to world" transformation matters (i.e. the path from the transform root to the node itself) - the underlying geometry should still be represented by a separate spatial index. Looking at a good spatial subdivision of a scene compared to its transform hierarchy makes this pretty clear (and these sorts of comparisons are easy to make if you have separated out the two graphs).

There are tons of examples where the transform hierarchy is a bad spatial hierarchy, even if the former is "deep". This is why almost all monolithic scene graph designs are forced to include "dummy spatial nodes" or similar that separate out portions of the graph even if the transformation has not changed. *This* is the mixing of functionality that we're advising against as it's nothing but bad news down the road...

Quote:Original post by Jason Z
I am certainly not as well versed as Tom Forsyth in these topics, but a basic understanding of your problem, coupled with a basic knowledge of data structures can get you much further down the road to solving a problem than someone telling you which way is better.

Oh I encourage you to go try this all out for yourself if you have the time. However its naive to think that the experience of others (who have gone through all of these design ideas already) is irrelevant, particularly considering that very little in game development is "novel" by itself... it's the combination of algorithms and the inherent software engineering that consumes most of the time and requires the most innovation.

Quote:Original post by Jason Z
Also, assuming that someone is a hack and doesn't understand a language simply because they don't use it according to your standards is a pet peeve of mine.

Firstly, people aren't "hacks", but programming certainly can be. Secondly, I have no problem with people using a programming language very differently than me, but there are certain fundamentals that are not up for debate. For instance: a software design that is centered around the use of dynamic_cast for multiple dispatch is inefficient and poorly designed (sure you can use it here and there, but it shouldn't be critical to the design). This isn't some rule of mine, it's part of the theory of programming languages and type safety, and there are many software engineering "design patterns" to allow people to avoid blunders like this and others. Anyways this is besides the point and getting pretty off-topic. I'd be happy to continue this discussion in PM if you wish.

Quote:Original post by Jason Z
If you think you have a better grasp on scene graph management, its benefits and detriments, and how to use them in C++ than Dave Eberly (who uses them extensively and has published several books, and many research papers) then I would recommend that you write a book to enlighten the rest of us on how to go about it.

Dave Eberly's scene graph designs are fairly usable in that they *don't* try to incorporate complex, unrelated indexing into a single graph (at least as far as the Wild Magic engine goes). Wild Magic does, however, combine transform and spatial into a single graph and I think you'll find that for larger, denser scenes (with physics and other queries) you have to do something a bit more sophisticated at which point you'll have to either start making nodes that are purely spatial (identity local transform), or separate the two pieces of data, which really don't need to be coupled anyways.

Anyways the following article actually sums up what I'm trying to say very well:
Scenegraphs: Past, Present, and Future. Tom's blog says pretty much the same thing: there's lots of information to index in a given scene in order to efficiently perform a wide range of queries, and there's no reason why we should push, squeeze and try to cram it into one monolithic "graph". Keeping separate accelerators for each of the unrelated queries is really much more efficient and reasonable.

Quote:Thus what you need at the very least, is multiple "views" that "index" your scene "database". Indeed scene management starts to look more and more like a DBMS (although a full-blown one is certainly not required for typical games yet). Indeed it may be desirable to even have a *relational* structure for certain views, which certainly follows the typical data management pattern of things starting hierarchical and becoming more relational as they get more complicated, and more complex queries are required.

That sounds catchy and I've actually come across similar statements quite a few times. The problem though is the implementation part. DBMS does no magic. It's all about data structures and if someone is going to implement a hierarchical tree-like structure to store nodes and use that in a DBMS, why call that a DBMS? What's wrong with calling that a scene graph? I can't imagine how a DBMS is going to help transformations propagate through the scene. How will these "views" be implemented? I don't want to be skeptical and would definitely welcome new ideas, but I think you need to be more specific.

Tom has based most of his reasonings on the fact that scene graphs are not good for state sorting and minimizing state switches. Although I completely agree with him, ruling out scene graphs mostly based on this reasoning is not fair, especially when an alternative is not presented. What strikes me then is

Quote:
2. Because of this, the number of state changes you make between rendering calls is not all that relevant any more. This used to be true in the DX7 and DX8 eras, but it's far less so in these days of DX9, and it will be basically irrelevant on DX10. The card treats each unique set of states as an indivisible unit, and will often upload the entire pipeline state. There are very few incremental state changes any more - the main exceptions are rendertarget and some odd non-obvious ones like Z-compare modes.

This is almost against everything I've read and heard so far. Is state sorting basically irrelevant to some extent on DX9 and to a more extent on DX10? What about Wloka's "Batch, batch, batch"?! This presentation is not that old and belongs to DX9 era.

I have a great respect for Tom, but this seems too radical.

Hey. I'm not a game-industry veteran or anything (far from it), but I thought I'd add my voice to the "Scene Graphs can be useful" side.

For example, the following is what I used for my last 3D scene-creating foray:
1) Loose-octtree for fast visibility/"update sphere" culling.
2) Many nodes added to this tree which often include scene-graph features (programable transforms, property inheritance, AI waypoints, etc).
3) Draw calls made on these nodes don't immediately draw renderables, but add "draw calls" for each applicable item into the relevant drawing bucket/batch.

People may say this is a naive way of doing this, but I personally found it to be a intuitive, flexible and quite efficient method. I'm sure that scene-graphs by themselves can be monstrously inefficient things, but when mixed with good culling/batching mechanisms, I think they can provide a good compromise between flexibility and efficiency.

A caveat to this is that if the project your working on has no need for this flexibility, then there's not point in using it. If all you need are a heightmap with quad-tree, or BSP etc, then there's no point. The project I was working on used features that benefit from the ability to define the properties of an entity based on the properties of its parent. Obviously if I didn't need this then it would have been more efficient to just spacially organise and treat each as seperate entities.

Anyway, that's just my $0.02AUD.