Scene graphs

A scene graph is a general data structure that defines the spatial and logical relationship of a graphical scene for efficient management and rendering of graphics data. It is typically represented as a hierarchical graph, which contains a collection of graphics nodes including a top-level root node, a number of group nodes each of which can have any number of child nodes, and a set of leaf nodes each of which has zero child nodes and that serve together as the bottom layer of the tree. A typical scene graph does not allow a directed cycle (where some nodes are connected in a closed chain) or an isolated element (a node that has no child or parent) inside of itself.

Each group node can have any number of children. Grouping these child nodes allows them to share the information of the parent and be treated as one unit. By default, an operation performed by a parent propagates its effects to all of its children.

It also happens that certain nodes have more than one parent node, in which case the node is considered to be "instanced", and the scene graph can be defined as a directed acyclic graph (DAG). Instancing produces many interesting effects, including data sharing and multi-pass rendering.

The concept of scene graph has been widely applied in many modern software and applications, for instance, AutoCAD, Maya, CorelDraw, VRML, Open Inventor, and the one that we are going to investigate—OpenSceneGraph.