Step 5:  Scene Graphs

This step will serve to introduce the concept of scene graphs and the storage of graphical data in a data structure.  We'll build up some simple data structures that can be used to store graphical data.  This step also provides a starting point for Project 1.  What you turn in is a project that completes what is listed under Your Tasks at the end.

First, create a new C++ project named Project.  Be sure to create it just like you did in Step 1.  Be sure to select Single Document and to uncheck Document/View architecture support.  Also, uncheck Use Unicode Libraries.  Then install the CGrCamera class in it.  Use the example code from CGrCamera to get a scene up and going.  When you are done you should be able to use the camera to move around a simple tetrahedron.

Scene Graph Nodes

A scene graph is a graphical description of scene contents.  It has nodes that represent things we can draw and operations we can do on these things.  For example, a scene graph may consist of a node that does rotations.  The child of that node might be a node that draws a polygon.  We end up with a simple graph like this:

Now, as we discussed in class, scene graphs are actually graphs (technically a directed acyclic graph or DAG), so a node could have more than one node pointing to it.  I might have a node that draws a box.  Here's a scene graph that may draw that box twice, one rotated and the other translated:

Simple observation and some initial thought gives us several basic requirements for a scene graph node:

• Interior nodes can have one or more children.

• Any node can have one or more parents.

• A node should know how to render itself and its children.

Good programming practice all gives us a few more useful attributes:

• When done we need to be able to clean up after ourselves (freeing any used memory)

• There needs to be a way to point to a node without caring what type it is.

This should automatically make you think of a class hierarchy.  We're going to create a set of C++ classes, representing nodes of our scene graph.  Each of these will be derived from a superclass we'll call CSGNode.  In Visual Studio, do Project/Add Class.  Select the C++ category on the left and C++ Class on the right.  Click Add.  For Class Name enter CSGNode.  Check the item Virtual Destructor.  Then click Finish.  You'll see new files SGNode.h and SGNode.cpp. 

We need to be able to clean up after ourselves. We are not using Java; there's no free garbage collection.  So, we need a way to free the memory for any node.  Just as in Java, an object should be deleted when no other object is pointing at it.  We'll do that by keeping a count of how many objects point to this object.  Add a private integer member variable to the class called m_refs.  Initialize it to zero in the constructor.  Then, add these member functions inline in the class:

    void IncRef() {m_refs++;}
    void DecRef() {m_refs--;  if(m_refs == 0) {delete this;}}
    int  RefCnt() const {return m_refs;}

When we point to a node, we'll call IncRef().  This counts one pointer.  When we are no longer pointing at the node, we'll call DecRef() and the count will be decremented.  When nobody else is pointing at the node, it deletes itself.

This takes care of making the node be able to clean up after itself.  Now we're going to add a mechanism so a node can render itself.  Add this public member to CSGNode:

    virtual void Render() = 0;

The "= 0" means this is a "pure virtual function".  There is no implementation in CSGNode.  It is required that every child of CSGNode create a local virtual function with this name.  This makes CSGNode an abstract base class.  You won't be able to allocate CSGNode by itself, only children and all of those children must implement the Render function.

Here's SGNode.h and SGNode.cpp so far.

A Polygon Node

Now we'll build the most basic scene graph node: a polygon.  Do Project/Add Class.  As before, create a C++ class.  This time name it CSGPolygon.  Make the base class CSGNode.  Add this line to the declaration (header):

    virtual void Render();

Then add this code to SGPolygon.cpp:

void SGPolygon::Render()
{
}

So, what does it take to describe a polygon?  It will definitely have 3 or more vertices.  It needs vertex normals, maybe one that's for the entire surface or one per vertex.  If we texture map the polygon, it will need to know a texture object to use and texture coordinates for each vertex.  Here's member variables that will take care of all of these requirements:

private:
    std::vector<CGrPoint>   m_vertices;
    std::vector<CGrPoint>   m_normals;
    std::vector<CGrPoint>   m_tvertices;
    CTexture               *m_texture;

You'll need to add these headers to SGPolygon.h:

#include <vector>
#include "graphics/GrPoint.h"
#include "graphics/Texture.h"

Add code to the CSGPolygon constructor to set m_texture to NULL.

