Scene Graphs: Why Bother?

This was my attitude towards scene graphs for a long while, for the most part what I did in my game engine was very linear using either a queue, vector or list and it seemed to work just fine. I'd add new objects and still my FPS would power along at over 60 until the straw (or maybe more accurately the 'grass') that broke the camels back. You can check my previous post on using a quad tree for grass rendering and keep an eye out for a future post on Terrain rendering using a scene graph.

I'd seen and read all sorts of information on scene graphs and why I needed one, but every article or post I found was so 'wishy washy' (technical term). It seemed nothing more than some fancy buzz word that was flavour of the month. They wouldn't give good details of how best to actually implement one and most gave completely different implementations. The ones that did give implementations seemed so overly slow and complicated and involving so much overhead that I didn't see the point still. So when I eventually ran into trouble with my linear approach I went to quad trees because I could understand those posts and articles and I thought to myself I'm always going to choose quad tree when it comes to the scene graph vs quad trees debate.

But how naiive I was. What I didn't know then that I do know now is that scene graphs and quad trees are not a one or the other decision like a DirectX or OpenGL. Infact a quad tree is a basic type of scene graph I'd been using a scene graph all along and not realised it, but worse than that by being blinkered to the fact I also missed out on other benefits.

But it's actaully more than that because an OctTree is also a type of scene graph, a DAG (Directed Acyclic Graph) is also a scene graph plus countless other possible implementations. Hence the reason why all the different articles could have such different implementations. So infact you can build all of these implementations from a scene graph and best of all that mean's you can design and build all sorts of hybrid graphs to suit your needs perfectly. Sound familiar? it's got inheritance written all over it.

Put simply a scene graph is made up of a series of nodes each of which has links to other nodes (however many you need) and in some cases other information. This other information can range from bounding volumes to meshes and vertices and everything in between. For example if you make every node have axis aligned bounding boxes and must include 4 nodes which divide the current nodes axis aligned bounding box into 4 equal parts bingo! you've got a traditional Quad Tree.

I now have ideas beyond a traditional quad tree for my terrain rendering. I'll still have 4 child nodes just like in a quad tree used for visiblility determination but now I can also have 4 additional nodes for Level of Detail (LoD). So it will actaully be a network of Quad Trees that will allow the rendering of the terrain even more efficiently taking into account both visibility and level of detail at the same time.

So in summary don't be afraid of the concept of a scene graph, you could very well be using one already and not realise it just like me. If you're not using one then jump in the deep end and have a go and keep tuned for future posts on my Scene Graph design, implementation and real world benefits for Terrain rendering. I promise to try not to be so 'Wishy Washy'.