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.

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.

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.