Jump to content
  • Advertisement
Sign in to follow this  
Raeldor

Nodes, Meshes and Scene Graphs

This topic is 4814 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

Hi All, Just wanted some quick tips and pointers on scene graphs. Here are a few of my questions... 1. Am I right in thinking that a scene graph should have nodes, and that under those nodes should be meshes. That way the node can hold the local transformation, and the meshes can be shared by multiple nodes? This means multiple parents? 2. The scene graph should be a hierarchy, and each node/mesh can have child meshes each with their own local transformations and potentially have animation controllers attached to them to make them move? 3. Should the objects in the scene graph be only those that will be rendered in the next pass, or should it contain the entire scene? If it contains the entire scene, then does this mean the rendering is done by an external class (such as a quad tree)? Or should the external tree-like class be the one to add the objects to the scene? 4. Should the scene graph nodes hold bounding information that covers itself and it's children? Sorry to bombard you with so many questions, but it seems hard to find good material on this (at least that consistently agrees with other material!). Thanks

Share this post


Link to post
Share on other sites
Advertisement
I started to reply to this during class about 6 hours ago, but I got in trouble for typing. Woops. Well, I will try again now that I'm not in class.

I have worked quite extensively with OpenSceneGraph (probably the best open source scene graph you can find). I will recommend you take a look at their structure for some more information (although the codebase is huge).

A scene graph has nodes. Nodes can be ANYTHING. Nodes can be meshes, matrices, textures, lights, the list goes on.

1. The leaf of a branch will usually be a mesh, but it definitely doesn't have to be. Multiple parents happens a lot. If you have some chair object, you can assign the chair mesh to a node. Then, throughout your scene, every place you want a chair, all you do is create a new matrix node (which will be the orientation of THIS chair), and add the chair mesh node as a child.

2. One way to do animation in OpenSceneGraph was to use callbacks. Any node can have various callbacks attached to it. When the scene graph is traversed, these callbacks are executed. For example, you can create an AnimationPathCallback and attach it to a MatrixTransform node (which provides the offset of the animation in the world). Then you store your animation path control points within that MatrixTransform node. (OSG allows you to create the control points in 3d max, export the file to .osg format, and then load it up into your app).

Callbacks are great as they allow you to do stuff like this. They also provide an easy way to visit every node of the scene graph and perform some operation on their data. The supplied callback traversal types in osg were update, cull, and draw.

3. Entire scene. The entire scene should be a single scene graph. Having multiple scene graphs for a single scene sort of defeats the purpose of having a scene graph in the first place (limit state transitions/batch rendering, culling, etc). I am not sure 'exactly' how the multi-pass rendering is handled. OSG, for example, has a node type called osgFX::Scribe. If you add a mesh as the child of a Scribe node, the mesh will be drawn with a scribe effect (rendered once normally, and rendered in a 2nd pass in wire-frame with a slight offset). You may want to download the OSG source code (I don't have it on this computer atm or I would look) and check out the osgFX::Effect class.

A simple guess would be that every time the renderer encounters a node with a multi-pass render flag, it makes note of that while continuing it's depth-first rendering. Once it eventually pops back up to this multi-pass render node, it renders it again. These seems pretty efficient as all states above this node only need to be set once... i.e. We don't render the entire scene graph once, then have to traverse down through various branches, setting numerous states/transformations, all to draw some node a 2nd time.

4. Each object in the world should have it's own bounding box (for obvious reasons). OSG has commands such as node->getBoundingBox(), node->getBoundingSphere(), etc. These actually create a union of node's bounding box, and all of it's children. So, the answer is: each node should have it's own bounding box; a parent node doesn't need to 'know' the bounding boxes of it's children until it is asked for these bb's, at which time it just has to union them as they are already computed.

Hope that helps. For more specifics on OSG, or even scenegraphs in general, you may want to try the OSG mailing list. It recently broke 1100+ members, and it gets a ton of attention from the subscribers.

Share this post


Link to post
Share on other sites
Thanks Doggan. Hope you didn't get into too much trouble in class!

One thing I am still unsure of is how the scene graph interacts with tree structure(s) that are used for culling. For example, let's say that you want to use a quadtree for culling, how does the tree tell the scene graph which nodes to display? Or is the scene graph of a particular tree type itself, ie quadtree, and the nodes are built dynamically to break the level of detail in the scene down?

Hope that question makes sense.

Thanks

Ray

Share this post


Link to post
Share on other sites
Quote:
Original post by Raeldor
1. Am I right in thinking that a scene graph should have nodes, and that under those nodes should be meshes. That way the node can hold the local transformation, and the meshes can be shared by multiple nodes? This means multiple parents?


It depends on what you mean by "... and that under those nodes should be meshes"

if you mean't some mesh type is a sub-type of a node type then you could have multiple parents if the node type *maintains a list of parent pointers* but then you don't have an n-ary tree you have a directed acyclic graph (DAG).

if you mean't nodes types of an n-ary tree refer to meshes and can share the same mesh instances then this has nothing to do with nodes having multiple parents.

I recommend not having a mesh type be a sub-type of a node but something like a geo node type that can refer to meshes/renderables/etc then they can be shared and it doesn't matter if the scene graph is a DAG or n-ary tree here.

Quote:
Original post by Raeldor
3. Should the objects in the scene graph be only those that will be rendered in the next pass, or should it contain the entire scene? If it contains the entire scene, then does this mean the rendering is done by an external class (such as a quad tree)? Or should the external tree-like class be the one to add the objects to the scene?


They are loads of ways to go about this, if you where going to stick with a SG alone then general SGs are typically augmentated (n-ary) bounding volume hierarchies (plus transform graph) to prevent/limit traversing the entire scene graph everytime, to attain logrithmetic time complexity queries as opposed to a linear one. In this case for something like multiple render passes you will be traversing a sub-set of the scene not the entire scene, the sub-set represents the (potentially) visible set (no i'm not talking about PVS).

Even if are not going to use a SG alone (as a SG is not spatial partitioning structure but an object partitioning structure) it's still worth having cheap nested bounding volumes in a SG to speed up queries of almost any kind.

Quote:
Original post by Raeldor
4. Should the scene graph nodes hold bounding information that covers itself and it's children?


For the typical "general SGs" having nested bounding volumes of a very cheap BV type is a good idea even if you have spatial partitioning structures to speed up particular tasks.

Quote:
Original post by Raeldor
One thing I am still unsure of is how the scene graph interacts with tree structure(s) that are used for culling.


One way i've seen of doing this had a dynamic AABB n-ary tree (proper BVH) where its elements where pointers to scene graph nodes and SG nodes also had nested BVs which sphere BV, basically the SG is the input into the AABB tree creation and in order to maintain it and handle dynamic scenes it used the info of the sphere BV of nodes to determine stuff for the AABB tree.

Another way is you use the scene graph again as basically an augmented BVH to deal with general object level culling in general and where you have things like terrain (which would be a single node instance in a hypothetical SG) the terrain object internally would be some or has a particular spatial partitioning structure, the SG has no idea about this and doesn't need to know it just sees the terrain as another SG node.

Quote:
Original post by Raeldor
For example, let's say that you want to use a quadtree for culling, how does the tree tell the scene graph which nodes to display? Or is the scene graph of a particular tree type itself, ie quadtree, and the nodes are built dynamically to break the level of detail in the scene down?


Well a "pure" quadtree isn't very good for dynamic objects, you would use it to break up a large static mesh (like terrain).

Here is some ideas:

If you made some object a single node in a SG tree where its internal representation is a quadtree then you would probably have some kind of renderer visitor that when visiting that particular type of object it can know that it represents/represented by a quadtree and take advantage of that knowledge.

If you had a spatial data structure that is completely seperate from the SG and around for the same duration as the SG then you have to keep the structures synched.

Personally i'm coming to think the original scene graph concept is flawed, its one big monolithic polymorphic tree that tries to do everything imaginable at average performance instead of optimal, it has to many responsibilities, they typically have ridiculously deep inheritance hierarchies. I can't really think of a better idea though (although i have an untested idea...)

Share this post


Link to post
Share on other sites
Great post snk_kid, thank you. That gives me a lot to think about.

Sound like there are different ways of doing this, most based around whether or not the scene graph should be spatial. It also doesn't help that most of the conversations on here are very theoretical. I think I have enough information now to at least take a first stab at implementing the scene graph and it's interactions with a spatial partitioning structure. Once I have played and found my best solution, I will post it up for comment.

Thanks again.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!