Scene graphs

I need a good book on scene graphs.
Can someone suggest one.
Thanks.

Coriolios, in another thread wrote:
Anyway, from what you said in your last post, my confusion may be in terminology, because I thought it had to be monolithic to be considered a scene graph. If you only have one type of data in a structure, it seems to me that it is just a good fit for the current problem and not a scene graph. Of course I do hierarchical data representation of the stuff I draw, but I would not call it a scene graph. So, I guess my biggest question is, how do you know when something stops being a simple data structure well suited for the problem and starts being a scene graph? In other words, what is a scene graph, and what isn’t?

For a quick definition, I’d say that a scenegraph is any organized infrastructure that facilitates traversing or extracting information from a visual database.

It need not be a tree or even strictly hierarchical, but it should be something that helps you avoid visiting every piece of data in your world every frame. One common property of scenegraphs is that they have “nodes” (a property of all graphs I’m aware of) which have some sort of “topology” connecting them. Often, renderable data lives in the “leaf nodes,” but that’s not strictly necessary either.

Trees or DAGs tend to be very useful for spatial data, but they aren’t the only approach. Portals, BSP, KD-trees, Octrees, and so on are all covered, IMO. Portals, btw, are a good example of an approach that isn’t necessarily hierarchical, but is still a scenegraph.

And there’s nothing requiring you to have only one kind of organization. Even Performer, the granddad of modern scenegraphs, had its node tree(s) for culling and rendering traversals, but did actual state sorting and final draw traversal on a different data structure. (my concern is that many modern scenegraphs forget how important it is to use the right structure at the right time and attempt to be monolithic, as you said).

So most likely, you’ve written or used scenegraphs by my definition, if not yours. And the key isn’t whether you call it a scenegraph or not, but that you’re willing and able to look at scenegraphs and find technology that’s useful to you, which it sounds like you may already do.

Avi

Heh, I can see how my statement about knowing a guy who used VisKit could be read that way. Seriously, I try to avoid judging algorithms based on their implementers or their users

I think that what I do fits under your definition. Currently, I have a hybrid of BSP / portals / AABB tree. The BSP is used to quickly find which cell you are in, then portals are used to decide which cells to draw and AABB trees do hierarchical culling within a single cell. I think this fits the Scene Graph definition you gave, but I still think that the Scene Graph name is inappropriate since it implies a basic implementation approach that I don’t think my code follows. I just think of it as using the appropriate data structure at the appropriate time.

It seems then that you consider a scene graph to be simply the application of some structure useful for some degree of culling on your scene. While I can accept this definition, it then seems to me that “scene graph” loses almost all of its meaning. I can know what people mean when they say BSP or PVS or octree or portals, but “scene graph” encompasses all of these and so I have no information.

It seems to me that when people describe the scene graphs they use, that it is the only structure they have for describing their world. In other words, there is a single graph shared by the simulation and the rendering parts of the program (and any other parts they may have). While it can be seen as elegant from a theoretical standpoint that a single structure satisfies both needs, in practice it seems that the needs of the two systems are invariably different, so in the end this adds an awkward coupling between them that causes the code to be difficult to use. Because nodes are used for more than one thing in a massive hierarchy, you end up putting code for unrelated things into the same spot, and code for doing a single thing gets spread all over the place. This leads to code that is hard to learn, hard to maintain, and hard to modify.

By contrast, the code I have started out as a BSP + PVS renderer, and for a while it was actually able to do both BSP + PVS and portal rendering, and never in the transition was any code outside the renderer affected. Such changes to scene graphs seem far more impractical.

BTW, I’m enjoying this discussion. Thanks for moving it here; I wasn’t aware of this forum.

That’s a reasonable and articulate critique of my definition. It is broad, but I don’t see any need to restrict scenegraphs to make the definition more useful. I can still say I have a scenegraph which uses a quadtree for the terrain, a transform DAG for each articulated character, and a set of overlapping AABBs for everything inbetween. I can make the cull() call handle all of those seamlessly, so what matters is how the scenegraph behaves, i.e., what it does to improve resource utilization, ease of use, and most importantly, performance.

Notably, there is culling. As far as I can tell, culling was introduced with scenegraphs, and for the obvious reasons. So let’s at least call culling a “scenegraph concept.” BSP trees may have been invented to facilitate culling too, but my recollection is they were originally more for depth sorting (before, or instead of z-buffers).

