This article is a continuation of previous WebGL articles. The previous article was about drawing multiple things. If you haven't read them I suggest you start there.
I'm sure some CS guru or graphics guru is going to give me an ear full but ... A scene graph is usually a tree structure where each node in the tree generates a matrix... hmmm, that's not a very useful definition. Maybe some examples would be useful.
Most 3D engines use a scene graph. You put the things you want to appear in the scene graph. The engine then walks the scene graph and figures out a list of things to draw. Scene graphs are hierarchical so for example if you wanted to make a universe simulation you might have a graph that looks like this
What's the point of a scene graph? The #1 feature of a scene graph is it provides a parent child relationship for matrices as we discussed in 2D matrix math. So for example in a simple (but unrealistic) universe simulation the stars (children), move along with their galaxy (parent). Similarly a moon (child) moves along with its planet (parent). If you move the earth the moon will move with it. If you move a galaxy all the stars inside will move with it. Drag the names in the diagram above and hopefully you can see their relationships.
If you go back to the 2D matrix math you might remember we multiply lots of matrices in order to translate, rotate, and scale objects. A scene graph provides a structure to help decide what matrix math to apply to an object.
Typically each Node
in a scene graph represents a local space. Given the correct
matrix math anything in that local space can ignore everything above it. Another
way to state the same thing is that the moon only has to care about orbiting the earth.
It does not have to care about orbiting the sun. Without this scene graph structure
you'd have to do much more complex math to compute how to get the moon to orbit the sun
because its orbit around the sun looks something like this
With a scene graph you just make the moon a child of the earth and then orbit the earth which is simple. The scene graph takes care of the fact that the earth is orbiting the sun. It does this by walking the nodes and multiplying the matrices as it walks
worldMatrix = greatGrandParent * grandParent * parent * self(localMatrix)
In concrete terms our universe simulation that would be
worldMatrixForMoon = galaxyMatrix * starMatrix * planetMatrix * moonMatrix;
We can do this very simply with a recursive function which is effectively
function computeWorldMatrix(currentNode, parentWorldMatrix) {
// compute our world matrix by multiplying our local matrix with
// our parent's world matrix.
var worldMatrix = m4.multiply(parentWorldMatrix, currentNode.localMatrix);
// now do the same for all of our children
currentNode.children.forEach(function(child) {
computeWorldMatrix(child, worldMatrix);
});
}
This brings up some terminology which is pretty common to 3D scene graphs.
localMatrix
: The local matrix for the current node. It transforms it and its children in local space with
itself at the origin.
worldMatrix
: For a given node it takes stuff in the local space of that node
and transforms it to the space of the root node of the scene graph. Or in other words it places it
in the world. If we compute the worldMatrix for the moon we'll get that funky orbit you see above.
A scene graph is pretty easy to make. Let's define a simple Node
object.
There's a zillion ways to organize a scene graph and I'm not sure which
way is best. The most common is to have an optional field of thing to draw
var node = {
localMatrix: ..., // the "local" matrix for this node
worldMatrix: ..., // the "world" matrix for this node
children: [], // array of children
thingToDraw: ??, // thing to draw at this node
};
Let's make a solar system scene graph. I'm not going to use fancy textures or anything like that as it would clutter the example. First let's make a few functions to help manage nodes. First we'll make a node class
var Node = function() {
this.children = [];
this.localMatrix = m4.identity();
this.worldMatrix = m4.identity();
};
Let's give it a way to set the parent of a node.
Node.prototype.setParent = function(parent) {
// remove us from our parent
if (this.parent) {
var ndx = this.parent.children.indexOf(this);
if (ndx >= 0) {
this.parent.children.splice(ndx, 1);
}
}
// Add us to our new parent
if (parent) {
parent.children.append(this);
}
this.parent = parent;
};
And here's the code to compute world matrices from local matrices based on their parentchild relationships. If we start at the parent and recursively visit the children we can compute their world matrices. If you don't understand matrix math check out this article on them.
Node.prototype.updateWorldMatrix = function(parentWorldMatrix) {
if (parentWorldMatrix) {
// a matrix was passed in so do the math and
// store the result in `this.worldMatrix`.
m4.multiply(parentWorldMatrix, this.localMatrix, this.worldMatrix);
} else {
// no matrix was passed in so just copy.
m4.copy(this.localMatrix, this.worldMatrix);
}
// now process all the children
var worldMatrix = this.worldMatrix;
this.children.forEach(function(child) {
child.updateWorldMatrix(worldMatrix);
});
};
Let's just do the sun, the earth, and the moon to keep it simple. We'll of course use
fake distances so things fit on the screen. We'll just use a single sphere model
and color it yellowish for the sun, bluegreenish for the earth and grayish for the moon.
If drawInfo
, bufferInfo
, and programInfo
are not familiar to you see the previous article.
// Let's make all the nodes
var sunNode = new Node();
sunNode.localMatrix = m4.translation(0, 0, 0); // sun at the center
sunNode.drawInfo = {
uniforms: {
u_colorOffset: [0.6, 0.6, 0, 1], // yellow
u_colorMult: [0.4, 0.4, 0, 1],
},
programInfo: programInfo,
bufferInfo: sphereBufferInfo,
vertexArray: sphereVAO,
};
var earthNode = new Node();
earthNode.localMatrix = m4.translation(100, 0, 0); // earth 100 units from the sun
earthNode.drawInfo = {
uniforms: {
u_colorOffset: [0.2, 0.5, 0.8, 1], // bluegreen
u_colorMult: [0.8, 0.5, 0.2, 1],
},
programInfo: programInfo,
bufferInfo: sphereBufferInfo,
vertexArray: sphereVAO,
};
var moonNode = new Node();
moonNode.localMatrix = m4.translation(20, 0, 0); // moon 20 units from the earth
moonNode.drawInfo = {
uniforms: {
u_colorOffset: [0.6, 0.6, 0.6, 1], // gray
u_colorMult: [0.1, 0.1, 0.1, 1],
},
programInfo: programInfo,
bufferInfo: sphereBufferInfo,
vertexArray: sphereVAO,
};
Now that we've made the nodes let's connect them.
// connect the celestial objects
moonNode.setParent(earthNode);
earthNode.setParent(sunNode);
We'll again make a list of objects and a list of objects to draw.
var objects = [
sunNode,
earthNode,
moonNode,
];
var objectsToDraw = [
sunNode.drawInfo,
earthNode.drawInfo,
moonNode.drawInfo,
];
At render time we'll update each object's local matrix by rotating it slightly.
// update the local matrices for each object.
m4.multiply(m4.yRotation(0.01), sunNode.localMatrix , sunNode.localMatrix);
m4.multiply(m4.yRotation(0.01), earthNode.localMatrix, earthNode.localMatrix);
m4.multiply(m4.yRotation(0.01), moonNode.localMatrix , moonNode.localMatrix);
Now that the local matrices are updated we'll update all the world matrices
sunNode.updateWorldMatrix();
Finally now that we have world matrices we need to multiply those to get a worldViewProjection matrix for each object.
// Compute all the matrices for rendering
objects.forEach(function(object) {
object.drawInfo.uniforms.u_matrix = m4.multiply(viewProjectionMatrix, object.worldMatrix);
});
Rendering is the same loop we saw in our last article.
You'll notice all of the planets are the same size. Let's try to make the earth larger
// earth 100 units from the sun
earthNode.localMatrix = m4.translation(100, 0, 0));
// make the earth twice as large
earthNode.localMatrix = m4.scale(earthNode.localMatrix, 2, 2, 2);
Oops. The moon got larger too. To fix this we could manually shrink the moon. A better solution though is to add more nodes to our scene graph. Instead of just
sun

