1. Scene graph

The main type of structure used by X3DToolKit is the scene graph. Any 3D scene should be represented by a scene graph.

1.1 Scene graph definition


fig 1 : A typical scene graph example.

The scene graph is used to organize the objects of a scene into a hierarchy. Thus the coordinates of the object A are transformed by the transformation T, whereas the coordinates of the object C remain unchanged.

1.2 Nodes: graph elements divided into components

A scene graph is a set of nodes, which can have children. Each node has a unique type (ex: Transform). Using an object-oriented conception, a node is the instance of a class.


fig 2 : A typical example of conception. The class D inherits the class C.

Besides the set of types is partitioned into components. In this example, the type D belongs to the com3 component.

2. Traversing and processing the scene graph

The main action in X3DToolKit is the traversal and the process of the scene graph. The object which realizes the action is called a processor.

processor = walker + visitor

Traversal and visit are separated into distinct objects.

2.1 Walker

It is the traversal algorithm which is generally a DFS (depth first search) algorithm. It calls the visitor for processing the nodes.

2.2 Visitor

This implementation of the visitor design pattern acts exclusively on the nodes. The three different actions of the visitor are enter, leave and walkOn. walkOn indicates whether the children have to be explored or not.


fig 3 : An example illustrating the order of calls during a DFS traversal.

Recall that the set of nodes is partitioned into components. Each component is related with a component visitor (different from a visitor!). The union of the different component visitors creates the visitor (using a proxy design pattern) which groups the visiting functions associated with the nodes of the component.


fig 4: the visitor holds the component visitors of the com1 and com3 component.

For example, we want to count the number of C in a scene graph. We only have to define the com2Visitor, visitor of the com2 component with an enter function defined for C that increases the number of nodes.

When enter of the visitor is called by the walker, the visitor calls the appropriate function of its component visitors. .

2.3 Double dispatching

The visiting functions can be defined for any node.

The schema shows which functions are actually applied when only some of them are defined.


fig 5 : The enter functions are defined for the nodes A, C and D. The type E inherits the enter function for the type C, whereas D redefines its enter function.

The rule is simple: For a given processor, each node inherits the functions of the node from which it derives.

2.4 State variables

During a traversal, it is possible to need to memorize informations (for example the node stack) in order to use them in the visiting functions. The mechanism of state variables ensures the unicity of the informations per processor.
Generated on Fri Aug 27 13:16:25 2004 for X3DToolKit by doxygen 1.3.6