State Sorting is another scenegraph concept. Pure GL or OpenGL doesn’t help you minimize state changes. Scenegraphs do, either by giving you explicit state objects to share, or by “binitizing” the drawables in a secondary render-friendly state-coherent structure. Scenegraphs have been doing that for 20 years. So I’ll claim state sorting (of many types) is another “scenegraph concept” put to general use.

Articulation (transformation hierarchy) is another example of a “scenegraph concept” widely used.

There are more too, but where I think scenegraphs get into trouble is when they try to stuff too much into the nodes. It may be fine to create a dataflow graph with sensors, effectors, math operators, and so on, but this shouldn’t be in the same tree as an optimized culler and renderer, IMO.

Those scenegraphs that go too far, I’d call Christmas Trees, since they’re all about ornimation and less about functionality. The middle-of-the-road DAG is just that, a DAG. One can specify whether it’s a tree with single-parenting or multi-parenting, balanced, depth or breadth optimized, and so on. There’s all sorts. So the word Scenegraph is really an umbrella term after all.

Avi

To me the main difference between a scene graph and other systems is the specialization. In a scene graph I can put any kind of object anywhere in the graph, and I can have an arbitrarily deep hierarchy of things, if I want that.

Most other systems, especially games engines and their close cousins, tend to be much more specialized, e.g. you have a world consisting of rooms (maybe connected by portals) and each room can contain a number of fixed single objects and a couple characters.

These things tend to be useful for the sepcific scenario they were written for, while scenegraphs try to solve the rendering problems as much as possible in a general way, to allow whatever application the user wants to create. It’s probably true that it is always possible to write a specialized system that performs the same task faster than a scene graph, and some things, especially global optimizations like a full scene octree, don’t fit the scene graph paradigm well. But many of the scene graph’s users want to solve their problems and don’t worry about all the details in writing a rendering system optimized to their purpose, and thus can live with the cost involved.

Just my $.02 (I’m in the states now :wink:

Dirk

I agree that one thing that distinguishes scenegraphs from non-scenegraphs is generality. It’s a form of abstraction, similar to object-oriented programming but addressing the relationships between objects. The topology of a scenegraph represents those relationship very directly, parent, child, within, near, visible-from, and so on. And, I’d argue that a good set of topologies and connections can make for a faster generalized algorithm than many specialized solutions, when dealing with unknown or dynamic data.

Why? Because the scenegraph is designed to figure out and avoid what it doesn’t need to do. That beats out many brute force specialized algorithms that often only answer one kind of query at a time (e.g., depth sorting, culling, proximity searching). By maintaining multiple topologies, a good scenegraph can track and coordinate changes in those topologies and answer multiple kinds of queries in a comprehensive fashion.

However, I still want to change the idea that a scenegraph implies a tree. That’s just wrong. A portal system is also a topology (and has been implemented in scenegraphs). An octree is also a kind of topology and has been included as a node in scenegraphs, where instead of having N children, an octree node has N spatially and hierarchically grouped children, including non-octree sub-graphs.

Avi

[This message has been edited by Cyranose (edited 10-20-2003).]

Originally posted by Cyranose:
However, I still want to change the idea that a scenegraph implies a tree. That’s just wrong. A portal system is also a topology (and has been implemented in scenegraphs). An octree is also a kind of topology and has been included as a node in scenegraphs, where instead of having N children, an octree node has N spatially and hierarchically grouped children, including non-octree sub-graphs.

Very true. But only using those hierchies on separate nodes severely limits their usefulness. The graph hierarchy is a logical hierarchy that applications usually depend on. They need specific relations between objects for hierarchical transformations to make sense, so in general most scenegraph nodes will only have a limited number of children, as the strength lies in the hierarchy.

But spatial structures like Octrees work best when they can destroy the scene’s hierarchy and rebuild it to fit the octree better. If you look at how ray tracers (who invented many of the speed-up structures for spatial queries because their performance critically depends on them) use them, you’ll see that the first thing they do is throw away the loaded hierarchy, break everything down to a polygon level and build their own hierarchy. Because that’s the way you get the most benefit from the hierarchy.

Integrating something like that into a scenegraph is hard, especially for moving/changing objects. That’s why I still see a case for systems that have a very limited hierarchy and can optimize for that.

Dirk