by [email="s.marechal@jejik.com"]Sander "Tweety" Mar?chal[/email], Lone Wolves Production
April 22, 2002
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
Computer capacity has increased greatly over the last couple of years. 3D accelerators can process huge numbers of polygons per second. Because of this brute force has been gaining on CLOD algorithms. It cannot produce the same quality as CLOD but it has gained enough speed to present a realistic alternative to CLOD. There are still many situations in which brute force is not a real option, but in some cases brute force might actually be good to use. At the moment 3D graphics power is still advancing faster than CPU power. As long as this trend is continuing, BF is gaining on CLOD because CLOD relies more on CPU capacity than 3D hardware power. After all, CLOD was invented to bybass the problem of relatively slow 3D graphics processors.
Example of the Raid3D brute force engine running at 138 fps at a resolution of 800x600x32.
Wireframe render of Raid3D's brute force. Quite a lot of polygons but still fast because there's very little CPU overhead.
Brute Force applications
Below, i present some situations in which BF could do the trick and situations in which it really isn't a good idea.
Clipping horizon: Brute force cannot handle very far clipping distances. The number of triangles it has to process increases very rapidly in comparison to CLOD. Say for example you want to extend the horizon by the size of a patch. This means drawing, for example, 8 extra patches of terrain on the screen. For brute force, with 256 triangles per patch, this would add 2048 extra triangles. For CLOD this would be only 64 extra triangles.
I tried to double the horizon in my Raid3D engine from 100f to 200f (with a detail of 4f). The framerate dropped from 130 fps at 100f to about 50 fps at 200f. 50 fps is not bad at all but a major decrease from the 130 it was running at before. From this perspective, good candidates for brute force would be strategy games. Near the horizon the player units get very small so you don't need to have a really distant horizon. Flightsims on the other hand do need to have a distant horizon and are therefore ill suited for brute force. The loss in speed can be compromised by decreasing the detail of course but that would indicate significant quality loss, which you obviously don't want.
Detail: The same story as above can be applied to detail. Doubling the detail is pretty much the same as doubling the clipping horizon as far as triangle counting goes. Brute force is therefore best suited to applications that do not require much detail. Generally this means applications where the camera is further away from the terrain. This makes brute force a poor candidate for outdoor first person shooters where you want lots of detail, but still suitable for strategy and god games.
3D hardware: Brute force needs a relatively fast 3D accelerator to function properly. It has to be fast enough draw the extra triangles you get with brute force in the time CLOD uses to calculate the perfect triangle set. I tested with a nVidia TNT2 32Mb. In my testing comparisons CLOD was slightly faster so TNT2 would be the absolute minimum card you could use brute force on. I haven't had the opportunaty to test with higher end cards like GeForce 4 but brute force should do better on those.
Frustum culling: Finally brute force requires accurate frustum culling. With CLOD this is of less importance since the patches that get rendered near the clipping edge are usually made up of 4 or 8 triangles. With brute force this can be as much as 256. Therefor CLOD benefits the most from high speed culling, sacrificing some accuracy. Brute force really needs high accuracy to cull away as many patches as possible. In Raid3D I use a quadtree and accurate math to do this.
GeoMipMaps
Of course I'm not the first person to think of this. One solution I found on the internet is called GeoMipMapping, which was developed by [email="whdeboer@iname.com"]Willem de Boer[/email] for the e-mersion project. It's much like ordinary texture mipmapping. Terrain patches are precompiled with different levels of detail. At rendering time the detail level rendered is based on the distance from the camera. It's a great idea but ill suited for my Raid3D demo. Using four GeoMipMap detail levels means precompiling the entire map four times, which uses a lot of precious memory. This is no problem with medium scale maps, but I wanted Raid3D to use huge maps. The very early beta on this site uses a 4 sq. kilometer map, which is rather small to medium sized in comparison to what I desire in the final release.
Putting Brute Force to the Test
I have put brute force to the test against a simple ROAM engine. I used [email="brturn@bellsouth.net"]Bryan Turner's[/email] ROAMsimple demo for this. Here's the technical info on the test:
Computer:
Pentium III 600 Mhz
128 Mb RAM
nVidia TNT2 32 Mb Video
800x600x32 resolution
Basis for comparison:
The detail level at the near clipping plane, defined as the size of the quad drawn between 4 adjecent points on the heightmap. This is the most interesting for game developers as it determines the quality of the scene. In both renderers I set the far clipping plane at 100.0f and increased the map size so it would fill in all directions beyond the far clipping plane.
The results:
I put the results in the graph below. The data is interpolated to find the crossing point which lies near the detail level of 2.0f. This means that if you need better detail than 2.0f you'd better use a CLOD engine. If you don't need this high a detail level, brute force can be a good alternative.
Of course this is by no means a correct scientific experiment but I think it gives a reasonably good representation of the two methods.
Evaluation
The graph above shows that, when the detail is equal or worse than 2.0f, brute force can be used. But there are other differences that should be taken into consideration. For example, brute force can render maps with less memory usage because no triangle lists are built every frame. Finding the exact (interpolated) height with brute force is easier than with CLOD. Maps can be bigger, and finally, brute force is easier to implement (which is very good for hobby coders like me). On the flip side, CLOD simply gives higher quality and more detailed levels, and 3D accelerators need to become much faster before brute force can do the same. In the end, the choice totally depends on the needs of your engine.
Conclusion
The power of 3D accelerator cards has increased so much over the last few years that, under the right conditions, old fashioned brute force terrain rendering can be faster than CLOD algorithms. The extra CPU overhead of reducing triangles can sometimes be higher than the speed increase that you get out of it. With current technology, brute force can become faster than CLOD when the size of the triangle quads rises above approximately 1/50th of the distance to the horizon, but this value will become smaller as technology advances.
Sander "Tweety" Mar?chal
Lone Wolves Production
[email="s.marechal@jejik.com"]s.marechal@jejik.com[/email]
