Understanding and Implementing Scene Graphs
by Garret Foster

Introduction

A graphics engine is not complete without some sort of way to manage its data. For some engine's needs a simple list of objects in the world with frustum culling is enough. But for modern game engines this will just not suffice in most cases. This is why a scene graph is needed. Through this article I will explain the theory behind a scene graph then dig deep into the workings of this device. Although this technique can be used in any language you like, I chose to write this article with C++; because I like C++. Even though there is not much code in this article I'd still suggest that you have a firm knowledge of C++ including inheritance, virtual functions, and on the theory side of things have a basic knowledge of trees.

What is a Scene Graph?

The most popular question I get while explaining what a scene graph is - is: what is a scene graph? Well a scene graph is a way of ordering your data into a hierarchy where parent nodes affect child nodes. You might be saying "isn't that what a tree is?" and you're exactly right; a scene graph is an n-tree. Meaning it can have as many children as it wants. But scene graphs are a little bit more involved than a simple tree. They represent some action to take place before proceeding to the children objects. If this doesn't make sense now then don't worry it will all be explained in due time.

How is a Scene Graph Useful?

Well if you've yet to discover why scene graphs are so cool then let me explain some of the finer sides of the scene graph. Let's say you have to model a solar system in your game. This system has a star in the middle, with two satellite bodies (planets). And each of the planets also has two moons. There are two ways to solve this. We can create a complex behavior function for each body in our solar system, but if the designer wants to change a planet position then there is a lot of work to do by changing all the other objects that should be rotating around it. The other choice would be to create a scene graph and make our lives simple. The following diagram shows how we would create a scene graph to represent the objects:

Now the code becomes trivial. Let's assume that the rotation node saves the current world matrix, and multiplies it with a rotation. That would affect all other objects rendered after it. So with this scene graph let's see the logical flow of this scene graph would be.

Draw the star
Save the current matrix

Apply a rotation
Draw Planet One
Save the current matrix

Apply a second rotation
Draw Moon A
Draw Moon B

Reset the matrix we saved
Draw Planet two
Save the current matrix

Apply a rotation
Draw Moon C
Draw Moon D

Reset the matrix we saved

Reset the matrix we saved

Now this is a very simple example of a scene graph, and you should start seeing why a scene graph is a good thing to have. But you might be saying to yourself that this is very easy to do, I'll just hard code it. The beauty about scene graphs is they're not hard coded, specific things such as rotations, rendering, and any type of node you can think of are, but the way the scene is displayed is not. With our new found knowledge we can make this scene a lot more complex, so let's do it! Let's add some life into our solar system and make Planet 1 wobble a little. Yes planet 1 was hit by a large asteroid and is now rotating slightly off its axis. No need to worry all we need to do is create a wobble node and set it before we draw Planet 1.

But planet 1 wobbling is just not enough realism for me, let's go further with this and make the two planets rotate at different speeds.

Now this scene graph is a lot more complex than what was originally presented, so let's go over the logical flow of the program now.

Draw the Star
Save the current matrix

Apply a rotation

Save the current matrix

Apply a wobble
Draw Planet 1

Save the current matrix

Apply a rotation

Draw Moon A
Draw Moon B

Reset the Matrix

Reset the matrix

Reset the matrix

Reset the matrix
Save the current matrix

Apply a rotation

Draw Planet 2
Save the current matrix

Apply a rotation
Draw Moon C
Draw Moon D

Reset the current matrix

Reset the current matrix

Reset the current matrix

Wow! Now that is to model just a simple solar system! Just imagine what would happen if we modeled the rest of the level.

Enough Theory! Get on with it!

Well I think that is enough of a high level discussion on scene graphs, let's talk about how we're actually going to implement them. For this we're going to need a base class for all scene graph nodes to derive from.

class CSceneNode
{
public:
  // constructor
  CSceneNode() { }

  // destructor - calls destroy
  virtual ~CSceneNode() { Destroy(); }

  // release this object from memory
  void Release() { delete this; }

  // update our scene node
  virtual void Update()
  {
    // loop through the list and update the children
    for( std::list<CSceneNode*>::iterator i = m_lstChildren.begin();
         i != m_lstChildren.end(); i++ )
    {
      (*i)->Update();
    }
  }

  // destroy all the children
  void Destroy()
  {
    for( std::list<CSceneNode*>::iterator i = m_lstChildren.begin();
         i != m_lstChildren.end(); i++ )
      (*i)->Release();
  
    m_lstChildren.clear();
  }

  // add a child to our custody
  void AddChild( CSceneNode* pNode )
  {
    m_lstChildren.push_back(pNode);
  }

protected:
  // list of children
  std::list<CSceneNode*> m_lstChildren;
}

