Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
109 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

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();
    glLoadMatrix( (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




Contents
  Understanding
  Implementing

  Printable version
  Discuss this article