I also recommend that you add "using namespace std;" to SGPolygon.cpp.  It's bad practice to put a using statement in headers, since it exposes the namespace to any file that may include that header.

Now we need the ability to build our polygon.  Add these functions to CSGPolygon as public:

    void AddVertex(const CGrPoint &v) {m_vertices.push_back(v);}
    void AddNormal(const CGrPoint &n) {m_normals.push_back(n);}
    void AddTexCoord(const CGrPoint &t) {m_tvertices.push_back(t);}
    void SetTexture(CTexture *texture) {m_texture = texture;}

Now I have the ability to set up the data, all we need is the ability to render the polygon.  Add this code to the body of CSGPolygon::Render():

    // Create an iterator for each of the three arrays
    vector<CGrPoint>::iterator v=m_vertices.begin();
    vector<CGrPoint>::iterator n=m_normals.begin();
    vector<CGrPoint>::iterator t=m_tvertices.begin();

    glBegin(GL_POLYGON);
    for( ; v != m_vertices.end();  v++)
    {
        // If we have an available normal, use it:
        if(n != m_normals.end())
        {
            glNormal3dv(*n);
            n++;
        }

        // If we have an available texture coordinate, use it:
        if(t != m_tvertices.end())
        {
            glTexCoord2dv(*t);
            t++;
        }

        glVertex3dv(*v);
    }

    glEnd();

Be sure you understand what this is doing.  Now, I didn't put in any code to handle texture mapping other than supplying the texture coordinates.  I'll leave that to you.  Also, since this gets called for every vertex, it might make more sense to make the textured version a special case, repeating the loop above, but omitting the texture part when m_texture is NULL.  (You can tell if texture mapping is needed by m_texture being something other than NULL).

Here's SGPolygon.h and SGPolygon.cpp so far.

Creating and Using Your Node

Let's get just this node rendered so we can see it working.  Add this code to the CChildView class:

private:
    void CreateSceneGraph();
    CSGNode *m_scenegraph;

Be sure to #include "SGNode.h".  Add a call to CreateSceneGraph() to the CChildView constructor.

Here is the CChildView::CreateSceneGraph function:

void CChildView::CreateSceneGraph()
{
    CSGPolygon *poly = new CSGPolygon();
    poly->IncRef();            // Indicate we are using it

    CGrPoint a(0,    0,   2.5);
    CGrPoint b(2.5,  0,  -2.5);
    CGrPoint c(-2.5, 0,  -2.5);
    CGrPoint d(0,    4,   0);

    poly->AddNormal(CGrPoint(0.861411, 0.269191, 0.430706));
    poly->AddVertex(d);
    poly->AddVertex(a);
    poly->AddVertex(b);

    m_scenegraph = poly;
}

You'll have to #include "SGPolygon.h" in ChildView.cpp, not ChildView.h.  There are a few things to notice here.  First, we create a CSGPolygon node, but what we keep as a pointer to our scene graph is CSGNode *.  Also, IncRef is called to indicate we are using the object. 

Add this line to the CChildView destructor:

    m_scenegraph->DecRef();

We are now creating a scene graph and keeping one pointer to it.  When we are done, we're decrementing the pointer, so the object goes away.  We have cleaned up after ourselves. 

Last, but least, go to the OnGLDraw function.  Delete all lines of the sample code between the glMaterialfv() call and glFlush().  Replace these with:

    m_scenegraph->Render();

Run this.  It should display one triangle from the tetrahedron. 

A Smart Pointer Class

Remembering to increment and decrement those pointers is very hard to do and tends to be error prone.  If you envy those Java and C# programmers who just don't worry about deleting things, you'll see that we can make a C++ program just as convenient using a smart pointer class. A smart pointer class is an object that contains a pointer to another object.  However, it also knows to increment and decrement reference counts to those other objects.  Add this class to SGNode.h:

// class CSGPtr
// Class that is a pointer to a scene graph node

