Home What It's All About Who Is This Guy? The List Complete Archive Personal  RSS Feed People		Game Object Structure: Scene Graphs Revisited By Kyle Wilson Saturday, February 08, 2003 The last time I wrote on this subject, I suggested that scene graph-based game engines had the benefit of incorporating "functionality that Performer and MultiGen encapsulate neatly in switch nodes and LOD nodes.  Switch nodes and LOD nodes render a subset of their children based on scripted conditions or viewing distance." In the months since I wrote that, I've gone to work at a new company, worked with a new game engine, and given game object structure some more thought.  And I'm less fond of switch nodes or LOD nodes now, because they seem to exist in a structure of fuzzy abstractions. In MechAssault, if you shoot a pine tree, it appears to catch fire.  The effect is generated by adding a "fire" particle emitter as a child of the pine in the scene graph.  It inherits the transform on the pine, emits its particles in the correct spot, and all is right with the world.  Right? Not quite.  You see, our engine also supports LOD and switch nodes.  So if a pine tree has multiple levels of detail, then shooting it doesn't produce fire.  Instead, it adds another level of detail, and if you back far enough away from the pine, it'll disappear and you'll see a fire emitter in its place. So it's time to ask, again, what the scene graph represents.  I see three choices, and switch nodes and LOD nodes don't fit neatly into any of them: A transform hierarchy.  This is the most traditional form of scene graph, in which each node exists in the local space of its parent node. A stack.  This is an extension of the transform hierarchy in which parameters can be passed down to each renderable component.  For example, you could have material nodes or transform nodes which pushed state values into the renderer before calling down to their children, then popped those state values when the children's render calls were done. A dependency graph.  In its loosest incarnation, a scene graph would simply be a tree of objects in which parents needed to be updated before children.  There is no global state, there are no transforms passed from parent to child, and each node is responsible for storing any data it needs or fetching that information, as required, from its already-updated ancestors in the graph. At this point what you have isn't really a scene graph any more.  It's just a dependency graph that may contain all sorts of non-scene objects for AI, physics, game logic, and so forth.  How many different types of objects you choose to include in the graph depends on how bold you are. I suspect you'll quickly find that a tree isn't sufficient to model all the dependencies you need anymore.  What you really need is a directed acyclic graph.  But if you have a DAG, and you're modeling dependencies, how do you determine order of update?  I can think of three ways. 1.  Start with a model of the whole dependency graph.  Add objects which depend on nothing to the update list and remove them from the graph.  Repeat.  In the end, you'll have an ordered list of objects that insures that every object will be updated before its dependents.  Unfortunately, it's worst-case O(n²), where n is the number of objects in the dependency graph.  You can probably improve on that substantially in practice since worst-case scenarios will be rare and, besides, you only have to compute update order when the graph topology changes.  If you're creating and removing lots of game objects dynamically, though, I don't think this will work well. 2.  Make every object update the objects it depends on before it updates itself.  This "bottom-up" approach will give you a wave of updates recursing up your graph, then coursing back down.  You're touching every game object twice, though, once on the up-pass and once on the way back down.  Expect to suffer from cache misses. 3.  Update as needed.  Simply have every object detect when its state has changed and notify its dependents that a change has occurred.  This is, in essence, the Observer Pattern.  It's also the approach taken by 3D Studio Max's ReferenceMaker/ReferenceTarget system.  I'm intrigued by the notion of applying it to games.  In large complex worlds with lots of static objects that don't need to do any kind of updates every frame, I think there would be big advantages to only updating objects on demand and not pulling into the cache anything you don't need.  Sure, there would be issues with making lots of successive changes to one object, but Lock() and Unlock() methods could be added to those objects so notifications could be batched. Like I said, it's an intriguing notion.  Next time, I hope to explore a possible implementation of an acyclic dependency graph which performs updates as needed. I'm Kyle Wilson.  I've worked in the game industry since I got out of grad school in 1997.  Any opinions expressed herein are in no way representative of those of my employers.
Home