The Blog

Scene Graphs

Overview

There are a lot of misconceptions regarding what a scene graph is, does, and how it is applied to the world of video games.  For many years even Wikipedia took note of this confusion and mentioned the dispute within in the industry as to exactly what it is and does.  This is probably largely due to a software package called OpenSceneGraph, which bills itself by name as primarily just an advanced implementation of a scene graph, but causes confusion via its feature list and promotional language, which does not indicate how certain features are related to the “scene graph” part of the software, leading those oblivious to what scene graphs are to conclude that features such as frustum culling, OpenGL state sorting, etc., are somehow features of the scene graph itself.

Beginners often think about how to implement frustum culling and state sorting into their scene graph implementations and get stuck.  It may be possible that OpenSceneGraph actually does somehow incorporate these features directly into their scene graph implementation, but the reason that people get stuck in considering how to do it in their own scene graph implementations is because it’s extremely counter-intuitive and overall just a flawed approach to the problem.

This article intends to make clear what a scene graph is, what it does, and what it does not.

 

What is a Scene Graph?

A scene graph is a simple hierarchy of nodes that allow propagating properties from parent nodes down to children nodes.  It is nothing more.  What gets propagated can vary between implementations, but all of it is straight-forward when you consider that its only purpose is to pass properties down.  If you ever get confused on how to use a scene graph, it means you are trying to use it for something for which it was not meant to be used.  If you are trying to figure out what you can pass down to children from parent nodes to help with frustum culling, you will draw a blank, because aiding in frustum culling is not the purpose of a scene graph and there is no information you can pass down from a parent node to a child node that can intuitively be used to aid in the performance of frustum culling.

 

How is a Scene Graph Used?
It is used to pass down context-free data from parents to children.  The data is context-free because the scene graph itself has no idea what the data is that it is passing down nor is it necessarily supposed to use anything it propagates.  As mentioned before, a scene graph is a means of passing data/properties down a tree of parent/child nodes.  It is used for nothing more.

Typical things that could be passed down include:

  1. Spatial data.  When the parent moves left, all of its children move left the same amount.  Each child has its own local orientation, but in addition to their own local orientations they are “attached” to their parents’ orientation.  For example a character may have a graph of nodes representing its skeleton.  The joints in the arm and hand move when the shoulder joint rotates because the arm and hands are directly or indirectly children of the shoulder joint.  Likewise, a knife could be added as a child of the hand joint, and now the character can easily carry a knife in the correct position as his or her hand waves around.  Each node has local orientation data, which is combined with its parent’s orientation to create a world orientation (or in graphics terms a world matrix) that ultimately represents its actual world position in the scene, which is then used later in frustum culling, physics, rendering, etc.  Note again that just because each object’s world orientations and bounding boxes are derived from information propagated through the scene graph it does not mean the scene graph actually somehow does frustum culling, rendering, etc.
  2. Material data.  Perhaps it could be desirable for the alpha of a parent to be passed down to its children, so that when the character fades out, the knife it is holding fades with it.  Once again, the scene graph is used only as a means of propagating the material data down, and the children each have their own local copies which are combined with their parents’ copies to create a final value.  It may be data related to rendering, but it is not the job of the scene graph to render it.
  3. Physical properties.  If a parent suddenly becomes gravity-free, it would probably make sense to disable gravity for all its children as well.
