Scene Graph Theory

Question

I have a scenegraph that represents the whole world. However, at the moment if there are multiple copies of the same scene graph (aka the same model) it will just create a new scenegraph linking. This works, however, the loading time is insane. Which is to be expected. I have tried to load the model's scene graphs and simply just have the world link to these. However, when I need to travel up the scenegraph the model doesn't know anything about the world unless you count the last one that was using it. Making it impossible to render the models in the right place as everytime you travel up the scenegraph you get into the problem of not knowing where to go from the models node to get to the world node.

For example I have a scene graph for each model in the world, like a boat has a scene graph. If I want multiple copies of the boat in the world at the moment I will have to load the boat x amount of times. Which I don't want. I want to be able to specify the boat, load it, then have a world scenegraph which specifies down at the leaf nodes (Load boat). What is a design that would solve this problem?

Answer 1

You seem to be treating your scene graph as a tree - each scene contains N boats, each of which contains its own copy of the "boat" scene graph, etc. This is not fundamentally wrong, but can certainly be improved upon. The following diagram illustrates my understanding of your current approach, for a scene with two boats¹:

Rather than storing N copies of the "boat" scene graph if you have N boats, instead create N copies of a "SceneGraphReference" node that all reference a single copy of the "boat" scene graph. Each such node should maintain its own position/rotation/scaling etc information, so that the bulk of the information (the "boat" scene graph) is only stored once, but the information necessary to draw multiple copies in different places (position etc) is stored as often as necessary. This would look something like the following, for the same example with two boats:

To put this in more technical terms, your current approach is an N-ary tree: consider using a unidirectional acyclic graph instead².

---

1. Please excuse my (minor) abuse of UML diagrams.
2. Interesting things can be achieved by relaxing the unidirectional and acyclic restraints (i.e. using a plain old unrestricted graph), but that's a discussion for another time.

Answer 2

I assume you're doing a top-down traversal of the scene graph, e.g. for frustum culling or similar. You just need to remember where you came from when descending into the instanced scene graph (the boat in your example). You can do this by maintaining a stack of the nodes from the root to the current node, pushing when you descend a level and popping when you ascend. That way the stack at any point contains a complete record of how you got to the current node. (This is assuming a depth-first traversal order, which is the most common, I think.)