Jump to content
  • Advertisement
Sign in to follow this  
Ashkan

Anti-SceneGraphism: A Tale of Tom Forsyth's "Scene Graphs Just Say No"

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

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
One of the goals you see of some scene graphs -- particularly those that emerge from academia or overly complex frameworks -- is that the perfect rendering order arises naturally as a consequence of how the scene graph is arranged for traversal. So during a single traversal, you're able to transform, cull, and render efficiently during the traversal. That single structure is supposed to minimize the amount of maintenance necessary, and provide a very elegant arrangement for getting your scene rendered.

This is absurd.

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. Most scene graph related research proceeds with the goal of merging these three contradicting trees into one. Things like switch nodes and DAGs emerge as a result, trying to provide more sophisticated control of this single traversal.

Personally I think you're better off running it in discrete steps with discrete (and highly compressed) structures. So first, you do transformations across the board. Then you cull and collect a list of visible objects for the frame. Lastly, you do a fast sort across those objects to get a final list with optimal batching.

Oh, and TomF, if you happen to read this: It's really, really nice to see that you've been writing to your blog again recently. Please continue to do so!

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
I find it hard to believe that people are still having this discussion - this one is almost as silly as the OpenGL vs. DirectX discussion. 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.

<Begin Rant>
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.

If a scene is very hierarchical, then a graph makes sense to use for transformations. 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. Why would you keep a separate graph (or other data structure) to redundantly traverse and calculate something that is already available to you in another structure?

If a scene is very non-hierarchical (i.e. would result in a very flat tree) then maybe a BSP tree or quadtree would make more sense. In the same token, the same data structure could be used for both transforms and culling.

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.

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. It doesn't do anyone any good to make those kinds of statements. 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.
<End Rant>

* Sorry for the rant, but that's how I see it...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
I forgot before; I have some suggested reading on the matter.
Part 1
Part 2
Part 3
Unfortunately these articles pose more questions than answers, but they do an excellent job of calling out the main problems involved.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Andy: as you said, I don't want to hijack the thread - we can continue the conversation in PM. I actually have used a significant number of scene management data structures and there are pros and cons to each. I don't think there is a typical 'modern' game scene - something like Doom III is going to be quite a bit different than a poker game. In a given context a scene graph may be the best solution.

I do agree with both you and promit about sorting by render state after the objects have been selected as visible. But I still disagree about the geometric information in each node. If the transform hierarchy is used to transfrom the bounding volumes in a scene, why is that not a good place to do the culling? If there is a known spatial data structure that better represents a good way to cull the objects, why not use that as the criteria for building your scene graph? Then a single traversal would be capable of doing both functions, and the only change is how you build the graph.

Sorry if I came accross as rude, after re-reading my post and your response I don't think it was a fair comment. I look forward to hearing your (and others)thoughts on the topic (including Tom if he's around...)

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!