Core Scene Graph Data Structures in C++

Recursive Computation of Bounding Boxes

We have implemented methods to compute a bounding box aligned with the global coordinate system (the coordinate system of the top level SceneGraph node) for the complete scene described by the SceneGraph. In fact, since each Group node has fields to represent a bounding box, we do this computation recursively. But we do take into account the coordinate changes described by the Transform nodes. The coordinates of the eight corners of the bounding box enclosing all the children of a Transform node are transformed using the 4x4 matrix specified by the fields of the transform node before they are used to update the bounding box of the Transform node parent. This computation is performed using recursive function calls, as illustrated above. Alternatively, we can modify the SceneGraphTraversal class to achieve the same result within a single loop. We do need stacks to keep track of the state in the traversal algorithm, as well as to store the various accumulated transformation matrices. Here you have a pseudo-­‐code segment which illustrates this approach. 

SceneGraph wrl;
// load from file or build by adding children
// initialize the global transformation matrix to the identity
// initialize the matrix stack to empty Node* node = &wrl  while(node!=(Node*)0) {
if(node-­‐>isShape()) {
  Shape* shape = (Shape*)node;
  // -­‐  apply the global transform matrix to the geometry node of the Shape node
  // -­‐  process the transformed geometry node (rendering, bounding
  //      -box update, etc.)
} else if(node-­‐>isTransform()) { Transform* transform = (Transform*)node;
  // -­‐  push a copy of the current global transformation  matrix
  //	  onto the matrix stack
  // -­‐  compute the transform 4x4 matrix and multiply it on the right hand  side
  //	  by the current global transformation matrix in place
  // -­‐  set node to the first child of  transform
} else if(node-­‐>isGraph()) { Graph* graph =  (Graph*)node;
  // -­‐  push a copy of the current global transformation  matrix
  //	  onto the matrix stack
  // -­‐  set node to the first child of  transform
}
// while (node!=&wrl && node is the last child of its parent) {
//	pop last matrix from the stack
//	set node to the parent of the current node
// }
// if(node == &wrl) {
//	break;
// } else {
//	set node to the next child of its parent
// }

We have implemented a Group node method to update its bounding box as well as the bounding boxes of all its Group node descendants. When called for the SceneGraph node, the computation of the overall bounding box results. The overall bounding box is used in the DGP2023 application, for example, to compute an appropriate initial viewpoint.