earth

moon
We'll change it to
solarSystem
 
 sun

earthOrbit
 
 earth

moonOrbit

moon
This will let the earth rotate around the solarSystem but we can separately rotate and scale the sun and it won't
affect the earth. Similarly the earth can rotate separately from the moon. Let's make more nodes for
solarSystem
, earthOrbit
and moonOrbit
.
var solarSystemNode = new Node();
var earthOrbitNode = new Node();
// earth orbit 100 units from the sun
earthOrbitNode.localMatrix = m4.translation(100, 0, 0);
var moonOrbitNode = new Node();
// moon 20 units from the earth
moonOrbitNode.localMatrix = m4.translation(20, 0, 0);
Those orbit distances have been removed from the old nodes
var earthNode = new Node();
// earth 100 units from the sun
earthNode.localMatrix = m4.translation(100, 0, 0));
// make the earth twice as large
earthNode.localMatrix = m4.scale(earthNode.localMatrix, 2, 2, 2);
+earthNode.localMatrix = m4.scaling(2, 2, 2);
var moonNode = new Node();
moonNode.localMatrix = m4.translation(20, 0, 0); // moon 20 units from the earth
Connecting them now looks like this
// connect the celestial objects
sunNode.setParent(solarSystemNode);
earthOrbitNode.setParent(solarSystemNode);
earthNode.setParent(earthOrbitNode);
moonOrbitNode.setParent(earthOrbitNode);
moonNode.setParent(moonOrbitNode);
And we only need to update the orbits
// update the local matrices for each object.
m4.multiply(m4.yRotation(0.01), sunNode.localMatrix , sunNode.localMatrix);
m4.multiply(m4.yRotation(0.01), earthNode.localMatrix, earthNode.localMatrix);
m4.multiply(m4.yRotation(0.01), moonNode.localMatrix , moonNode.localMatrix);
+m4.multiply(m4.yRotation(0.01), earthOrbitNode.localMatrix, earthOrbitNode.localMatrix);
+m4.multiply(m4.yRotation(0.01), moonOrbitNode.localMatrix, moonOrbitNode.localMatrix);
// Update all world matrices in the scene graph
sunNode.updateWorldMatrix();
+solarSystemNode.updateWorldMatrix();
And now you can see the earth is double size, the moon is not.
You might also notice the sun and the earth are no longer rotating in place. That is now independent.
Let's adjust a few more things.
sunNode.localMatrix = m4.translation(0, 0, 0); // sun at the center
+sunNode.localMatrix = m4.scaling(5, 5, 5);
...
*moonOrbitNode.localMatrix = m4.translation(30, 0, 0);
...
+moonNode.localMatrix = m4.scaling(0.4, 0.4, 0.4);
...
// update the local matrices for each object.
m4.multiply(m4.yRotation(0.01), earthOrbitNode.localMatrix, earthOrbitNode.localMatrix);
m4.multiply(m4.yRotation(0.01), moonOrbitNode.localMatrix, moonOrbitNode.localMatrix);
+// spin the sun
+m4.multiply(m4.yRotation(0.005), sunNode.localMatrix, sunNode.localMatrix);
+// spin the earth
+m4.multiply(m4.yRotation(0.05), earthNode.localMatrix, earthNode.localMatrix);
+// spin the moon
+m4.multiply(m4.yRotation(0.01), moonNode.localMatrix, moonNode.localMatrix);
Currently we have a localMatrix
and we're modifying it each frame. There's a problem though
in that every frame our math will collect a little bit of error. There is a way to fix the math
which is called ortho normalizing a matrix but even that won't always work. For example let's
imagine we scaled down zero and back. Let's just do that for one value x
x = 246; // frame #0, x = 246
scale = 1;
x = x * scale // frame #1, x = 246
scale = 0.5;
x = x * scale // frame #2, x = 123
scale = 0;
x = x * scale // frame #3, x = 0
scale = 0.5;
x = x * scale // frame #4, x = 0 OOPS!
scale = 1;
x = x * scale // frame #5, x = 0 OOPS!
We lost our value. We can fix this by adding some other class that updates the matrix from
other values. Let's change the Node
definition to have a source
. If it exists we'll
ask the source
to give us a local matrix.
*var Node = function(source) {
this.children = [];
this.localMatrix = makeIdentity();
this.worldMatrix = makeIdentity();
+ this.source = source;
};
Node.prototype.updateWorldMatrix = function(matrix) {
+ var source = this.source;
+ if (source) {
+ source.getMatrix(this.localMatrix);
+ }
...
Now we can create a source. A common source is one that provides translation, rotation, and scale something like this
var TRS = function() {
this.translation = [0, 0, 0];
this.rotation = [0, 0, 0];
this.scale = [1, 1, 1];
};
TRS.prototype.getMatrix = function(dst) {
dst = dst  new Float32Array(16);
var t = this.translation;
var r = this.rotation;
var s = this.scale;
// compute a matrix from translation, rotation, and scale
m4.translation(t[0], t[1], t[2], dst);
m4.xRotate(dst, r[0], dst);
m4.yRotate(dst, r[1], dst);
m4.zRotate(dst, r[2], dst);
m4.scale(dst, s[0], s[1], s[2]), dst);
return dst;
};
And we can use it like this
// at init time making a node with a source
var someTRS = new TRS();
var someNode = new Node(someTRS);
// at render time
someTRS.rotation[2] += elapsedTime;
Now there's no issue because we are recreating the matrix each time.
You might be thinking, I'm not making a solar system so what's the point? Well, If you wanted to animate a human you might have a scene graph that looks like this
How many joints you add for fingers and toes is up to you. The more joints you have the more power it takes to compute the animations and the more animation data it takes to provide info for all the joints. Old games like Virtua Fighter had around 15 joints. Games in the early to mid 2000s had 30 to 70 joints. If you did every joint in your hands there's at least 20 in each hand so just 2 hands is 40 joints. Many games that want to animate hands animate the thumb as one and the 4 fingers as one large finger to save on time (both CPU/GPU and artist time) and memory.
In any case here's a block guy I hacked together. It's using the TRS
source for each
node mentioned above. Programmer art and programmer animation FTW! 😂
If you look at pretty much any 3D library you'll find a scene graph similar to this. As for building hierarchies usually they are created in some kind of modeling package or level layout package.