Scene Graphs (Advanced Methods in Computer Graphics) Part 2

A Planetary System

As the third example, we consider a simple planetary system consisting of the Sun, the Earth and the Moon. The translational and rotational parameters used in modelling the system are shown in Fig. 3.8.

The rotation angles 9E, 9M represent the spin of the Earth and the Moon respectively about vertical axes, ¢E denotes the revolution of the Earth-Moon system around the Sun, and ¢M the revolution of the Moon around the Earth. The scene graph for this system is shown in Fig. 3.9.

A simple planetary system showing the translational and rotational parameters used for the construction of its scene graph

Fig. 3.8 A simple planetary system showing the translational and rotational parameters used for the construction of its scene graph

Scene graph of the planetary system


Fig. 3.9 Scene graph of the planetary system

One notable difference between the planetary system example and the previous ones is the form of transformation matrices applied to nodes. Most of the transformations applied in a hierarchical fashion have a general form T(v)R(6 ), which is a rotation followed by a translation. In simple implementations, the structure of nodes is often designed to accept only transformations of the form T(v)R(6 ) or I. Scene graphs where transformations at internal nodes have one of the forms I, T(v), R(6 ), or T(v)R(6) are said to be in the standard form. The example given in Fig. 3.9 is an exception to this rule. However, this scene graph can be easily converted to the standard form with the addition of a group node as shown in Fig. 3.10.

The equivalence of the scene graphs in Figs. 3.9 and 3.10 can be verified by obtaining the combined final transformation matrices applied to the leaf nodes. In a scene graph, transformations are combined using a recursive procedure starting at the root node, accumulating transformations at internal nodes and ending at object nodes. This process will be explained in detail in the next section.

The scene graph in Fig. 3.9 converted to the standard

Fig. 3.10 The scene graph in Fig. 3.9 converted to the standard

Relative Transformations

The transformation of one node relative to another can be readily obtained from a scene graph. The model transformation matrix of an object gives the composite transformation that converts points from the local coordinate space of the object to the world coordinate space. In a scene graph, this is the transformation of the object node relative to the root (the world node). The composite matrix can be obtained by collecting all matrices along the path from the root node to the leaf node representing the object. At each node, the matrix is post-multiplied by the transformation matrix of that node. The process is illustrated in Fig. 3.11, where node transformation matrices are denoted by letters A..G. The model transformation matrix of the object node in the figure is ABCDE.

Leaf nodes can also be used to represent fictitious objects such as light sources and camera. In Fig 3.11, the transformation from the coordinate system of the camera to world coordinates is given by AFG. The inverse of this matrix, (AFG)“1, transforms a point from world space to camera space. This matrix is called the view matrix. The combined model-view matrix that transforms the object’s local coordinates to camera space is therefore given by (AFG)“1 ABCDE, or equivalently, G“1 F_1BCDE. An upward tree traversal from a leaf node to root can be quickly performed if every node has a pointer to its parent. On the other hand, a downward traversal would typically require a recursive algorithm similar to the depth-first search method.

The above example can be generalized to a procedure for finding the transformation from one object’s local coordinate frame to another’s. If we require the transformation from Object-1 (source) to Object-2 (target) in a scene graph, we have to first find the Lowest Common Ancestor (LCA) of both the object nodes. Let the transformation matrix of this common ancestor be denoted by M (Fig. 3.12). Let S1… Sm denote the transformations of nodes starting from the child of LCA towards Object-1, and T1..Tn the transformations towards Object-2 as shown in Fig. 3.12. The composite transformation from the source’s frame to the target’s frame is given by the matrix Tn_1..T1_1S1..Sm. Note that this matrix product does not involve the transformation M of the LCA or any of its ancestors.

Computation of the model transformation matrix of an object represented by a leaf node in a scene graph

Fig. 3.11 Computation of the model transformation matrix of an object represented by a leaf node in a scene graph

Representing Object-1’s coordinates relative to Object-2’s local reference frame requires the computation of the Lowest Common Ancestor (LCA) of both the nodes

Fig. 3.12 Representing Object-1’s coordinates relative to Object-2’s local reference frame requires the computation of the Lowest Common Ancestor (LCA) of both the nodes

There are several well-known algorithms to compute the Lowest Common Ancestor of two nodes in a tree. A simple method uses two lists of nodes visited in sequential upward traversals of the tree from the two nodes towards the root. The last item of both lists would be the world node. Corresponding entries in the lists are compared for equality, starting from the last item towards the beginning of each list. The process of comparison stops when the list entries are different. The previous matched entry in the lists gives the reference to the Lowest Common Ancestor (Fig. 3.13).


