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.

As a learning exercise I've written a deferred rendering engine. Now I'd like to add a scene graph to this engine but I'm a bit puzzled how to do this.

On a normal (forward rendering engine) I would just add all items (All implementing IDrawable and IUpdateAble) to my scene graph, than travel the scene-graph breadth first and call Draw() everywhere.

However in a deferred rendering engine I have to separate draw calls. First I have to draw the geometry, then the shadow casters and then the lights (all to different render targets), before I combine them all. So in this case I can't just travel over the scene graph and just call draw. The way I see it I either have to travel over the entire scene graph 3 times, checking what kind of object it is that has to be drawn, or I have to create 3 separate scene graphs that are somehow connected to each other. Both of these seem poor solutions, I'd like to handle scene objects more transparent.

One other solution I've thought of was traveling trough the scene graph as normal and adding items to 3 separate lists, separating geometry, shadow casters and lights, and then iterating these lists to draw the correct stuff, is this better, and is it wise to repopulate 3 lists every frame?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

An approach I've used in a C++ project is that the scene-graph (which has the spatial index) fills up a 'visible' std::vector of hits based on the current viewing frustum. This visible list is managed by the scene-graph so is only recalculated when the camera moves - moving objects in the graph are moved in this list and using tombstones and unsorted change-lists that get sorted and merged back in as-needed.

The list of visible items is sorted by shader-ID first and within each type by distance from camera. The shader IDs are assigned such that terrain sorts first and then buildings and then units and then projectiles and then particles and so on - it being an RTS. Some models have more than one shader, but they only advertise their primary shader. When they are asked to draw, those which need bits drawn with another shader too add themselves to a next-pass single linked list.

So drawing goes through the visible array in one pass, and in that one pass a linked list of those items to revisit is created, and they get drawn a second pass and so on.

Drawing front-to-back and opaque-then-transparent helps keep everything sane.

This is perhaps not minimising the number of shader changes etc but it is fairly workable and straightforward to implement.

I have no idea about XNA and how applicable this is and how much of this low-level stuff you create I'm afraid. It would be most interesting to know what the veterans think of this approach for C++ RTSes however.

share|improve this answer
Hey Will, I really like this answer, especially because it's totally different of what I've thought of so far. Your method seems very sane, especially when also thinking of semi-transparent objects (which I've mostly just avoided so far). Building a (linked) list from your scene graph for objects to visit seems like a very good idea. And yes in XNA we have to do all of this low level stuff too :). –  Roy T. Feb 7 '11 at 15:02

My suggestion would be a 2-step approach tailored to your specific requirements similar to what you described yourself. You need a scene graph and a "render collection" for each of the rendering steps, in your case shadow, geometry, lights (maybe a fourth being transparent objects?)

The scene graph can be based on any type of relationships, but my personal preference would be based on spatial relationships where each node can contain the other nodes to facilitate fast culling.

The render collections can be any type of data structure tailored to the specific step. For instance, the shadow collection could be a list or tree sorted by depth to maximize early-z rejection. The geometry collection could be sorted by shader usage to minimize shader (state) changes. The light collection could be a list or tree sorted by light distance, size or a combination of those so you can limit light rendering to only the most effective lights if performance is an issue.

Whatever data structures you pick, be sure the insert operation is fast and make sure it uses pooling and other techniques to eliminate any allocation/destruction of data because you will be clearing and filling these lists each frame.

Now tying it all together is easy. Just walk through the scene graph and add each item to the relevant render collection(s). It helps if your data structure automatically sorts/structures new entries based on the requirements. When you're done, go through the render collections in the required order and render them.

Because your data structures have fast insert and don't generate garbage, there is no penalty for repopulating lists as you mentioned.

share|improve this answer

Your Answer


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.