This article will present an abstract, expandable, object-oriented method to handle generic objects for a practical and organized game engine. These generic objects can be graphical objects such as shapes and meshes, or non-graphical entities such as lights, cameras, and sound objects, all organized in a convenient scene hierarchy.

What is a Scene Graph?

Abstractly put, a Scene Graph is an organized hierarchy of nodes in a data structure with special relationships that simplify a problem. Put more concretely for our project: A Scene Graph is an m-ary tree, a tree with any node possessing any number of children, in which any particular node will inherit and amalgamate the transformations and render states, or other such states of the parent.

Inheritance and Polymorphism (OOP)

As the complexities of game programming increase, it is immediately important in the beginning of a project's lifetime to start organizing your core engine. The more time that is spent understanding the purpose of your project, defining the features and limitations, and planning the long-term scale, the faster projects will fall together in a well-polished final product. Object-oriented programming can greatly help in this organization.

The real powers in OOP lie in two key areas: Inheritance and Polymorphism. Inheritance allows for an object to extend the functionality of a base class, if necessary. Polymorphism allows you to call derived class methods which have been marked as virtual through a base class pointer.

These two concepts are used heavily in the scene management framework that will be described later in this article. For further information on Object-Oriented Programming check out Bjarne Stroustrup's book (Stroustrup97).

Using STL for the Scene Graph

The Standard Template Library (STL) is a collection of container classes that handle useful data structures. STL encapsulates linked-lists, queues and many useful trees, and gives programmers the ability to use iterators to iterate through the data structure. This article's description of a scene graph uses the simplest STL container called a vector which is nothing but a dynamic array. The FFGameEngine uses vectors extensively, so if you don't have a good understanding of them, you may want to read James Boer's article in the first Game Gems book (Boer00).

Object Ownership

Determining ownership of objects is an important part of constructing a game engine for two reasons. First and most important, objects are used and reused all over the lifetime of the game. It is important to know when it is safe to change or delete an object. Second, to avoid memory leaks, objects must be deleted. Since a game will deal with many objects, it is wise to design a good solution to deal with object lifetime so that object management does not get out of control.

A good resolution is to allow parent objects to take ownership of their directly descendent child objects. This method allows the ability to divide the responsibility of objects being deleted. Later we will be adding child objects similar to this:

void LoadModel(char* pFile, char* pName)
{
	FFObject* pObj = new FFMeshObject(pFile, pName);
	m_pSceneRoot->AttachChild(pObj);
}

Here, pObj is a dynamically allocated object that is handed to the scene root, and m_pSceneRoot takes full responsibility of pObj. Whenever m_pSceneRoot determines that it no longer needs pObj, it must free the resources.

Defining the "All Important" Base Object

In our scene graph, we will need a base class object that will take on the role of a mold for all objects that will be derived from it. This class will have the ability to handle all scene graph operations. Let's call this base class FFObject.

This object will need to store a pointer to its parent so that we can get the parent's world matrix, and a list of all children that it may possess.

// A protected list of children pointers
vector m_ChildrenList;

// A pointer to the parent of this object
FFObject* m_pParentObject;

This object will need a function to tell a child, "Who's your Daddy?"

// Called internally to set the parent node
void SetParent(FFObject* pParent) {
	m_pParentObject = pParent;
}

Next, the base class will also need a function to enable the ability to attach children.

// Called to attach a object as a child of this object
void AttachChild(FFObject* pChild)
{
	assert (pChild);
	pChild->SetParent(this);
	m_ChildrenList.push_back(pChild);
}

Next, FFObject will need a way to return a pointer to the children list for the recursive traversal of the scene graph.

vector* GetChildList() {
	return &m_ChildrenList;
}

Finally, FFObject will need pure virtual functions for rendering and updating the object. The following two function prototypes take a float fElapsedTime which will be how much time has passed since the last time that function was called. This information is useful for interpolative animation of objects as well as determining collision of moving objects.

virtual void Draw(float fElapsedTime) = 0;
virtual void Update(float fElapsedTime) = 0;

The scene graph now has a basis that can be built upon. FFObject itself really doesn't do much of anything on the surface; you cannot render it, and it doesn't understand how to update itself. But now let us expand FFObject by deriving objects that can actually do something.

Let us publicly derive a FFShapeObject class from FFObject where we can override the Draw function with the ability to draw shapes. Try to derive other classes like FFMeshObject to draw meshes or even FFLightObject and FFSoundObject to gain light and sound abilities.

Hierarchy in Action

Imagine, for example, that our game has a monster truck with four massive wheels. Our game is going to allow the truck to drive around while seeing the wheels move up and down depending on what the truck is driving over. The root of this sub tree will be the truck body, and the four wheels will be children of the truck body (all FFMeshObjects).

Each node contains a transformation matrix that tells the renderer the position, rotation and scale of the object in relation to its parent. So in our example, the position, rotation and scale of each wheel is an offset from the truck's position, rotation and scale. And in turn, the truck's transformation matrix is offset from whatever its parent's transformation matrix is. With this hierarchy, when the truck moves, all four wheels as children will also move with the truck. This kind of model allows for a clean method of updating objects in the scene graph.

Rendering a Node

