Traversing a scene graph means “visiting” nodes in some sequence and invoking a callback as each node is visited. Callbacks allow you to perform operations whenever a node is visited during a traversal; for example, you can count nodes, render objects, or compute the volume of objects in a scene.

OpenGL Optimizer provides tools for two scene-graph traversal sequences: depth first or breadth first.

Depth-First Traversal Sequence

To picture depth-first traversals, imagine the path you would take if the links between nodes in a scene graph were hallways and you walk through the scene graph holding your right hand on a wall. Nodes would be rooms, and you would continue to hold your hand on the wall as you walked through the room. Callbacks are made each time you enter a room, except when the hand-on-the-wall rule returns you to a parent node before visiting all its children: a callback is made when you first “descend” into the parent node and after you “ascend” from the last child.

Figure 12-1 shows a depth-first traversal of a simple scene graph. The solid circles in the figure indicate pre-node callbacks, which are implemented when a traversal first visits a node. The solid squares indicate post-node callbacks, which are implemented as a traversal leaves a node.

Figure 12-1. Depth-First, Left-to-Right Traversal of a Simple Scene Graph

Notice that a depth-first traversal visits each parent node twice, once before and once after visiting its children. A depth-first traversal is inherently sequential and so cannot be reasonably executed by more than one process; the ordering of actions, particularly when parents are visited after their children, is best maintained by one process.

Breadth-First Traversal Sequence

The central concept of a breadth-first traversal is that the traverser visits the nodes at a given level and proceeds to a lower level in the scene graph after all the nodes at a higher level have been visited. Figure 12-2 shows a breadth-first traversal of a simple scene graph. The solid circles in the figure indicate per-node callbacks, which are implemented when a traverser first visits a node.

Figure 12-2. A Breadth-First Traversal of a Simple Scene Graph

Some features such as a multiprocess traversal or nodes with multiple parents, can complicate the sequence of nodes visited in a bread-first traversal. In those cases, the simple left-right, top-to-bottom sequence may not hold exactly.

When a breadth-first traversal is executed by several processes, or when nodes in the graph have several parents, a simple rule guarantees a reasonable sequence of events: the traversal does not visit children until it visits at least one of the parents. Whenever a parent node is encountered by a traverser, it places the node's children at the end of the processing queue.

The possible return values of callbacks, and the method apply() which initiates a traversal callback sequence, are set by the enumerated type opTravDisp whose values determine whether the traversal should continue, skip over the children of the current node, or stop.

This is the type definition for opTravDisp:

typedef enum {opTravCont=0, opTravPrune=1, opTravStop=2} opTravDisp;

After you complete a traversal, you can keep the object for subsequent use, or free storage assigned to the traversal object. For example, you may repeatedly use a cull traverser, invoking it each frame, but you may perform a tessellation traversal only once.

To specify whether a traversal object remains in memory after the traversal stops, specify the return value of the last callback, end(). The possible values are set by the enumerated type opActionDisp. This is the declaration for opActionDisp:

typedef enum {opDeleteThis, opKeepThis} opActionDisp;

The class opDFTravAction is used for a depth-first traversal of the scene graph. Parent nodes are visited at least twice, before and after their children are visited with a different callback for each visit (see “Depth-First Traversal Sequence”).

class opDFTravAction : public opAction
{
public:
opDFTravAction();
virtual ~opDFTravAction();

opTravDisp apply(csNode *root);

virtual void         begin   (csNode *& , const opActionInfo&);
virtual opTravDisp   preNode (csNode *&, const opActionInfo&);
virtual opTravDisp   postNode(csNode *&, const opActionInfo&);
virtual opActionDisp end     (csNode *&, const opActionInfo&);
};

The class opBFTravAction is for a breadth-first traversal, which can be performed on one or several processors. All nodes are visited only once, typically, in contrast with an opDFTravAction, for which parent nodes are typically visited at least twice.

class opBFTravAction : public opAction
{
public:
opBFTravAction();
virtual ~opBFTravAction();
  
opTravDisp apply(csNode *root);
void     applyMP(csNode *root, 
                 opThreadMgr *tm, 
                 const opTIDSet& tids = opTIDSet::opAllTIDs,
                 opPriority p = Optimizer::opDefaultPriority);

virtual void         begin  (csNode *&, const opActionInfo& );
virtual opTravDisp   perNode(csNode *&, const opActionInfo& ):
virtual opActionDisp end    (csNode *&, const opActionInfo& );
};

The following code fragment illustrates the use of a traverser, and also shows how simplification traversal works.

OpenGL Optimizer does not provide a simplification traversal class, instead, an application can design its own traversal class to meet particular needs. The example below provides one approach: It defines a simplification traversal function that returns the root of a new, simplified scene graph.

The example performs two checks that are not usually needed for a traverser, but are necessary for a simplifier:

These lines of code are taken from simplify.cxx and main.cxx in /usr/share/Optimizer/src/apps/opoptimize.

The class opDispatchAction is a csAction that, as it traverses a scene graph, applies a csDispatch to each node in a scene graph.

Recall that a csAction is a Cosmo3D object for traversing a scene-graph. The class csDispatch is an object designed to follow the “Visitor Behavioral Pattern,” which provides a convenient way to organize and define operations on scene graph elements. The Visitor Behavioral Pattern is described in Design Patterns, listed in “Recommended Background Reading”. A csDispatch is a “Visitor,” and subclasses are “Concrete Visitors.” This pattern is also used in Open Inventor; see The Inventor Toolmaker. For more information about csAction and csDispatch, see Cosmo 3D Programmer's Guide.

An example of an opDispatchAction is the tool for gathering scene graph statistics; see “Getting Statistics About a Scene Graph: opTriStats”.