Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Scene graph contains game nodes representing game objects. At a first glance, it might seem practical to use Scene Graph as physical container for in game objects, instead of std::vector<> for example.

My question is, is it practical to use Scene Graph to contain the game objects, or should it be used only to define scene objects/nodes linkages, while keepig the objects stored in separate container, such as std::vector<>?

share|improve this question
    
@Duck: thanks for editing. –  Bunkai.Satori Feb 6 '11 at 21:56
    
Does anybody have an idea? I plan to use both Scene Graph to organize Game Actors/Nodes, and then Vector to perform various sortings that should be faster than sorting a multiway SceneGraph tree. –  Bunkai.Satori Feb 7 '11 at 20:16
    
@ All: I have one more quesion: does SceneGraph contain the whole map, or should it contain only a map portion, say its visible area? Obvioulsly, the Scene Graph would then be continuosly updated, as the player moves over the map. –  Bunkai.Satori Feb 8 '11 at 15:12
add comment

3 Answers

up vote 5 down vote accepted

Deciding on what type of scene management to use depends very heavily on what type of logic you are trying to run. Consider the different consumers of your scene:

Rendering Consumer

The renderer probably just wants to know what is currently visible to the user at any given point. It wants a bounding volume hierarchy for fast culling (BVH wiki article) so that it can figure out that a chair inside a boat doesn't need to be drawn because the boat's bounds are outside the view frustum. This might be embedded into an octree.

It also might want to have an idea that the chair is on its back inside the boat, and that the boat is rolling up and down on some waves when it finally comes into view. That way to find the final world coordinates of the chair's vertices it can concatenate the chair and boat transforms and be done with it (this also makes your job as a programmer easier).

Yet another way of looking at this problem is that the renderer is probably running a good card, and ultimately just wants a pile of triangles sorted so as to minimize texture, shader, material, lighting, and transform state changes. This last will probably help you more than a BVH, preformance-wise.

Game Logic Consumer

The game logic probably just wants a flat list of things that can talk to each other by a messaging system, so a std::vector is probably fine.

The game might also want a way of keeping track of who is closest to what, so some sort of [nearest-neighbor][3] information might be helpful in that case. This can be provided by a BVH also, but having to up and down the graph might be annoying.

The game might even just want to know that when it moves A, A's item B should move too... in which case we are back to a sort of transform hierarchy.

Physics Consumer

Your game physics might want to have a [special representation][4] of indoor spaces for very fast collision detection. Alternately it might use some sort of octree or [spatial hashing][5] to efficiently find things that might collide.

None of the above physics data structure really looks like a "scene graph" in the Java3D sense.

Audio Consumer

An audio engine just wants geometry, perhaps a potentially visible (audible) set, or some sort of bounding volume hierarchy to calculate sound attenuation and propogation. Again, not really a normal sort of scene graph, though it may well be a graph of geometry in your scene.

Ultimately... ...it really just depends on the exact needs of your application. I'd suggest using a flat list to start with, and seeing where your issues arise. You might even try a flat list with a transform hierarchy, because that is perhaps the one sort of scenegraph useful for reasons other than efficiency.

Good luck!

share|improve this answer
    
@ChrisE: +1 for excellent question. In my opinion, this is the best answer here, let me therefore mark this one as the Accepted Answer. If I understood correctly, you proved that Scene Graph is not always the ultimate solution. Especially in Game Logic, do you see a Scene Graph as the correct way of updating transformation(scale, translation) of related objects? Example, a chair is on the boat, so the coordinates of the chair get updated as the boat moves? Alternatively, do you see any better solution to relative coordinates update? –  Bunkai.Satori Feb 8 '11 at 23:01
    
@ChrisE: In addition to the above mentioned, in the case Scene Graph is used, can it itself be used as the only objects holder for the scene, or would you recommend having another container (say std::vector<>) besides Scene Graph? –  Bunkai.Satori Feb 8 '11 at 23:03
1  
I was actually in the process of suggesting just that. I would try keeping a transformation hierarchy (here, an n-ary tree where nodes have one parent and multiple children, and no children are shared between nodes) with each node containing a reference to game object. Game objects are kept in a separate, flat array (say, std::vector). –  ChrisE Feb 8 '11 at 23:05
    
