# is a scene graph actually a tree?

All "scene graphs" I've seen in practice are actually trees, but I have some vague memories about somebody saying a while ago that sometimes they can actually be graphs (technically, trees are already graphs, but you get the point).

If they can actually be graphs, what are some practical examples?

If they're always just trees, is there some history behind why it was originally called "scene graph"?

• Any time you have instancing in your scene, i.e. multiple copies of the same base geometry, you can represent that as a single leaf node with multiple transformation nodes as parents. – user106 Jan 27 '18 at 8:15
• I completely missed that common use case, that's a very practical and clear example. Thanks. – Mei Zhang Jan 27 '18 at 9:24
• @Rahul You should post that as an answer, even though it's short. It's exactly the example the questioner was looking for. – Dan Hulme Jan 27 '18 at 13:50

Yes, scene graphs can be non-tree graphs. Your question is a little vague, but assuming you're talking about something like the scene graph in rendering a frame of video, for say a feature film, then yes, there are often references between objects. For example, in a compositing application, you might have a piece of footage with an effect applied. The effect may have as one of its inputs another piece of footage which is also in the scene. (It might use the other image for blending, as a reflection map, as a diffuse or specular lighting map, a bump map etc.) So you could have a scene that looks like this:

scene contains:
footage A contains:
filter "Multiply Blend" which takes input:
footage B
footage B
footage C


In something like a game, you might objects that refer to other objects that they can collide with:

scene contains:
ground which can collide with:
player
ball
goal
player which can collide with:
ground
ball
goal
ball which can collide with:
player
ground
goal


etc.

• Sorry, my question was indeed a little vague. I had in mind scene graphs for 3D rendering. The collision examples are a bit too much into the app-specific side of things from my point view. At the app level, it's easy to imagine almost anything as a graph of relationships between different objects. However, as pointed out by @Rahul, one example is when multiple nodes with different transformations share the same geometry, in that case it's a non-tree graph. – Mei Zhang Jan 27 '18 at 9:30