logo

X3DToolKit concepts

home_link
concepts_link
download_link
examples_link
developer_link

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.

a) Scene graph definition

scene graph
fig 1: A typical example of a scene graph.


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.

b) 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.

inheritance tree
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.

a) Walker

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

b) 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.

DFS calls
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.

visitor
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. .

c) 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.

visitor functions

inheritance tree functions
fig 6: The enter functions are defined for the nodes A, C and D. The type E inherits the enter function of 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.

d) 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.

3. Scene views

Several views of the X3D scene are provided:

a) X3D

The X3D scene graph is the typed version of the DOM tree and implements part of the standard X3D nodes. Nevertheless, these nodes have no dynamic behaviour unlike nodes of a standard X3D browser. An X3D file is first loaded into an X3D scene graph. If you want to have enhanced behaviour you might convert it to a GL or MESH scene graph.

a) GL

The GL scene graph is an image of the X3D scene graph provided for fast rendering, by including the nodes for which a draw method can be defined in an OpenGL context. A processor called X3D::GLBuilder converts the X3D scene graph to the GL scene graph.

b) MESH

The MESH scene graph is a simpler scene graph than the X3D one and contains fewer nodes - Mesh and Vertex are the main nodes - thanks to templates providing a fully customizable mesh structure.

The Mesh node is a winged-edge structure enabling topological requests on vertices, edges and faces.

The processor X3D::MeshBuilder converts an X3D scene graph to a MESH scene graph.