How is a Scene Graph NOT Used?
By now it should be clearer what a scene graph does and does not do—it facilitates propagation of data and properties but it does not use any of that data or those properties.  Propagation of spatial data is the most common use for scene graphs, but this does not mean they are able at all to directly aid in frustum culling or collision detection (2 separate subsystems which rely on spacial data of objects).  Here are a few other examples:
  1. Scene graphs do not sort render states.  This is done via a render queue (article on this coming soon), which is part of the graphics module.
  2. Scene graphs do not facilitate in rendering at all and are not even part of the rendering system/module.  The things that get propagated through them are not necessarily related to graphics at all, and likewise some things that do get propagated through them are entirely unrelated to graphics.
  3. Scene graphs do not drive animations, although an animation subsystem can use a scene graph to propagate spatial data down its joint hierarchy in order to accomplish animation.  In practice, you would not create a separate scene graph just for the joints in a model though; the root joint(s) would be children of the model directly and the existing scene graph would be used to implement all parenting/childing involved.
  4. Scene graphs do not act as the primary representation of your scene.  A scene graph can optionally be used to provide a spatial representation of the scene, but when the scene manager wants to iterate over all objects it does not do so by traversing the scene graph.  The scene manager should have a simple linear array of all the objects in the scene.  The scene graph itself is implemented within those objects by themselves, separately from the scene manager.  The only thing the scene manager needs to know about any scene graphs is that one exists between all the objects it contains and that it should linearly iterate over that array and call curObj->Propagate() on each object.
    1. If that sounds inefficient, that is because it has the potential to be.  Implementation details are outside the scope of this article but the propagation stage can be made faster with dirty flags etc.  When a dirty-flag system is in place, objects that have nothing to propagate (have not changed since the last propagation) will simply return immediately without recursion.  The alternative is to traverse the scene recursively node-by-node, adding the overhead of recursion unnecessarily.
Other subsystems exist for certain types of operations and even secondary spatial representations of your game world may exist.  Frustum culling should actually be done through a quadtree or octree.  After spatial data gets propagated down all children, if their world orientations have changed they should be re-updated inside the quadtree/octree, and then other subsystems can work off the quadtree/octree to perform culling, collision detection, etc.
Conclusion
The words “scene” and “graph” have carried a cloud of confusion since they were first put together, and applications such as OpenSceneGraph have only added to that cloud, with a feature list leading newcomers and even somewhat experienced developers to question the scope and functionality of a scene graph.
I hope this article has made it very clear what is a scene graph is and what it is not.
L. Spiro

About L. Spiro

L. Spiro is a professional actor, programmer, and artist, with a bit of dabbling in music. || [Senior Core Tech Engineer]/[Motion Capture] at Deep Silver Dambuster Studios on: * Homefront: The Revolution * UNANNOUNCED || [Senior Graphics Programmer]/[Motion Capture] at Square Enix on: * Luminous Studio engine * Final Fantasy XV || [R&D Programmer] at tri-Ace on: * Phantasy Star Nova * Star Ocean: Integrity and Faithlessness * Silent Scope: Bone Eater * Danball Senki W || [Programmer] on: * Leisure Suit Larry: Beach Volley * Ghost Recon 2 Online * HOT PXL * 187 Ride or Die * Ready Steady Cook * Tennis Elbow || L. Spiro is currently a GPU performance engineer at Apple Inc. || Hyper-realism (pencil & paper): https://www.deviantart.com/l-spiro/gallery/4844241/Realism || Music (live-played classical piano, remixes, and original compositions): https://soundcloud.com/l-spiro/

4 Awesome Comments So Far

Don't be a stranger, join the discussion by leaving your own comment
  1. EarthBanana
    December 6, 2013 at 6:55 PM #

    Great Article – some explanations like this are hard to find unless you are around people who do it for a living. I will be interested to read your article on the rendering system.

  2. Irlan
    May 7, 2014 at 9:02 PM #

    I always make confusion between Scene Graph and a Scene. It aggregate Scene Nodes, sometimes called actors.

  3. Wobbly
    June 13, 2015 at 6:04 PM #

    “Scene graphs do not act as the primary representation of your scene” That’s really interesting. A book I read actually teaches the readers to write a scene graph for that purpose.

    • L. Spiro
      June 13, 2015 at 6:43 PM #

      Loosely, you can say that it is a central structure for the overall architecture of your game, but internally the main representation needs to have fast iteration times etc. A simple array inside the scene manager.

      L. Spiro

Leave a Comment

Remember to play nicely folks, nobody likes a troll.