Ok now that that's out of the way we can now make a laundry list of all the types of nodes we want to have. Here is a list of nodes I thought every scene graph should have. Of course you can always add onto it if you feel fit.

Geometry Node
DOF (will explain)
Rotation (animated)
Scaling (animated)
Translating (animated)
Animated DOF
Switch

That should be plenty for a basic scene graph engine. You can always add in more to your engine to make it the best new thing.

Geometry Node

Well what is a graphics engine without graphics? NOTHING! OK so let's get the most important one out of the way first. Here is our geometry node in all its glory.

class CGeometryNode: public CSceneNode
{
public:
  CGeometryNode() { }
  ~CGeometryNode() { }

  void Update()
  {
  // Draw our geometry here!

  CSceneNode::Update();
  }
};

Notice I went a bit shallow on the rendering code. Well that is sort of engine specific on how you want to draw your geometry. Anyways the point is very clear on how to handle this node though. We render the geometry (or send it somewhere to be rendered), then update our children.

DOF

DOF nodes are commonly known as transformations. They're nothing more than just a matrix representing an offset, rotation, or scale. These are useful if you don't want to store a matrix in the geometry node. For our next example let's just assume we're using OpenGL for our rendering.

class CDOFNode: public CSceneNode
{
public:
  CDOFNode() { }
  ~CDOFNode() { }

  void Initialize( float m[4][4] )
  {
    for( int i = 0; i < 4; i++ )
      for( int j = 0; j < 4; j++ )
        m_fvMatrix[i][j] = m[i][j];
  }

  void Update()
  {
    glPushMatrix();
    glLoadMatrixf( (float*)m_fvMatrix );

    CSceneNode::Update();

    glPopMatrix();
  }

private:
  float m_fvMatrix[4][4];
};

The Animated Node Series

There are four flavors of the animated node series. There is a rotation animation, scaling animation, translating animation, and an animated DOF. The first three can all be represented by an animated DOF, but interpolating matrices is a very expensive process and should be avoided at all cost. So that's why we have specific animations like we do.

For the sake of avoiding confusion with math and get away from the point (scene graphs) I'm not going to present the code for the animated nodes. I don't want to clutter this article with too much code. In my last engine and in engines I've seen before, the scene graph's animated nodes all work off of a frame based animation. There are a certain number of key frames and they are all time stamped. At a certain time this is where I want to be. Well let's say I'm at a time where I don't have a specific key frame? What do we do then? Well what we'll have to do is make one up. We need to make a logical guess as to where we actually should be, this is called interpolating. There are several methods of how to interpolate between the different values you have, but for the sake of brevity let's discuss linear interpolation. The basic algorithm for this is to find the two key frames we are in between (based off time). Get the difference in time between them (key_frame002.time – key_frame001.time). Get the time elapsed since the first key frame (current_time – key_frame001.time). Make a ratio of the difference in time then multiply it by the difference in values. After you have all that add that to the first frame and you have your interpolated value. So the final equation for interpolating linearly between two values is as follows:

There are much more complex ways to interpolate between key frames, but this is a good way to introduce the problem.

Switch Node

The switch node starts to bring out some of the more complex things you can do with a scene graph. What a switch node does is act like a junction in a rail road and only lets you take one of the following paths (they can be altered to go down two paths, but that will be up to the reader to fulfill). Let's see a picture of a scene graph with a switch node in it.

Now for this section of the scene graph, the switch represents a car door in our racing game. As the car takes damage we want to show that it is taking damage. When we start out the race we want the car to have no damage on it, but as the car progresses through the level taking more and more damage we need to switch the paths to a more damaged car door. We could even extend this to make the more damaged body parts have particle systems attached after them making a smoke effect. The possibilities are only limited by your imagination.

Don't Stop There!

Now these are just some examples of what you would find in a scene graph, but are certainly not all the nodes you would find. There are a ton of different nodes you could create, a particle system node, a character node, a camera node, more geometry types, terrain node, billboard node, the list doesn't end. If you have needs for a new type of node then make that new type of node. Also extend your base functionality. Don't think that the base class I presented here is enough for you to have a robust scene graph, it's a start but extend it with things like: names, descriptions, IDs, Type Checking, etc. The more information you have on your base class the easier it is for you to debug.

Conclusion

Well I hope you enjoyed reading this article as much as I enjoyed writing it. I'm really happy to give back to the community with this article. If you have any questions, comments, or concerns feel free to email me at me@garretfoster.com

Discuss this article in the forums

Date this article was posted to GameDev.net: 12/21/2003
(Note that this date does not necessarily correspond to the date the article was written)