Scene Management Part One: The Scene Graph

I've decided to do a little blog series on Scene Management, since I just wrote some classes for it in the Render Engine.

Introduction
Firstly, some terms, and a few words covering the question: what is Scene Management?

Well, principally, scene management has nothing to do with rendering. This may seem a bit weird, seeing as I've just said I'm covering it because it's used in the renderer.

However, Scene Management is all about taking the data we have as inputs - lights, meshes and cameras, and sending what we can see over to the renderer to draw. Anything that can't be seen ideally shouldn't get sent. There's a great quote that sums the reasoning behind limiting what the renderer has to process: "It is simply very, very fast to render nothing."

So the aim of the scene manager is to generate a Potentially Visible Set of render data, to send to the renderer.

Structure
Now, the main part of today's blog will be on the structure of something called the Scene Graph, which is where all the objects in the scene are stored. Terrain will be covered separately, when I add that to the engine!

There are numerous ways of setting up a representation of the objects in your scene. Really, there are as many different ways of doing it as there are implementations - every developer will program it differently. Personally, I like the Bounding Volume Hierarchy Tree system, which I'll cover in depth now after taking a brief look at some alternatives.

Quad Trees
Quad trees split space into four. And then four again. And again and again, until the desired resolution is met.
This is easiest to see with a diagram, courtesy of Dion Picco in this article on flipcode:



In each node goes a series of objects. The idea is, the objects in one node can't be in contact with objects in another. In any portion of the quad tree which can't be seen, none of the children nodes can be seen either.

Quad trees are very useful for terrain rendering.

Oct Trees
Oct trees are very much like Quad Trees, in that they split space up, so I won't go into too much detail. So, imaging you have a quad tree, completely flat, stretch it vertically. You now have a lot of cuboids. Divide these based on the size of the quad tree node, so that each cuboid is split into multiple cubes. You should end up with something like this (Thanks to Stefan Giesecke for image):



An oct-tree has the same properties as a quad tree, but in 3D. It is more useful in areas where objects have variable heights, since it covers the y axis as well as the x and z axes.

Bounding Volume Hierarchy Trees
BVH Trees are made up of BVH nodes, and are a spatial structure. By this I mean that each node bounds all of its children, of which there may be many. To do this, they use bounding volumes, which are typically bounding spheres and bounding boxes.

In my implementation, there is a single main world node, which contains all the objects in the scene. Each object has its own bounding volume set, which is a group consisting of the bounding box and the bounding sphere. More on why I use both later!

Each BVH node can have an object attached, be it a camera, mesh or light. Since only meshes have any real volume, only they are taken into consideration when we calculate the bounding volume, along with the bounds of the children. This forms a system like the one shown below:



Here, both objects are part of a tree where the green bounding box represents their common parent.

That concludes part one of this series on Scene Management. Part two will be on frustum culling, and I'll write that in a few days time.

I'll sign off with a picture of the BVH system in the latest screenshot of the engine:



Have you got any thoughts on our use of scene graph systems in our render engine? Let us know in our forums!

---

Well, after our breifer than expected break from development, I'm glad to say that myself and Dotmister are back at DarkKnight, and we've brought reinforcements.

I'd like to welcome:

Zkajo - Artist, Storywriter
TomCatFort - Programmer
Galasteno - Artist

to the team.

I'd also like to announce that we have a brand new plot, which will be revealed in due course. We've also changed the name of our RPG to the much more pronouncable "End of Days", rather than the old mouhtful "Knights of the Forgotten Realms". The new abbreviation is EoD.

Not only that, but there are several new members who still may join, who we met during our time at IndiX. It was definitely a worthwhile experience, and I'm proud to say that we made a great little arcade game, called Techtris, which obviously isn't based on any other game. The final touches will be made to that this weekend, then I'll release it on this blog and over at the IndiX forums ( http://www.mitsiee.co.uk/forum/index.php ).



On the topic of relations with other teams, are there any other groups you'd like to see us get to know? Tell us what you think!

---

Dotmister and I have decided to take a break from development, in order to gain some more skill in developing games. It was a bit stupid to start with an MMORPG as our first project - after all, something which takes many years for professional studios can't really be achieved by two guys at school.

We're now at http://www.mitsiee.co.uk/forum/ if you want to contact us.

So, this will be my last post here in a while. Hopefully we'll return eventually, ready to continue where we left off, with a ton more knowledge. But until then, farewell!

---

How technology progresses! Yup, that's right, within three hours of stating very firmly that I was using quad trees for our terrain, I was told that they weren't all that good - "so year 2000". Hence, I've b een researching a new form of Level-of-Detail called Geoclipmapping, which features a shader-based approach to rendering terrain - much faster and much more efficient. I've begun to implement some of the shaders that will allow us to use this, and I have a screenshot!

---

Well, this weekend I've been focusing my attentions on the Terrain system of the game. There are a number of things wrong with it at the moment, namely that I completely hate the layout! It also uses PNG files, which are slow to load, and the current system requires the storage of whole files.

So, I've been addressing two of these issues. Heightmaps will now be stored as TGAs, which while larger than PNG files, make up for it with their simplicity. This'll mean that we can read individual pixels at a time, rather than the enitre file.

I've written a TGA loader to load the new format, and I'm extremely impressed with its performance. It can read 6000 pixels across 6 different TGAs in 200ms - and with a startup time of 156ms, this means that each pixel takes 0.007ms to load - more than quick enough for our terrain system.

Our old terrain system used the equivalent of 30 massive grids of about 16 million bytes each, racking up a massive 460mb of memory! Most PCs only have 4x this amount, so it was obvious that the memory requirements would have to change unless I wanted the game to run on anything less that a supercomputer.

There are a number of ways of storing the terrain once we have the data - and I've been researching quad trees, which seem to be the most memory efficient route. Quad trees allow us to have variable levels of distance as the terrain becomes further away from the player - meaning that less and less memory is used, further away. They also fit in great with our new frutum culling system (next news post is a big one!), and I reckon that terrain will run brilliantly once they're in.

Do you have any suggestions on how we can increase the performance of our terrain, or anything you'd like to see with our terrain in general?

---

Well, just a quick blog post to say that I've decided to switch our physics engines once again, due to lack of support and unclear documention on the part of Bullet. We're now using the NVidia PhysX Engine, which is well known, very fast and very stable. It also has far better documentation than Bullet, and a full blown SDK.

In other news, we're currently implementing frustrum culling, which should speed the game up no end, and I'm just finishing off the GameObject classes to allow us to begin constructing the actual game. Our current character classes will inherit the GameObject class (means that we can treat characters just like any other object) and GameObjects will be able to be created and deleted anytime.

The modelling department is filling up once again, and I'd like to give a warm welcome to our newest developer, Matt. He's also the provider of our new server, so try not to upset him! Only kidding Matt...

On a side note, if you can help us or know of anyone willing to help, we have LOTS of vacancies in the modelling and concept departments. The more the merrier!

So, good times at the moment, watch this space for upcoming news!

---