Simple Scene Graph in C++

There are several articles gathering dust bunnies on the internet on creating a scene graph class in C++ for your 3D engine but most are pretty vague and quite old. Hopefully, this post will give you a foot in the door in creating your own scene graph for your engine.

To start off, let’s go over some basics. A scene graph is a tree-like data structure which holds information about the scene you want to display. Every node has a parent and every node may have children. In this post we’ll use the std::vector to store the scene nodes but you can substitute this with whatever you want. A scene graph can be visualized like so:

             [root node]
                  |
        o=========o=========o
        |         |         |
    [child 1] [child 2] [child 3]
        |
    o===o====o
    |        |
[child 4][child 5]
             |
         [child 6]

Any node may have any number of children who’s children may have any number of children, etc. Each node in the scene graph may have a name for lookup functionality so a very lookup system will be implemented. We will also need functionality to add a child node, remove a child node, set/get a node’s parent and an update function for updating the graph hierarchically.

Beware that this scene graph is for educational purposes only, I do not recommend that you implement this scene graph into your engine as it uses very simple algorithms and general-purpose classes from the C++ Standard Template Library. Also, keep in mind that a scene graph is not used for rendering your objects, it is used to keep hierarchical information and for applying hierarchical transformations.

Rendering your objects is done through a different type of structure such as a Binary Space Partitioning Tree (BSP-Tree) or an Octree which are structures more suitable for visibility testing and quite a bit faster. Your scene graph is updated each cycle of your simulation or game so that all the objects in your scene have their correct transformations.

Let’s start off with declaring our base class, the Node (below is the entire Node.h file):

#ifndef __node_h_
#define __node_h_ 1
#include <vector>

class Node
{
public:
	Node(Node* Parent = NULL, const char* Name = NULL);
	virtual ~Node(void);

	virtual void Update(void);

	Node* GetParentNode(void) const;
	void SetParentNode(Node* NewParent);

	void AddChildNode(Node* ChildNode);
	void RemoveChildNode(Node* ChildNode);

	const char* GetNodeName(void) const;
	const size_t CountChildNodes(const bool& RecursiveCount = false) const;
	virtual const bool IsRootNode(void) const = 0;

	Node* GetChildNodeByName(const char* SearchName);

private:
	Node* m_Parent;
	const char* m_Name;
	std::vector<Node*> m_Children;

}; // class Node

#endif

There are not many methods in this class so you have room for expansion if you feel like it. Beware that this class can only be used as a base class and cannot be initialized as new Node(). Let’s continue by examining the individual methods of this class:

Node::Node(Node* Parent, const char* Name)

Node::Node(Node* Parent, const char* Name)
	: m_Name(Name)
{
	m_Parent = Parent;
} // Constructor

As you can see I’ve kept the constructor very simple. The default for both parameters is NULL as both are optional. A node does not necessarily need a parent and a node does not require a name. You can of course change this by removing the = NULL sections out of the header file and throwing and exception if NULL was found in the source file.


Node::~Node(void)

Node::~Node(void)
{
	m_Parent = NULL;
	m_Children.clear();
} // Destructor

The class destructor is also very simple, it simply sets the pointer to the parent node to NULL and clears the children-vector.


void Node::Update(void)

void Node::Update(void)
{
	if(!m_Children.empty())
	{
		for(size_t i = 0; i < m_Children.size(); ++i)
		{
			if(NULL != m_Children[i])
			{
				m_Children[i]->Update();
			}
		}
	}
} // Update()

Still pretty simple, this method goes through the children-vector and calls the Update method on each child that does not equal NULL. The child object in return calls the Update method so the behavior is recursive.

This method was designed to be overriden and called as Node::Update() by the overriding method.


Node* Node::GetParentNode(void) const

Node* Node::GetParentNode(void) const
{
	return(m_Parent);
}; // GetParentNode()

A “property” which simply returns a pointer to the parent node.


void Node::SetParentNode(Node* NewParent)

void Node::SetParentNode(Node* NewParent)
{
	if(NULL != m_Parent)
	{
		m_Parent->RemoveChildNode(this);
	}
	m_Parent = NewParent;
}; // SetParentNode()

This method sets a new parent node for the selected node and removes the node from the old parent node’s children-vector.


void Node::AddChildNode(Node* ChildNode)

void Node::AddChildNode(Node* ChildNode)
{
	if(NULL != ChildNode)
	{
		if(NULL != ChildNode->GetParentNode())
		{
			ChildNode->SetParentNode(this);
		}
		m_Children.push_back(ChildNode);
	}
}; // AddChildNode()

Adds the node to the children-vector and updates the parent to the new parent if a parent was set.


void Node::RemoveChildNode(Node* ChildNode)

void Node::RemoveChildNode(Node* ChildNode)
{
	if(NULL != ChildNode && !m_Children.empty())
	{
		for(size_t i = 0; i < m_Children.size(); ++i)
		{
			if(m_Children[i] == ChildNode)
			{
				m_Children.erase(m_Children.begin() + i);
				break; // break the for loop
			}
		}
	}
}; // RemoveChildNode()

This method loops through all of the child nodes and will remove the selected child node from the children-vector if found.


const char* Node::GetNodeName(void) const

const char* Node::GetNodeName(void) const
{
	return(m_Name);
}; // GetNodeName()

A “property” which returns the name of the current node.


const size_t Node::CountChildNodes(const bool &RecursiveCount) const

