Scene Graphs
A scene graph is a set of nodes that hold transformation matrix data and pointers to other nodes and geometry. It takes the form of a directed tree. The idea is that to render a shape, you traverse the directed tree of transformations. This is the basis of most scene data structures.
As you traverse a scene graph, you multiply the matrices you arrive at on the right of the current matrix. Therefore, if you had a scene graph like A -> B -> C, you would have a total transformation matrix of $ABC$.
The scene graph is traversed depth first. The algorithm looks like this:
traverse(Node n, Matrix m) {
m = m * n.matrix()
foreach child c of n {
traverse(c)
}
draw(n.geometry())
}
You’ll see that the drawing is done after the traversal. That means that while we calculate our matrices top-down, the drawing is done bottom-up. Generally, a child node is drawn before a parent node is drawn.
Representing Scene Graphs
A scene graph is essentially a tree. Generally, these are usually represented as a high level as a pointer to a Node object, with pointers to their children contained within. In C++, there are five pointer/reference types:
NodeNode&Node*unique_ptr<Node>shared_ptr<Node>We’ll find that the best solution for a scene graph is to useunique_ptr.
Within the Node class, you’ll find the following member variables:
class Node {
std::vector<uPtr<Node>> children;
mat4 transformation;
Polygon2D* geometry; //Geometry stays on the stack
}