Open Scene Graph States and StateSets part 2: the StateGraph

by Tim Moore

In the previous article we introduced the mechanisms that Open Scene Graph uses to track and modify OpenGL graphics state, the StateSet and the State classes. These classes optimize state changes on a micro level: as StateSets are pushed and popped, the State object only makes calls into OpenGL for state that actually changes. The problem of rendering an entire scene graph with the minimum number of state changes is more complex, though: objects that should be rendered with the same OpenGL state should be rendered together, and it would be nice to render all the objects in an order that minimizes the number of state changes. This last optimization is becoming less important because, on modern graphics hardware, the cost of making any change to OpenGL state is very expensive, but several changes made together are batched up by the driver and aren't measurably more expensive than one change. Still, the objects in the scene need to be sorted in order to group the objects by state, and it would be nice to avoid redundant state-changing function calls.

Some game engines hash the complete state -- shaders, textures, etc. -- into an integer, then sort all the objects based on that. This can work well with a small number attributes, especially if they can all be stored in a single object. In that case, if a state object is associated with each piece of geometry in the scene, the states can be gathered simply and efficiently. A linear-time radix sort may even be possible. However, Open Scene Graph's state attributes are not only stored with graphical objects, but also throughout the scene graph in StateSet objects. Also, with the large number of possible attributes in the OpenGL state, it becomes complicated to manage the transitions between states and set all the different attributes.

Open Scene Graph uses a scheme that preserves the application order of state sets, as they appear in a traversal of the scene graph, while grouping objects that use identical state sets together so that they can be rendered without changing the OpenGL graphics state. This is called the StateGraph. It's a graph (really a tree) that is constructed and traversed by several cooperating classes.


The class StateGraph represents a node in a tree of StateSet objects. Figure 1 shows the state graph that corresponds to the scene graph shown in Figure 1 of the first article. Each node in this tree has an associated OpenGL state: it is the result of applying all the attributes found in the StateSet objects from the root of the tree down to this node. In the first article we learned that StateSet objects can be efficiently pushed on and popped from the State to arrive at a different OpenGL state. We can see that to arrive at the state for a StateGraph node we would push the StateSet objects in nodes from the root down to that node. If we then wanted to arrive at the graphics state for another node in the graph, we would pop the StateSet objects in each parent node up to a common ancestor of the two nodes, then push StateSet objects while descending to the new node. In fact, there's a function, StateGraph::moveStateGraph(), that does exactly that. This function is used by Open Scene Graph whenever it renders an object that requires a different graphics state from the one that was last used.
Figure 1. State graph for a simple scene.

Note that a pointer to a StateGraph is a very compact representation of a graphics state, like the hash code we mentioned earlier. In order for it to be useful the state graph must be constructed so that each chain of StateSet applications in the scene graph has a unique node in the state graph. OSG must also track the current state graph node in order to set up a new graphics state using moveStateGraph(). It would be very difficult to work backwards and look up a StateGraph pointer using the current state of State.

Each StateGraph node contains a pointer to its parent and map of child nodes, indexed by StateSet objects. The map makes the construction of the graph more efficient. The node also contains a list of objects that should be rendered using the corresponding graphics state. In a moment we'll see how the scene graph is constructed, but first we'll look at how the StateGraph is used in the Open Scene Graph "back-end."

RenderLeaf and RenderBin

As mentioned in the first part of this article, the visible Drawable objects in the scene graph are collected in RenderBin objects before they are rendered. The objects can be sorted and drawn in several different ways. The RenderBin class actually works with a wrapper around the Drawable called a RenderLeaf. This object contains a pointer to a Drawable, a pointer to a StateGraph node for the graphical state of the Drawable, and pointers to the projection and model-view matrices. Open Scene Graph does not use OpenGL's matrix manipulation routines; but instead calculates the final matrix values on the CPU using double precision floats. The use of doubles solves the problem of loss of precision when using large numbers e.g., earth-centric coordinates, as vertex coordinates.

A RenderBin contains three lists of objects:

The render bin map provides a powerful mechanism for controlling rendering order. Open Scene Graph programmers are probably familiar with the default render bins available for opaque and semi-transparent geometry. A StateSet can contain a high-level rendering hint that selects either a global "opaque bin" or "transparent bin". The opaque bin contains only StateGraph objects, with their associated RenderLeaf objects. Its bin number is 0. The transparent bin holds RenderLeaf objects on its "fine grain" list of leaves which will be sorted back-to-front before the scene is rendered. Its bin number is 10, so it will be rendered after the opaque geometry.The rendering hint set via StateSet::setRenderingHint() is a high-level mechanism built on top of the ability to specify a RenderBin in each StateSet. Usually the render bin associated with a StateSet is inherited from a StateSet in a parent node.

The CullVisitor

At every video frame, the objects we've mentioned -- RenderLeaf, RenderBin, and StateGraph -- must be assembled from the high-level objects in the application's scene graph. This is the CullVisitor class' job. As the name suggests, the high level task of this class is to remove, or "cull," everything in the scene that is out of the field of view of the camera from the scene before it is rendered by OpenGL. But the job is not as much removal as it is the assembly of everything that is visible in a scene.

The CullVisitor is an Open Scene Graph NodeVisitor that traverses the scene graph for each camera, using the bounding spheres on nodes to avoid descending into nodes that fall outside the camera's frustum. Each node could contain a StateSet that affects the graphics state of objects below that node in the scene graph. These StateSet objects must be incorporated into the StateGraph that will eventually be used to render geometry. This process is fairly simple. CullVisitor tracks the current StateGraph node which would be used to render any geometry encountered. When it finds a StateSet in a node, it checks to see if the StateSet object matches any state graph node that is a child of the current state graph. If it does, then that state graph node becomes the current state graph; otherwise, a new StateGraph child of the current state graph is created and becomes the current state graph. After the traversal of the current scene graph node and its children has finished, the current state graph reverts back to the parent, or former state graph. In this way the state graph mimics the relationship of StateSet objects in the scene graph. An important result is that a StateSet object found in different nodes in the scene graph will be associated with a single StateGraph node, as long as the chain of "parent" StateSet objects is the same for each use.

CullVisitor also tracks the current render bin, as specified in StateSet objects, on as stack during its scene graph traversal. When the traversal reaches the geometry at the leaves of the scene graph, the current state graph node and render bin are directly used to construct a RenderLeaf that will hold the geometry and its state graph, put the leaf in a state graph node if necessary, and then put the leaf on the appropriate list of the current render bin. After the CullVisitor object's work is finished, the resulting collection of render bins are ready to be rendered.


In these articles we've looked at some very technical details of Open Scene Graph's graphics state management. One reminder to take away is that a StateSet does not correspond to a unique OpenGL graphics state; instead, an ordered chain of StateSet objects from the root of the scene graph specify the graphics state. A single StateSet object could be used in several of these chains, which would each specify a different graphics state. It is still important to have unique StateSet objects for the portions of the state that they do specify, because OSG uses only a pointer comparison to check if two StateSet objects are equal. The StateGraph mechanism does a good job of identifying distinct, unique graphics states and grouping the geometry that is rendered with those states. In order to minimize state changes at rendering time, one must think of the order of state sets in the scene graph, and their relation to the final graphics state, in addition to the StateSet objects themselves.