• 13
• 16
• 27
• 9
• 9

# Yet Another Scene Graph Thread

This topic is 3979 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
Let me start out by first saying I'm no expert and I'm still trying to get my head around all the scene graph and scene management stuff too...however this is what I'm leaning towards after reading many threads, books, and articles online. I hope this helps.

Basically my scene graph is a purely abstract logical hierarchy of EVERYTHING in the scene. That includes characters, etc. For my game that I'm hoping to make (if any of you remember the old Heroquest board game, it'll be very similar to that), there will be several characters along with the 3d world itself. The internal nodes of the scene graph only contain grouping nodes, switch nodes, transformation nodes or some other type of non-renderable item. The leaf nodes contain the actual data that is to be rendered. This would include the scene partition item as well.

Now lets say I have some terrain and multiple large houses. The terrain is rendered with some sort of algorithm and the houses are all octrees. Also lets say I have a few characters in each of the houses. So I believe my scene would look something like this as a scene graph (transformation nodes, shader nodes, etc are removed as this only shows relationship between objects and what is to be rendered):

                            [3D world]                            /        \                                 /          \                           [terrain of world 1]      [terrain of world 2]                  /       |      \               \                    /        |       \               \            [terrain spatial  [house1]  [house2]        [blah]      partition]         /  |       \                                                  /   |        \                            [octree]  [elf]    [octree]                            |                            |                        [elf data]

For an update, I'll start at the top of the scene graph and work my way down which also updates all my dynamic nodes which would basically be like the specific characters, animations, particle effects, etc. This is where I would have my elf test for collision between the house1 octree and other items within the house1.

For rendering, you still walk the tree and there is "some" form of culling but not much. The culling deals with where you are in the scene, it does not deal with the actual visibility determination. For example, lets say house1 is really huge and thats where I'm at. Well, the house1 octree will figure out what needs to be rendered and what doesn't based off where I am. The other characters in house1, such as the elf, will also be rendered if they are within my line of sight. I have to rely on my scene graph for that because the elf is dynamic data, not static data such as my house1 octree.

At the end of the day, everything I want to be rendered gets put into a render queue, sorted, and then rendered. If I was in house1, I would put my octree there, render the octree as appropriate, then add all my dynamic objects as well testing against the frustum, etc.

Like I said, this is the way I'm looking towards and I hope it helps. If anyone else has suggestions let me know.

##### Share on other sites
The SceneGraph is often a SceneTree to begin with, and it's mean is to have uniform access to all 'nodes' in your scene, by defining a base interface.

The SceneTree (as it should be [ie not graph]) is often used to represent Hierarchical relationship.

A Game Engine most likely needs more than simple a SceneTree, it would also need a SpatialGraph (Graph for Portals/Sectors...), and likely RenderTree too.

Now the real problem is to make everything stick together in a coherent and useful way.

You'll also have a problem with Lights, which cannot be put inside a usual SceneTree Bounding Volume Hierarchy as they would break it, so you'll need another way to find out what lights are visible.

It's usual to combine SpatialGraph & SceneTree, but I wouldn't recommend it, unless you plan it very carefully.

(I know I'm not providing solutions but rather food for thought, sorry about that...)

##### Share on other sites
Quote:
 Original post by ussnewjersey4... I am trying to get this right the first time.

Before proceeding note that if you've never done it before you'll never get it right/perfect the first time and if you try you'll never get anything done and never gain any real experience. So i suggest an incremental & refactoring approach, get yourself some software dev tools to help out i.e. version control, etc, etc. Another thing to note there is no right/perfect way and you just have to accept it, don't think to much about it.

Whether to have "multiple representations/views" or "one graph to rule them all" the former is the better because each "view" is optimized specifically for the task at hand. The "one graph to rule them all" approach suffers from conflicting goals, takes on to many responsibilities.

Take for instance optimizing collision detection and rendering of a single massive static mesh with millions of polygons, in the "on graph to rule them all" you have SG typically agumentated with nested bounding volumes i.e BVH and a some special leaf node type which contains a huge mesh subdivided up by some spatial data structure.

The problem with this is now you have to deal with conflicting goals, a spatial data structure for CD, leaves typically contain just ~1-40 polygons but for rendering this is madness, for rendering ideally you will want leaves of relatively large batches of polygons say a few thousand polygons per leaf maybe much more. How are you to deal with this optimally in a traditional scene graph? the best you can do is to try and balance the two and end up with sub-optimial results for both.

The best approach in this case would probably be to have two seperate views (using polygon indices/references) of this data one optimized for CD and the other for rendering.

When talking about spatialization you need to be clear whether you're doing it on a single object or an entire scene. You'll most likely need to be able to do both, for instance advance occlusion culling techniques which typically want objects to be in a (rough) ordering (as well as other requirements) in which case you'd use either an octree or axis-aligned BSP tree or something similar for the entire scene, you can't use the BVH aspect of the scene graph to do this because BVHs provide no ordering.

[Edited by - snk_kid on April 24, 2007 7:37:18 AM]

##### Share on other sites
Quote:
 Original post by snk_kidThe best approach in this case would probably be to have two seperate views (using indices) of this data one optimized for CD and the other for rendering.

A lesson well learned in other areas too. Take DX10 for example which provides the use of different views for the same data.

As another example, our engine builds the world itself first, and then extracts specialized (and synchronized) representations for each of our subsystems (rendering, physics, AI, ...). Data isn't really duplicated, but rather augmented with additional, per subsystem information.

Quote:
 Original post by snk_kidWhen talking about spatialization you need to be clear whether you're doing it on a single object or an entire scene. You'll most likely need to be able to do both, for instance advance occlusion culling techniques which typically want objects to be in a (rough) ordering (as well as other requirements) in which case you'd use either an octree or axis-aligned BSP tree or something similar for the entire scene, you can't use the BVH aspect of the scene graph to do this because BVHs provide no ordering.

snk_kid said it in his first paragraph: think it through, but don't try to work it out all in one breath. Not only can you learn from past mistakes, but you can learn new means to existing ends every day, and ultimately, it will require some refactoring anyway :-).

##### Share on other sites
I've nothing much to add beyond a simple link: Scene Graphs - just say no. Worth reading (as is pretty much everything else Tom Forsyth writes [grin]) if you haven't already...

hth
Jack

##### Share on other sites
I forgot to mention when you have multiple views obviously there is the synchronization issue, a simple and obvious way to handle this is by events/signals. It all depends on how loosely coupled the views are from the real data which will determine how you'll handle synchronization of updates/modifications.

##### Share on other sites
Quote:
 Original post by jollyjeffersI've nothing much to add beyond a simple link: Scene Graphs - just say no. Worth reading (as is pretty much everything else Tom Forsyth writes [grin]) if you haven't already...hthJack

Indeed. However, scenegraphs are still useful for small parts of your scene. I.e. you might have one "scenegraph" for your gun model (containing all the usual material markup, and markup for where the hands go, where optional addons go etc.), one for the character (containing markup for where the hat goes etc.). In short, scenegraphs probably shouldn't be used religiously for the whole scene, but the concept is very good for separate objects, that are then organized in some higher level fashion (depending on the particular scene, they might be placed in a portal cell graph, for example, or a loose oct-tree, or whatever).

##### Share on other sites
Thanks for all the replys guys, ratings ++ for all of you.

I realize that trying to make it perfect the first time will not work, and that continued refactoring is good. What I meant by my original post was that I wanted to avoid my usual quick design process, which is "design the system while I am typing it." This has a few advantages for me, in that things get done quickly, which is necessary because otherwise I get bored, and I end up refactoring things quite often. With the scene management issue, however, I realize that making bad design choices here could box me in later without my realizing, and that it would take more than a little refactoring to make things work out.

I was already leaning towards the multi-view approach before I posted this, and now I am more certain than ever.

While I have this thread out, I am wondering how people deal with dynamic objects in their engine, ostly in the collision and rendering processes. With static geometry, I know that the standard way to handle things is to throw them into an octree and divide as necessary. For dynamic objects, however, that may move between leaves in the octree, problems are introduced. You could always keep a seperate list, but then you must check for collisions with every other object in the list, which could get expensive. I was thinking of maybe having a sort of cube based manager, similar to an octree, but where all the cubes are the same size, and aligned with the axis. They would be laid end to end in all directions. Then, you can easily update the grid of cubes with the new objects that have moved into them over the previous frame. This allows at least a little optimization. I am still curious to here your thoughts.

Finally, I am wondering how geometry is handled that is static most of the time, but could be deformed, maybe by an explosion for example. Can this still be organized into an octree, even though it could possibly change during the course of the game?