Digital Geometry Processing / Core Mesh Data Structures

Core Scene Graph Data Structures in C++

The Virtual Reality Modeling Language (VRML’97) is the International Standard ISO/IEC 14772-1:1997. The VRML2 Cheat Sheet is a summary of all the VRML'97 nodes. The Core Scene Graph is an implementation of minimal subset of the VRML'97 standard.

A VRML file represents a scene graph. A scene graph is a tree structure, which comprises a hierarchy of nodes, linked by relative geometric transformations. The geometry nodes are the leaves of the tree. Our first task this week is to understand how the SceneGraph data structures are implemented in the DGP2023 application and how they work. The DGP2023 SceneGraph is a restricted VRML SceneGraph. The DGP2023 SceneGraph comprises a tree-‐ structure which can be changed dynamically, and may contain an arbitrary number of IndexedFaceSet nodes as leaves. Other nodes, such as the Group and Transform nodes, allow for grouping and for relative positioning of nodes with respect to their parents in the tree.

The Group and Transform nodes, which may have multiple children, are used to build the tree structure. This is how these two nodes are described in the VRML standard

Group {
  MFNode children               []
  SFVec3f bboxCenter            0 0 0
  SFVec3f bboxSize              1 1 1
}

Transform {
  SFVec3f center                0 0 0
  MFNode children	            []
  SFRotation rotation           0 0 1 0
  SFVec3f scale                 1 1 1
  SFRotation scaleOrientation   0 0 1 0
  SFVec3f translation           0 0 0
  SFVec3f bboxCenter            0 0 0
  SFVec3f bboxSize              1 1 1
}

We have implemented the Transform node as a subclass of the Group node with additional functionality. We have implemented a virtual Node class as the base class of all our VRML nodes. The Node class does correspond to any VRML node, but we will use it to store information common to all the nodes, such as a node name. The Group node has been implemented as a subclass of the Node class. We use an instance of the SceneGraph class to represent the root of each scene graph. The SceneGraph class which is also implemented as a subclass of the Group node. Each instance of the SceneGraph class is associated with a file. The name of the file, as well as other global parameters, are stored as fields of the SceneGraph class. Any Group node is allowed to be a child of any other Group node, as long as the directed graph defined by the parent-‐child relationships does not have cycles.

We start the design of our classes by writing down their private variables, for which we have implemented public methods to access them. The constructors take care of setting default values for all the fields, as specified in the VRML standard. Initial assignment of private variables for the Node, Graph, Transform, and SceneGraph classes are

class Node {
  string         _name;
};

class Group : public Node {
  vector _children;
  Vec3f	         _bboxCenter;
  Vec3f	         _bboxSize;
};
  
class Transform : public Group {
  Vec3f	         _center;
  Rotation       _rotation;
  Vec3f	         _scale;
  Rotation       _scaleOrientation;
  Vec3f	         _translation;
};
    
class SceneGraph : public Group {
  string         _fileName;
};

We also need to define some data types corresponding to the various field types used in the VRML’97 specification. We have decided to construct some simple classes of our own to represent these VRML data types. For example, a starting point to define some of these data types could be

class Vec2f {
public:
  float x,y;
  Vec2f():x(0.0f),y(0.0f) {}
  Vec2f(Vec2f& src):x(src.x),y(src.y) {}
  Vec2f(float X, float Y):x(X),y(Y) {}
};

class Vec3f { public: float x,y,z;
  Vec3f():x(0.0f),y(0.0f),z(0.0f) {}
  Vec3f(Vec3f& src):x(src.x),y(src.y),z(src.z) {}
  Vec3f(float X, float Y, float Z):x(X),y(Y),z(Z) {}
};

class Color { public: float r,g,b;
  Color():r(0.0f),g(0.0f),b(0.0f) {}
  Color(Color& src):r(src.r),g(src.g),b(src.b) {}
  Color(float R, float G, float B):r(R),g(G),b(B) {}
};

class Rotation { public:
    Vec3f u; Float angle;
  Rotation():u(0.0f,0.0,1.0),angle(0.0f) {}
  Rotation(Vec3f& u0, float angle0):u(u0),angle(angle0) {}
};

The Group node and all its subclasses constitute the parent nodes of the SceneGraph tree structure. At the leaves of the tree structure we have Shape nodes. In addition to Group nodes and the Group subclasses, Shape nodes are also allowed to be children of any Group node. We will not allow any other node to be a child of a Group node. As Shape node has two fields, appearance, and geometry, and both fields may contain null pointers

Shape {
  SFNode appearance NULL
  SFNode geometry   NULL
}

The appearance field of a Shape node is only allowed to contain a pointer to an Appearance node. In the VRML’97 specification the Appearance node has three fields, material, texture, and textureTransform. In our implementation the Appearance only has two fields, material and texture.

Appearance {
  SFNode    material         NULL
  SFNode    texture          NULL
  // SFNode textureTransform NULL
}

The material field of an Appearance node is only allowed to contain a pointer to a Material node. The Material node has several fields which contain information used to render the objects represented in the geometry node of the Shape node. Not all of these fields are actually used in the DGP2023 application yet. The diffuseColor field value is used to paint a geometry object when the object is not specified with bound color properties.

Material {
  SFFloat ambientIntensity	0.2	
  SFColor diffuseColor		0.8 0.8 0.8
  SFColor emissiveColor		0 0 0
  SFFloat shininess		0.2	
  SFColor specularColor		0 0 0
  SFFloat transparency		0
}

In the VRML’97 specification the texture field of an Appearance node is allowed to contain pointers to several different texture nodes. In our implementation we only allow the texture field of an Appearance to contain a pointer to an ImageTexture node, which we have implemented as a subclass of the PixelTexture node, just to allow for future expansion of the DGP2023 application to support texture mapping. Right now the DGP2023 application does not have internal data structures to represent images, even though texture coordinates are supported.

ImageTexture {
  MFString url     []
  SFBool   repeatS TRUE
  SFBool   repeatT TRUE
}

PixelTexture {
  // SFImage image   0 0 0
  SFBool     repeatS TRUE
  SFBool     repeatT TRUE
}

As for the design of these classes, here we have an initial layout of private variables.

class Shape : public Node {
  Node*	     _appearance;
  Node*	     _geometry;
};

class Appearance : public Node {
  Node*	_material;
  Node*	_texture;
  // Node*   _textureTransform;
};

class Material : public Node {
  float      _ambientIntensity;
  Color      _diffuseColor;
  Color      _emissiveColor;
  float      _shininess;
  Color      _specularColor;
  float      _transparency;
};

We have not implemented a class to represent a TextureTransform node, and our Appearance class does not contain a field to store a pointer to an instance of TextureTransform. Along the same lines, we have not implemented a class to represent images yet. We have implemented the PixelTexture node just because it make sense to make ImageTexture a subclass of PixelTexture, but we have not implemented the functionality needed to manipulate images and pixels. We will add this functionality as the need arises later.

class PixelTexture : public node {
  // Image* _image;
  bool      _repeatS;
  bool      _repeatT;
};

class ImageTexture : public PixelTexture {
  vector _url;
};

Finally, we only allow pointers to IndexedFaceSet nodes and IndexedLineSet nodes as values for the geometry fields of Shape nodes. In the VRML'97 standard teh IndexedFaceSet node is defined as follows:

IndexedFaceSet {
  SFNode	color           NULL	
  SFNode	coord           NULL	
  SFNode	normal          NULL	
  SFNode	texCoord        NULL	
  SFBool	ccw             TRUE
  MFInt32	colorIndex      []		# [-1,)
  SFBool	colorPerVertex  TRUE		
  SFBool	convex          TRUE		
  MFInt32	coordIndex      []		# [-1,)
  SFFloat	creaseAngle	0		# [ 0,)
  MFInt32	normalIndex	[]		# [-1,)
  SFBool	normalPerVertex TRUE		
  SFBool	solid           TRUE		
  MFInt32	texCoordIndex   []		# [-1,)
}

In our implementation the IndexedFaceSet class has the following layout of private variables, and the public methods are added to get and set these variables.

class IndexedFaceSet : public Node {
  private:
    vector	_coord;
    vector		_coordIndex;
    bool		_colorPerVertex;
    vector	_color;
    vector		_colorIndex;
    bool		_normalPerVertex;
    vector	_normal;
    vector		_normalIndex;
    vector	_texCoord;
    vector		_texCoordIndex;
    bool		_ccw;
    bool		_convex;
    float		_creaseAngle;
    bool		_solid;
};

Tree Traversal

Several operations, including your file loader, your file saver, and the rendering loop require methods to depth-first traverse the scene graph. In the case of the file loader, the scene graph is also constructed as it is traversed. To simplify these tasks the file loader assumes some restrictions on the VRML syntax. That is, both input and output files to and from your program will be valid VRML files, but the file loader is supposed to parse only those which satisfy the restrictions listed below. In addition, the file loader must be able to parse all the files written by the file saver.

After the first header line "#VRML V2.0 utf8" the VRML file is only allowed to have a sequence of nodes, concatenated one after the other. Only the Group, Transform, and Shape nodes are allowed at this level. We have also implemented the DEF/USE syntax as defined in the VRML’97 specification to assign names to nodes and to reuse nodes. In this implementation of the SceneGraph data structure, we are able to load VRML files containing node names, and we are able to save the names to the output files.

All these nodes are saved in the children field of the SceneGraph node. Even though the SceneGraph node is implemented as a subclass of Graph, the tokens “children” “[“ and “]” are not written in the file to delimit its children. Instead, all the nodes parsed after the header line are considered children of the SceneGraph node. The end of the file marks the end of the list of children of the SceneGraph node. If the application is successful parsing the whole file without errors, it should also save the filename in the SceneGraph field “filename”.

The nodes “Appearance”, “Material”, “ImageTexture”, and “IndexedFaceSet” can be found only while parsing a Shape node. They are not allowed to be listed as children of a Group or Transform node, and they cannot be children of the top level SceneGraph node either. In all cases, after recognizing the type of node from the parsed token, the file loader constructs an instance of the node, attach it to the proper place (children of a Group, Transform, or SceneGraph node; or specific field of another node), and parses the node starting from the expected “{“ token until the matching “}” token. One way to organize the loader code is to write a separate function to parse each different node class. For example, our implementation has the following structure

void load(string filename, SceneGraph& wrl) {
  try {
    // open file
    ifstrm istrm(filename);
    // read header line and verify
    // ...
    // create Tokenizer from open input stream Tokenizer tokenizer(istrm);
    // parse SceneGraph children while(tokenizer.get()) {
    if(tokenizer==”Shape”) {
      Shape* shape = new Shape();
      Wrl.addChild(shape);
      parseShape(istrm,*shape);
    } else if(tokenizer==”Graph”) {
      Graph* graph = new Graph();
      wrl.addChild(graph);
      parseGraph(istrm,*graph);
    } else if(tokenizer==”Transform) {
      Transform* transform = new Transform();
      wrl.addChild(transform);
      parseTransform(istrm,*transform);
    }
    wrl.setUrl(filename);
  } catch(MyException* e) { wrl.clear();
    cerr<< “ERROR | “ << e-‐>what() << endl; delete e;
  }
}

Again, note that after a token such as “Shape” is detected, an instance of the Shape class is constructed, added to its parent as a child, and then the parser method for the Shape class is invoked. This parser parses from the “{“ token expected to follow the “Shape” token, until the matching “}” token is detected. While parsing the Shape node, the parseShape() method may encounter a number of other nodes which can only appear in specific places within a Shape node. For example, if a “Material” token is found, then a parseMaterial() method is be called, which parses from the “{“ token expected to follow the “Material” token, until the matching “}” token is detected.

When the load() method described above encounters a “Graph” token, it creates an instance of the Graph class, adds it to its parent as a child, and calls the parseGraph() method, which parses from the “{“ token expected to follow the “Graph” token, until the matching “}” token is detected. Within these limits the parseGraph() method may encounter the “children” token, which should be followed by the “[“ token, an arbitrary number of “Shape”, “Transform”, or “Graph” nodes, and a closing “]” token. For each of the children nodes, the parseGraph() calls the corresponding node parser. The process continues recursively in this way, resulting in a depth-‐first traversal of the SceneGraph structure.

Note that rather than building special data structures to keep track of the traversal within the top load() method, we have decided to use recursive function calls, in fact using the program stack to control the tree traversal. This strategy is acceptable here because in practice we don’t expect to encounter very large and/or deep scene graphs. The same strategy is used in the saver class, as well as in the rendering loop, to traverse the SceneGraph. An alternative is to implement a SceneGraphTraversal class, with a structure such as

class SceneGraphTraversal {
private:
  SceneGraph& _wrl;
public:
  SceneGraphTraversal(SceneGraph& wrl);
  void	reset();
  Node*	next();
  void	advance();
};

The reset() method starts the traversal pointing internally the current node to the root of the tree. The next() method returns the current node. The advance() method moves the current node to the next node in the depth-‐first traversal order, and returns a NULL pointer at the end of the traversal. Note that the only node types returned are Shape, Graph, and Transform. You get access to other node types, such as Material, or IndexedFaceSet, from the fields of the Shape nodes. Here you have an example of how this class can be used

SceneGraph wrl;
// load from file or build by adding children SceneGraphTraversal
// traversal(wrl); traversal.reset()
Node* node;
while((node=traversal.next())!=(Node*)0) {
  if(node-‐>isShape()) {
    Shape* shape = (Shape*)node;
    // for example
    node = shape-‐>getMaterial();
    if(node!=(Node*)0 && node-‐>isMaterial()) {
      Material* material = (Material*)node;
      // process fields of this Material node
    }
    node = shape-‐>getGeometry();
    if(node!=(Node*)0 && node-‐>isIndexedFaceSet()) {
      IndexedFaceSet* ifs = (IndexedFaceSet*)node;
      // process fields of this IndexedFaceSet node
    }
  } else if(node-‐>isTransform()) { Transform* transform = (Transform*)node;
    // ... you should not traverse the children here
  } else if(node-‐>isGraph()) { Graph* graph =  (Graph*)node;
    // ... you should not traverse the children here
  } else {
    // throw new StrException(“unexpected node type”)
  }
  traversal.advance();
}

The Transform node

The Transform node provides the functionality necessary to change the coordinate system of the Transform node children with respect to the coordinate system of the Transform node itself. To understand how this transformation is specified and represented in the Transform node fields you need to read the VRML specification. Some of these fields are used to store 3D rotations, which in VRML are specified by an axis of rotation and an angle. The axis of rotation is described by a 3D unit-‐length vector, and the angle is measured in radians. Rodrigues’ Formula is used to convert this (axis,angle) representation into a 3x3 orthogonal matrix representation. For the mathematical detail of how to convert back and forth between these two representations, read the 3D Rotations http://mesh.brown.edu/rotations notes.

The overall transformation specified by the fields of a Transform node can be represented as a 4x4 matrix. The transformation is applied to a 3D point by multiplying the 4x4 matrix by the homogeneous coordinates of the 3D point. This is the standard in computer graphics pipelines such as OpenGL, which we use in the DGP2023 application.

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.

Brown University School of Engineering

ENGN 2501 Digital Geometry Processing

Spring 2023

Core Scene Graph Data Structures in C++

Tree Traversal

The Transform node

Recursive Computation of Bounding Boxes