On The OP's Question: If you don't use a scene graph for culling (even though you used it for transformations), then it would probably make the most sense to use some spatial structure like octrees or quadtrees. I went back and re-read the old Yann thread that Ashkan mentioned above. His approach is actually what I have implemented currently - a scene graph with hierarchical links between nodes, but with the option to have special nodes (octrees, quadtrees and so on). There are ultimately just graph nodes with different add/remove/access methods for their children.

One thought that I had while considering the problem - if you want to use a separate culling data structure from the scene graph due to a large scene size, and if the other structure is spatially constructed (i.e. the leafs are placed according to their world space position) then it would be an enormous processing task to keep that structure up to date. Every time an object moves in every frame, it would have to be tested or re-inserted into the structure. This may be acceptable in a given design, but if the hierarchical structure is coupled with the culling mechanism (ala Wild Magic) then you get both functionalities and only have to maintain one data structure. This is where I fall in this debate - the transformations and culling are done through the scene graph (possibly with fancy special nodes) and the rendering is done by picking the visible objects after culling. The visible objects then get added to a list or a heap, get sorted and then actually get rendered. I don't really see the benefit of using separate structures for transform and culling...

On Using Databases: I thought Ysaneya had mentioned that he would be doing some form of data base for Infinity Station? Maybe he could share some of his thoughts on the topic or has some insight into it?

Quote:Original post by jollyjeffers

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

Here are some figures related to LINQ-SQL query efficiency (not directly related to games, I know) provided by Rico Mariani, the performance man at Microsoft:
DLinq (Linq to SQL) Performance (Part 4)
((Linq to SQL) Performance (Part 3))
((Linq to SQL) Performance (Part 2))
((Linq to SQL) Performance (Part 1))

Also Rico's main blog page has some interesting articles like The Costs of Managed Code: The Avoidable and the Unavoidable.

[EDIT]DLinq (Linq to SQL) Performance (Part 5).[/EDIT]

Quote:Original post by Jason Z
On The OP's Question: If you don't use a scene graph for culling (even though you used it for transformations), then it would probably make the most sense to use some spatial structure like octrees or quadtrees. I went back and re-read the old Yann thread that Ashkan mentioned above. His approach is actually what I have implemented currently - a scene graph with hierarchical links between nodes, but with the option to have special nodes (octrees, quadtrees and so on). There are ultimately just graph nodes with different add/remove/access methods for their children.

I have a similar approach to this aswell, it's what I would consider to be the modern scene-graph, notice how it's more of a semantic graph.
The monolithic jack of all trades style scenegraphs were best suited to static scenes where in theory the optimal rendering order can be dictated in a graph structure. In practice however we like dynamic scenes and we don't especially want to burden our artists with the responsibility of ensuring they do the state sorting correctly for us; they shouldn't even have to know or care which states are the most expensive.

Quote:One thought that I had while considering the problem - if you want to use a separate culling data structure from the scene graph due to a large scene size, and if the other structure is spatially constructed (i.e. the leafs are placed according to their world space position) then it would be an enormous processing task to keep that structure up to date.

That depends on how you implement things surely?
A simple bounding volume hierarchy is about the only spatial structure you can incorporate into a scenegraph with minimal hassle or tradeoffs, I'm certain you'd struggle with having BSP branches on a scenegraph for example, so making your scenegraph double up as your spatial culling structure is inherently restrictive.

Quote:Every time an object moves in every frame, it would have to be tested or re-inserted into the structure.

Yes, that's always going to be the case, it doesn't matter where the spatial structure is. If you intend on using it for dynamic objects you're always going to need to re-test and possibly re-insert the entity. If you use some kind of 'loose' structure (loose-octree maybe) then after a while the structure itself is likely to become degenerate so you might have to rebuild entire branches.

Quote:This may be acceptable in a given design, but if the hierarchical structure is coupled with the culling mechanism (ala Wild Magic) then you get both functionalities and only have to maintain one data structure.

