What's a "Scene Graph"?

A scene graph is a way to hierarchically store render objects in order to do visibility culling.

Here: http://www.gamedev.net/reference/programming/features/scenegraph/

Quote:

Original post by CadetUmfer A scene graph is a way to hierarchically store render objects in order to do visibility culling. Here: http://www.gamedev.net/reference/programming/features/scenegraph/

According to that article, I did indeed write a scene graph, although it's not as fully-featured and everything has rotation+position matrices and math.

Thanks - What are some other good references?

A scene graph is not for visibility culling. It's just a way of representing objects parented to other objects in a tree graph, rather than in a list. In game engines it's usually convenient as you can parent objects to other objects without manually having to update their position and orientation every frame.

Quote:

Original post by MichelPaulissen A scene graph is not for visibility culling. It's just a way of representing objects parented to other objects in a tree graph, rather than in a list. In game engines it's usually convenient as you can parent objects to other objects without manually having to update their position and orientation every frame.

I thought that sounded suspect from the description given in the link, but decided that since I may not have all the facts, to not contest it.

The explanation I gave was just a short summary of the summary given in that article.
By the way, most games don't need a scene graph, you may be better off with just a list of drawables.

Quote:

Original post by MichelPaulissen A scene graph is not for visibility culling.

It is worth pointing out that a lot of people abuse their scene graph to also do visibility culling. It isn't the most efficient structure for visibility culling at the best of times, but combining the two concepts lends a certain (IMO flawed) simplicity to your code.

Code simplicity has a lot of plus points, but yes you should be using an octree or something for culling big scenes. Just to muddy the water, we use a BVH system for fast collision detection and we bend that for visibility culling with a kind of octree connection layered over the top.

Just remember that most of your scene doesn't need a parent->child relationship. If you have a tank with a moving turret and a moving gun and wheels that go round, then it makes perfect sense to have a graph. Buyt remember that the rocks and trees in your level never move, so you don't want to waste time flattening their heirarchies each frame.

Each container in our graph has two matrics called local and world. The renderer and other stuff always uses the world one, which is not automatically updated. We use the local one for complex heirarchies and manually call a "flatten" method to update all these local transforms into the world ones that actually get used for rendering. This is both efficient and easy to use and I would recommend it a lot.

Quote:

Original post by Rubicon Code simplicity has a lot of plus points, but yes you should be using an octree or something for culling big scenes. Just to muddy the water, we use a BVH system for fast collision detection and we bend that for visibility culling with a kind of octree connection layered over the top. Just remember that most of your scene doesn't need a parent->child relationship. If you have a tank with a moving turret and a moving gun and wheels that go round, then it makes perfect sense to have a graph. Buyt remember that the rocks and trees in your level never move, so you don't want to waste time flattening their heirarchies each frame. Each container in our graph has two matrics called local and world. The renderer and other stuff always uses the world one, which is not automatically updated. We use the local one for complex heirarchies and manually call a "flatten" method to update all these local transforms into the world ones that actually get used for rendering. This is both efficient and easy to use and I would recommend it a lot.

I'm familiar with Octtrees, but do you have a link to a specific description of their use with visibility culling?
What's a good resource on BVH? For that matter, what is it?

Rocks and trees can get added to the SceneManager directly, in which case their hierarchy has a grand total of one level - The SceneManager itself.

