sponsors gamedev.net search:

Overview 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. Pre-built terrain, used in games like Unreal and other action games. With this type of terrain, it it usually pre-built in a BSP tree for fast rendering. The detail is not very high but the rendering speed is, although it becomes increasingly slow when the terrain gets bigger. The main advantage of this type of terrain is that the shape is unlimited. Overhangs, sheer cliffs and the like are no problem. Just build some brushes and polys and there they are. Example of a heightmap Heightmap terrain is generated from a height map. Usually this is some sort of greyscale image, with the color index of a pixel representing the height of the terrain at that point. It can be used to generate gigantic maps with very high detail but it is usually slower. This form of terrain generation has benefitted the most from increased computing capacity in recent years. The only real drawback to this approach is that the terrain is in effect flat 2D, i.e. no overhangs of any sort. Sheer cliffs are possible but look ugly because the textures get stretched. There is a way around this problem by using models placed on the map to represent overhangs and the like, but this is beyond the scope of terrain mapping in this article. 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! Brute Force 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 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. High Speed Brute Force

Contents   Introduction   High Speed Brute Force   Putting Brute Force to the Test   Printable version   Discuss this article