You have it in one structure, yes, but it doesn't solve the issues of re-testing and re-insertion. If an object moves far enough in a spatial structure you need to move it to a different node or branch, in a logical/semantic/modern-scenegraph structure it doesn't matter how far the object moves; if it's logic relationship hasn't changed then you don't move it between nodes or branches.

Combining a spatial structure with a scenegraph means you have to traverse logical (nonspatial) nodes when you're interesting in spatial relationships (such as for culling) and you have to traverse spatial nodes when you're interested in the logical relationships (such as nodes for AI or triggers). Keeping them separate makes traversals and algorithms more efficient.

Quote:This is where I fall in this debate - the transformations and culling are done through the scene graph (possibly with fancy special nodes) and the rendering is done by picking the visible objects after culling. The visible objects then get added to a list or a heap, get sorted and then actually get rendered. I don't really see the benefit of using separate structures for transform and culling...

A scenegraph does lends itself quite well to being a transformation graph. The important thing to realise is (as mentioned before) a scenegraph is a high-level structure, much closer to being a semantic hierarchy so even using it as a transformation graph doesn't always make sense, so even putting a matrix in the base class may not be the best thing unless you would otherwise require a large proportion of transform-nodes.
A spatial structure used for HSM is an accelerative structure, it is used as an optimisation for performance gains (the scenegraph is not a mechanism to push up framerates). Combining the two graphs together certainly does lead to a performance gaining scenegraph however the gain is likely less than the dedicated structure could have produced.

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

It does sound interesting.

I've thought along similar lines before, but I was never able to define how exactly it would gain us much over current style scenegraphs.

Perhaps I have a little bit different scene graph than the modern standard, because I only put spatial objects into the graph. With that said, a transformation hierarchy is always appropriate in my particular implementation.

As for the culling aspects, the graph is used to represent logical and/or hierarchical relationships in the scene. There are no spatial semantics used when inserting a node. For example, if a spaceship has a gun mounted to it, then the gun object would be attached to the spaceship as a child node. The gun would have a transform relative to the ship, and would be well suited to the transform hierarchy. This relationship is static, but it need not be - say the gun gets blown off. Then the gun has to be removed from the ship and reinserted at the scene root node since it does not have a logical relationship to the ship anymore.

In the first case, it makes sense that if you cull the ship (based on the combined bounding volume of all of its children) that you need not cull the gun. If the only point that is referenced by the gun is the root node, then it has to be culled on its own. At least on the projects that I have worked on, any time there is a hierarchical relationship relevant enough to have a scene graph connection, there is also a spatial link as well. I think this is a direct result of only including spatial objects in the graph (i.e. no textures or other renderstate related info in the graph). All of the rendering state is stored locally in the objects and is used as a key for sorting once the visible list is determined.

Can anyone think of two spatial objects that logically fit together in a transform hierarchy that don't fit together in a culling hierarchy?

Quote:Original post by Jason Z
Perhaps I have a little bit different scene graph than the modern standard, because I only put spatial objects into the graph. With that said, a transformation hierarchy is always appropriate in my particular implementation.

Yeah transformation hierarchies are so trivial and so common that the scenegraph can 'be' one with practically no tradeoffs, but always assuming a SceneGraph <-> A transformation tree is not accurate and frequently you can find nodes that don't need a transformation, in this case you either ignore the transform matrix that it inherits from the base class or you don't put a matrix in the base class and have a specialised transform node. So there's clearly tradeoffs either way.

Quote:At least on the projects that I have worked on, any time there is a hierarchical relationship relevant enough to have a scene graph connection, there is also a spatial link as well. I think this is a direct result of only including spatial objects in the graph (i.e. no textures or other renderstate related info in the graph).

A spatial relationship is a specialisation upon a logical relationship. You often find they go hand in hand and and this is why a BVH is fairly easily combined in a scenegraph. That said a scenegraph might contain non-spatial relationships in which case you want to make sure that such a branch isn't culled because of a spatial relationship higher up the graph.

Remember though there are other types of spatial structure that can be used for culling (like BSPs) which don't lend themselves so well to life 'as a' scene-graph. A BVH is good for somethings and not others so being able to choose is important.

