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 seems to be the most effective way of representing the game world.

The game world usually tends to be as large as the memory and device can handle. In contrast, the screen of the device captures only a fraction of the Game World/Scene Graph.

Ideally, I wish to process(update and render) only the visible game objects/nodes on per-frame basis. My question therefore is, how to traverse the scene graph so, that I will focus only on the game notes that are in the camera frustum?

  • How to organize data so that I can easily focus only on the scene graph nodes visible to me?
  • What are techniques to minimize scenegraph traversal time?
  • Is there such way as more effective traversal, or do I have to traverse whole scene graph on per-frame basis?
share|improve this question
    
A scene graph is a great tool for hierarchal organisation, but not for culling or 'is this in the frustrum'. Try an octree or similar. –  The Communist Duck Feb 6 '11 at 13:33
    
Hi Duck, so what is the approach then. Scene Graph is the main structure to store game objects, right? Should I have another container to store the same objects just for the purpose of fast 'in frustum' processing? –  Bunkai.Satori Feb 6 '11 at 13:58
1  
Scene graphs are far from the be-all, end-all of object organization and they are not generally well-suited to game objects at all -- they're for rendering, and even then, they suffer from being extremely trendy and misunderstood in their use. You should read this. –  Josh Petrie Oct 27 '11 at 15:33
add comment

2 Answers

up vote 4 down vote accepted

If your scene is static, you can build BVH. And if you want clever BVH, use SAH. You can also build BVH for static scene and dynamic part of scene test every frame.

But. What is most effective (mean HW effective) is sorting your geometry by shader it uses. Shader switching is one of most slowing down things for GPU. So i would prefer to prepare your scene graph traversal for no needless shader switching and frustum test every Bounding box/sphere. It would be more faster than any BVH/octree tests. Sorting by shader can increase rendering performance twice.

share|improve this answer
    
If you are interested, i can write more detailed anwer. –  Notabene Feb 6 '11 at 14:06
    
+1 for clever answer. Hi Notabene, thanks for your response. According to what you say, it is perfectly OK, if I traverse the whole scene graph during every frame, even if it has 1000 or more scene objects? Should not I try to focus somehow only on the nearest objects? I use OpenGL so, yes, I will be switching shaders. Because I am now in the middle of scene graph plannig, so if you wish to give me more information, I would be happy. Thank you. –  Bunkai.Satori Feb 6 '11 at 14:13
    
Ok. The more complex answer would take a little time. I'll discuss it tomorow with our scene graph expert for getting more practical informations. But, yeah as far as i know: 1000 scene objects sorted by shader used and frustum tested (every object) would be fast, even much faster than just BVH/octree etc. If you want to be hardcore, you can do the frustum test using SSE - its not hard, really –  Notabene Feb 6 '11 at 14:27
    
Thank you again, Notabene. You mentioned couple of teqniques, I will have to study now. However, if you don't forget to talk to your scenegraph expert tomorrow, that would be really nice. Thanks. –  Bunkai.Satori Feb 6 '11 at 14:33
    
and anybody else: could you please advise, if Scene Graph itself can be a main container of gameworld objects, or if i should keep another container, say Std::Vector<> to keep list of dynamically allocated scene objects? –  Bunkai.Satori Feb 6 '11 at 22:00
show 1 more comment

I'm going to explain how my little engine does it, as whilst it is not generally tested against alternatives - its my approach and I haven't tried many others - it does explain how things can work:

I store my scene in an octree or quadtree (recommend quadtree if the scene is mostly flat e.g. RTS even if units can have height; only go true 3D if things really are dense at all y).

There are various recipes for dealing with fast-moving objects or objects that span two or more cells. I just put these objects into the node that contains them, even if that node has children. If they are fast-moving I compute a reasonably large bounds e.g. position of the next n frames, and store that, so I don't have to wriggle them each update.

When the camera moves, I then compute the intersection of the viewing frustum on the tree. I put the intersecting items in a list. I note in a bit-flag if the node or which of its children intersect the frustum, so later when objects are moving and being moved in the tree I can avoid unnecessary frustum checks.

Then I sort them by shader program and front to back.

Then to draw, I iterate through the list drawing the opaque parts of the models. Those models that have semi-transparent parts I build a single-linked-list of, so I can then go a second pass quickly back through those items back-to-front drawing the semi-transparent parts.

As the items move, I have the bit-fields so I know if the node in the tree they are in is visible or not, so I know if I have to insert, remove or resort them in the visible array that the tree is maintaining. If I have to sort them, rather than doing the sort there and then, I just put a tombstone in their old position in the list and put them in a new 'dirty' list; its then only to sort those things that moved and then merge that into a new visible list in O(n). Those types of tricks gained real frames for me.

share|improve this answer
    
and how do you sort by shader and front/back at once? –  PeeS Sep 25 '13 at 19:43
    
@PeeS you can't do both at once and I don't know any trick for getting things optimal. You have to pick some middle ground. I tend to try and actually use only one or two programs total, and sort by program and these days I only z-sort the semi-transparent pass; if its opaque, I let the GPU sort it all out. –  Will Sep 29 '13 at 18:31
    
Okay, i was thinking you have some kind of a magic sorting algo running :) Anyways yep, it's just a matter of sorting per material (opaque) and leave transparency at the end which is Z sorted. Cheers! –  PeeS Sep 29 '13 at 18:53
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.