Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Anti-SceneGraphism: A Tale of Tom Forsyth's "Scene Graphs Just Say No"


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.

  • You cannot reply to this topic
42 replies to this topic

#1 Ashkan   Members   -  Reputation: 451

Like
0Likes
Like

Posted 17 September 2007 - 07:45 AM

I've lately noticed that Tom Forsyth has registered to these forums or at least so it seems as not much can be told from a username. There has been numerous discussions here on Scene Graphs. I've seen references to that article here and there, most of which also complain why an alternative is not presented if scene graphs are to be completely left out. It's working for a lot of people anyway. I am curious as to what alternatives he suggests and thought now that he has registered to these forums, it might be a good time to put this to discussion. It would be nice if you could shed some light on this, Tom. It would be even nicer if other people participate and see what we would get out of it. Thanks

Sponsor:

#2 Sneftel   Senior Moderators   -  Reputation: 1781

Like
0Likes
Like

Posted 17 September 2007 - 07:58 AM

My guess would be that the alternative is an immediate-mode drawing paradigm, in which per-frame scene bucketing comes from the objects themselves, as opposed to their scene graph representations.

#3 Promit   Moderators   -  Reputation: 7658

Like
0Likes
Like

Posted 17 September 2007 - 08:12 AM

One 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.

This is absurd.

This design mixes three unrelated structural ideas into one. First is the hierarchical culling structure. Second is the transformation hierarchy. Third is the optimal rendering order (for batching etc). These are three different trees, which are going to have different arrangements and different structures. Most scene graph related research proceeds with the goal of merging these three contradicting trees into one. Things like switch nodes and DAGs emerge as a result, trying to provide more sophisticated control of this single traversal.

Personally I think you're better off running it in discrete steps with discrete (and highly compressed) structures. So first, you do transformations across the board. Then you cull and collect a list of visible objects for the frame. Lastly, you do a fast sort across those objects to get a final list with optimal batching.

Oh, and TomF, if you happen to read this: It's really, really nice to see that you've been writing to your blog again recently. Please continue to do so!

#4 AndyTX   Members   -  Reputation: 802

Like
0Likes
Like

Posted 17 September 2007 - 08:37 AM

Quote:
Original post by Promit
This design mixes three unrelated structural ideas into one. First is the hierarchical culling structure. Second is the transformation hierarchy. Third is the optimal rendering order (for batching etc). These are three different trees, which are going to have different arrangements and different structures.

This is absolutely true, and having a single "scene graph" is nonsense for this reason alone. I did a term of full-time research related to scene graphs and graphics engine design and can say definitively that "traditional" scene graphs are a dead end.

That doesn't change the fact that you need some accelerator structures to do things efficiently of course, but one should always remember that they are just that: accelerators for specific tasks! In particular, a spatial accelerator is needed almost universally for doing things like culling and collision detection. Similarly it's often desirable to have a transform hierarchy, both for design and computational efficiency reasons. Often a unique scripting "view" of the game/scene is desirable as well, and the list goes on.

Thus 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). Indeed it may be desirable to even have a *relational* structure for certain views, which certainly follows the typical data management pattern of things starting hierarchical and becoming more relational as they get more complicated, and more complex queries are required.

Usually, however, only a few simple trees or DAGs are required for a typical graphics engine. At the very least one will want "transform" and "spatial" views, but any number of views can be created that all index data that exists conceptually outside of any of these indices.

Incidentally this design avoids many common pitfalls of "uber scene graphs" when it comes to object orientation and polymorphism. People should have gotten the hint when they had to dynamic_cast stuff everywhere or create virtual functions that only make sense for a few classes in the hierarchy, but alas they did not. That's a particular pet peeve of mine in that people need to understand *why* a programming language is designed as it is, and *why* some things are hard to do. Often when you're writing awkward, brittle or inefficient code it's because you have a bad design to begin with...

#5 Jason Z   Crossbones+   -  Reputation: 5382

Like
0Likes
Like

Posted 17 September 2007 - 10:10 AM

I find it hard to believe that people are still having this discussion - this one is almost as silly as the OpenGL vs. DirectX discussion. The term 'Scene Graph' has so many definitions and permutations that you need to be very precise when you describe what you are talking about.

<Begin Rant>
In any case, it doesn't make any sense to make a blanket statement that using a scene graph is 'awkward, brittle, or inefficient'. A graph is good at doing things that benefit from known graph based algorithms.

If a scene is very hierarchical, then a graph makes sense to use for transformations. As it turns out, the same graph can be used for culling since all of the information needed to transfrom a bounding volume is inherently included in the transformation hierarchy. Why would you keep a separate graph (or other data structure) to redundantly traverse and calculate something that is already available to you in another structure?

If a scene is very non-hierarchical (i.e. would result in a very flat tree) then maybe a BSP tree or quadtree would make more sense. In the same token, the same data structure could be used for both transforms and culling.

I am certainly not as well versed as Tom Forsyth in these topics, but a basic understanding of your problem, coupled with a basic knowledge of data structures can get you much further down the road to solving a problem than someone telling you which way is better.

Also, assuming that someone is a hack and doesn't understand a language simply because they don't use it according to your standards is a pet peeve of mine. It doesn't do anyone any good to make those kinds of statements. If you think you have a better grasp on scene graph management, its benefits and detriments, and how to use them in C++ than Dave Eberly (who uses them extensively and has published several books, and many research papers) then I would recommend that you write a book to enlighten the rest of us on how to go about it.
<End Rant>

* Sorry for the rant, but that's how I see it...

#6 AndyTX   Members   -  Reputation: 802

Like
0Likes
Like

Posted 17 September 2007 - 11:26 AM

Quote:
Original post by Jason Z
The term 'Scene Graph' has so many definitions and permutations that you need to be very precise when you describe what you are talking about.

I think it has been made pretty clear that we're talking about a monolithic single-graph that is used for tasks that are largely unrelated (spatial culling and hierarchical transformations were cited both by myself and Promit). Performer is a good example of this, although OpenSceneGraph also suffers from it to a lesser degree. Often newer engines like OGRE actually separate out transform and spatial information nicely.

Quote:
Original post by Jason Z
In any case, it doesn't make any sense to make a blanket statement that using a scene graph is 'awkward, brittle, or inefficient'. A graph is good at doing things that benefit from known graph based algorithms.

I didn't say the former at all - that was in the context of bad designs (in particular, scene graphs like Performer and so forth). I certainly agree with that latter; I said pretty much the same thing:
Quote:
Original post by AndyTX
That doesn't change the fact that you need some accelerator structures to do things efficiently of course [...] accelerators for specific tasks!


Quote:
Original post by Jason Z
As it turns out, the same graph can be used for culling since all of the information needed to transfrom a bounding volume is inherently included in the transformation hierarchy.

On this point I disagree, and I believe so would Promit and Tom Forsyth (among others). Even if a scene is very hierarchical in transformations, there is no reason to assume that *geometry* referenced by that graph is similarly coherent or in any way represented by the same structure as the transformations. Only the final "object to world" transformation matters (i.e. the path from the transform root to the node itself) - the underlying geometry should still be represented by a separate spatial index. Looking at a good spatial subdivision of a scene compared to its transform hierarchy makes this pretty clear (and these sorts of comparisons are easy to make if you have separated out the two graphs).

There are tons of examples where the transform hierarchy is a bad spatial hierarchy, even if the former is "deep". This is why almost all monolithic scene graph designs are forced to include "dummy spatial nodes" or similar that separate out portions of the graph even if the transformation has not changed. *This* is the mixing of functionality that we're advising against as it's nothing but bad news down the road...

Quote:
Original post by Jason Z
I am certainly not as well versed as Tom Forsyth in these topics, but a basic understanding of your problem, coupled with a basic knowledge of data structures can get you much further down the road to solving a problem than someone telling you which way is better.

Oh I encourage you to go try this all out for yourself if you have the time. However its naive to think that the experience of others (who have gone through all of these design ideas already) is irrelevant, particularly considering that very little in game development is "novel" by itself... it's the combination of algorithms and the inherent software engineering that consumes most of the time and requires the most innovation.

Quote:
Original post by Jason Z
Also, assuming that someone is a hack and doesn't understand a language simply because they don't use it according to your standards is a pet peeve of mine.

Firstly, people aren't "hacks", but programming certainly can be. Secondly, I have no problem with people using a programming language very differently than me, but there are certain fundamentals that are not up for debate. For instance: a software design that is centered around the use of dynamic_cast for multiple dispatch is inefficient and poorly designed (sure you can use it here and there, but it shouldn't be critical to the design). This isn't some rule of mine, it's part of the theory of programming languages and type safety, and there are many software engineering "design patterns" to allow people to avoid blunders like this and others. Anyways this is besides the point and getting pretty off-topic. I'd be happy to continue this discussion in PM if you wish.

Quote:
Original post by Jason Z
If you think you have a better grasp on scene graph management, its benefits and detriments, and how to use them in C++ than Dave Eberly (who uses them extensively and has published several books, and many research papers) then I would recommend that you write a book to enlighten the rest of us on how to go about it.

Dave Eberly's scene graph designs are fairly usable in that they *don't* try to incorporate complex, unrelated indexing into a single graph (at least as far as the Wild Magic engine goes). Wild Magic does, however, combine transform and spatial into a single graph and I think you'll find that for larger, denser scenes (with physics and other queries) you have to do something a bit more sophisticated at which point you'll have to either start making nodes that are purely spatial (identity local transform), or separate the two pieces of data, which really don't need to be coupled anyways.

Anyways the following article actually sums up what I'm trying to say very well:
Scenegraphs: Past, Present, and Future. Tom's blog says pretty much the same thing: there's lots of information to index in a given scene in order to efficiently perform a wide range of queries, and there's no reason why we should push, squeeze and try to cram it into one monolithic "graph". Keeping separate accelerators for each of the unrelated queries is really much more efficient and reasonable.

#7 Promit   Moderators   -  Reputation: 7658

Like
0Likes
Like

Posted 17 September 2007 - 11:39 AM

I forgot before; I have some suggested reading on the matter.
Part 1
Part 2
Part 3
Unfortunately these articles pose more questions than answers, but they do an excellent job of calling out the main problems involved.

#8 Ashkan   Members   -  Reputation: 451

Like
0Likes
Like

Posted 17 September 2007 - 11:53 AM

Quote:
Thus 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). Indeed it may be desirable to even have a *relational* structure for certain views, which certainly follows the typical data management pattern of things starting hierarchical and becoming more relational as they get more complicated, and more complex queries are required.


That 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? I can't imagine how a DBMS is going to help transformations propagate through the scene. How will these "views" be implemented? I don't want to be skeptical and would definitely welcome new ideas, but I think you need to be more specific.

Tom has based most of his reasonings on the fact that scene graphs are not good for state sorting and minimizing state switches. Although I completely agree with him, ruling out scene graphs mostly based on this reasoning is not fair, especially when an alternative is not presented. What strikes me then is

Quote:

2. Because of this, the number of state changes you make between rendering calls is not all that relevant any more. This used to be true in the DX7 and DX8 eras, but it's far less so in these days of DX9, and it will be basically irrelevant on DX10. The card treats each unique set of states as an indivisible unit, and will often upload the entire pipeline state. There are very few incremental state changes any more - the main exceptions are rendertarget and some odd non-obvious ones like Z-compare modes.


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.

I have a great respect for Tom, but this seems too radical.

#9 LachlanL   GDNet+   -  Reputation: 508

Like
0Likes
Like

Posted 17 September 2007 - 12:15 PM

Hey. I'm not a game-industry veteran or anything (far from it), but I thought I'd add my voice to the "Scene Graphs can be useful" side.

For example, the following is what I used for my last 3D scene-creating foray:
1) Loose-octtree for fast visibility/"update sphere" culling.
2) Many nodes added to this tree which often include scene-graph features (programable transforms, property inheritance, AI waypoints, etc).
3) Draw calls made on these nodes don't immediately draw renderables, but add "draw calls" for each applicable item into the relevant drawing bucket/batch.

People may say this is a naive way of doing this, but I personally found it to be a intuitive, flexible and quite efficient method. I'm sure that scene-graphs by themselves can be monstrously inefficient things, but when mixed with good culling/batching mechanisms, I think they can provide a good compromise between flexibility and efficiency.

A caveat to this is that if the project your working on has no need for this flexibility, then there's not point in using it. If all you need are a heightmap with quad-tree, or BSP etc, then there's no point. The project I was working on used features that benefit from the ability to define the properties of an entity based on the properties of its parent. Obviously if I didn't need this then it would have been more efficient to just spacially organise and treat each as seperate entities.

Anyway, that's just my $0.02AUD.

#10 Jason Z   Crossbones+   -  Reputation: 5382

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...)

#11 dmatter   Crossbones+   -  Reputation: 3298

Like
0Likes
Like

Posted 17 September 2007 - 12:40 PM

Quote:
Original post by Promit
One 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.

#12 AndyTX   Members   -  Reputation: 802

Like
0Likes
Like

Posted 17 September 2007 - 01:43 PM

Quote:
Original post by Ashkan
That 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 Z
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.

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 Z
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?

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 Z
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?

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 Z
Sorry 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 :)

#13 Jason Z   Crossbones+   -  Reputation: 5382

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.

#14 TomForsyth   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.

#15 Dave 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...



#16 jollyjeffers   Crossbones+   -  Reputation: 1542

Like
0Likes
Like

Posted 18 September 2007 - 02:42 AM

Very interesting read so far [grin]

Quote:
Original post by AndyTX
Thus 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>

#17 AndyTX   Members   -  Reputation: 802

Like
0Likes
Like

Posted 18 September 2007 - 03:50 AM

Quote:
Original post by Dave Eberly
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.

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 Eberly
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).

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 jollyjeffers
I 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! :)

#18 LorenzoGatti   Crossbones+   -  Reputation: 2774

Like
0Likes
Like

Posted 18 September 2007 - 04:01 AM

Quote:
Original post by Dave Eberly
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...

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?

#19 Ashkan   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?

#20 jollyjeffers   Crossbones+   -  Reputation: 1542

Like
0Likes
Like

Posted 18 September 2007 - 10:58 AM

Quote:
Original post by AndyTX
Quote:
Original post by jollyjeffers
I 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 AndyTX
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 :)
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 AndyTX
Definitely 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 AndyTX
Still, 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