Scenegraphs and multiple passes

Your scene graph is probably good for describing spatial relationships between objects in your virtual environment, but it's also probably not the best solution for describing render-state relationships. So why not keep things separate?

Traverse the scene graph in order to obtain a list of visible objects, and then organize those into *another* graph that describes render-state relationships. That way you don't need to worry about mixing different applications for the same structure (in this case, the scene graph). So you use another graph, maybe a "render graph" and let *that* worry about multi-pass and other such things.

I've been doing some work on that front lately, and I've actualy worked a lot more with "render trees" than with traditional scene graphs. The good thing in this approach is that you can try to design a method for building the render tree (or graph) based only on an arbitrary list of (visible) objects, so in the end you have a very optimized way of rendering things, without "enforcing" a particular way of organizing those objects spatially. That way you can work with a scene graph, or with objects lists, or whatever. And, of course, it is expected that each graph only needs to worry about one thing (i.e. rendering or spatial) so you reduce overall complexity.

Hope this helps.


[]s,
M.

Quote:

Your scene graph is probably good for describing spatial relationships between objects in your virtual environment,

i'm not going to include any spatial relationship in my scenegraph, it only contains render-state changing nodes like materials,transformations,cameras,etc.

i thought this is the "traditional" scenegraph( like the one in the gamedev article on sgs)

regards,
m4gnus

My understanding of scene graphs hasalways been similar to what Ng was saying, scenegraphcs are spatial/orientation graphs, not render state graphs. So while transform and even camera orientation might be in there, material data would not. In general, the graph is ignorant as to how the items actually get rendendered. Personally, I use the graph to figure out what world elements are visible, and then those elements generate "renderables" which are placed in a queue. Thus, the renderable encapsulates all renderstate changes and multipasses and what not. Hope that helps.

For exactly the reasons outlined in this thread, I'd recommend using multiple "scene graphs" organized for each usage scenario. Ex. one for transform, one for spatial, potentially one for render state (although just sorting the render list is efficient enough in most cases), etc.

god i regret that i switched from my (hardcoded) system to a scenegraph.

Quote:

I'd recommend using multiple "scene graphs" organized for each usage scenario.

isn't that kinda overkill? one scenegraph just for transformations oO.

Quote:

although just sorting the render list is efficient enough in most cases

that is one of the reasons i switched to a scenegraph. The sorting is included
and i don't need to sort.

guess i'll abandon the the whole scenegraph thing. That all seems horribly complicated with very little benefit.

thanks anyway.

regards,
m4gnus

Using a true DAG (directed acyclic graph) for a "scene graph" is simply not practical for modern game development on modern hardware. In fact, the term "scene graph," while useful due to its historical usage, is misleading relative to the way most people (should) use it.

I (and many, many others) would recommend you think of it more like a "scene database" or more generically, "scene manager." Implementing it in terms of a DAG doesn't offer you much advantage and has quite a bit of disadvantage (as you're discovering with multiple render passes, a classic example of where scene *graphs* become less practical/intuitive).

Now, a DAG can be useful for certain scene management tasks, such as spatial (hierarchical) relationships, or complex material descriptions (if they're dynamically editable at a high level, otherwise "bake" them into a more compact representation).

Most of the scenegraph groupthink comes from the SGI Inventor days. While many APIs and middleware have attempted to propogate the thinking (most of them as extensions of Inventor thinking), the majority of major commercial game developers I'm aware of don't implement scene graphs anywhere near that literally.

Now, you're at least not making the most fundamental mistake, which is mixing renderstate control flow (in the form of a DAG) with spatial/hierarchical relationships (in the form of a DAG) into one unified DAG, which is the classic scene graph that most people implement (and are eventually frustrated by). I still wouldn't personally use a DAG for renderstate control, as I tend to prefer something logically equivalent to display lists (which may or may not be populated by traversing a DAG, or querying a database, or by running script).

My most recent work on this subject has lead me to conclude that using DAGs for organizing render states is not a good idea because it smells like overkill for 99% of usage cases. So instead of a DAG, I am currently doing some work on "render state *trees*", which, of course, implies the graph is a tree, and not a generic DAG. The remaining 1% can be easily treated by creating separate trees. So maybe you cannot do some combinations of things using only *one* tree, but you can do them with additional ones.

One thing that comes to mind is granularity. I can probably solve every case with one or more render state trees, but now I'm left with managing those. But then again, you're on a higher level now, where you're not juggling render states around, but trees made of them, and that's gotta simplify things a bit. If I can direct the output of a render state tree to a specific render target, then I can actualy start chaining trees together, and solve for very complicated use cases, with relative ease.



[]s,
M.

Quote:

Original post by m4gnus isn't that kinda overkill? one scenegraph just for transformations oO.

Nope, it actually works perfectly and avoids ugly downcasts as well (since each data structure has a specific use which is valid for every node/member). It's similar in structure to a database "index", which is the key to databases' speed.

Quote:

Original post by m4gnus that is one of the reasons i switched to a scenegraph. The sorting is included and i don't need to sort.

That's fine, but just keep in mind the cases where the sorting isn't actually a bottleneck... I've never bottlenecked on state sorting - the actual state updates and draw calls are always at least an order of magnitude slower. Don't do unnecessary work :)

Quote:

Original post by m4gnus guess i'll abandon the the whole scenegraph thing. That all seems horribly complicated with very little benefit.

It's not, although there are a lot of bad ideas about it out there. Take the advice given in this thread; proper data structures for your scene are critical to getting any sort of performance what-so-ever, and make writing new algorithms easy.

Just don't try to mix too many things into one data structure. If you need a structure to represent a spatial BVH, make it. Similar for a transform hierarchy. Similar for a scripting language tie-in. Just realize that most of these tree-like (or otherwise) structures can use a common code-base.

ok i thought a little about it but even if i'd use a seperated tree for transformations and state changes the problem with multiple passes persists.

i.e the render state tree for a shadow mapping pass would look like that:

     ...      |[Depth Material]       |    [Mesh1]       |    [Mesh2]

while the render-state graph for the final pass that renders to the backbuffer is far more complicated (as each mesh has it's own material)



regards,
m4gnus

In the case of shadow mapping, you should actually have the lights themselves take care of the multipass part (well, the depth buffer rendering...). Using a "light-graph" or "light-list", every light that has any affect on whats in the current view frustum should render it's own shadow map. The light itself should take advantage of any spatial structure/tree to collect/cull the objects it sees. You then have a couple of choices to make the affected objects "aware" of the shadow map, for example, during the lights culling phase, "tell" the affected object that the specific light sees it or just "ask" the scenemanager about the closest(s) light(s) later on.
Of course, the lights will still also be part of the transformation graph, and any spatial structure...

As mentioned shadow map rendering and stuff like environment map generation is really in the realm of recursive rendering, so each of those should handle their own rendering passes (and render targets). That's a pretty clean design.

but (almost) every pass needs to traverse the scenegraph(s), because you need the meshes that should be rendered.

But you also want to ignore certain types of nodes(in this case materials).

So how do you handle that?

regards,
m4gnus

State sorting actually touches a broader chapter: state handling in general.
An example:

Two objects, one needs to be rendered with ZTest being lessequal, the other one needs to be rendered with ZTest = less and with blending being srccolor/invsrccolor. Of course in both cases the render passes of the respective objects assume that the other states are set to specific values; object #1 assumes blending to be disabled for example.

Now, one simple way of doing this would be to simply set ALL states on each render call. This is impractical of course. I developed a solution that works with state groups and deferred state setting. I put state set calls in a queue if the calls actually change the current setting (to filter out unnecessary calls), and in the end, the queue is traversed, appropiate API renderstate calls are made, and the queue gets flushed. Before the next object starts to render, the states are reset with a reset() method (duh :) ). reset() takes a parameter; a list of state calls. This tells reset() to set the state to their default values unless the given list includes these states.

In sum, this works perfectly, it guarantees default states while ensuring that only the really necessary state sets are done. This also has a nice side-effect; I have a list of state set calls that will be done after rendering object A and before rendering object B. Now one can sort the objects by the amount of calls necessary to be done between them, either binary (zero or non-zero state calls) or by weighting the calls and sorting by the sum of these. In short:

object #1: A
-- determine state sets necessary to ensure B is rendered correctly; calculate the weighted sum and store it in variable X
object #2: B
-- determine state sets necessary to ensure C is rendered correctly; calculate the weighted sum and store it in variable Y
object #3: C

Apply some minimizing algorithm to minimize X and Y by swapping A, B and C

Now do the actual rendering


This would solve the state sorting problem with state batches and without overly complex graphs. Has this approeach ever been done before?

that approach sounds quite good and solves the sorting without scenegraphs.
i'm a little tired now so i just skimmed through your post. i'll hve a closer look at it tomorrow.

But i still have the problem with multiple passes and scenegraphs.
Ppl suggested that i keep stuff like depth pass(for shadowmapping) out of the scenegraph but i still don't know how to do that.
My meshes are in the scenegraph so i have to traverse it once for every pass.

right now i'm thinking about having a (different) traverse(sceneGraphNode *pnode)-function for every pass.
i.e. For a depth pass that function would like this:

(or similar)


i'd say every pass should traverse one sceneGraph(we have one sceneGraph for one purpose:tranformations,(renderstates),spatial relationship,etc).

That would be the easiest way(and the first that came to my mind) but maybe the 'one scenegraph per pass' restriction is too strict.

So how exactly do you handle all the additional passes?(mostly depth passes,cube map rendering,stuff like that)


regards,
m4gnus

Quote:

Original post by m4gnus So how exactly do you handle all the additional passes?(mostly depth passes,cube map rendering,stuff like that)

I've seen the idea of RenderViews in another thread. I tried it myself and I like the idea of having a different RenderView for all passes.

What I have is different renderviews that are specialized to do a certain work and organized under a tree-like structure to represent the render priority of those views. The renderer class would only go through that tree (depth first) and render each views. If needed the RenderView would access the SceneManager to get the visible objects to render. The views can also be used as a texture (input) of another view, for cases like post-processing, shadows, etc.

At first I thought I'd include everything in my scene manager but with time and more prototyping most of what was done didn't made sense. Now my scene manager keeps track of all objects and their properties (and other things all related to rendering of the objects) and I made other structures to manage the multiple passes and the renderstates.

I don't have a complete system now (I can't load objects, I'm correcting this issue right now [wink]) so I can't say how fast it is but I personnally think that specialised structure (for render passes) helps. Otherwise (in my design), I was probably end up having multiple copies of my scene for each passes that need to render the objects.

If you want to have only one structure then I'd suggest you other structures than trees like a DAG and for all the passes that need to render the scene you point to that part of the scenegraph. What you'll probably get is a structure like mine (for the RenderViews) at the "top" of your graph and the nodes will point to the real scene graph when they need to access it.

As mentionned in this thread... the structures can share the same code.

If you have any questions or comments feel free to ask! [smile]


JFF