A scene graph is a data structure commonly used to represent hierarchical relationships between transformations applied to a set of objects in a three-dimensional scene. It finds applications in a variety of acceleration and rendering algorithms. A scene graph could also be used to organize visual attributes, bounding volumes, and animations as a hierarchy in a collection of objects. In the most general form, any scene related information that can be organized in a hierarchical fashion can be stored in a scene graph. It also provides a convenient way of representing logical groups of objects formed using their spatial positions or attributes. In this topic, we will outline the fundamental properties of scene graphs, look at some of the implementation aspects and consider a few applications.
The Basic Structure of a Scene Graph
The structure and contents of a scene graph will obviously depend on the type of information it stores, or equivalently, the set of operations it is used for. Let us consider a simple tree structure that contains three types of nodes:
1. The root node of the tree represents the whole collection of objects in a threedimensional scene. We call this node World or Virtual Universe. The root node is a special type of a group node.
2. A group node is an internal node of the tree. It can contain any number of children, and represents a logical grouping of objects. A group node does not store geometrical data, but it can contain some semantic information such as transformations or visibility attributes applied to a group.
3. Every leaf node represents either an object or a part of an object, and maintains the necessary geometrical information in addition to some semantic information. Camera and light sources may also be represented by leaf nodes.
Fig. 3.1 An example of a scene graph, where every internal node is a group node and every leaf node is an object node
Fig. 3.2 (a) An example of a model consisting of four connected parts that can move relative to each other. (b) A scene graph of the object model
Figure 3.1 shows an example of a tree with all three types of nodes described above. The tree structure of a scene graph allows a property associated with a group node to be inherited by all of its child nodes. For example, a transformation applied to a group node can be considered as also applied to all its children. Similarly, a bounding volume, if attached to a group node, also represents the overall bounding volume for the whole collection of its child nodes.
A scene graph is particularly useful for animating a composite object that has several parts which should move as if the parts are all physically connected to each other. A typical example of such an object is an articulated character model. We illustrate the formation of a scene graph using a simple model consisting of four interconnected parts: Base, Part-1, Part-2, and Part-3, as shown in Fig. 3.2.
Fig. 3.3 A 5-link joint chain and its scene graph
As can be seen from the diagram of the scene graph, the whole model is first subdivided into three logical groups Part-1, Base and a subgroup Group-2 to which Part-2 and Part-3 belong. Shortly we will see how we can assign transformation parameters to the individual nodes of the scene graph in such a way that the parts can rotate relative to each other while at the same time remaining connected as a single animatable object. We now consider a closely related object model, a joint chain consisting of five links as shown in Fig. 3.3.
Joint chains similar to the one shown above are commonly found in robotics and articulated models in computer graphics. The scene graph represents a hierarchical subdivision of the model, where at the first level, the whole object belongs to a single group World. At the next level of subdivision we have Link-1 and a subgroup Group-1 that contains the remaining links. Any rotational transformation applied to Group-1 affects all members of that group. It may appear that the group node Group-4 is redundant as it has only one child. However, the node is useful to provide a clear separation between the initial transformations applied to the object in Link-5 in its own coordinate system and the transformations applied relative to Link-4’s frame. We will also later add a camera as an object belonging to Group-4. The transformation hierarchy represented by scene graphs is explored in more detail in the next section.
A transformation applied to one part of an object often cascades with the transformations applied to the adjacent interconnected parts. For example, a change in the orientation of Part-2 of the model in Fig. 3.2a also affects Part-3. Such dependencies can be easily converted into hierarchical representations that are suitable for scene graphs. We consider below three examples involving hierarchical transformations: (i) the model of a mechanical part shown in Fig. 3.2, (ii) an articulated character model, and (iii) a small planetary system.
Fig. 3.4 A general transformation of the model in Fig. 3.2, showing translational and rotational parameters associated with links. The x and y axes denote the reference frame for the world coordinate system
A Mechanical Part
A general two-dimensional transformation of the model in Fig. 3.2a along with the translational and rotational parameters of each link is shown in Fig. 3.4. We will use T(a) to denote a translation by a vector a, and R(6 ) to denote an anticlockwise rotation through an angle 6. Note that thejoint angles 1i, 12,13 define relative angles of rotations of one part with respect to another. In order to build the transformation hierarchy, we have to consider first the transformation of each link from its own local coordinate frame to the coordinate frame of its group. The sequence in which the transformations are applied is shown in Fig. 3.5.
As shown in Fig. 3.5, transformations are applied from the leaf nodes upward to the root of the scene graph. Part-3 is first rotated by an angle 13, and then translated along the length of Part-2 by a vector d3. This composite transformation has a matrix given by T(d3)R(13). Group-2 now contains Part-2 and the transformed version of Part-3. In other words, both Part-2 and Part-3 have been transformed into the coordinate space of Group-2. It should be noted here that any rotational transformation of Part-2 is always applied to Group-2. The transformation matrix T(d2)R(12), effectively converts the points from the coordinate system of Group-2 to that of its parent group, Group-1. Figure 3.6 shows the scene graph with the transformation matrices added to the tree nodes.
From the above discussion, we note that every node transformation is defined relative to the node’s parent. At a leaf node, a transformation converts vertices from the local coordinate space of an object to its parent’s coordinate space. If an object node has an identity transformation I, it only shows that its parent’s node has the same coordinate reference frame as the object node. This also means that any transformation applied to that node is actually applied to its parent group node. In the above example, transformations applied to the Base are actually applied to Group-1, and they indirectly affect the transformations of each of Group-1′s child nodes.
Fig. 3.5 Each moveable component of an object model is transformed from its local coordinate space to its group’s space, and subsequently to the coordinate space of the group’s parent
Fig. 3.6 Scene graph with transformation matrices attached to nodes
A Simple Character Model
We now consider an articulated character model and its scene graph shown in Fig. 3.7. As in the previous example, we can define the translational and rotational transformations for each node, based on the joint position and angle of each link relative to its parent. Vectors vi… v9 denote the offsets of the origin of the links relative to their parent’s local coordinate system in the initial configuration. The vector v0 denotes the position of the base link (Torso) in the world coordinate frame.
Fig. 3.7 Scene graph of a basic articulated character model
The angles x, y, z represent a generalized rotation of the whole model in terms of Euler angles defined with respect to the principal axes of the world coordinate system. A detailed description of Euler angle rotations can be found in Sect. 5.4.1.
The model can be animated using key-frame sequences for the joint angles 91..99, and its position and orientation can be controlled using key-frame sequences for v0, \jfx, fy, and fz. The transformation hierarchy, if properly defined, ensures that the links stay connected and are rotated only about the joints. Owing to the symmetry of the model, we can also make use of the following relationships among the components (xi, yi, zi) of translational parameters vi: