## 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 DGP2016 application and how they work. The DGP2016 SceneGraph is a restricted VRML SceneGraph. The DGP2016 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 DGP2016 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 DGP2016 application to support texture mapping. Right now the DGP2016 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 structurevoid 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 DGP2016 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 DGP2016 application, for example, to compute an appropriate initial viewpoint.