Extensibility and software reuse have been big buzzwords in software development circles for a long time. Object-oriented languages and the concept of derivation help noticably, and newer concepts like aspect-oriented programming are trying to make it even more general. For practical systems, especially performance-conscious systems like scenegraphs, one has to work within the confines of a language like C++, which puts some constraints on the design.

Open Source Is Not Enough

For many people having the source code is all they need for extensibility. However, for a large system with high configurability and specialization potential like a scenegraph there are some limitations in this respect. Open Source works when changes done by the users are fed back into the main source line, so that they are available for everybody. But highly application-specific extensions may not be appropriate for inclusion and therefore the maintainers of the system might not accept them, even if the users are willing to provide (which is not always appropriate). For the application developer this means that she might have to apply the same changes to the system every time a new version is released, which can happen quite frequently for Open Source. The alternative is to decouple themselves from the development and stay with an old version of the system, which prevents them from benefitting from the new developments and bugfixes and removes one of the big advantages of Open Source.

This part is relatively involved and touches on a number of programming concepts that are important for scenegraphs. If you're not a programmer, you might want to skip to the Conclusion. ;)

Dynamic Extensibility

To avoid these problems OpenSG is designed around the idea of dynamic or run-time extensibility. As many pieces of the system as possible are built to be extended or replaced by an application at runtime without having to touch the library's source code. This is done through dynamic traversals, factory and prototype creation and reflective interfaces.

Dynamic Traversals

Traversing the graph's nodes is one central way of working with the data in a scenegraph, so to design a flexible scenegraph there needs to be a way to add new traversals as well as new nodes to existing traversals.

Given the heterogeneity of the graph for each kind of node and each kind of traversal a different action needs to be performed. Most object-oriented languages support dynamic action switching based on the object that a method is called on (based on a vtables). This single dispatch (based on one class) can be used to emulate the desired effect.

Virtual Traversal Methods

The simple way (and this is a prime example for object-oriented programming) is to have a separate virtual function for each kind of traversal needed in the base class of the nodes, like render(), intersect(), updateVolume() etc. Each of these just calls itself recursively on all the children of the traversed Node as necessary. The virtual function dispatch takes care of calling the right method of the actual node class on recursion.

Adding new node types to this system is simple, they just need to implement all the necessary traversal methods. The disadvantage is that to implement a new traversal the base node type needs to be extended, and all existing nodes need to be extended to handle the new traversal. This necessitates changes to a large number of classes and is in general not practical to be repeated.

Visitor Pattern

An alternative is the well-known Visitor pattern. Here the single dispatch is done in a traversal object that has different visit() methods for each kind of node to be traversed. Each node type has a generic accept() method that takes a Visitor and uses single dispatch to call the correct method in the specific Visitor class.

The advantage is that adding a new Visitor is easy, it just needs to implement the visit() method for all the given node types. But adding a new node type again demands changes to all existing Visitors, as they need to have the node-type-specific methods.

Double Dispatch

The real solution to the problem is the so-called double dispatch. It decides which method to call both based on the type of the class the method is called on as well as the class of the parameters given. In the context of a scenegraph traversal this means the traversal type and the type of the traversed node.

OpenSG realizes this by using an explicitly programmed dynamic selection of the function to call that is stored in each traverser. So at run-time the traverser decides dynamically, based on the type of the traversed node, which function to call. These functions can be methods of the node class, but they don't have to be. They can just as well be global functions or method of another class's instance, as long as they follow the interface conventions.

This gives full flexibility. Adding new nodes to old traversers is done by registering the function to call for this node type with the traverser (which can be done and changed at run-time). Adding new traversals is done by just creating a new traverser and registering the necessary traversal functions with it (which can be a class method but doesn't have to be). All of this is possible without touching a single line of system course code.

Factory & Prototypes

Adding new node types for taversals is an important part of extending a scenegraph. But a scenegraph is more that just a traversal engine. It contains a number of important and useful utilities like loaders, optimizers etc. When extending an existing node type, it is not practical nor desirable to reimplement all of these functions. The goal should be to be able to replace the types of nodes that the built-in tools create and manipulate and thus be able to have them create whatever application-specific types are needed. To support this OpenSG employs two major patterns: Prototype and Factory.

The Prototype allows an application to replace the actual type of object that the system creates whenever it needs a certain type of object like a transform or geometry node. The application can just supply a new Prototype instance and from then on the system will use copies of this type instead of whatever was compiled in. This allows extending and replacing pretty much any type of object in the system (in OpenSG this is limited to FieldContainers and derived classes, which encompasses pretty much all non-trivial classes). Applications can derive their own geometry that is more appropriate for their environment, replace the prototype and all loaders and optimizers will autoamtically use the new type.

The Factory pattern, in the way it is implemented in OpenSG, allows us to go even further. As it is based on using strings for naming the type to create, it can be used to automatically create instances of totally new, application-supplied types. This can be used to extend e.g. the system loader for the standard OpenSG file formats so that it can read and write application-defined types automatically, without having to change any of the internal code. These types are not limited to nodes or indeed anything related to the actual graph, anythig derived from FieldContainer can be read and written automatically.

To make this really easy and to allow the system to not only identify a class's type but also to read and write the actual data needs another programming paradigm: reflection.

Reflective Interfaces

Reflection as used by OpenSG is the ability of an object to give out information about itself, like the number and kinds of member variables (or Fields in OpenSG parlance) it has, and provided abstract access to these Fields.

This is used by the internal loaders and writers to read and write arbitrary types, especially including application-specific types that the system doesn't know anything aboutat compile time. This allows seamless integration of new types into the I/O system and makes adding new types to the system a very rewarding endavour. It can also be used to write generci user interfaces that can handle arbitrary node types. A user need never worry about being able to read or write their application-specific types, it just works. The same mechanism is used to support user-specific types across a cluster. As long as the type is known on the other side, OpenSG takes care of transfering all the data.

For an example see the VRED screenshots in the Application Gallery. The list of fields of the selected node and their editors is generated automatically and at runtime. It can even handle node types that were written by user-specific applications, totally independent of VRED.


In summary we can say that extensiblity is an important feature for a modern scenegraph. But it means much more than just using basic patterns and giving people access to the source code. Real extensibility is targeted at giving applications as much flexibility as possible without forcing them to touch library source code. OpenSG supports this to a very high level and encourages extensions by automating their support as much as possible.

Last modified 7 years ago Last modified on 01/17/10 14:19:06