Scene graphs, an anti-pattern?

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

    • I've been looking into scene graphs myself lately. First things first -- the link you posted goes to the top-level blog, but does not go directly to the article. Here is the article text (in case one day, it disappears from the 'net). I'll post my thoughts after, then I'm curious to hear from the rest of the forum, as well.

      Scene Graphs - just say no
      TomForsyth, 31 December 2010 (created 11 August 2006)

      A Scene Graph is essentially a method of rendering where you place your entire world into this big graph or tree with all the information needed to render it, and then point a renderer at it. The renderer traverses the graph and draws the items. Often, the edges between the nodes attempt to describe some sort of minimal state changes. The idea is fairly simple - we're computer scientists, so we should use fancy data structures. A tree or graph is a really cool structure, and it's great for all sorts of things, so surely it's going to be good for rendering, right?

      It's a great theory, but sadly it's completely wrong. The world is not a big tree - a coffee mug on a desk is not a child of the desk, or a sibling of any other mug, or a child of the house it's in or the parent of the coffee it contains or anything - it's just a mug. It sits there, bolted to nothing. Putting the entire world into a big tree is not an obvious thing to do as far as the real world is concerned.

      Now, I'm not going to be a total luddite and claim that trees are not useful in graphics - of course they are. There's loads of tree and graph structures all over the place - BSP trees, portal graphs, skeletal animation trees, spatial octrees, partitioning of meshes into groups that will fit in memory (bone-related or otherwise), groups of meshes that are lit by particular lights, lists of objects that use the same shader/texture/post-processing effect/rendertarget/shadowbuffer/etc. Tons of hierarchical and node/edge structures all over the place.

      And that's the point - there's tons of them, they all mean different things, and (and this is the important bit) they don't match each other. If you try to put them all into one big graph, you will get a complete bloody mess. The list of meshes that use shadowbuffer X are completely unrelated to the list of meshes that use skeleton Y. I've seen many Scene Graphs over the years, and typically they have a bunch of elegant accessors and traversers, and then they have a gigantic list of unholy hacks and loopholes and workarounds and suchlike that people have had to add to get them to do even the simplest demos. Try and put them in a big, real, complex game and you have a graph with everything linked to everything. Either that, or you have a root node with fifty bazillion direct children in a big flat array and a bunch of highly specialised links between those children. Those links are the other structures that I mentioned above - but now they're hard to access and traverse and they clutter up everything.

      Fundamentally of course you do have to resolve a traversal order somehow - the objects need rendering, and there's some sort of mostly-optimal way to do it. But you're just never going to get that ordering by just traversing a single tree/graph according to some rules. It's fundamentally more complex than that and involves far more tradeoffs. Do you traverse front to back to get early-Z rejection? Do you traverse by shadowbuffer to save switching rendertargets? Do you traverse by surface type to save switching shaders? Do you traverse by skeleton to keep the animation caches nice and warm? All of this changes according to situation and game type, and that's what they pay us graphics coders the big bucks for - to make those judgement calls. You can't escape these problems - they're fundamental.

      But trying to fit them all into one uber-graph seems like madness. This is compounded by the fact that most Scene Graphs are implicitly a "retained mode" paradigm, and not an "immediate mode" paradigm. My esteemed friend Casey Muratori has some uncomplimentary comments on doing things with retained mode concepts, and I'm very inclined to agree. Yes, they can work, and sometimes they're necessary (e.g. physics engines), but it's not what I'd choose given an alternative.

      The one major argument I hear presented for Scene Graphs is the "minimal state change" concept. The idea is that the edges between your nodes (meshes to be rendered) hold some sort of indication of the number or cost of state changes going from one node to the other, and by organising your traversal well, you achieve some sort of near-minimal number of state changes. The problem with this is it is almost completely bogus reasoning. There's three reasons for this:

      1. Typically, a graphics-card driver will try to take the entire state of the rendering pipeline and optimise it like crazy in a sort of "compilation" step. In the same way that changing a single line of C can produce radically different code, you might think you're "just" changing the AlphaTestEnable flag, but actually that changes a huge chunk of the pipeline. Oh but sir, it is only a wafer-thin renderstate... In practice, it's extremely hard to predict anything about the relative costs of various changes beyond extremely broad generalities - and even those change fairly substantially from generation to generation.

      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.

      3. On a platform like the PC, you often have no idea what sort of card the user is running on. Even if you ID'd the card, there's ten or twenty possible graphics card architectures, and each has a sucession of different drivers. Which one do you optimise for? Do you try to make the edge-traversal function change according to the card installed? That sounds expensive. Remembering that most games are limited by the CPU, not the GPU, and you've just added to the asymmetry of that load.

      Anyway, this is something we can argue til the cows come home. I just wanted to give my tuppen'orth against the "prevailing wisdom" of using a Scene Graph. I'm not saying there aren't some good reasons for using one, but after writing a fair number of engines for a fair number of games, I have yet to find any of those reasons particularly compelling. They invented a lot of cool stuff in the 70s and 80s, and there's plenty of it that we continue to ignore at our peril. But some of it was purely an artifact of its time, and should be thwacked over the head and dumped in a shallow grave with a stake through its heart.

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

    • My thoughts are: This dude seems to have way more knowledge than I have about scene graphs, and about graphics hardware. So, I may be talking from a position of ignorance, but.. I say make your scene graph, yo! (Disclaimer: I assume you're just trying to learn game development and rendering and what not).

      I've seen articles/blogs/posts describing many different ways to implement scene graphs, and some of them appear to do what the blog author is complaining about: Cram in too many elements of the rendering pipeline (e.g., some of them do describe using the scene graph for skeletal animation, which sounds like more than the scene graph is "supposed to do").

      But at the same time, I imagine that if the scene graph is implemented "properly" (whatever that means), then go for it.

      To the point of "anti-patterns", I think scene graphs are probably not anti-patterns.. You could say singletons are anti-patterns (this article does: michaelsafyan.com/tech/design/patterns/singleton). And yet, we use them in game development all the time (even the mighty Unity uses singletons).

      So, I say use scene graphs to your heart's content.

      But I'm an amateur... What do the experts say?
    • Scene graphs can be an unholy mess, but they are one place to start, and fairly easy for programmers to visualize. TomForsyth brings up some excellent points, and in practice I think it would be madness for any top flight game engine to use only a scene graph structure in the manner presented in Game Coding Complete. Complicated problems frequently require complicated solutions, and of course those solutions require more than a chapter or two to cover.
      Mr.Mike
      Author, Programmer, Brewer, Patriot