Then what? Go through entire scene-graph and render objects with visibility flag set to true? That's not the best way :)

Quote:Original post by Cote-Duke Tech
Then what? Go through entire scene-graph and render objects with visibility flag set to true? That's not the best way :)

If it suits one to completely overcomplicate the entire affair; When one sets the flag to true, they can also push a pointer to said object onto a "Please Render" stack at the same time.

However, that is pure overkill when a for-loop or container iterator (allows for easy depth sorting) would do just fine like suggested above.

And besides, if an object isn't to be even considered for rendering, what the heck is it doing in the scene graph in the first place? This is why these things are "disabled" temporarily, or completely removed altogether if it's a dynamically instantiated object.

Oh, well. There is no strong definition for Scene Graph itself. But usually,
Scene Graph used to represent entire scene, not just visible part.

Now, since scene may contain fairly big amount of reneder assets, going
through entire scene graph each frame to render just some nodes (the visible part) is not the best solution. Think of the overhead.

Best way is to separate. Culling is one thing and Scene Graph is another.
While you cull (via Octree, BSP, whatever you like) it's good to fill out
render queue on the place, so you'll end up with a list of objects to render.

This list should be much lighter than Scene Graph to iterate through.

Most important points have been covered for you to consider, I'll just stick in a little extra info.

I'd go with separating the scene graph with any spatial information, meaning that the internals of your, say, octree is totally invisible to the scene graph. The octree is simply another node in the graph. This will help if you want to stuff in some other spatial information.

Using vis-flags for every single node will work well as long as the number of octree-nodes is rather small. Oblivion-sized landscapes, now these are not small [smile]. When it's time to render and you traverse your scene graph, at one point you will bump into a node which the scene graph is not really sure about, the octree. The scene graph tells the node "if you wanna get rendered, start working". Now the octree kicks in and does its "traversing and putting nodes into renderer queue thingie". Unaware of what just happened, the scene graph goes to the next node, tells it the same thing and on it goes.

I keep hearing this suggestion of making a quad/oct-tree simply a node of the scene graph, but this introduces a huge problem as far as culling/collision efficiency goes. An object that lives outside of the quad/oct-tree (anything else in the scene graph according to this proposed method) looses the benefits of spatial locality that would otherwise be available if objects existed inside the quad/oct-tree's heirarchy. Instead, you propose to search from the root of the octtree heirarchy for every query. Thats seems absurdly inefficient to me.

Take the example of very large terrain implemented via geomipmapping (a good choice considering how well suited a quad-tree struture is to the algorithm for collision/culling purposes). Suppose this terrain is covered in various objects such as trees, fences, small buildings, furniture, potted plants, trash cans, vehicles, etc. Each object lies on a terrain patch. Why not place these objects in the same quadtree structure as the terrain. If a peice of furniture is flung into the air by an explosion, its most likely to hit a piece of terrain nearby. By simply stepping up the quad tree, spatial locality ensures a fast collision query most of the time (except when queries cross quad boundaries at higher levels in the hierarchy.)

Alternatively, in your approach, every object lives outside the quad tree. A collision query would involve both the spatial subdivision struture that objects exist in (such as a seperate bounding volume heirarchy) and the quad tree structre...starting from the root. As I said before, the terrain could be very large, and hence the quad-tree structure would be very deep.

If your argument is that dynamic objects are never stored in the same structure, then at least part of my argument would still apply. A query would always involve both the quad-tree as well as whatever other seperate spatial subdivision structures were used. While it makes sense to nest spatial structures inside each other, a quad/oct-tree is an exception because it is usually employed to subdivide things that have a massive span across the game world. (As opposed to a building which is relatively small and could efficiently be subdividied using say... a BSP tree). As a result seperating them severely inhibits culling/collision efficiency.

With modern games having more and more of a dynamic nature, where most things can moved and changed in various ways, is a structure that establishes an abstract relationship between objects in a scene valuable at all? The most classic example i see is books on a bookshelf, where the books are children of the shelf. Who cares what shelf the book "belonged to" if you can rip it off the shelf, carry it with you, sell it, or place it on another bookshelf miles away for where you originally found it. It seems like spatial structures are by far the most useful for most aspects of a game's functioning.

Of course, these are only my opinions and observations. I would love to get some crtiticism on this and see what other propose, and possibly some new alternatives. I suspect to often, information is propagted that sounds good in theory, but is wildly different in applicaiton. Does anyone have some hard-core experience and the tales of woe that go along?

And before you go and say, "Your missing the point, a scene graph is a seperate thing.. bla bla", tell me then was the point of putting a spatial structure in the scene graph at all if its "a seperate thing". Ultimately, the goal at hand is finding an efficient way to combine, nest, or otherwise use different spatial structures at the same time.

Introduction:
Good points samgzman, I can't say I have rock-solid experience on this and I won't discuss this thing with terminology and definitions in focus.

And now the discussion:
Most games will probably benefit from reusing spatial data structures, which saves memory, retraversing overhead and the lot you described. This is the most straightforward solution and it will work most of the time.

The reason I don't do it this way is that I'm working on a general-purpose plugin kernel (which doesn't even know what rendering is) where I prefer not to have a clue at all what will be put into the scene. Number of objects, object clustering, object sizes, nothing. For a particular application, I could probably write a custom scene graph to take care of it, but a general solution would be much easier in the long run. I also aim at rather scalable results so the "minor issues" with objects going amok high up in spatial structures isn't really minor. There are ways which are rather complicated but I won't get into that here...

You're right in that logical relationships start to lose meaning as games become more open and dynamic. I wouldn't bind books into a bookshelf in my scene graph as that relationship is doomed to be messed up by the player as fast as he sees the opportunity. My scene graph is simply a container of objects that exist in the scene and due to the plugins, there will probably be very few exposed parent-children relationships which instead will be taken care of "in the dark" by the plugins. The scene graph still gives a feeling of confidence in scene managing as everything is automatically handled.

This approach takes time and it's really hard work. But, as it's only a serious hobby of mine and not in my line of study, I got the time to live out my dreams [smile]

I often get into these discussions with misinterpretations [smile]. I generalized from old threads a bit.
Transforming every geometry node in the scene graph belonging to the octree/quadtree/ultratree is heavy and looping through them all to check vis-flags breaks the idea of trees. If the tree is use to remove things for processing, do it before anything else ("inverse" query in the octree, then only work on the geometry considered relevant).

Quote:Original post by ApochPiQ
... pointing to nodes in the other to retrieve things like geometry meshes ... does promote clean code design...

Not necessarily, lets assume a typical implementation by doing this you've introduced a dependency with a particular scene graph, this makes your spatial data-structures tightly coupled with the particularities of your scene graph.

Whether this is acceptable or not depends on the context and is another story.