Since each object does not directly know anything more than the offset from its parent, we define that object to be in object space - also known as local space. In our example with the monster truck, each wheel doesn't necessarily need to know about anything except its offset from the truck body. But in order to render an object, the renderer needs to know exactly where in world space that object will be. To know what the world space of this object is, the renderer would have to concatenate all transformations from the node it wants to draw to each parent up to the root of the tree. This is not a practical approach, so a simple way to speed this process up could be to force each node to keep a world matrix locally that is only updated if the parent (or any grand-parent of this node) has changed in some way. Then rendering a node is just a simple matter of multiplying the parent's world matrix with the object's model matrix, and drawing that node. Since space is limited, check out my web page for a more detailed explanation.

Recursive Iteration of the Scene Graph

Many beginning programmers cringe when they hear the word recursion, but any time you hear the word tree (as related to programming), you'd better get used to recursion. Recursion itself is a beautiful and painless technique normally used to reduce your problem to its simplest terms if you understand what is actually going on. Recursion for our scene graph is simple and necessary.

There are two ways to traverse any kind of tree: Breath-first, and Depth-first. Breath-first traverses a tree from left to right in any level before going to the next depth, and Depth-first traverses down the tree first and only goes back up when it can't go down anymore. Because of our hierarchy, it makes the most sense to update and render the scene depth-first in a sort of "in-order" fashion (see Figure 1).

To actually update and render the scene, the base object, FFObject, will contain virtual functions for updating and drawing the object. Each object will override this function so that the update and drawing is done correctly for that object. There will be at least two recursive passes each frame, one for updating and one for drawing. All objects will update their transformations based on their parents' transformations, but not all objects will need to draw. Lights and Sounds usually don't do anything in the draw functions, except maybe in debug mode where you might want to draw widgets to show where they are in the world.

To recursively update the scene, the function might look like this:

void FFSystem::UpdateScene(FFObject* pObject,
float fElapsedTime)
{
	// Base case for the recursion
	if (pObject == NULL)
		return;
	else
	{
		// Update this object.
		pObject->Update(fElapsedTime);

		// Recursively call all children
		vector::iterator it = pObject->GetChildList()->begin();

		for (;it != pObject->GetChildList()->end(); ++it)
			UpdateScene(*it, fElapsedTime);
	}
}

Rendering the scene looks exactly like the above code with the Update function replaced with the Draw function.

Run-time Type Information (RTTI)

Remember that polymorphism is the ability to call a derived class's function with a base class pointer. One small problem that may arise is that when using polymorphism, we don't know exactly what kind of object is actually being pointed to. As an example, calling the Draw function on a FFObject will call the Draw function on whatever object that derived from it. It could be a FFMeshObject or a FFSoundObject. There are some instances where we will need to know at run-time what type of object we're actually dealing with. This is where RTTI comes in.

Our implementation of the Run-time type Information is a system that will allow a constant to define exactly what kind of object we are dealing with at run-time.

Setting up such a RTTI system in our object-oriented framework is just a matter of defining the object types:

enum RTTI_OBJECT_TYPE
{
	RTTI_MESH,
	RTTI_PHYSICS_MESH,
	RTTI_SOUND,
	RTTI_LIGHT,
	RTTI_MIRROR,
	// Add more objects here as they are created
};

Then we would need a pure virtual function defined in FFObject to force all objects derived from this object to override this function to return the type:

// In FFObject
virtual RTTI_OBJECT_TYPE GetType() const = 0;

Then, for example, in the FFMeshObject, the function would be defined like this:

virtual RTTI_OBJECT_TYPE GetType() const {
	return RTTI_MESH;
}

Now by calling the GetType function on a base class pointer will return one of the constants of type RTTI_OBJECT_TYPE that define what type of object we have at run time.

Further Enhancements

Now that we have a basic framework, try deriving other objects from FFObject for your own creations. Other objects that are necessary for a game engine could be the various kinds of cameras (Follow Camera or First-Person Camera, etc). Another fun thing to try is to derive a class from FFMeshObject called FFPhysicsMeshObject that can handle collisions and other physical properties. Another example of a great object to create is the FFParticleEmitterObject. This would allow the spawning of particles that could be attached to a car exhaust, or a building on fire.

Something that has greatly increased performance is to do View-Frustum culling. This is where you only draw objects that are currently visible. The simplest method for this is to do a bounding sphere to view-frustum collision, and if the object's bounding sphere collides with the view frustum, then draw the object. This will enable the fast culling of objects that are not being seen. This is simple to add to our framework. Check out Gil Gribb's and Klaus Hartmann's paper on how to do this.

Conclusion

This explanation just scratches the surface, but was intended to give some ideas to people creating game engines. Also, this article is just one suggestion of scene management and is not complete by far. There are many books on game engine creation that contain full chapters on the subject. Check out the references section for more on the subject.

References

[Watt, Policarpo01] Watt, Allan and Policarpo, Fabio, 3D Games - Real-time Rendering and Software Technology, Addison-Welsey, 2001.

[Eberly01] Eberly, Dave, 3D Game Engine Design, Academic Press, 2000.

[Boer00] Boer, James, "Using the STL in Game Programming," Game Programming Gems, Charles River Media, Inc., 2000.

[Stroustrup97] Stroustrup, Bjarne, The C++ Programming Language, third edition, Addison Wesley Longman, Inc., 1997.