Rolling my own scene graph

Question

Hello Game Development SE!

I'm crawling my way through OpenGL with the hopes of creating a simple and very lightweight game engine. I view the project as a learning experience that might make a little money in the end, but will be fun either way.

So far I've used GLFW to gain some basic I/O, a window (with a oh so fancy F11 fullscreen key) and of course an OpenGL context. I've also used GLEW to expose the rest of the OpenGL extensions because I'm using Windows and I want to use all of OpenGL 3.0+.

Which brings me to the scene graph. In short, I'd like to roll my own. This decision came after looking at OSG and reading a few articles on how the concept of a scene graph has become twisted, bent and broken. One such article described how scene graphs have developed as...

Then we added in all this extra stuff, like hanging ornaments on a Christmas tree, except that some of the ornaments are nice juicy steaks and some are whole live cows.

Following the analogy, I'd like the steak, the meat of what a scene graph should be, without having to strap on piles of extra code, or any whole cows.

So with that in mind, I find myself wondering exactly what a scene graph should be and how a simple scene graph should be implemented? Here's what I have so far...

A one parent, n-children tree or DAG which...

• Should keep track of game object transformations (position, rotation, scale)
• Should hold render states for optimizations
• Should provide a means of culling objects not within the view frustum

With the following properties...

• All nodes should be treated as renderable (even if they don't render) This means they...

  • Should all have cull(), state() and draw() methods (return 0 if non-visible)
  • cull() recursively calls cull() on all children, thus generating a complete cull mesh for the entire node, and all children. Another method, hasChanged() could allow so-called static meshes to not need to have their culling geometry computed each frame. This would work such that if any node in the sub-tree has changed then all geometry down to root is rebuilt.

• Render states will be held in a simple enumeration, each node will select from this enumeration an OpenGL state set that it requires and that state will be setup before draw() is called on that node. This allows for batching, all nodes of a given state set will be rendered together, then the next state set is setup and so on.

• No node should directly hold geometry/shader/texture data, instead nodes should point to shared objects (perhaps managed by some singleton object like a resource manager).

• Scene graphs should be able to reference other scene graphs (maybe using a proxy node) to allow situations like this, thus allowing complex multi-mesh models/objects to be copied around the scene graph without adding a ton of data.

I'm hoping to get some valuable feedback on my current design. Is it missing functionality? Is there a vastly better way/design pattern? Am I missing some larger concept that will be necessary to include in this design for a somewhat simple 3D game? Etc.

Thanks, -Cody

Answer 1

The Concept

Fundamentally, a scene graph is nothing more than a bi-directed acyclic graph which serves to represent a hierarchically-structured set of spatial relationships.

Engines in the wild tend to include other goodies into the scene graph, as noted. Whether you see that as the meat or the cow probably depends on your experience with engines and libraries out there.

Keeping it Lightweight

I favour the Unity3D style of having your scene graph node (which at it's heart is a topological rather than a spatial / topographical structure) inherently include spatial parameters and functionality. In my engine, my nodes are even lighter-weight than Unity3D, where they inherit a lot of unncessary junk members from superclasses / implemented interfaces: Here's what I have -- about as light as you can get:

• parent / child pointer members.
• pre-transform spatial parameter members: xyz position, pitch, yaw and roll.
• a transform matrix; the matrices in a hierarchical chain can very quickly & easily multiply out by walking recursively up/down the tree, giving you the hierarchical spatial transformations which are a scene graph's main feature;
• an updateLocal() method which updates only this node's transform matrices
• an updateAll() method which updates this and all descendant nodes' transform matrices

...I also include equations-of-motion logic and thus velocity / acceleration members (linear & angular) in my node class. You can forego that, and handle it in your main controller instead if you wish. But that is it -- very lightweight indeed. Remember, you could have these on thousands of entities. So as you've suggested, keep it light.

Constructing Hierarchies

What you say about a scene graph referencing other scene graphs... I'm waiting for the punchline? Of course they do. That's their main use. You can add any node to any other node, and transformations should automatically occur within the new transform's local space. All you're doing is changing a pointer, it's not like you're copying data around! By changing a pointer, you then have a deeper scene graph. If using Proxies makes things more efficient then by all means, but I've never seen the need.

Avoid Render-related Logic

Forget about rendering as you write your scene graph node class, or you will confound things for yourself. All that matters is that you have a data model -- whether it's the scene graph or not doesn't matter -- and that some renderer is going to inspect that data model and render objects in the world accordingly, whether it's in 1, 2, 3 or 7 dimensions. The point I am making is: Do not contaminate your scene graph with render logic. A scene graph is about topology and topography -- i.e. connectivity and spatial characteristics. These are the true state of the simulation and exist even in the absence of rendering (which can take any form under the sun from a first person view to a statistical graph to a textual description). Nodes don't point to rendering-related objects -- however the reverse may well be true. Also consider this: Not every scene graph node in your entire tree will be renderable. Many will be just containers. So why even allocate memory for a pointer-to-render-object? Even a pointer member that is never used, is still taking up memory. So reverse the pointer direction: Render-related instance references the data model (which might be, or include, your scene graph node), NOT vice versa. And if you want an easy way to do run through your list of controller yet get access to the related view, then use a dictionary / hashtable, which approaches O(1) read access time. That way there is no contamination, and your simulation logic doesn't care what renderers are in place, which makes your days and nights of coding worlds easier.

As for culling, refer back to the above. Area-of-interest culling is a simulation logic concept. That is, you don't process the world outside of this (usually boxed, circular or spherical) area. This takes place in the main controller / game loop, before rendering happens. On the other hand, frustum culling is purely render-related. So forget about culling right now. It has nothing to do with scene graphs, and by focusing on it you will be obscuring the true purpose of what you are trying to achieve.

A Final Note...

I get the strong feeling you are coming from a Flash (specifically AS3) background, given all the details about rendering included here. Yes, Flash Stage/DisplayObject paradigm includes all the render logic as part of the scenegraph. But Flash makes a lot of assumptions that you don't necessarily want to make. For a fully-fledged game engine, it is better not to mix the two, for reasons of performance, convenience and controlling code complexity through proper SoC.