Combine that with passing by reference (C#'s more-limited version of passing by pointer) and I could get some quick updating...Also solves what to do in PreDraw...

Don't have a good resource on BVH, but google is your friend (bounding volume heirarchy). It's just a way of linking up larger objects with spheres so you can quickly test if a ray is going to hit something before going on to individual triangle testing.

We bodge it for visibility purely because there's already some good numbers in there such as world position and bounding radius. We have larger spheres that encompass groups of others and reject them like an octree would.

It's a bit of a kludge tbh so I would recommend using a plain octree if you're starting from scratch. We also support that option as it's just better at the culling part.

I've personally never been a fan of scene graphs, I find them pretty pointless and just slow things down. When you think about the average game scene, 95% of it has no use for a scene graph. Even then, you may have things like characters with weapons/items you want to parent to them, but these days that kind of stuff is handled in the animation system anyway. I'm actually struggling to think of a good example off the top of my head right now in favour of them.

That's just my opinion anyway, and I guess it all comes down to how you like to go about things and your style.

Quote:

I'm familiar with Octtrees, but do you have a link to a specific description of their use with visibility culling?

Octrees are just a way of splitting your scene up into pieces (spatial partitioning). Visibility culling is a very big topic but the basic idea is you can use an octree for very quick frustum culling (if a cube from the octree is outside of the viewing frustum, then you can immediately discard all of the actual items inside it), and then you can do some other type of culling like occlusion culling on the remaining nodes. Occlusion culling is another big topic yet again, but depending on how you go about it the octree can help out (testing whether nodes are visible or if they are being blocked by occluder geometry).

If you want to find out about culling, just start googling. It's a massive subject that doesn't really depend on the spatial partitioning scheme you use (until you start actually getting into nitty gritty details).

There is no clear definition of what a scene graph is and what not. Today scene graphs are often degenerated to a multi-purpose structure (e.g. OpenSceneGraph). I personally have once started so, too, but have dropped that structure already some years ago. Today I use a scene graph just as a "list with custom grouping" of instances (a.k.a entities or game objects) that participate in a scene. The custom grouping (i.e. nodes in the sense of graph theory) are just an ability to logically group/order instances (an admission to scripters).

Quote:

Original post by mightypigeon I've personally never been a fan of scene graphs, I find them pretty pointless and just slow things down. When you think about the average game scene, 95% of it has no use for a scene graph. Even then, you may have things like characters with weapons/items you want to parent to them, but these days that kind of stuff is handled in the animation system anyway. I'm actually struggling to think of a good example off the top of my head right now in favour of them. That's just my opinion anyway, and I guess it all comes down to how you like to go about things and your style.

That's a pretty strong statement. Can I get some commentary on this?

Quote:

Original post by MichelPaulissen A scene graph is not for visibility culling. It's just a way of representing objects parented to other objects in a tree graph, rather than in a list. In game engines it's usually convenient as you can parent objects to other objects without manually having to update their position and orientation every frame.

I knew someone would bring this up :)

1. You don't NEED a scene graph to do culling.
2. Scene graphs are a terrible way to structure game objects. Game objects represent a logical hierarchy, not a physical one. Even worse, you should not be sharing data structures across different systems (renderer and game). Those systems have different needs and should use different data structures. For example your renderer probably wants a list sorted by state changes/textures/meshes. Your game code probably wants a hash/etc keyed on the ID if it's a multiplayer game. Your physics code a spatial hash or octree/etc.
3. Don't use scene graphs

And we have a winner!

Definition of a scene graph: A perfectly fine data structure that can be used with just a little overhead to hold your scene together in a useable way. Therefore it's been totally replaced by "new thinking" to make data management harder and save perhaps a couple of nS on the fairly idle cpu.

It's added complexity that you don't need. There's nothing wrong with them--you shouldn't rip them out of your already working engine (though my renderer of choice, Horde3D, is seriously considering it).

Inevitably you get to the point where you're adding invisible triggers to your scene graph (because it's the "main" data structure where you put all your game objects) and it hits you: I'm maintaining this cache-inefficient threading nightmare of a data structure to save a few matrix multiplies?

Quote:

Original post by Rubicon Therefore it's been totally replaced by "new thinking" to make data management harder

The general focus is on making data management *easier*. Why shoehorn every piece of available data into a single container, when you can have one container per data type, specifically designed for that data?

Quote:

and save perhaps a couple of nS on the fairly idle cpu.

Outside of graphics demos, how many games do you play/develop that idle the CPU? I wish more would - my CPU fa is awful noisy...

And it isn't a savings of a few nanoseconds we are looking for - by the time you lump scene updates, culling, animation and physics into a single scenegraph (a la IrrLicht), the overhead of updating that data for all entity (whether or not they use it) can become significant.

Quote:

Original post by CadetUmfer Quote: Original post by MichelPaulissen A scene graph is not for visibility culling. It's just a way of representing objects parented to other objects in a tree graph, rather than in a list. In game engines it's usually convenient as you can parent objects to other objects without manually having to update their position and orientation every frame. I knew someone would bring this up :) 1. You don't NEED a scene graph to do culling. 2. Scene graphs are a terrible way to structure game objects. Game objects represent a logical hierarchy, not a physical one. Even worse, you should not be sharing data structures across different systems (renderer and game). Those systems have different needs and should use different data structures. For example your renderer probably wants a list sorted by state changes/textures/meshes. Your game code probably wants a hash/etc keyed on the ID if it's a multiplayer game. Your physics code a spatial hash or octree/etc. 3. Don't use scene graphs

Do you have a good link on this?

Quote:

From a Horde3D forum thread We are currently thinking about taking out the scene tree (transformation hierarchy) from the Horde core. Why? The classical example for a scene tree (or graph) is a car where the four wheels are attached to the chassis. This was how a virtual car might have been built in the early 90s but who would do it like that today? Either the car is completely modelled in a DCC tool and the wheels are part of the model as static meshes or the wheels are physicalized. In the latter case, a physics engine would completely take care of computing the transformation of the wheels and the hierarchical transformation on 3d engine side would just be disturbing. Sure, the scene tree can be convenient if you want to quickly attach a camera, light or particle system to an object (like in the knight sample). However, if you consider a game engine where all interactive objects are in some way represented as entities, you need to somehow store the relation between objects (e.g. camera is attached to character) on a higher level than that of the graphics subsystem anyway. If the 3d engine is doing the transformation in that case, it can even complicate things because then the game or physics has to read back the transformation after horde has updated the scene tree. It would be easier in that case if the game would compute the transformation of the attached camera and just submit the matrix to horde. So I begin to think more and more that is not a good idea if the 3d engine (and even less the renderer) is modifying transformations. Without a scene tree, all horde scene objects would just be added directly into a flat list. Besides making the game engine integration strategy clearer, this would also help to further simplify the horde code and would definitely be beneficial for performance, as the scene tree does not have to be updated every frame (an operation which causes a lot of cache misses).

To paraphrase, your objects are either controlled by physics, so the scene graph is redundant, or they aren't, in which case the scene graph is useless, because the renderer doesn't care what objects "own" others, it cares about state changes, effect parameters, etc. Transformations are the cheapest thing in the world for a renderer, why are you designing it around a data structure whose primary goal is to manage them?

The only blog I can recall is a series over at GameArchitect.net. Here's the third post. You can follow the links there to read the previous ones to gain context (they're a little more about Game Object structure than just scene graphs, but the whole blog is worth reading IMO)

Quote:

Original post by swiftcoder Quote: Original post by Rubicon Therefore it's been totally replaced by "new thinking" to make data management harder The general focus is on making data management *easier*. Why shoehorn every piece of available data into a single container, when you can have one container per data type, specifically designed for that data? Quote: and save perhaps a couple of nS on the fairly idle cpu. Outside of graphics demos, how many games do you play/develop that idle the CPU? I wish more would - my CPU fa is awful noisy... And it isn't a savings of a few nanoseconds we are looking for - by the time you lump scene updates, culling, animation and physics into a single scenegraph (a la IrrLicht), the overhead of updating that data for all entity (whether or not they use it) can become significant.

That was meant as rather tongue in cheek, but I guess my humour is too dry.

However, I don't see how having three or more lists of similar stuff can be somehow easier to maintain than one list of stuff. I explained a very low drag method of avoiding wasted heirarchy math and a qsort doesn't take long to get your rendering right. Chances are you'll need a sort on something whatever you do, so I don't see how separate lists are meant to help there either.

And with just one list, you can say "automate" on certain containers and the physics just works. Doesn't get much easier really.

The bodging is assumed by your use of "shoehorn", but that's unfair - certainly in our setup. The culling and rendering is done lower down than the scene graph containers, so all I'm really doing is making the same lists your are on about, but internally. Which leaves the engine user without much to worry about and the engine running optimally. Win-win.

And sure, the CPU in your game will be running flat out. And that's almost always due to the number of draw calls. Not even the physics usually, and certainly not a couple of qsorts. Our "overhead" doesn't show any spikes in a profile else we'd be doing it differently by now. Speed matters in graphics so I wouldn't advocate anything that wasted meaningful amounts of it.