PART I: Terrain Rendering using a Scene Graph

Now that I finally have my head around the concept of a Scene Graph the ideas of how best I can use it in my Brainstorm game engine has been keeping me awake at night. Here's hoping that getting my idea out on paper (well blog form actually) lets me sleep. I'm going to start from scratch and explain the evolution of my design.

So how does one represent a terrain in computer graphics? Well there are actually a number of ways, each with their own pros and cons. I'm not about to start a war of philosophies on this subject but to simply tell you that for my implementation I have chosen to use a regular grid heightmap because it suits my design best.

A regular grid heightmap has points that are evenly spaced in 2D with the height of them varying to represent the peaks and troughs of a terrain. In my case I'm using a 513 X 513 grid of heights. Each grid is 1 meter apart, giving a total area of 512m X 512m. Why 513 you might ask? Well it actaully makes it easier to divide up later as smaller grids always need to share a side of vertices to make them match up nicely. You can get to these numbers by taking 2^n + 1 eg. 2^9 + 1 = 513. I'll explain it a bit more later.

Now if we took a brute force approach to rendering this grid we would have 263,169 vertices and 524,288 triangles to attempt to render! Crickey that's a lot especially when if we're a character standing on the terrain we probably aren't actually able to see very much of the terrain at all (could be less than 10%). So that's a lot of wasted effort to render vertices and triangles we can't even see and our frame rate will suffer badly.

So the first step is to divide our large grid up into a series of smaller parts or patches. In my case I've divided it up into 256 individual terrain patches to represent the full 513 X 513 grid. That gives us patches that are 33 X 33 verticies across. This time to render the terrain we can check which patches are visible and only render those ones. It's a much better solution we now have 256 visibility checks and we only draw the terrain that is visible. But we will always have 256 visbility checks even if 3/4 of terrain is clearly behind us and not visible, can we do better?