const size_t Node::CountChildNodes(const bool &RecursiveCount) const
{
	if(!RecursiveCount)
	{
		return(m_Children.size());
	}
	else
	{
		size_t Retval = m_Children.size();
		for(size_t i = 0; i < m_Children.size(); ++i)
		{
			Retval += m_Children[i]->CountChildNodes(true);
		}
		return(Retval);
	}
}; // CountChildNodes()

Method counts all of the child nodes, recursive if required. If the recursive Boolean is set to true, the function will iterate over the entire hierarchy from the current node down and return a full node-count.


Node* Node::GetChildNodeByName(const char *SearchName)

Node* Node::GetChildNodeByName(const char *SearchName)
{
	Node* Retval = NULL;
	if(!m_Children.empty())
	{
		for(size_t i = 0; i < m_Children.size(); ++i)
		{
			if(0 == strcmp(m_Children[i]->m_Name, SearchName))
			{
				Retval = m_Children[i];
				break; // break the for loop
			}
		}
	}
	return(Retval);
}; // GetChildNodeByName()

This method will return a node referenced by name if it exists, otherwise it will return NULL. The function is fairly expensive and should be replaced with something more efficient but is fine for small trees and demos.

Conclusion:
As you can see, the scene graph is quite simple but once you understand how to implement one customization isn’t hard. Things you might want to change are passing a time value to the Update() method of Node so that your nodes may have a notion of time passed between calls, something faster than std::vector for storage and implementing a type-checking mechanism.

Regardless of the above, if you’re slapping together a quick demo that’s not performance sensitive the code with tweaks should do fine. Let me know if I missed or something or screwed something up since this post has been sitting in limbo for quite a while.

Comments

#1
c++ Lover Says:
On April 8th, 2009 at 10:45 AM

Great! It is so amazingly simple and useful !

#2
Joshua Says:
On July 9th, 2009 at 9:54 PM

This is extremely promising, but there is no actual code in Node::Update() for performing the transformations :-(

This is good code for creating a tree structure, but unfortunately it’s really not useful as a scene graph.

-j

#3
On July 14th, 2009 at 4:08 PM

The post is only meant to give you a foot in the door in creating your own scene graph, I never meant it to be a complete implementation. If you want a fully working production-ready scene graph, there are plenty of Open Source libraries out there.

#4
Stephen Says:
On July 20th, 2009 at 2:45 PM

The getChildNodeByName function doesn’t work.

I create a small tree of nodes in a Constructor for my Scene Graph. This scene graph ‘sg’ is a member of my main.cpp file

Now, the code that doesn’t work is:

Node *test = sg.getNodeByName("five");  
// already created this Node with this name in sg's constructor

if(test!=NULL)
    std::cout << "Found Node: " <getNodeName() << std::endl;

The If statement always returns false. The function in my SceneGraph class is:

SceneGraph::getNodeByName(const char* nName)
{
     return root->getChildNodeByName(nName);
}

I’m not experienced with C++. Did a second year Uni Course, so did have proper instruction however.

Could you help? Can you see what I’m doing wrong, or does it really not return the pointer properly?

#5
G P Says:
On May 2nd, 2010 at 10:17 PM

Hi, thanks for the overview code, but you don’t show alot here other than a abstract skeleton of an expanded composite, that you then say not to use. I think I might speak for a few when I say that I would like to know how this relates to an actual scenegraph. For example, what sort of classes extend this to become the actual implementation of a scene graph. Do we override the update functionality? If so, with what kind of logic? ‘How do I rotate my object in my world?’ Please please please could you expand or I think maybe this could end up being another one of those articles that will gather dust bunnies :)

#6
On May 3rd, 2010 at 9:38 AM

GP you’re right, the code provided is only an abstract skeleton created to make it easier to visualize a scene graph’s data structure. Maybe in the future we could go into the matrix and vector math, but for now I don’t see how that has to do anything with scene graphs. Until I get a little bit of time to throw together new posts, and if you really wish to learn the mathematics required to rotate an object (and more), the only thing I can recommend to you is: Mathematics for 3D Game Programming and Computer Graphics by Eric Lengyel.

#7
G P Says:
On May 4th, 2010 at 12:57 PM

Well, that’s the thing, I wasn’t really talking about the actual math. I was talking about how the math would be applied within this structure. I would suggest that people look to create a system that is bi-directional and consists of area/space aware classes for culling and collisions, a node wrapper and a geometry class. Rendering is called from a node which extends the area aware class (this contains your transform class which consists of translation, rotation and scale data). Once these transforms are recursivly applied to all children of that node, the bounding box data is traversed back up the tree so that collisions and culling can be perfomed on the geometry leaves. GP

#8
Hariprasad Says:
On July 30th, 2011 at 6:06 PM

Very nice article. Simple and easy to understand. Thanks Eddy.

#9
Jean Says:
On September 12th, 2011 at 10:22 PM

Just thought I could contribute a bit…

void node::Update(Matrix &parentworld)
{
// Compute LocalMatrix (one or the other..)
m_Local = Ljoint; // if node is joint, then build it from constraints
m_Local = matrixfromquat(q); // if it has orientation instead of joint params
// Compute WorldMatrix
m_World = parentworld * m_Local;
// Recursively call Update() on children
for (…)
{
children[i]->Update(m_World);
}
}

#10
Karl Says:
On December 3rd, 2011 at 11:18 PM

Awesome thanks! great post

Leave a Comment