Scene Graphs: The good, the bad and the ugly

[Roquen]

Since this subjet has popped up a few time, I thought I should open a new thread.

A Scenegraph is a distinct type of data structure and although the second paragraph of the Wikipedia article states that the defination is “fuzzy”, the third paragraph states exactly the form of the data structure and the remainder of the article works with that defination. The exception is the section on spatial partitioning which doesn’t really say anything and is mostly nonsense. For example: it talks about Quake, which is based on spatial partitioning (specifically a BSP) from the editor to the game…no scenegraph is ever involved. Stealing the defination from Wikipedia (in case of changes):

A scene graph is a collection of nodes in a graph or tree structure. A node may have many children but often only a single parent, with the effect of a parent applied to all its child nodes; an operation performed on a group automatically propagates its effect to all of its members.

The problem with calling methods which are not based on this method Scenegraphs is twofold. The first is it makes it difficult to talk about things that are and secondly it’s a source of confusion. To jump problem spaces, hashtables and search trees are examples of methods one can use to implement dictionaries. Calling a splay-tree a hashtable is just silly.

(edit for topic steering)

When I say that scenegraphs are a very bad idea for games, I’m talking about being the “primary” spatial database for a 3D game (the runtime portion). The problems are not bad in the 2D case. In 3D scenegraphs are reasonable (if not good) choices for art packages and rapid prototyping. Thus they can also be reasonable for any associated construction tool for a 3D game, but the big issue here will be the conversion process required to generate the runtime data. The choice(s) of the runtime database system will dictate if this is reasonable or not.

Choosing a spatial database representation is difficult and very game (or rather types of supported enviornments) dependent. However the primary form should virtually always be some form of spatial partitioning.

[gouessej]

The term “scene graph” is ambiguous because actually this word is almost always used to designate scene trees, for example Iris Inventor, OpenInventor, Java3D… Do you know a lot of scene graphs really structured as a graph?

I think it is possible to create an implementation of a scene graph for general purposes allowing anyone to adapt it to his own needs. There is almost no interest in writing its own scene graph from scratch except in a few cases. In my humble opinion, all scenegraphs structured as trees have some common properties. An extendable scenegraph is a good solution.

[Nate]

FWIW, libgdx has a 2D scene graph API.

[Orangy_Tang]

@gouessej

The term “scene graph” is ambiguous because actually this word is almost always used to designate scene trees, for example Iris Inventor, OpenInventor, Java3D… Do you know a lot of scene graphs really structured as a graph?

Java3D allows certain node types to appear in multiple places in the structure (such as geometry, to avoid having to duplicate the memory), usually at the leaf nodes. This means it’s a directed acyclic graph, not a tree.

IIRC most scene graphs take this approach, so ‘scene graph’ is much more accurate than ‘scene tree’.

[Roquen]

@gouessej: I don’t really understand what you’re saying. AFAIK all the packages you listed are scenegraphs. The operative part of a scenegraph isn’t really the implementation details or if it’s an N-tree or a DAG. The operative part is this (from above): “… with the effect of a parent applied to all its child nodes; an operation performed on a group automatically propagates its effect to all of its members.”

Or in other words: At a node (or the connection to a child) a set of geometric and/or rendering operations can be applied to that sub-root (i.e. all children).

[Demonpants]

Well you could say that just a list of entities being drawn is a scenegraph with only one node. I think that’s part of why this becomes fuzzy - a lot of ways of drawing can be argued to be a scenegraph, or multiple scenegraphs.

[Roquen]

Then why not call walking the elements of an array, walking a linked list? Because an array could be considered as a form of a (compact, cache oblivous) linked list. You could, but it would be misleading and (again) rather silly. You’re example is not a scenegraph because no geometric operations or rendering states are being applied. These kinds of definations only become “fuzzy” by improper usage.

But really the point of me opening this thread wasn’t to discuss terms, but to discuss the various pros & cons of scenegraphs vs. other world database represenations. When I stop being lazy I’ll post a first stab at my thoughts.

[appel]

This is a beneficial read:

The Technology of a 3D Engine

• Scene management
• The SceneTree and the SpatialGraph
• The RenderGraph
• The RenderQueue and the rendering process
• Effects, Meta-Effects and Renderables
  http://www.beyond3d.com/content/articles/102/1

[Roquen]