An algorithm for finding the Lowest Common Ancestor

Fig. 3.13 An algorithm for finding the Lowest Common Ancestor

Bounding Volume Hierarchy

Bounding volumes of objects are used for fast collision detection and also in acceleration algorithms such as view frustum culling. Bounding volumes can be computed for different moving parts of an object and then combined in a hierarchical manner to obtain the overall bounding volume (Fig. 3.14). The geometric parameters defining a bounding volume can be stored in a scene graph node, and computed on the fly whenever a transformation is applied to the vertices.

Commonly used bounding volumes are axis-aligned bounding boxes (AABB), oriented bounding boxes (OBB), spheres, discrete oriented polytopes, and convex hulls. Each bounding volume has certain advantages and limitations over others, and is suitable for a specific set of applications. An AABB can be computed and represented using six parameters that define the minimum and maximum values of x, y, and z coordinates of points it encloses. However, these parameters will have to be recomputed every time an object is rotated. On the other hand, OBBs and spheres are rotation invariant. In this topic, examples are provided using AABBs and spheres only. Other types of bounding volumes and their computational aspects are discussed in detail in Chap. 9.

Since the bounding volume parameters depend on the transformed object coordinates, bounding volume updates can be performed only after applying the transformations. Unlike transformations, this process starts at the nodes containing object primitives, and the bounding volume parameters of group nodes are updated based on the computed values at the child nodes.

Two-dimensional bounding volume hierarchies for the model in Fig. 3.2, using axis-aligned rectangles (top row) and circles (bottom row)

Fig. 3.14 Two-dimensional bounding volume hierarchies for the model in Fig. 3.2, using axis-aligned rectangles (top row) and circles (bottom row)

 (a) Bounding circles of two objects. (b) Combined bounding circle formed using the parameters of the two component bounding circles. (c) The minimal bounding circle

Fig. 3.15 (a) Bounding circles of two objects. (b) Combined bounding circle formed using the parameters of the two component bounding circles. (c) The minimal bounding circle

It is therefore often desirable that the parameters defining a bounding volume stored at a group node can be computed based on the bounding volume parameters of its child nodes. It should also be noted here that such a computation may not always yield a minimal bounding volume. For example, the bounding sphere computed as the union of two bounding spheres may not necessarily be the minimal bounding sphere for the union of points within those spheres. A two-dimensional equivalent of this case is shown in Fig. 3.15, using bounding circles of two objects.

We discuss below the process of updating the bounding volume parameters (using AABBs and spheres as examples) at a group node based on the updated parameters of its child nodes. If there are n child nodes, we combine the volumes of

Box 3.1 Bounding Volumes

Given a set of mesh vertices with coordinates fxi, y,-, z,}, i = 0…N— 1, the bounding volume parameters for AABB and sphere are computed as follows:

Axis Aligned Bounding Box (AABB):

tmpc2f9-114_thumb[2]tmpc2f9-115_thumb[2]

Sphere: fu, v, w, r}

Computation of bounding sphere using the geometric centre of points:

tmpc2f9-116_thumb[2]

Computation of bounding sphere using AABB of points:

tmpc2f9-117_thumb[2]

two children at a time and obtain the final bounding volume of the parent, in n— 1 steps. Given two AABBs with parameters {Xmin1, ymin1, Zmin1, Xmax1, ymax1, Zmax1} and fxmin2, ymin2, Zmin2, Xmax2, ymax2, Zmax2}, the combined volume has parameters fmin(Xmin1, Xmin2), min(ymin1, ymin2), min(zmin1, Zmin2), max(xmax1, Xmax2), max(ymax1, ymax 2), max(zmax1, zmax2)} (Box 3.1).

In the case of spheres, let the parameters of the two volumes be given by fu1, v1, w1, r1} and fu2, v2, w2, r2}. The required parameters of the combined sphere are denoted as fuc, vc, wc, rc}. First we compute the distance between the centres:

tmpc2f9-118_thumb[2]

If d < |r1 — r21, then one of the spheres is inside the other. The combined sphere in this case is the same as the larger among the two spheres. If d> |r1 — r21, the spheres either overlap or are disjoint. For this configuration, we compute the radius and the centre of the combined sphere as follows:

tmpc2f9-119_thumb[2]

A detailed description of different types of bounding volumes, their computation and intersection tests is given later in Sect. 9.1.

Next post:

Previous post: