Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
1  
Thanks Nick. I'm actually a 3D animator (real 3D not flash) turned programmer, thus I tend to think in terms of graphics. If that's not bad enough, I started in Java and have been prying myself from the "everything must be an object" mentality instilled in that language. You've convinced me that the scene graph should be separated from rendering and culling code, now my gears are spinning on exactly how that should be accomplished. I'm thinking of treating the renderer like it's own distinct system that references the scene graph for transform data, etc. –  Cody Smith Dec 29 '12 at 19:57
1  
@CodySmith, Glad it helped. Shameless plug, but I maintain a framework which is all about SoC / MVC. In doing so, I've come to blows with the more traditional camp in the industry who insist everything should be in a central, monolithic object. But even they would tell generally you -- keep your rendering separate from your scene graph. SoC / SRP is something I cannot emphasize enough -- never mix more logic into a single class than you need. I'd even advocate complex OO inheritance chains over mixed logic in the same class, if you put a gun to my head! –  Nick Wiggill Dec 29 '12 at 20:10
    
No I like the concept. And your right, this is the first mention of SoC I've seen anywhere in years of reading about game Design. Thanks again. –  Cody Smith Dec 29 '12 at 20:51
    
@CodySmith Quick thought while browsing over this again. In general it's good to keep things decoupled. For various types of model-controller objects in your codebase that undergo rendering, however, it is fine for you to keep collections of Renderables (which is an interface or abstract class) internally to those core model-controller objects. Good examples of this are entities or UI elements. Thus you can rapidly access only those renderers pertinent to that particular core object -- without implementation specifics which would contaminate the entity class, hence the use of interfaces. –  Nick Wiggill Jan 4 '13 at 22:27
    
@CodySmith The benefit is clear with entities, which might eg. have representations both in the world viewport and on a minimap. Hence, the collection. Alternatively, you can allow just a single renderer slot for each model-controller object, internally to that object. But keep the interface general! No specifics -- just Renderer. –  Nick Wiggill Jan 4 '13 at 22:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.