Quote:Can anyone think of two spatial objects that logically fit together in a transform hierarchy that don't fit together in a culling hierarchy?

When it comes to scene-graphs there's an element of your mileage may vary.
Imagine an implementation where an object has a transformation 'built-in' (so it's not a separate node and your scenegraph is a transformation hierarchy) and also where you have the scenegraph double up as a BVH culling structure...ok?
Now consider if you had a torch, which is a static mesh object and a lightsource, because of the implementation you attach the light source as a child of the static mesh (See Yann's scenegraph diagram helpfully linkified by Ashkan).
So far so good, but now what about culling?

To implement culling I can think of 3 options:

• Create a large bounding volume to encompass the mesh and the light's range thus sacrificing efficiency of the culling of the torch's mesh.


• Create a small bounding just to encompass just the mesh and suffer the light source suddenly popping out of existence whenever the mesh is just off screen.


• Have the mesh as the child of the light source, culling will work efficiently but now you're sacrificing the intended logical use of the scenegraph.

Quote:Original post by dmatterTo implement culling I can think of 3 options:

• Create a large bounding volume to encompass the mesh and the light's range thus sacrificing efficiency of the culling of the torch's mesh.


• Create a small bounding just to encompass just the mesh and suffer the light source suddenly popping out of existence whenever the mesh is just off screen.


• Have the mesh as the child of the light source, culling will work efficiently but now you're sacrificing the intended logical use of the scenegraph.

I'll answer this from the point of view of my engine, in which the scene graph is entirely spatial nodes. There are two ways to handle the torch idea:

1. The torch and light are the same object. Since without the torch there is no light, then it may make sense to have them be the same object. In this case, the bounding volume of both the torch and the light are one in the same, and there is no controversy over how to handle it.

2. The light is itself a spatial object attached to the torch. In this case, if the light is attached to the torch and is transformed into the location at the end of the torch. The lights bounding volume is combined with the torch's bounding volume at the torch node and the light will be culled if the torch node is culled.

In both cases, this is correct behavior - just because the torch is smaller than the light doesn't mean that you lose efficiency. If the larger bounding volume of the torch node is culled, then the light is also culled. If not, then they are individually tested.

Now consider if the light and the torch are individually tracked in a quadtree for culling and the scene graph for logical connections. When they are created they are inserted into the scene graph and reside in their current locations most likely until they are destroyed. They are also inserted into the quadtree, and must be updated as they move. Their bounding volume locations have to be updated as they move, and a culling pass is done via the quadtree structure.

If the scene graph is also used for culling, there is no work done to reinsert the objects into the quadtree as they move - but in exchange you are expanding the bounding volumes of the higher level nodes to include all of their children. The number of insertions/tests for objects going into the quadtree is N*d where N is the number of elements and d lowest level of the quadtree (assuming that all objects have to get to the lowest level - for best case you could say d == 1).

On the other hand, rebuilding the bounding volumes of each of the nodes in the scene graph is a tree operation and depends on the depth of the tree. Regardless of the shape of the tree, if you start at the leaf nodes and work your way up you will always have N-1 operations of joining bounding volumes since every node has only one parent. The graph has a slight advantage here, but depends on the depth of the quadtree (both are of the same order, so they are somewhat the same thing).

Now, the variation comes while performing the actual culling operation. The quadtree has a fixed tree structure, which means that the worst case for culling is one object for each leaf node of the lowest level - this results in at least N tests. In the same situation, if the objects in consecutive cells happen to have logical connections (as is typically the case in my experience), then the scene graph method will actually outperform the quadtree with some hierarchical benefit.

Of course this is somewhat contrived, since the opposite can be stated as well - if all of the objects are in a single quadtree leaf node, then it will cull very quickly. If the same scene is culled through the scene graph, and there are no logical connections to each other, then the scene graph is essentially a brute force tester.

The point of my example is that the efficiency is based on the composition of the scene - and the more efficient method is likely to vary as the scene composition changes. In some instances the scene graph method is more efficient and in some cases a quadtree (or others) would be more efficient. But there is no grounds to say that a graph 'should not' be used for culling as well as transformations.