template <class T> class CSGPtr
{
public:
    CSGPtr() {m_ptr = NULL;}
    CSGPtr(T *p_ptr) {m_ptr = p_ptr;  if(m_ptr) m_ptr->IncRef();}
    CSGPtr(const CSGPtr &p_ptr) {m_ptr=p_ptr.m_ptr;  if(m_ptr) m_ptr->IncRef();}
    ~CSGPtr() {Clear();}

    void Clear() {if(m_ptr) {m_ptr->DecRef(); m_ptr = NULL;}}
    T *operator=(T *t) {if (t) t->IncRef();  Clear();  m_ptr = t;  return m_ptr;}
    T *operator=(CSGPtr &t) {if (t.m_ptr) t.m_ptr->IncRef();  Clear();  m_ptr = t.m_ptr;  return m_ptr;}
    operator T *() const {return m_ptr;}
    T *operator->() const {return m_ptr;}

private:
    T *m_ptr;
};

This may look complicated, but it's really just a bunch of variations on the same theme:  when I set m_ptr to something, I decrement anything it may have been pointing to before and increment what it points to now. 

In CChildView.h, replace the line CSGNode *m_scenegraph; with this:

    CSGPtr<CSGNode> m_scenegraph;

Remove the call to DecRef in the CChildView destructor.  Also, remove the call to IncRef from the CreateSceneGraph() function. When using pointer classes, you don't ever call IncRef or DecRef yourself.  This should run just like before.

Note that this now cleans up after itself automatically.  When CChildView is destroyed, its members are also destroyed, including m_scenegraph.  That decrements the reference count on our polygon object and it destroys itself.

CSGPtr acts like a pointer, but it's really an object with a pointer inside it.  So, you won't use an "*" before the object name. 

An Interior Node

Right now our scene graph only has leaf nodes.  It has no interior nodes, so it can contain exactly one node.  Let's create an interior node.  A handy node is one that does a rotation, then a translation.  We'll call it CSGRotationTranslation.  Go ahead and create that class.  Make it a child of CSGNode, of course.  Create a dummy render function as well.  Be sure you can compile.

So, what data do we need?  We'll need the data to define the rotation and translation.  We'll also need a list of child nodes.  Add this data to the CSGRotationTranslation class:

private:
    double  m_angle, m_rx, m_ry, m_rz;      // Rotation definition
    double  m_tx, m_ty, m_tz;               // Translation definition
    std::vector<CSGPtr<CSGNode> > m_children;

In the CSGRotationTranslation constructor, set all of the translation and rotation variables to zero other than m_rx, which you should set to 1.  (rx, ry, rz is a vector we rotate around; we would not want that to be a zero vector).

We'll need public access functions to set these variables and to add children:

    void SetRotate(double angle, double rx, double ry, double rz) 
        {m_angle = angle; m_rx = rx; m_ry = ry; m_rz = rz;}
    void SetTranslate(double tx, double ty, double tz) 
        {m_tx = tx; m_ty = ty; m_tz = tz;}
    void AddChild(CSGNode *) {m_children.push_back(child);}

Now add this code to the Render function:

    glPushMatrix();
    glTranslated(m_tx, m_ty, m_tz);
    if(m_angle != 0)
        glRotated(m_angle, m_rx, m_ry, m_rz);

    for(std::vector<CSGPtr<CSGNode> >::iterator child=m_children.begin();
        child != m_children.end();  child++)
    {
        (*child)->Render();
    }
    glPopMatrix();

You will have to add #include <gl/gl.h> to use the OpenGL functions.  (Brain teaser:  why didn't you have to add this line to SGPolygon.cpp?)

Here's SGRotationTranslation.h and SGRotationTranslation.cpp so far.

Putting This to Use

We're going to recreate the original tetrahedron, but this time as a scene graph.  Replace CChildView::CreateSceneGraph with this version:

