• Create Account

### #10Jason Z  Crossbones+   -  Reputation: 6125

Like
0Likes
Like

Posted 17 September 2007 - 12:21 PM

Andy: as you said, I don't want to hijack the thread - we can continue the conversation in PM. I actually have used a significant number of scene management data structures and there are pros and cons to each. I don't think there is a typical 'modern' game scene - something like Doom III is going to be quite a bit different than a poker game. In a given context a scene graph may be the best solution.

I do agree with both you and promit about sorting by render state after the objects have been selected as visible. But I still disagree about the geometric information in each node. If the transform hierarchy is used to transfrom the bounding volumes in a scene, why is that not a good place to do the culling? If there is a known spatial data structure that better represents a good way to cull the objects, why not use that as the criteria for building your scene graph? Then a single traversal would be capable of doing both functions, and the only change is how you build the graph.

Sorry if I came accross as rude, after re-reading my post and your response I don't think it was a fair comment. I look forward to hearing your (and others)thoughts on the topic (including Tom if he's around...)

### #11dmatter  Crossbones+   -  Reputation: 3544

Like
0Likes
Like

Posted 17 September 2007 - 12:40 PM

Quote:
 Original post by PromitOne of the goals you see of some scene graphs -- particularly those that emerge from academia or overly complex frameworks -- is that the perfect rendering order arises naturally as a consequence of how the scene graph is arranged for traversal. So during a single traversal, you're able to transform, cull, and render efficiently during the traversal. That single structure is supposed to minimize the amount of maintenance necessary, and provide a very elegant arrangement for getting your scene rendered.

No...

Quote:
 This is absurd.

Yes it is, 100%ly absolutely!

It stems from the idea that since all these structures can be expressed hierarchically and all operate on the scene that combining them into one monolithic monstrosity will lead to a more unified representation of the pipeline. It doesn't, all you've done is canabalised your acceleration structures.

However,
completely scoffing all scene-graphs on the basis that using them for minimising state changes, HSM and transformations all at once is damn hard isn't fair. It's hard because it's giving the scene-graph the responsibility of several lower level structures.

State changes should be managed by sorting the visible renderable entities once they have been collated into a single list.

HSM should be achieved using some dedicated spatial partitioning structure, you may want to perform collision detection using such a structure also.

A scene-graph should represent a high-level overview of the scene that allows you to define relationships between the components that comprise a scene. With a scene-graph you have a unified (and ideally simple) interface to access a wealth of concepts: Skinned meshes, particle systems, water, fog volumes, Octrees, Sounds, Lights, etc

Say I want my main character to hold an axe, all I do is attach the axe to the entity et-voila a few pointer modifications later and it's done, no special case code needed; most definately not anything like Player->AttachAxeToRightHand().

Quote:
 This is almost against everything I've read and heard so far. Is state sorting basically irrelevant to some extent on DX9 and to a more extent on DX10? What about Wloka's "Batch, batch, batch"?! This presentation is not that old and belongs to DX9 era.

Basically state setting is no longer done on a per-state level but as chunks of state so collecting individual states together by traversing a (scene)graph is not ideal. State sorting however is still possible and important but you sort the chunks of state instead of deciding whether you need to change an individual one or not.

### #12AndyTX  Members   -  Reputation: 802

Like
0Likes
Like

Posted 17 September 2007 - 01:43 PM

Quote:
 Original post by AshkanThat sounds catchy and I've actually come across similar statements quite a few times. The problem though is the implementation part. DBMS does no magic. It's all about data structures and if someone is going to implement a hierarchical tree-like structure to store nodes and use that in a DBMS, why call that a DBMS? What's wrong with calling that a scene graph?

Oh certainly all of this is just data structures and algorithms. My only point is that many of the problems we're trying to solve have been studied extensively in the databases field and many of their results can be applied, if not the implementations (which have different goals). There's no need to call the result a DBMS at all, and I continue to call it a "scene graph", although sometimes with the prefix "multi-view" to differentiate it from classical scene graphs like Performer.

Quote:
 Original post by Jason ZI don't think there is a typical 'modern' game scene - something like Doom III is going to be quite a bit different than a poker game. In a given context a scene graph may be the best solution.

Oh definitely, I agree 100%. That's why I think something like OGRE's design of having a separate interchangable spatial data structure (octre, BSP, portal, whatever) that's not at all coupled to the transform hierarchy is extremely clean and efficient. You could even conceivably have multiple accelerators that could be chosen at runtime, or used for different queries. This is all that I'm suggesting - decoupling these "query accelerator indices" from the semantic information in the scene "like transform hierarchies".

Quote:
 Original post by Jason ZIf the transform hierarchy is used to transfrom the bounding volumes in a scene, why is that not a good place to do the culling?

The hierarchy actually isn't used to transform the volumes... only the final, composite matrix is needed; there's no need to know the entire path through the transform graph. When the object->world matrix in a geometry node in the transform graph is updated, it can easily propogate that change to any spatial data structures (simple dirty flags are sufficient).

Quote:
 Original post by Jason ZIf there is a known spatial data structure that better represents a good way to cull the objects, why not use that as the criteria for building your scene graph?

Well the spatial data structure shouldn't affect your transform hierarchy. For example a terrain object should be a single node in the transform hierarchy since it is transformed together, but it will probably be split into many spatial parts for culling/physics efficiency.

The transform graph need never be fully "traversed" unless the root node transform changes. The spatial hierarchy is traversed any time that a spacial query needs to be made (including view frustum culling for instance). State sorting, etc. should definitely be done at the render list level... there's no real hierarchical relationship there.

Quote:
 Original post by Jason ZSorry if I came accross as rude, after re-reading my post and your response Idon't think it was a fair comment.

No offense taken; I'm sorry if I wasn't clear in my original post. To be absoltely clear I like "scene graphs" and such structures are most definitely required! I think that they can be made even better by separating out the different ways to organize the data, and we can certainly argue about what constitutes "different-enough data", but I think we can at least all agree that Performer and OpenSceneGraph have some major design issues due to confounded class roles :)

### #13Jason Z  Crossbones+   -  Reputation: 6125

Like
0Likes
Like

Posted 17 September 2007 - 03:58 PM

When I talk about the transform and culling passes done together, I'm specifically referring to the Eberly scene graph. If bounding volumes are calculated and transformed at each node, then hierarchical culling can be attained with the scene graph. Maybe its not the best for gigantic scenes, but its a pretty darn good system for small to moderate scenes. In fact, even for very large scenes it could be argued that his system is more efficient in many cases than having separate data structures (of course depending on the scene make-up, but you know what I mean).

I think you are right - we can agree to disagree on some of the semantics regarding scene graphs. I just don't want to see everyone take an all or nothing stance on the topic, that's all.

### #14TomForsyth  Members   -  Reputation: 436

Like
0Likes
Like

Posted 17 September 2007 - 06:55 PM

Wahey! Always fun to see a thread with your own name in it.

Many have already reinforced my main points, but two things bear clarification:

1. I'm not against graphs. Very useful things. I use lots of them all the time. What I'm against is trying to stuff everything into one single uber-graph - it's silly and complicates the graph structure. So for example what LachlanL talks about is using multiple graphs at different times - some for reducing computation, some for culling, some for sorting. Nothing wrong with that at all. But they're still multiple different graphs, not one big complex thing.

2. Batching state is still extremely important (unfortunately). If two objects use the same state, you should draw them together. But if in your scene you have X different states, it doesn't really matter what order you draw those X states in. For example, if object 1 and object 2 have different pixel shaders, but the same alpha-blend state, there's not much point rendering them close to each other. Their states are not the same, end of story. The graphics cards don't generally save any time just because two objects share *some* state. Either they share *all* state, or they're different and the order doesn't matter.

The exception to this is that some states that are *numbers* and not *enables* (e.g. Z bias, transformation matrices, shader constants, etc) don't count as being different states. Ditto with two textures that are the same format (and possibly size) but just have different addresses - the pipelines often save some time if you batch them together.

### #15Dave Eberly  Members   -  Reputation: 1161

Like
0Likes
Like

Posted 17 September 2007 - 09:11 PM

Always an interesting discussion, these scene graphs. I agree with most, that trying to stuff everything into *one* scene graph is absurd. This was one of my complaints with the samples that shipped with NetImmerse/Gamebryo--they gave the impression that a monolithic scene graph is required.

If you have a biped, make it a scene graph. The hierarchical transformations work nicely here. But don't make the biped a child node of a Terrain node. You know you are going to render the terrain, so no need to attempt culling. You might want to attempt culling the biped at its root, but does it make sense that if the root is potentially visible, then you traverse to child nodes to determine visibility? Many of these decisions depend on how you build your art assets.

The decisions you make depend on the generation of hardware you are using. With software rendering, aggressive culling was a Good Thing. With current hardware, it might be cheaper not to cull as much as possible and just let the hardware beasts do their thing (even when much is not visible). On Xbox360, you have a few general CPUs to do the work. On PS3, you have one PPU and a bunch of SPUs. I guarantee that your algorithm development will vary based on the platform and hardware :)

Batching by state is good when it works well :) However, trying to batch only by state is just as bad as trying to organize only by spatial coherency. For example, the most expensive operation on the PS3 graphics for the game I currently work on is setting the shader constants that are the transformation matrices. Should I try to sort the drawables based on transformation matrix state? You reduce that profiling blip by optimizing the problematic code, only to find out that something else pops up. To optimize that, you have to go back to not sorting by transformation state. Damned if you do, damned if you don't.

In the end, profile like hell and figure out where the problems are. Understand that removing the first bottleneck does not mean that your next optimization problem is the second bottleneck. Removing the first can introduce a whole new set of problems. If you have multiple processors, figure out a way that you can distribute the load so that, compared to a sequential machine, you get something for free (i.e. factor the algorithms into independent components so that all you have to deal with is processor/thread synchonization).

Regarding the design of Wild Magic. You can build an entire application that never uses the scene graph system. TriMesh, TriStrip, etc. are container classes to store data to feed to the renderers. This was not "by luck". That said, I doubt I will ever separate the transformation and hierarchical culling aspects. If you build a scene graph, you get both together. If you don't want them both together don't build a scene graph. Naturally, if you sort by render state, and you have thousands of objects, it might very well be the case that you need *some* culling system. It does not have to be hierarchical. It could very well be cell-based (quadtree, octree, or whatever). The one thing you can do with Wild Magic is create as many scene graphs as you like, and in the OnIdle loop, draw them all to your heart's content, and in whatever order you like (sure, sort by render state). Bottom line is that this is all about tradeoffs...

### #16jollyjeffers  Crossbones+   -  Reputation: 1542

Like
0Likes
Like

Posted 18 September 2007 - 02:42 AM

Very interesting read so far [grin]

Quote:
 Original post by AndyTXThus what you need at the very least, is multiple "views" that "index" your scene "database". Indeed scene management starts to look more and more like a DBMS (although a full-blown one is certainly not required for typical games yet
I agree, but purely in the interest of research I've been tempted to give this a go at times. Performance would probably suck but I'd be interested in whether it presented an elegantly designed and implemented solution.

An extension is the new LINQ stuff in C# 3 - from the demo I saw at MIX it seems there could be some very elegant ways of implementing a relational "scene graph"-like data structure.

Jack
<hr align="left" width="25%" />
Jack Hoxley <small>[</small><small> Forum FAQ | Revised FAQ | MVP Profile | Developer Journal ]</small>

### #17AndyTX  Members   -  Reputation: 802

Like
0Likes
Like

Posted 18 September 2007 - 03:50 AM

Quote:
 Original post by Dave EberlyThat said, I doubt I will ever separate the transformation and hierarchical culling aspects. If you build a scene graph, you get both together. If you don't want them both together don't build a scene graph.

Fair enough. As I mentioned earlier, Wild Magic's design is actually fairly clean IMHO because it doesn't try to include render state, LOD, "switches", groups, etc. etc. into the scene graph. By my understanding (I've not used Wild Magic, but I've skimmed some of the code/documentation), it's primarily a transform graph but it can also do some hierarchical culling if your scene transformations are somewhat spatially coherent.

Quote:
 Original post by Dave EberlyIt does not have to be hierarchical. It could very well be cell-based (quadtree, octree, or whatever). The one thing you can do with Wild Magic is create as many scene graphs as you like, and in the OnIdle loop, draw them all to your heart's content, and in whatever order you like (sure, sort by render state).

That's exactly the sort of design that I'm supporting: you may well want to use a completely different structure for spatial subdivision than transformation, and a good "scene graph" should be able to accommodate that. So it's clear that Wild Magic is flexible enough to support multiple "views" as desired... sorry if I implied otherwise earlier; all I knew was that there was some combination of spatial and transform in the "stock" scene graph nodes.

Very interesting discussion, and I'm glad to see that most people agree on an aversion to monolithic scene graphs. I don't think that would have been the case 5-10 years ago.

Quote:
 Original post by jollyjeffersI agree, but purely in the interest of research I've been tempted to give this a go at times.

Yeah I've considered it on occasion but haven't had the time to prototype anything. It'd be interesting to at least do a thought experiment and consider the cool things that you could do if you had - for example - the ability to make arbitrary SQL queries into your scene :)

Definitely too slow right now though... as I mentioned, almost all databases are designed to optimize IO efficiency and often sacrifice computational efficiency to that end.

Still, if you do decide to do any research in that area, I'd be really interested in seeing the results! :)

### #18LorenzoGatti  Crossbones+   -  Reputation: 3179

Like
0Likes
Like

Posted 18 September 2007 - 04:01 AM

Quote:
 Original post by Dave EberlyRegarding the design of Wild Magic. You can build an entire application that never uses the scene graph system. TriMesh, TriStrip, etc. are container classes to store data to feed to the renderers. This was not "by luck". That said, I doubt I will ever separate the transformation and hierarchical culling aspects. If you build a scene graph, you get both together. If you don't want them both together don't build a scene graph. Naturally, if you sort by render state, and you have thousands of objects, it might very well be the case that you need *some* culling system. It does not have to be hierarchical. It could very well be cell-based (quadtree, octree, or whatever). The one thing you can do with Wild Magic is create as many scene graphs as you like, and in the OnIdle loop, draw them all to your heart's content, and in whatever order you like (sure, sort by render state). Bottom line is that this is all about tradeoffs...

I'm all for eclectic approaches like this one, but I wonder what advantages (other than subjective elegance) a pure scene graph that contains everything and renders everything could have.
For example, for what applications are generic scene graphs smart enough to provide decent performance with low effort?

### #19Ashkan  Members   -  Reputation: 451

Like
0Likes
Like

Posted 18 September 2007 - 08:04 AM

Although there has been some debate as to what degree of decoupling is considered the sweet spot, now that most people here agree that a monolithic scene graph is as bad as one can get, I think the next step is to determine how those different structures are to interact. I think state sorting is mostly solved. It's better to be totally left out from scene graphs and be done in a separate pass pretty much as LachlanL and dmatter pointed out. This leaves us with hierarchical culling structure and the transformation hierarchy. Up to this day, I think of Yann's approach the cleanest design I've come by so far. In an interesting discussion I had with dmatter a while ago, we shortly went over a few different possibilities and he made some good points, which I prefer not to repeat at this moment so as to avoid shifting your minds and getting bogged down to a particular implementation. What do you think?

### #20jollyjeffers  Crossbones+   -  Reputation: 1542

Like
0Likes
Like

Posted 18 September 2007 - 10:58 AM

Quote:
Original post by AndyTX
Quote:
 Original post by jollyjeffersI agree, but purely in the interest of research I've been tempted to give this a go at times.

Yeah I've considered it on occasion but haven't had the time to prototype anything.
You seem to be well-versed in what already exists - have you seen any other attempts at this sort of thing? I've not, and I prefer not to reinvent the wheel if someone else has tried some of it before...

Quote:
 Original post by AndyTXIt'd be interesting to at least do a thought experiment and consider the cool things that you could do if you had - for example - the ability to make arbitrary SQL queries into your scene :)
Well I was sitting in the ASP.NET 3.5 e2e demo at MIX last week and saw some seriously cool demos of LINQ and RDBMS's. Nothing you can't see elsewhere I'm sure, but it was very sweet the way they used ORM to define SQL tables as objects (inc. relations) and then interact with those objects as you'd normally expect in OOP with the appropriate SQL queries/updates being done lazily in the background. So with something like LINQ it seems like you could define your scene as a set of tables and then write "normal" code against it, albeit as an abstraction over an RDBMS.

Quote:
 Original post by AndyTXDefinitely too slow right now though...
I don't doubt it for a second, but one glimmer of hope is the ORM part that I touched on above. I really haven't looked at the details, but Scott Guthrie seemed to suggest you could write ORM 'wrappers' over almost any datasource. At a stretch we could possibly run SQL-like queries inline in our code against optimized data structures - essentially creating a very elegant interface to the back-end store....

Quote:
 Original post by AndyTXStill, if you do decide to do any research in that area, I'd be really interested in seeing the results! :)
Only so many hours in the day unfortunately... I want to give it a go, but I doubt it'll be in the near future [headshake]

But if anyone else happens to give it a go I'd be very interested!

Jack

<hr align="left" width="25%" />
Jack Hoxley <small>[</small><small> Forum FAQ | Revised FAQ | MVP Profile | Developer Journal ]</small>

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS