   Taking The Plunge: Scene Graphs
  I just completed incorporating Models (with Bone Animations) into my engine. The bone structure in a skeleton works much the way a Scene Graph does which got me thinking about incorporating one into my engine. I'm concerned about some things regarding it:- Speed improvements are obvious but can a scene graph have opposite effects on performance (Due to tree traversal)?- How does terrain rendering fit into a scene graph?- How does instancing fit into a scene graph?- Does anyone know of a scene graph implementation that uses shaders?- Does anyone know of a good website about scene graph design (I'm using OGRE's SG as reference)?To give you some idea about the game that I am creating, it will involve large scale armies on the battlefield (much like in the Total War games) within a high fantasy setting.   
  I use a scenegraph for my racing game.  I'm not an authority on the subject but can at least relate my experience.Quote:- Speed improvements are obvious but can a scene graph have opposite effects on performance (Due to tree traversal)?So, first of all, the purpose of my scene graph is to nest transformations and abstract drawable objects.  There are two types, scene nodes and drawables.  Scene nodes contain drawables, transformation information, and other scene nodes.  My car node has transformation information for the car's rigid body, a few drawables for the body and interior meshes, and wheel nodes which themselves have transformation info for the wheel and a drawable for the wheel/tire mesh.  This all gets set up once at load time.I keep a separate AABB tree structure to speed up collision queries, culling, etc, so my scene graph doesn't play any role in speeding anything up.  The reason I'm using a scene graph is that transforming the car, its meshes, and its child nodes is just one call to the car scene node, and it just works.  Likewise, updating the transformation for each wheel is very simple (just rotate it a bit on the horizontal axis).  Without a scene graph this would be a hassle.Traversing the scene graph can be a performance hit because some of my game's tracks have a huge number (~10,000) of objects; however I optimize this by keeping a separate scene graph for static objects and only traversing it once after they are loaded, then caching the results in an optimized form.Quote:- How does instancing fit into a scene graph?If I understand your meaning correctly (using one mesh for several objects), I do this through my drawable type.  A mesh and texture library is kept elsewhere, and when the drawable is set up, I pass it pointers to the mesh and texture to use.  Using a smart, shared pointer class can make this easy to implement.Quote:- Does anyone know of a scene graph implementation that uses shaders?In my engine, the parameters set through the drawable type (whether or not the object should be lit, object color, etc) are used by the graphic system to determine which shader (out of a fixed list) to use and what parameters to pass to it.  As noted above I cache the static objects after one traversal; I then sort them for the shader, texture, etc as a slight performance optimization.Hope this helps.  I haven't used a lot of other scene graphs so my experience is limited -- hopefully others can provide more diverse viewpoints.   ;  Good answer. I'm trying to mull over all the info you just threw at me. A UML diagram or similar would be nice but I will do with what I have. Thanks for the Info.- Does your SG sort by types in order to optimize rendering (for example, sorting by Shader or 3D-vs-2D)? I was actually thinking of having either two separate SGs for 3D and 2D (UI) rendering so that I would minimize Shader swapping. - Is your AABB structure completely separate from the SG or is it built into your Drawables?   ;  You might also be interested in checking out www.GeometricTools.com.  This is the home for the Wild Magic engine, which is where I learned all about scene graphs.  The entire engine source is available for free, and provides lots of examples, math routines etc.  It is shader based as well, and has DX9, OGL, and software renderers which makes for an interesting comparison.  If you really dig it, you could also pick up one of his books on engine design which I think are pretty much industry standard references.   ;  Don't bother with a scene graph, they don't actually solve anything. Very few things in a game world have a parent-child relationship. Just use spatial partitioning for culling etc (SGs were never intended for spatial information anyway). Use a simple structure like World->Sector->Object or something if you need to have some sort of world hierarchy.   ;Quote:Original post by RealMarkP- Speed improvements are obvious but can a scene graph have opposite effects on performance (Due to tree traversal)?Usually other data structures are used for optimisation; there shouldn't be any adverse performance effects, not in comparison to most alternatives at least.Quote:- How does terrain rendering fit into a scene graph?Often as a single terrain node, or it might be pulled out of the scenegraph alltogether.Quote:- How does instancing fit into a scene graph?I presume you mean resource instancing as opposed to GPU based instancing -- You can have nodes reference anything you want to be instanced (meshes, etc), these can be acquired by the nodes from some repository of resources, like venzon described.Quote:- Does anyone know of a scene graph implementation that uses shaders?- Does anyone know of a good website about scene graph design (I'm using OGRE's SG as reference)?For some pretty diagrams and another perspective on scene-graphs you can check out Google O3D's Scene-Graph API.   ;Quote:For some pretty diagrams and another perspective on scene-graphs you can check out Google O3D's Scene-Graph API.Thanks, I'll definitely look into it.Quote:Don't bother with a scene graph, they don't actually solve anything. Very few things in a game world have a parent-child relationship. Just use spatial partitioning for culling etc (SGs were never intended for spatial information anyway). Use a simple structure like World->Sector->Object or something if you need to have some sort of world hierarchy.On the contrary, In the game that I am developing, there will be models that have gear and weapons attached to them. Having a relationship between Hand->Sword or Chest->Breastplate or Head->Helm would be easier to code, I think. Also, I do not believe the SG was designed to do collision detection, rather it is a grouping mechanism. I have an octree in place and I believe a SG and Octree can work together to implement Culling. For example, I would not have to check weather or not each armour piece on a unit needs rendering (Octree way), I could rule it out by checking the AABB of a unit (or squad of units).However, I am open to other ideas of scene optimization and I'm not hard set on using a SG. If a scenario occurs where a SG is negligible, I will pursue other avenues.Quote:You might also be interested in checking out www.GeometricTools.com. This is the home for the Wild Magic engine, which is where I learned all about scene graphs. The entire engine source is available for free, and provides lots of examples, math routines etc. It is shader based as well, and has DX9, OGL, and software renderers which makes for an interesting comparison. If you really dig it, you could also pick up one of his books on engine design which I think are pretty much industry standard references.I am familiar with Geometric Tools and Used it's math library. I did not realize that it also incorporated a Scene Graph. Thanks for telling me! :)   ;  I wouldnt use a scene graph for that, just let the gear retrieve the bone transform of the bodypart where it is attached.   ;Quote:Original post by _swx_I wouldnt use a scene graph for that, just let the gear retrieve the bone transform of the bodypart where it is attached.I would love to hear your reasoning against scene graphs, because thus far I have heard/read a lot of information on using scene graphs and how great they are. Data structure wise, having a tree structure for models and effects is clean and very easily implemented. Having a model holding a torch to which a particle system (fire) is attached to is easy to implement using a SG. Adding an Octree or some sort of culling onto that, I can ignore testing against the torch and particle system if the model is out of view. I agree that a SG (in it's purest sense, ie. OpenSG) might be overkill and I'm looking into a more simplified version of a SG for my use. I also just read this article which was very thought provoking.   ;  It just falls into the category of "build games not engines." Sure a sweet generic all encompassing graph would be wonderful. But i'ts complex and could lead to dev slow downs or limitations down the line. Where as if you just coded it a little bit more direct, you may get what you need running with little effort.I'm always on the fence about SGs. I usually conclude that an all encompassing graph is not worth the effort. I prefer three graphs, one for logical hierarchy, a spatial hierarchy, and a rendering graph. The logical hierarchy is responsible for resolving the transformation dependencies, a gun is in a hand, so the hand updates first, then gun. None of the transformation stuff is inherited from the graph, it's up to the individual objects to interpret there parents transform and apply it to their own (or children).The rendering graph is a simple tree of viewables and scenes. Each viewable is a camera object associated with some kind of render target. And under it are scenes of renderable objects. The scenes themselves can have sub scenes or sub cameras. No material or shader or transform information is stored within this graph.Then a spatial hierachy stored per scene just for querying the visible set, once the previously mentioned graph has been iterated.   