What is a scene graph?
A scene graph as used in videogames is defined as a tree of nodes, where each node has 1 parent or no parent. The node without a parent is called the root node, because it defines the start of the tree. Each node can also have 0 or more children.
What are they used for? Suppose you have a game where tanks are driving over terrain, shooting at each other. Each tank has a rotation and a position, compressed into a single 4x4 matrix. But what if we want to move the barrel of the tank? We want it to move relative to the tank, not completely independently.
So we'll split up the task: we put each tank in a separate node and add them as children to our root node. And then we add another node to each tank, a node for the barrel.
We traverse a tree from the bottom up. However, this is hard, because while a tree only has 1 root node, it can have n leaf nodes (nodes without children). Fortunately, the math works the other way around too.
To get the transformation for our barrel, we need to multiply the transformations of its parent, all the way up to the root node.
final_transform = root_transform * tank_transform * barrel_transform;
So what happens if we change the rotation in the tank_transform variable? The barrel rotates with it! This means that our barrel transformation is now relative to the tank transformation.
Updating a scene graph using multiple threads
And now to your question. You effectively want to flatten your scene graph. You would like to update your graph in steps, without those pesky dependencies on parent transformations. Well, one approach I've used in the past is to have each node contain a "dirty" flag for its transformation.
Let's say our tree looks like this in memory:
0 root
1 tank1
2 barrel1
3 tank2
4 barrel2
When can we use barrel2? When tank2 has finished building its transformation matrix. When can we use tank2? When root has finished building its transformation matrix. So here's how it would work in practice. We add a flag saying if a transformation matrix is dirty or not to each node, and we give them a parent id.
id name parent_id dirty
----------------------------
0 root -1 true
1 tank1 0 true
2 barrel1 1 true
3 tank2 0 true
4 barrel2 3 true
Now let's traverse the list. Check if the dirty flag is true. If so, check if its parent's dirty flag is true. If not, compute transformation matrix. If so, wait until next pass.
First pass:
id name parent_id dirty
----------------------------
0 root -1 false
1 tank1 0 true
2 barrel1 1 true
3 tank2 0 true
4 barrel2 3 true
Second pass:
id name parent_id dirty
----------------------------
0 root -1 false
1 tank1 0 false
2 barrel1 1 true
3 tank2 0 false
4 barrel2 3 true
Third pass:
id name parent_id dirty
----------------------------
0 root -1 false
1 tank1 0 false
2 barrel1 1 false
3 tank2 0 false
4 barrel2 3 false
Why is this useful for multi-threading? Because by using multiple passes to compute the transformation matrices, you have negated the dependency on the parent data. However, this glosses over several problems:
If thread 1 is writing to node 0, what will thread 2 read for node 1's parent?
What happens when nodes point to each other as parents? (deadlock)
How do you safely remove a node from this tree?
Summary
If you're not interested in a multithreaded scene graph, I would suggest just using a generic Node class that can have 0 or more children. Call its Update function with its parent's transformation matrix and you're golden.
If you want to look at some source code for that, I'd suggest looking at Ogre's scene graph implementation. It's very easy to read and understand.