During the update, you can foreach over the flat list and perform game logic, and whenever relative movement occurs (say, the chair is pushed forward on the boat) you use the transform hierarchy to find the final local-to-world transform by walking up the parents of your object and concatenating their transforms. This uses the transform hierarchy for what it is best at (simplifying relative movement), and still lets you keep a convenient list of objects around. –  ChrisE Feb 8 '11 at 23:10
    
A further improvement is to keep in each object a dirty flag and a transformation of everything above it in the transform hierarchy. The cached parent-to-world transform (that transform I just mentioned) means that for any object position updates you only have to do one matrix multiplication (the relative transform to parent with the parent-to-world transform). Every time you update the relative transform, you also update your dirty flag. –  ChrisE Feb 8 '11 at 23:13
show 3 more comments

There's one good reason not to use the scene graph as the container for game objects, and that's instancing. If you want to reuse some resources, it makes much more sense to just refer to the resource from your scene graph several times than to have several actual copies.

share|improve this answer
    
@Jari: +1 for good answer. As I understand it, the general approach, is having a separate container of renderable meshes. Scene graph normally refers to the renderable meshes container, to take object shape information. Besides that, every scene graph node contains transformation information. Jari, having such design, I would like to know, if it is still recommended to have separate std::vector<> container for game nodes, say for the purpose of faster sorting, or another reasons.. –  Bunkai.Satori Feb 8 '11 at 12:48
2  
Depends - it may be useful to actually have several linear lists of nodes for faster processing of AI, physics, whatever. But I'd go there after I see if there's a problem otherwise. –  Jari Komppa Feb 8 '11 at 12:53
    
So, to conclude, it should be acceptable for the beginning to have only one SceneGraph, that would contain all the objects in the scene. Can you advise please, if cameras, lights, triggers should be in the scene graph as well? –  Bunkai.Satori Feb 8 '11 at 13:21
    
Everything that is affected by transformation hierarchy has to be in the scene graph, but I still would not give the scene graph the ownership, but store them elsewhere for easier (animation, physics, etc) processing. –  Jari Komppa Feb 8 '11 at 13:56
    
Understood Jari. Thanks. I will start with smaller version, and add another containers for easier processing later as needed. –  Bunkai.Satori Feb 8 '11 at 14:02
show 3 more comments

Separating your objectmodel and viewmodel(your scenegraph) is usually a good idea.

See this article on the subject.

Among many things this will allow for the use of object pools. Which might be essensial for efficient memory managment.

share|improve this answer
    
+1 for good contribution. I went through the article. It discusses programming patterns, and if I understood correctly, Object Model would keep the list of objects in the scene organized in a kind of std:vector<> container, while ViewModel would contain the same objects organized into the Scene Graph? However, only the objects being currenty displayed would be contained in the Scene Graph? –  Bunkai.Satori Feb 8 '11 at 13:41
    
And what about cameras, triggers, lighs? would they be part of the scene graph as well? –  Bunkai.Satori Feb 8 '11 at 13:41
    
@Bunkai.Satori Well, you could potensially have things in the scenegraph that aren't displayed on screen. You build up your scenegraph, then you could run a culling algorithm on the scenegraph before rendering the visible nodes. Cameras lights and triggers could exist both in the model and the viewmodel. –  Nailer Feb 8 '11 at 14:27
    
thanks for your response. As you mentioned culling, how is it done in practice? is the whole scene included in the Scene Graph, or is there only the visible part? If the whole scene is in the Scene Graph, is the whole scene graph traversed per frame to send only the visible area into OpenGL/DirectX API? I doubt that the whole scene is send to the API on per frame basis, as the visible part is usually less than 5% from the complete scene. Alternatively, is scene graph organized somehow, to quickly retrieve the closest areas without full travelrsal on per-frame basis? –  Bunkai.Satori Feb 8 '11 at 14:35
    
Put your whole scene in the scenegraph. Balance the graph based on certain criterion(eg. you could make an oc-tree out of it). Traverse the tree and determine which nodes are "Visible", "Partially visible" and "Invisible" based on if the bounding boxes are in your view frustum. You can build a super-lightweight "visibility graph" that basically just consists of references to SG nodes and a flag. After the frustum culling you can traverse the tree again to do occlusion culling. Redo the culling every frame, or every frame where the camera or scene has been marked as "dirty". –  Nailer Feb 9 '11 at 19:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.