## 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:

`Node`

`Node&`

`Node*`

`unique_ptr<Node>`

`shared_ptr<Node>`

We’ll find that the best solution for a scene graph is to use`unique_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
}
```