Core Scene Graph Data Structures in C++


Tree Traversal

Note that rather than building special data structures to keep track of the traversal within the LoaderWrl::load() method, we have decided to use recursive function calls in our implementation, in fact using the program stack to control the tree traversal. This strategy is acceptable here because in practice we don’t expect to encounter very large and/or deep scene graphs. The same strategy is used in the SaverWrl::save() method, as well as in the rendering loop, to traverse the scene graph. An alternative is to implement a SceneGraphTraversal class, with a structure such as

class SceneGraphTraversal {
 public:
           SceneGraphTraversal(SceneGraph& wrl);
  void	   reset();
  Node*	   next();
};

The reset() method starts the traversal pointing internally the current node to the root of the tree. If not all the scene graph nodes have been visited, the next() method returns the current node value and moves the current node pointer to the next node in the depth-first traversal order, if such a next node exists. Otherwise it sets the next node value to NULL, so that the next call the the next() method returns the NULL pointer, indicating the end of the traversal.

Note that the only node types returned are Shape, Graph, and Transform. You get access to other node types, such as Appearance, Material or IndexedFaceSet, from the fields of the Shape nodes.

Here you have an example of how this class can be used

SceneGraph wrl;
// load from file or build by adding children
SceneGraphTraversal traversal(wrl);
Node* node;
while((node=traversal.next())!=(Node*)0) {
  if(node->isShape()) {
    Shape* shape = (Shape*)node;
    // for example
    node = shape->getMaterial();
    if(node!=(Node*)0 && node->isMaterial()) {
      Material* material = (Material*)node;
      // process fields of this Material node
    }
    node = shape->getGeometry();
    if(node!=(Node*)0 && node->isIndexedFaceSet()) {
      IndexedFaceSet* ifs = (IndexedFaceSet*)node;
      // process fields of this IndexedFaceSet node
    }
  } else if(node->isTransform()) {
    Transform* transform = (Transform*)node;
    // ... you should not traverse the children here
  } else if(node->isGraph()) {
    Graph* graph =  (Graph*)node;
    // ... you should not traverse the children here
  } else {
    // throw new StrException(“unexpected node type”)
  }
}