void CChildView::CreateSceneGraph()
{
    CSGPtr<CSGPolygon> poly1 = new CSGPolygon();
    CSGPtr<CSGPolygon> poly2 = new CSGPolygon();
    CSGPtr<CSGPolygon> poly3 = new CSGPolygon();
    CSGPtr<CSGPolygon> poly4 = new CSGPolygon();
    CSGPtr<CSGRotationTranslation> rt = new CSGRotationTranslation();

    CGrPoint a(0,    0,   2.5);
    CGrPoint b(2.5,  0,  -2.5);
    CGrPoint c(-2.5, 0,  -2.5);
    CGrPoint d(0,    4,   0);

    poly1->AddNormal(CGrPoint(0.000000, -1.000000, 0.000000));
    poly1->AddVertex(c);
    poly1->AddVertex(b);
    poly1->AddVertex(a);

    poly2->AddNormal(CGrPoint(0.861411, 0.269191, 0.430706));
    poly2->AddVertex(d);
    poly2->AddVertex(a);
    poly2->AddVertex(b);

    poly3->AddNormal(CGrPoint(0.000000, 0.529999, -0.847998));
    poly3->AddVertex(d);
    poly3->AddVertex(b);
    poly3->AddVertex(c);

    poly4->AddNormal(CGrPoint(-0.861411, 0.269191, 0.430706));
    poly4->AddVertex(d);
    poly4->AddVertex(c);
    poly4->AddVertex(a);

    rt->AddChild(poly1);
    rt->AddChild(poly2);
    rt->AddChild(poly3);
    rt->AddChild(poly4);

    m_scenegraph = rt;
}

You will have to #include "SGRotationTranslation.h".  Since we'll use it later in the CChildView header, add this to CChildView.h. When you compile and run this, you should see the same tetrahedron that was the original demonstration.

This does almost the exact same thing we did using straight OpenGL code, but we are now putting out data into a data structure that then is rendered.

Here's what the scene graph looks like now:

Stuff You Can Add

Once you start creating these nodes, you can add all kinds of things to them.  When I create a polygon node, I usually make a member function called ComputeNormal() that automatically computes a surface normal after I've loaded the vertices. I also tend to create variations on functions that I find convenient, like a version of AddVertex that takes x, y, z instead of a CGrPoint or a SetRotation function that only sets the angle.  Scene graph nodes tend to be highly customized for given applications.

Hooks

Suppose we want to make our tetrahedron rotate.  How would we do that in a scene graph? 

First, let's make our program draw continuously so we can have animation.  Repeat what you did in Step 2 to make the barbell spin when a menu option is selected. 

Add these member variables to CChildView:

    CSGPtr<CSGRotationTranslation> m_hook1;
    CSGPtr<CSGRotationTranslation> m_hook2;

See how these pointers know they are pointing at rotation/translation nodes. 

Now, go to CreateSceneGraph().  Delete the last line of the function (m_scenegraph = rt) and replace it with this:

    CSGPtr<CSGRotationTranslation> root = new CSGRotationTranslation();
    CSGPtr<CSGRotationTranslation> rt1 = new CSGRotationTranslation();
    CSGPtr<CSGRotationTranslation> rt2 = new CSGRotationTranslation();

    root->AddChild(rt1);
    root->AddChild(rt2);

    rt1->AddChild(rt);
    rt2->AddChild(rt);

    rt1->SetTranslate(5, 0, 0);
    rt2->SetTranslate(-5, 0, 0);

    m_scenegraph = root;
    m_hook1 = rt1;
    m_hook2 = rt2;

Now, in OnGLDraw right before m_scenegraph->Render(), add these lines:

    // Animation
    m_hook1->SetRotate(m_spinangle, 0, 1, 0);
    m_hook2->SetRotate(-m_spinangle, 0, 0, 1);

Here is the scene graph now.  See how our hooks are pointers to nodes inside the scene graph that we use for animation purposes.

Other Nodes

Large graphics system may have hundreds of scene graph node types.  As mentioned, a composite node is very common.  Other common nodes are:

• Rotation around a point.

• Material Properties

• Lights

• Camera controls

• Complete meshes (we'll do this next week)

• Textures

• Boxes, spheres, and other primitives

Your Tasks

Your task is to add some additional nodes to your scene graph and create a simple scene that demonstrates these nodes.  The nodes to add are:

• Box

• Sphere

• Composite

• Cylinder

• Texture

How would you do textures in this structure?  We put this line in our CSGPolygon class:

    CTexture               *m_texture;

A good way to handle textures in a scene graph is to make them a node.  We'll call it CSGTexture.  It's member variable will be a CTexture object (not a pointer, but an actual object).  Then, each object that requires texture mapping would had a member variable like this:

    CSGPtr<CSGTexture>      m_texture;

Then a scene graph with four textured polygons might look like this: