What should be contained in a game scene graph?

Question

Would you help me to clarify, please, what what exactly should be contained within a game scene graph? See the following list, please:

• Game Actors? (obviously yes, all the objects changing state should be the major prart of the Scene Graph)
• Simple static game ojbects? (I mean ojects places in the background that do not get animated, neither do they collide)
• Game Triggers?
• Game Lights?
• Game Cameras?
• Weapon Bullets?
• Game Explosions and Special Effects?

The above considered object types. Now to the coverage of the scene graph:

• Should a scene graph contain the whole game level map since the level start, or should it contain only the visible portion of the map? If the second is true, it would mean that scene graph would be continuously updated, by adding/removing game objects, as the player moves. However, containing only the visible are of the map obviously would be much faster to traverse and update.

Answer 1

I think a good bit of reading up on what other scene graph technologies are doing would yield a lot of benefits for you.

Background
For example, look at the Ogre3D description. It is a scene graph based graphics engine which is open source. I would suggest looking at the tutorials and see how scene nodes are being used (Note: I'm not telling you to learn how to use Ogre, rather what features are present in Ogre's scene nodes and scene managers)

SceneNode documentation:
http://www.ogre3d.org/docs/api/1.9/class_ogre_1_1_scene_node.html

SceneManager documentation: http://www.ogre3d.org/docs/api/1.9/class_ogre_1_1_scene_manager.html

Something else worth looking at is the following link:
http://sgl.sourceforge.net/#features

It is an OpenGL based scene graph solution and the features page there shows all of the nodes that it can contain.

Your Suggested Nodes
I'm of the opinion that a scene graph should be as abstracted away as much as possible from the game logic so you don't have any dependency issues. For each of your bullet points I would say the following:

Game Actors
I'd probably say no. Similar to Ogre, I would have a base Entity class (which would contain the object specific logic) and a base SceneNode with an Entity member pointer to get the appropriate information to render the object (Position, Orientation, etc)

EDIT: I'm not saying to not include your game actors in the scene graph here (otherwise nothing would show up :P) I'm saying to have a scene node with a reference to the logical game actor class, so you've still got loose coupling of the rendering and updating of game objects.

Simple static game ojbects
Yes

Game Triggers?
No, this sounds like game specific logic to me.

Game Lights?
Yes

Game Cameras?
Yes

Weapon Bullets?
Not completely certain about this one, but I'd probably say yes, but you'd probably want all bullets as children to a "BulletCollection" parent scene node, just so you can cache that position and you won't have to traverse the scene graph much to remove and add bullets to render.

Game Explosions and Special Effects?
Not certain, I'll let someone else answer that.

Scene Graph Coverage
If you have a relatively small level, you should be able to store the entire level in a scene graph and then optimize for visibility using an Octree (usually for outdoor environments) or a BSP tree (usually for indoor environments).

If you have a much larger level and you don't want to do any level loading, this is where streaming would come into play, but that's another issue entirely. I'd start out with a small level and incrementally see how large you can make it without adversely affecting performance.

Conclusion
To me a scene graph is for the Render portion of a game loop. You shouldn't couple your rendering and your logic updates too closely together, otherwise you're going to run into annoying dependency issues.

Answer 2

My inclination is to suggest putting fewer things in a scene graph. See in particular this article by Tom Forsyth: "Scene Graphs -- Just Say No."

The crux of Forsyth's article is that you shouldn't be trying to cram a bunch of unrelated stuff into one big master data structure. This is much akin to the ideas that I touched on in this answer as regards deriving everything in the game from GameObject and then shoving it all in one big heterogeneous list (which is to say, that's bad).

Relatively few objects in the world truly exhibit a strong parent-child relationship as befits a tree structure. The canonical example of a coffee cup on a table is usually used here -- sure, you could consider it to be a 'child' of the table... at least until it gets knocked off. Then is it really still a child of the table? This means your 'tree' can end up pretty shallow and kind of degenerates to a list anyhow.

So I would suggest you use multiple data structures for multiple things, as makes the most sense for those things. Static geometry and lights, for example, seem like a reasonable thing to shove into a scene graph. Even if the represented objects don't have natural parent-child relationships, the fact that they are static means you can give them structural parent-child relationships knowing that they never change.

Game actors... I'm not so sure about. Anything that tends to move, in fact, means you usually need to keep them near the root of the graph or re-parent them constantly (which is a chore and not super efficient).

Bullets, triggers, special effects and other transient objects I would store elsewhere. Nothing that renders or has a visual representation (a trigger is typically an invisible bounding volume, a bullet is usually just a ray-cast) should be in a render graph. You should strive for separation of render and logic layers.

For what it's worth, I have never used a tree-like scene graph in any of the renderers I have built for non-academic use (obviously I have built tree-like scene graphs before, which is how I came to the conclusions that I am now attempting to get you to agree with).

I use spatial partitioning methods that are appropriate to the style of game (quad-tree, octree, BSP, et cetera) to group/cull the logical entities in the game that are should be (a) processed this frame and (b) rendered this frame. I then end up feeding the set of objects from list (b) into a system that maps logical objects to render descriptions and sorts those descriptions into buckets based on properties (for example, anything that uses transparency will be shoved into the bucket for "stuff that should be rendered back-to-front). Then I render every bucket in order, and for each bucket render every description in order. I guess you could call this a "tree," but it's doesn't exhibit the typical state/transform propagation methods that traditional tree-oriented scene graphs do. YYMV, because the system certainly has deficiencies, but it works pretty well for me.