How can I traverse a scene graph and hit only nodes in the view frustum?

Question

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?

Answer 1

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.

Answer 2

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.