Visitors – Part II: Implementation

In my last post I mentioned the reasons behind my decision of using visitors in order to perform scene traversal operations. This time I’m going to briefly describe how the Visitor pattern is implemented and executed.

Before starting let me point out that I’m going to make several references to Crimild’s source code, so it will be a good idea for you to download it if you don’t have it already.

Visitors in Crimild are implemented following GoF recommendations, although I made some changes on my own. On one hand, the NodeVisitor class (include/Core/NodeVisitor.hpp) defines an abstract visitor by declaring operations for each of the known Node-derived classes (visitNode, visitGeometryNode, visitGroupNode) as well as providing a basic implementation for the traverse method, which is used as the entry point for scene traversal (more on that later).

class NodeVisitor {
   virtual ~NodeVisitor( void );

   virtual void traverse( Node *node );

   virtual void visitNode( Node *node );
   virtual void visitGroupNode( GroupNode *group );
   virtual void visitGeometryNode( GeometryNode *geometry );

The Node class (include/Core/Node.hpp) provides the perform method which is the entry point of any scene traversal operaton.

class Node : public Object {

   void perform( NodeVisitor &visitor );
   void perform( const NodeVisitor &visitor );

   virtual void accept( NodeVisitor &visitor );

For those of you wondering about the reason of having two perform functions, there is a nice comment awaiting for you in the source code 😉

The accept method is part of the double-dispatch between Node and NodeVisitor. Each Node-derived class should override the accept method in oder to invoke the proper visit* function call. For example, the following code shows how this is done in both GroupNode and GeometryNode:

void Node::accept( NodeVisitor &visitor )
   visitor.visitNode( this );

void GroupNode::accept( NodeVisitor &visitor )
   visitor.visitGroupNode( this );

void GeometryNode::accept( NodeVisitor &visitor )
   visitor.visitGeometryNode( this );

Using a visitor is as simple as invoking the perform function on a Node instance passing a NodeVisitor object as argument:

aNode->perform( CustomVisitor() );

Now, it seems that the perform call is wasted since the only thing it does is to invoke the visitor’s traverse method and there is no option to override it. Why not using the traverse function directly instead of wasting a function call? While it’s technically doable (you can initiate the process by using the traverse function), I prefer the entry point for any scene operation to be on the scene itself instead of any external object.

There is one more thing I would like to mention before closing this post. Consider the case of a scene consisting of a GroupNode instance with three children. A scene traversal involves visiting all nodes in the hierarchy, does iterating between parents and children. But while some operation might be executed in a depth-first traversal, others might involve more complex traversals. All things considered, I decided to not implement children iteration in the GroupNode class but instead forcing each NodeVisitor implementation to do it by itself. This might lead to a bit of code duplication, but so far it’s acceptable.

In my next post I’m going to introduce you to several visitors that are bundled with the engine and I’ll do a quick tutorial about implementing one on your own.

Visitors – Part I: Identifying the problem

Today I’m going to talk about the Visitor pattern and its usage within the engine. Visitors are a powerful tool used to perform scene traversal operations, like updating world transformation, computing bounding volumes, gathering debug information, updating components, rendering the scene, etc.

Since this is a long topic I decided to split it into several parts, with this one serving as a kind of introduction. So without further ado, let’s get started.

It was late 2007 and Crimild was a lot different than it is right now. By that time, I was following Dave Everly’s design (almost) by heart, dealing with several classes implementing each of the different node types conforming the scene graph hierarchy. Scene traversal operations were limited to a couple of scene updates calls, the rendering pass and collision tests and the entire scene graph was implemented following a variation of the composite pattern, as follows:

Notice how the doSomething() method is propagated throughout the entire class hierarchy

As my experience with scene graphs increased, I started to notice the rising cost of adding new scene traversal operations, requiring the modification of pretty much all of the classes in the hierarchy. For example, in order to add an operation for printing the name and type of all nodes in the hierarchy required to add a new abstract (or virtual) function at the top of the hierarchy (the Node class) and then override it in each of the subclasses (notice the doSomething method in the class diagram above).

Let’s take a break for a moment so I can introduce you to Behaviors. You’ll see the reason behind this soon enough.

The inclusion of Node Behaviors (an early implementation of what is currently known as Node Components) assisted me in the task of reducing the number of core classes, shifting the mechanism for extending the scene graph implementation from inheritance to composition. I’ll talk about behaviors/components in another post, but if you have no idea about the Game Object Component “pattern”, just think about the Strategy Pattern. It’s not the same thing, but it will give you an idea about where this is going.

Anyway, by using behaviors game objects could be created by instantiating any of the standard Node-derived class (GeometryNode, GroupNode, etc.) with one ore more behaviors attached to it. So I ended up with a class hierarchy resembling the following diagram:

Only a handful of nodes and lots of behaviors

This new design ensured a high stability for the Node class hierarchy. It was unlike for developers to create new Node-derived classes, since all of the game specific logic was enclosed in behaviors.

With a stable hierarchy and an ever increasing number of scene traversal operations, that seamed to be perfect scenario for implementing the Visitor pattern. As a side note, I spent some time researching open source engines like OpenSceneGraph and noticed they were already using visitors for scene traversal which gave me the confidence to move forward.

That’s it for today. Next week we’ll talk about how visitors are implemented and used in Crimild.  Stay tunned