Terrain, Part 2
By Shamus on Feb 1, 2006 
Filed under: Programming 
8 comments 
Last time we left off, I had created a very simple program for loading in a big ‘ol wad of terrain data and rendering it in painful, CPUkilling detail. This time I’m going to be adding code to cut down on the number of polygons drawn. Here is how the terrain looked last time:
Right now it’s rendering about half a million polygons, which is a grotesque waste of rendering power. There are way too many polygons, most of which we could do without. So how to simplify? There are any number of opensource solutions, but since the goal of this project is to write my own terrain engine from scratch, I’m going with this system as explained by Peter Lindstrom. It’s titled Terrain Simplification Simplified: A General Framework for ViewDependant OutofCore Visualization. Despite making the claim of simplicity twice in the title alone, this stuff is, in fact, quite tricky to grasp. Maybe the claims of simplicity are just dry humor. Or maybe I’m just dense. Either way, this stuff was brainbusting for me.
The goal here is to reduce flat areas into few polygons, and keep complex areas (slopes) more highpolygon.
The problem is that you need to smoothly transition from highpoly in one area to lowpoly in another. If you don’t, there will be little gaps in the terrain between high and low detail areas. The background (the blue sky, in this case) will shine through the gaps.
But how do you do this? Imagine a piece of paper. On the left half of the paper you have dots an inch apart. On the right, the dots are two inches apart. Now, connect all the dots in such a way that you make only triangles, and that you use the fewest number of triangles possible. If you work at it for a while, you’ll do it. Now: Same piece of paper, except it’s 512 inches wide and 512 long. Some spots have dots an inch apart, others have dots 2 inches, others have dots every 4, 8, 16 or 32, or even 64 inches. Now try making the right triangles.
The secret here is a quad tree. This is a great way to handle a large grid of data, which is what I’m up to.
To use a quad tree, our grid must be a perfect square. It has to have the same width and height, and they must be a power of 2. In the terrain I’ve been using, the width and height is 512, which is 2^{9}. For our example here, let’s assume we’re working with an 8×8 grid, which is 2^{3}.  
The main grid is divided into 4 quadrants. So, we have this subgrid of 2 x 2. Then…  
…each of those squares is, in turn, divided into 4 quadrants. This yields a subgrid of 4 x 4, which in turn can be divided further, and so on.
Anyway, this gives us a way to look at the grid at different levels of detail. 

My program starts at the largest blocks on the 2 x 2 grid. Let’s say it examines the four blocks in question and determines that the lowerleft one is a bit hilly, and needs to be divided further. The other three quadrants are flat enough that they can be left alone. So, we divide the lowerleft block.  
Within that block, we have 4 smaller blocks, and of those 4, we determine that the upperright has some detail that needs to be preserved, but the other 3 are again simple enough that they can be left alone. Once again, we divide the one block into 4 smaller ones.  
Now for the magic. My program knows where the interesting detail is on the terrain, and what areas are flat and should be left simple. But how do I turn this into triangles?
The great thing about programming is that you can still follow a given set of directions and get to where you’re going, even if you don’t understand how to get there. By following the proceedures described in the Lindstrom article, I was able to get the triangulation to happen. However, I couldn’t actually understand it until I was done. This was an amazing moment. I didn’t know how to do it until after I’d done it. Strange. The is one of those concepts where I wonder how someone thought of it in the first place. I can only conclude that they must be a good bit smarter than me. 
It took most of last weekend to sort out these ideas and distill them into code. Still, the results are impressive:
The upperright side of the image is of the unoptimized terrain. The lowerleft is of the exact same view using the polygonreduction system. Note that when viewed solid, and not wireframe as they are here, these two would look almost identical. That is, I’ve only sacrificed a tiny bit of visual quality. So how much did I save?
The new terrain is 158,000 polygons. So, I’ve removed an amazing twothirds of the polygons from the scene.
There is obviously a tradeoff at work here. I can sacrifice visual quality for polygon reduction. If I’m too agressive, small hills and other details will vanish altogether, and the scenery will look bland. However, I’m not at the point where I want to start tuning it just yet.
Looking at all of this wireframe is getting dull. Let’s make it solid and add some lighting.
By turning my optimizations off, I can now confirm that the optimized and nonoptimized views are so similar that it isn’t even worth adding more screenshots to show the differences: they really do look almost the same.
Do you have a brief outline of the source used in the LOD subdividing system presented here?
I am not looking for anything that specifies where to subdivide; or the entire source code; just a simple subdividing rendering example where the flat areas contain less polygons, and the hilly areas contain more..
Thanks,
DEAR
The Lindstrom article isn’t available at the specified URL, but there’s a (probably simpler) article on the same technique at Gamasutra.
very usefull…
but will be perfect if source code is available for each part, besides explaining the algorithm instead of the result.
[…] The previously mentioned Shamus Young used in one of his previous projects and talked about it here. The links he gives are dead now, but if you’re interested you can find a copy of the paper […]
Could the code be available for download?
The Lindstrom paper is now available here http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.4771&rep=rep1&type=pdf
And Lindstrom’s list of publications:
http://people.llnl.gov/lindstrom2
[…] Young talked about terrain simplification some time ago during his original terrain project. This seemed as good a place as any to start, so I grabbed a […]