This article is intended for hobby programmers like myself but it should be interesting for any programmer out there involved in terrain mapping. I don't consider myself to be an excellent programmer. It could very well be that to guru programmers, my opinion about terrain mapping is utterly ridiculous, but then again, it could also be an eye opener. You decide. For me, the techniques I present here work well. In this article I'm going to explain my personal vision about terrain mapping and especially the very old and simple brute force algorithm.
Terrain mapping techniques
If you type "terrain mapping" into a random search engine on the net, you'll get a huge number of hits, all about terrain mapping and all about making it faster and better looking. In the last few year computers have become increasingly fast and terrain mapping is one of the fields that benefits greatly from this. If you sift through all the info you can see that there are basically 2 approaches to rendering terrain.
My focus is purely on the second type of terrain generation. It has gained enormous popularity over the years because new and faster rendering algorithms have been developed to speed it up greatly!
For my own game project Raid3D I was looking for a good algorithm to render my terrain. I required fast rendering and huge maps (counting terrain in sq. kilometers rather than sq. meters). The oldest and most simple algorithm is simply the brute force approach. A typical brute force renderer simply draws a quad between any 4 adjacent points on the heightmap. This works well and gives the highest quality graphics you can have but it used to be extremely slow. In order to fix the speed problem new algorithms were invented, such as CLOD (Continuous Level Of Detail), which is currently the ruling emperor in terrain mapping.
CLOD relies on a simple principle, reducing the amount of polygons that the renderer has to draw. One way of doing this (called Realtime Optimally Adapting Meshes or ROAM) is to split up the terrain in patches (squares) of arbitrary size (e.g. 32x32 points on the heightmap). This patch is then reduced to two triangles, ignoring any heightpoints that are inside the patch. The computer then calculates the eventual triangle position on the screen and compares this to the points on the heightmap that were earlier ignored. If the difference of height in pixels between the triangle and the heightmap is greater than a certain threshold value (e.g. 3 pixels) then the triangle is split in two. After that, the two new triangles are recalculated again, and the process is repeated until the screen error is less than the threshold value. In the end you'll get a list of triangles to display on the screen. The amount is much much smaller than the amount you get when brute force is applied and therefore faster while the quality is still high (maximum error of 3 pixels).
Comparing Brute Force and CLOD
There are two main differences between brute force and CLOD. The first one is CPU overhead. CLOD needs to build a new set of triangles to display every frame. This requires quite a bit of processing power. Brute force always displays the same set of triangles and can therefore precompile all the traingles of the terrain on the 3D accelerator (e.g. using display lists in OpenGL). At rendering time one call is made to the 3D card and the triangles get rendered. This takes much less CPU overhead and the triangles get rendered faster because they are already precompiled.
The second main difference is the way brute force and CLOD use triangles to display terrain. Both algorithms can handle approximately the same numbers of triangles. Brute force handles slightly more because they are precompiled on the 3D card. CLOD however uses more triangles in the areas close to the camera and less near the horizon. Bruce uses the same density everywhere, independent of the camera's position. Therefor brute force cannot display the same quality of landscape as CLOD even though both landscapes are made up of the same number of triangles.