Jump to content
  • Advertisement
Sign in to follow this  
Mike.Popoloski

Yet Another Scene Graph Thread

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Sorry for bringing up a topic that seems to have been covered a billion times, but I still can't seem to bring everything together in my head in a nice, neat, compact design that incorporates everything that I need the management section of my engine to do. Because this is probably the most important part of my engine, as far as the long range problems that can be introduced with a bad design, I am trying to get this right the first time. I recently completed the basic rendering section of my engine, such as initializing DirectX, setting up windows, etc. I decided to move onto scene management, so I decided to take a search around GameDev to see what others had said on the subject. I very quickly ran into the huge scene graph resource thread, and began reading. And after all that reading, I am still very confused about the use of scene graphs and other scene management constructs. I quickly found that scene graphs should really only be used for logical hierarchies, such as a player that has a rocket launcher child node that has a particle emitter child node, and so on and so forth. That part I could understand quite well. Then I got onto the topic of using scene graphs for some of the other necessary engine features, and I soon found many conflicting tales on what should be done. Many posts, especially by Yann L, say that a scene graph should not be used for hidden surface removal, collision detection, state management, etc. Some other spatial structure should be used. But what this other structure is, how it should be managed, and what it can do are never described, or even mentioned. So I sat down and thought about it for a while. I made a list of the things that I wanted the scene manager of my engine to be able to do, and how the user should go about using it. This almost always works for me, and it easily lets me see what I need to do to accomplish the problem. In this case, however, I am still rather befuddled. I need my scene management, to be dead easy for the user (ie. they only have to add their objects once, and don't have to worry about updating them all over the place whenever they change something). It also has to , in some way, deal with culling and hidden surface removal, be able to facilitate physics and collision calculates, and enable efficient rendering through state management. The question remains, how do I do all of that? The solutions that I could come up with were as follows: 1. Have a seperate "tree" structure for all of the different tasks. This had the downside, however, of having to reconcile changes accross multiple trees, which seemed to be a very bad thing to me. 2. Have the scene graph only contain hierarchal relationships, but mark each renderable object, possibly by deriving from a common IRenderable interface. Then, the renderer could crawl through the tree and make a list of all of the renderable objects. This also seemed no good to me, because it would introduce many inefficiencies. For example, when performing frustum culling, would you check every single renderable object against the frustum? It seems that if everything were organized for rendering, such as with an octree or something else, many nodes could be instantly culled away without having to perform any costly tests. And when I was thinking of those, more questions popped into my head. How do I handle static versus dynamic geometry? The only way I could see handling static geometry would be to have a separate static vertex buffer for every static object. Then, when dynamic objects were to be rendered, the renderer would automatically collect and batch them by effect, texture, transform, etc. so that they would be as efficient as possible. How would this be accomplished with a scene graph? If I add an octree node to the scene graph, with all of my static geometry contained within it, how do I handle collisions between dynamic objects and static geometry? As you can see, I am having a hard time making it all fit together in my head. There are too many things that I need it to do, and I can't see a way to make them all work together. If any of you have any insights, tutorials, links, examples, etc, it would be most appreciated. Finally, sorry for the long post, but I hope I have made my problem crystal clear.

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
The 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_kid
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.


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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by jollyjeffers
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


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 this post


Link to post
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?

Share this post


Link to post
Share on other sites
A good scene graph engine I have looked at before is panda3d. ( www.panda3d.org )
IIRC, it allows the user to build a scene graph. CD is also setup by the user in scene graph format but then does some caching of positional data. Although I might be wrong on that part, it was a long time ago.

Its well worth a look. After trying it I had a go at creating my own scene graph engine which works ok but is nothing special and does not contain any CD at all. This bit did my head in on how to implement it in a clean way against the scene graph. But I did learn loads of stuff doing it :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!