Scenegraph Design Notes

Base Classes

Relationships (parent/child) are defined at the first level of derived nodes: Node and NodeComponent.

Node represents the structural parts of the scene graph - it has a set of bounds (either implicit or explicit), and a single parent. The design of the scene graph is to provide a simple structure. All nodes have only a single parent (exceptions noted shortly), but may have multiple children. The single parent restriction is to keep update costs to a minimum. One of the most important structures to scene graphs is the bounding box information that is used for culling, sorting, picking etc. Any change to a bounds low in the scenegraph can be quite costly forcing a large number of recalculations up the tree. In CAD applications, in particular, the nesting of nodes can become very deep, so any change to one part will have a heavy cost on the updates. Updating bounds requires a walk back up the tree informing the parents of such a change. If multiple parents were generally permitted, that means each level of the scenegraph would require a for loop iteration over the parent listing. Looping structures are, relatively, expensive particularly as a multi-parent scene graph structure would require possible hundreds of nested for loops to be performed.

NodeComponent represents a non-structural property of a Node. These properties define aspects such as visual appearances, rendering instructions (for example blending requirements), and so forth. These structures may be shared between many parents (in fact, for good rendering performance it is highly recommended to!).

Both base classes provide explicit rendering call methods that assume a typical rendering pipeline with state sorting. Methods define push and pop states that allow the node to directly call the OpenGL methods needed for rendering. We don't ever expect end users to be making these calls, but there is nothing preventing you from doing so if you manage to obtain a GL context to work with. The idea behind this design descision was that we wanted to keep the data and GL commands as close together as possible. Most other APIs work with a different strategy of having the renderer commands in a separate area (typically named something like RenderBin). There were several aspects of that design path that we didn't like - most principally the idea of being able to quickly extend the scene graph with new features or custom node implementations. Having a centralised renderer object means that adding any new rendering functionality requires modification of that class as well as the class that is representing the node in the scene graph. By containing the data and rendering instructions in a single class, extensibility for the most part is much easier to handle, while the cases where modification to the pipeline and output stages are drastically reduced.

Moving up the class heirarchy in both trees from Node and NodeComponent show the standard set of nodes that one would expect of a scenegraph. We've mostly stayed with conventions here, and only done minor deviations. For example, with textures, we've assumed multitexture support from the start - Using single or multiple textures uses exactly the same code structure (TextureUnit).

Structures Permitted

All classes that derive from Node may only have a single parent. The one exception to this rule is the SharedNode class that provides the ability to have multiple parents for a portion of the scene graph. We've decided to part from the typical way of doing this of having the sharing done through a Group node (eg SharedGroup) as we found this to be causing a lot of extra calculation work to be done every frame. Effectively when doing picking a lot of double calculations are performed on the bounding boxes. By providing a single child node with multiple parents, the culling and picking algorithms could look for a single class instance and ignore it, directly moving onto the children.

All classes that derive from NodeComponent have multiple parents all the time. Since these represent rendering attributes, for the purposes of fast state sorting, it is encouraged that you share instances of these as much as possible.

Reading/Writing a node

Our design works on the principle of the scene graph instructing the user code about the appropriate time to update the code. The design principle is to allow reading at any time, but writing only at one very specific time and only to the nodes that the user has marked as needing to be modified. By doing this, we can keep track internally of what has changed and thus provide optimised internal updates.

There are two different types of updates that one can do on the scene graph - those that effect structural information (ie bounds) and those that effect visual or rendering properties. We've made the distinction between the two types of update to provide for internal optimisations. Changing the emmisive colour of an object should not result in the need to change the bounding box values of the parent grouping structures. By providing two separate callbacks we know which nodes need to update bounding information and which do not, thus saving ourselves a lot of CPU cycles that could be otherwise wasted.

Updating the scene graph is a two step process. Firstly application code informs the scene graph that it would like to perform an update, and then at some point in the future the callback is made and the node will update the appropriate details.

Updating the bounds

The approach we have taken to bounds updating separates the two processes. A lot of the matrix multiplication and transformation updates can be avoided by not updating them until needed, or not even calculating them at all. Our code does not keep a local to v-world transformation matrix at all. If you need these, you calculate them yourself or they are calculated on demand (for example only once the results of a pick operation are successful and the user has requested this information). Bounding box updates work from a bottom-up perspective.

Since we know which nodes of the scene graph had had their bounds altered, we can use this knowledge to optimise the updates without causing unnecessary recalculations for parts of the scene graph that have not changed. Each node that has had it's bounds registered as being changed will be told to update, and it marks it's parent as being dirty. The parent keeps a count of the number of dirty notifications it receives. Once the node has updated the bounds, it then informs the parent to update it's bounds. The parent decrements it's dirty counter. If the counter is non zero, nothing happens because it knows it has more children that are yet to update. Once the counter is zero, the parent updates it's bounds from all the children, then informs it's parent that an update should be made and thus the cycle continues. This method ensures that only parts of the scene graph that have changed need to be recalculated and does so in an efficient manner.