Scene graph

From DmWiki

A scene graph is a data structure that holds nodes to different objects in a scene. A scene graph represents the logical representation of the scene. You can get as complex as you want with a scene graph and add collision detections, different visibility checks, and a whole bunch of advanced, headache-bringing stuff. But on its simplest level, a scene graph just tells the program where an object is positioned, relative to its parent object. A scene graph usually is in the form of a tree data structure. There is a root node that represents the base of the entire hierarchy. Attached are a number of children to the root node. So the root becomes the children's parent, and the children are each others' siblings. A child node can also have children.

The classic example is a human figure. Take the chest as the root of the scene graph hierarchy. The chest has 4 children: head, left arm, right arm, hips. The hips have 2 more children: right leg, left leg. Each leg has a foot as a child, and each foot has 5 more children: the five toes. Same thing with the arms. They consist of upper arm and lower arm, and palm, then 5 fingers. The chest would be the great great grandfather of a toe!

So we need something to represent all these parts of a scene graph. And we're going to call them scene nodes. All objects that have a position in space can be derived from a scene node object and inserted into the scene graph for the appropriate traversal. A node also doesn't necessarily have to be an actual object, it can also be a function applied to all its children. For example a node can only be a transformation, or an "Enable Billboarding" command. There are lots of things you can do, it's very flexible.

Imagine Tom is running in a classic Tom and Jerry cartoon, and his left arm gets crushed under a falling piano. The piano squishes his entire arm, but not the rest of his body, so now we need to render the entire arm with a certain effect - a "Make Geometry Flat" effect. We can create a MakeGeometryFlatNode class and stick in between the chest and the left arm. Now whenever we render the character, we just call Root->Render() and then the entire hierarchy is rendered, AND a "Geometry Flat Effect" is applied just before the left arm is rendered. The scene graph will automate all of this for you, you just insert the node in the appropriate place, and then you do not have to worry about anything else. Another neat application would be an EffectNode. A node that enables some vertex/pixel shader effect on the children.

Double-helix

The other obvious thing (and a very important one at that) is that whenever the root moves, all other objects that are attached to the root will move with it. This is a good time to introduce a TransformNode. The transform node is inserted between nodes that under go certain transformations. For example take a DNA strand takes the form of a double helix.

Imagine the root of the scene graph as the base of that helix. Then two spheres are attached to the root as the root's children. Then another sphere is attached to each child, and spheres keep on being attached to the previous child until you have 2 long towers of strings. Now each sphere can contain a transformation matrix that transforms itself a bit to the left, and a bit to the top (a few degrees clockwise and a few units up the Y axis). If each sphere is a little bit higher and rotated around it's child, you end up with a helix.

[edit]