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.
StateGraph
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.
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:
- A list of
StateGraph
nodes. The RenderLeaf objects stored with each node
are rendered in sequence, using that StateGraph node.
- A list of
RenderLeaf objects. These objects are
usually sorted for example, from back-to-front in the
scene. Transparency effects that use alpha blending use this order.
- A map of other
RenderBin objects that will be
rendered before and after this one. This map is keyed by an integer
bin number: negative values are rendered in order before the current
render bin, postive values after.
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.
Conclusion
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.
