First off, some background. For the final release, and maybe for the demo, we want really cool things out of the graphics engine. A couple of them being:

1. Rings around planets
2. Moons around planets
3. Other things orbiting planets
4. Cheap star halos
5. Swappable ship parts
6. Articulating ship parts (maybe)

All good and, for the most part, easy to implement given the right framework. Not so in our case. All this can still be implemented, but at twice the complexity and cost in terms of engineering time and especially debugging. It looks like now is the time, while the dough is still gooey,  to make drastic changes to the demo or final engine to support these features.

The problem...

Simply stated, we don't have any spatial relationships. That's it. Pure and simple. In our case, we need relationships like the orbiting of moons around a planet. Our current implementation doesn't support them because all the renderable objects are placed in a singly linked list.

Figure 1: Our current scene architecture

The solution, the almighty scene graph...

A scene graph is a hierarchical way for storing all the data needed to render the scene. The hierarchy of a scene graph gives us a way to code the spatial relationships between objects. I'm sure you've heard of a scene graph before. Heck, you can be described as a scene graph yourself. The most common hierarchy is the human body. In game programming terms, the root of your scene graph is your mid section. Attached to it are your arms, legs, and chest. Attached to your arms are your hands, etc...

Figure 2: Humanoid frames

There are two common ways to implement a scene graph. As a directed acyclic graph, or as a tree. I'm going to opt for the tree version. Firstly because we don't need the complexity of an acyclic graph. In an acyclic graph, sharing happens at the node level. This means that nodes can have multiple parents. We don't want that complexity involved in managing that kind of graph. We want our sharing to happen at the data level. Shared mesh instances and textures for instance. Secondly because that's the most common way it's implemented. Thirdly because all programmers have dealt with a tree structure in their course work or in practice.

Figure 3: Tree representation of a humanoid

A scene graph has many advantages over the single list.
First and foremost, is the reduced number computations involved when operating on a large selection of data. Groups of objects can be ignored, or singled out without having to traverse the entire list to collect the objects. For example, imagine that our nodes in our scene graph were grouped by sector. If we wanted to implement culling to increase performance, we could completely eliminate entire sectors in one test. So, instead of testing each star, planet, debris, moon, ring, halo, or ship in the sector, we just test the sector bounds.
Second, groups of objects in the world can be modified as one object by modifying their common parent node. Imagine the case of the ship with swappable parts where all the parts are connected to the ship. If we wanted to move the ship, all we have to do is move the body and all the parts come with it FOR FREE! In the old method, we'd have to find all the parts of the ship, and then apply the same transform to them all. If rotations were involved, then there's the extra pain of calculating the body coordinate system and doing more calculations to get the pieces to fit right.
Thirdly, ease of programming. Imagine you want to render the scene graph. You don't have to manually traverse each level and node of the scene graph to execute the same function for each node. Because of the recursive nature of the tree, all you have to do is render the root node and let the tree take care of your traversal.

Have I convinced you yet? I hope so. If I haven't, please go back to the top, and read until this point.*
It shouldn't take you more than 3 or 4 times to get convinced.

*If you blow the stack, stop now and reboot. Recursion, you gotta love it.
Programmer humor for the truly geeky

The details...

Now that I've convinced you to use scene graphs, we have to define one. Here's a simple definition for a scene graph that will work just fine for us. First some terms:

Node

A node is a structure in the hierarchy. Nodes have exactly zero or one parent and zero or more children. Nodes are also referred to as frames because they are often a "Frame of Reference" for other frames.

Scene

A scene is a collection of nodes that make up the renderable world. Each scene has at least one child node. See Root Node.

Root Node

Represents the top of the scene graph. Each scene has exactly one Root Node. The Root Node does not have a parent Node.

Child Node

A child node is any node that exists under the parent node.

Parent Node

A parent node is the the single node that is directly above the child node.

Leaf Node

A leaf node is any node that has exactly zero Child Nodes.

Now that the terms are out of the way, let's talk data structures. DX9 already comes with a pseudo scene graph. Their D3DXFRAME structure encapsulates the heirarchy. It's a great place to start. It includes pointers for siblings and children. Ok, this implementation isn't a traditional tree implementation, but it works. In a traditional tree implementation, the frames wouldn't have pointers to their siblings, just their children. Microsoft may have done it this way to make breadth first traversal a whole lot quicker. It also has a transform that we can use for spatial relations. It has a name for easy identification. It also has a D3DXMESHCONTAINER, which is really just a pointer to an ID3DXMesh. I want to stick closely to the way DX9 does it because this frame is the format they use when load an animation from an X file.

The D3DXFRAME is a good start, but there are some important things that we need to do with the scene graph. That aren't supported in the it's interface:

• Initialization/ReInitialization
• Updating
• Rendering
• Bounds checking (for collision and culling)
• Adding children
• Adding siblings

Here's the definition  for a better frame class that supports what we want it to do. Some of these functions were taken from the DX9 Samples. They used a common framework that supported a common game loop. The functions I took seemed like they'd be important in any DX9 appication.
*Note, this isn't a complete interface. There are some important issues I want to address, which I'll do in a future article.

Let me give you a rundown of the function categories and the rationale behind them.

Construction/Destruction

This is pretty standard. You have to construct at some time or another. On a philosophical note, I'm a believer in the Construct/Create paradigm. It's not as convenient as defining a constructor with a whole bunch of parameters, but it's really convenient for things like loading from a stream. In derived classes, it really helps because you don't have to write a derived class constructor that takes all the parameters from the base class plus those from the derived class. You could just call the specialized initialization functions for each class.

Updating

Pretty standard stuff here. Each frame needs to be notified of when the game loop runs. This is the "mini-game loop" for each frame. We pass in the time so that each frame is updated with the same time slice. You don't want frames to be thrown off justt because they were last in line. Also, frames should be time based, not frame based. Faster machines should create smoother animations, not faster ones.

Rendering

There's a 3 part render system here. The PreRender is used to set up any render states, textures, etc. If you create objects properly, you don't have to reset the render states for each node, just the parent nodes. If we were doing lazy evaluation of the bounding box, this would also be the place to do theh updates. You might also do culling here. If the object is culled, just bail from the PreRender and the other two functions won't be called. The Render is where the actual drawing should be done. The PostRender is just there so you have a chance to cleanup anything you've done in the PreRender.

BoundsChecking

Bounds checking just supports the bounding box. In the scene, Updates are usually pushed down the tree. Bounding box updates are pushed up. Because of the hierarchical nature, the bounds for each part of the tree must contain the bounds for each child.

Adding/Searching/Removing

Self explanatory. Just for convenience.

That's it for the frame. Most of the node functions are recursive in nature so I'll just show you an example of one, the UpdateFunction.

All that's left to do now is to derive custom frames for our object categories. That's a whole discussion in itself. Before I drop the topic though, I want to clarify that we should derive frames for different object categories instead of object types. The difference being deriving a custom frame for a moveable object versus a static object instead of deriving a frame for a planet versus a ship. There is a difference there. It may be subtle at times, but there is a difference.

Now that the nodes of the scene graph are defined, the only thing left is the scene graph itself. The interface is really small and each function is relatively the same, so I'll just show you the interface and leave the implementation as an excersize for the user. If you really have trouble with the implementation, let me know and I'll update the article.

That's it for today. I hope you enjoyed today's episode.  One more article explaining some more concepts and then I think I'm ready to unleash the scene graph. See you next time.