OK. I’m still being lazy, but appel’s link points out “the tip of the iceberg” of the problems with scenegraphs. So I don’t really see any point to writing more unless someone thinks that they are a good idea.

(edited my intial post to “steer” the topic in the direction I intended.)

[lhkbob]

I think the main problem right now is that a lot of engines, in particular Java engines all advertise having “scene graphs” (regardless of what their particular implementation might be capable of). Some examples include Ogre3D, Java3D and JMonkeyEngine. A lot of programmers new to 3D will see this and think that scene graphs are the way to go.

From a programming design and engine perspective, as has been pointed out, scene graphs have a lot of problems. This is easily summed up in the statement that they are “jacks-of-all-trades that can do many things but are not good at any of them”.

Maybe what we should focus on now is not what the exact problems of scene graphs are, but instead on alternates to how engines might be designed:

In my current engine, I’ve scrapped the scene graph completely. It was originally inspired by the concept of a scene tree, spatial structure and render queue but was then combined with an entity-component system. All of the rendering, geometric and physical properties are components on entities. These are processed by “controllers” which handle a number of tasks from animation, culling, to actually rendering the engine specific representation of each entity.

[jezek2]

@lhkbob

I think the main problem right now is that a lot of engines, in particular Java engines all advertise having “scene graphs” (regardless of what their particular implementation might be capable of). Some examples include Ogre3D, Java3D and JMonkeyEngine. A lot of programmers new to 3D will see this and think that scene graphs are the way to go.

I don’t think this will ever change. Programmers doing these opensource engines always seek ‘nice’ structures and modularity. The problem is that this is never the case, it’s always shades of ‘ugliness’. Creators of commercial engines seek a way to make it really work, otherwise they couldn’t sell it. Opensource engines don’t need to sell anything and since they’re not developed with concrete game(s) in mind they spend development on wrong or wrongly done features.

[Orangy_Tang]

@lhkbob

It was originally inspired by the concept of a scene tree, spatial structure and render queue but was then combined with an entity-component system.

Yeah, this is my approach as well. The nice thing about this approach is that each individual part (scene tree, spatial structure, render queue) can have a brain-dead simple implementation when you’re starting so you get things working quickly, but then be replaced with a proper implementation later without having to rework the rest of the game. Eg. the spatial tree might just be a big list of objects at first and then get replaced with a quad tree. And if your game’s requirements in one particular area are simple then you can even get away with the simple part for the entire game (like if you’re doing a single-screen platformer where you’ve only got a handful of objects so don’t need the quad tree).

Keeping things decoupled is good, and traditional scene graph runs counter to that in so many ways.

[gouessej]

@Orangy Tang

Java3D allows certain node types to appear in multiple places in the structure (such as geometry, to avoid having to duplicate the memory), usually at the leaf nodes. This means it’s a directed acyclic graph, not a tree.

IIRC most scene graphs take this approach, so ‘scene graph’ is much more accurate than ‘scene tree’.

When I had to implement my network to contain my cells and my portals in JMonkeyEngine 2, I couldn’t simply put the same node representing a cell into the list of children of several other nodes because there was no mechanism to check whether I had already looked at a particular node (it would have drawn several times exactly the same cell which is completely useless). JMonkeyEngine 2 is structured as a tree like Ardor3D; if I put the same node several times into the scene graph, it will “treat” them several times, it will render them several times, it will act as a tree, it won’t consider the multiple occurrences of the same node as a single node. That is why the term “scene tree” would be more accurate in my humble opinion.

@Roquen

@gouessej: I don’t really understand what you’re saying. AFAIK all the packages you listed are scenegraphs. The operative part of a scenegraph isn’t really the implementation details or if it’s an N-tree or a DAG. The operative part is this (from above): “… with the effect of a parent applied to all its child nodes; an operation performed on a group automatically propagates its effect to all of its members.”

Or in other words: At a node (or the connection to a child) a set of geometric and/or rendering operations can be applied to that sub-root (i.e. all children).

The definition of Wikipedia makes a difference between scene trees and scene graphs, that is what I meant. All famous scene graphs written in Java are … scene trees with some tiny modifications.

@jezek2

I don’t think this will ever change. Programmers doing these opensource engines always seek ‘nice’ structures and modularity. The problem is that this is never the case, it’s always shades of ‘ugliness’. Creators of commercial engines seek a way to make it really work, otherwise they couldn’t sell it. Opensource engines don’t need to sell anything and since they’re not developed with concrete game(s) in mind they spend development on wrong or wrongly done features.

You’re a bit to harsh with open source engines as JMonkeyEngine is used for concrete commercial games like Poisonville and Ardor3D is used in some commercial scientific applications.

@Orangy Tang

Keeping things decoupled is good, and traditional scene graph runs counter to that in so many ways.

I admit using some spatial partitioning methods with traditional scene graph engines can be difficult but it can be implemented cleanly.

[Mr_Gol]

@jezek2

Open source engines don’t need to sell anything and since they’re not developed with concrete game(s) in mind they spend development on wrong or wrongly done features.

I understand your point, but to put it like that is not really fair. Hibernate is also being developed without a specific (web) application in mind, yet it is used by thousands of companies. I am quite sure that there are open source game engines that are quite good, and that there are commercial engines that are incredibly bad. Unfortunately quality is not the same as popularity, regardless of the licensing a project uses.

[gouessej]

@Mr_Gol

Unfortunately quality is not the same as popularity, regardless of the licensing a project uses.

;D Microsoft Windows is popular…

[jezek2]

@Mr_Gol

I understand your point, but to put it like that is not really fair. Hibernate is also being developed without a specific (web) application in mind, yet it is used by thousands of companies. I am quite sure that there are open source game engines that are quite good, and that there are commercial engines that are incredibly bad. Unfortunately quality is not the same as popularity, regardless of the licensing a project uses.

I’m afraid Hibernate falls into this “bad” category too. ORMs, at least how done with libraries such as Hibernate, are useless abstraction that hurts things than helps them. It pretends to be ultimate solution for data problem, but the data “problem” is much bigger. One must understand the centre of everything is in the data structures / database and not the code, think of lossless schema updates and stuff. And relational databases are really good at this, even if it means some manual work, but it’s actually needed as no automatic mechanism can make eg. the schema changes automatically without flaws.

Instead of putting head into the sand, it’s better to fully explore it and embrace it. Thousands companies use Hibernate or other ORMs, but they’re producing mediocre results, only saved by huge amount of employees to make it work. Not that I’m opposed to ORM idea generally, but so far I’ve only seen the bad way of doing it.

[gouessej]

@jezek2

I’m afraid Hibernate falls into this “bad” category too. ORMs, at least how done with libraries such as Hibernate, are useless abstraction that hurts things than helps them. It pretends to be ultimate solution for data problem, but the data “problem” is much bigger.

Thinking Hibernate is magic and solves all problems is the wrong way to go but Hibernate is far from being useless. You remind me that I worked for a corporation that had created its own ORM and I can tell you that:

• an ORM can be useful
• creating and maintaining your own ORM requires a lot of resources
• it is difficult to obtain something as powerful as Hibernate when only 2 employees work on it
• a badly used ORM is worse than no ORM
• using ORMs to ignore SQL and performance issues is like asking a child to run a car without a driving license…

[jezek2]

@gouessej

Thinking Hibernate is magic and solves all problems is the wrong way to go but Hibernate is far from being useless. You remind me that I worked for a corporation that had created its own ORM and I can tell you that:

• an ORM can be useful
• creating and maintaining your own ORM requires a lot of resources
• it is difficult to obtain something as powerful as Hibernate when only 2 employees work on it
• a badly used ORM is worse than no ORM
• using ORMs to ignore SQL and performance issues is like asking a child to run a car without a driving license…

Yeah I agree. There are different kinds of ORMs and different ways how to use them, unfortunatelly I see that most people using such ORMs have attitude of thinking of it as a silver bullet and even refuse to learn SQL. Any abstraction is as great as the users using it, it’s great tool for advanced users while creating disaster for the less skilled ones.

[loom_weaver]

Hibernate is like any other framework–it makes the easy 90% easier and the hard 10% harder.

[gouessej]

@jezek2

Yeah I agree. There are different kinds of ORMs and different ways how to use them, unfortunatelly I see that most people using such ORMs have attitude of thinking of it as a silver bullet and even refuse to learn SQL. Any abstraction is as great as the users using it, it’s great tool for advanced users while creating disaster for the less skilled ones.

The same thing happens with scene graphs and IDEs. Some people use Eclipse and Netbeans to avoid learning how Java works, some people use JMonkeyEngine to avoid learning how a Java binding for OpenGL works… In my humble opinion, we should know the lowest level layers before using high level solutions to be able to understand them and to fix bugs in them.