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

A few notes about Windows support

First of all, I would like to thank Eduard Gibert for making me notice some issues in Windows that were preventing the correct compilation of Crimild under that platform. I’ve been so  focused on iOS recently that I completely forgot about Windows. And since there’s no continuous integration tool (shame on me) it was a matter of time until these kind of problems occur. Maybe this is a good time to start using one.

Anyway, I wanted to share the changes I made in order to fix the Windows build:

First, all third-party libraries and frameworks required to build Crimild on Windows are now stored in the /third-party folder in the SVN repository. This allows CMake to correctly discover them during the project configuration process and ensures that the development environment is properly set. The reason for doing so is that both Linux and MacOS are much more developer friendly when it comes to depending on third party libraries. Unfortunately, this is not the case for Windows so I have to do what’s necessary in order to ensure the environment is correctly configured.

Concerning Lua, up until now the Lua core had to be compiled separately for each platform in order to produce the correct static library for our projects. It turns out that Lua itself proposes an alternative process which is as simple as including all core files as part of our build process. And that’s exactly what I did. Now the Scripting module will build Lua sources as well without having to worry about the target platform. I should thank Lua engineers for using ANSI C and making my life easier.

On the downside, I was forced to disable a couple of examples and the new shader-based OpenGL renderer until further notice as I’m still working on them.

As a side note, I also noticed that the documentation regarding node visitors is far from helpful so I’ll be writing a little bit more about them in my next post.