The second life for brute force terrain mapping

By Sander Marechal
Originally posted June 20, 2002

Overview

I have written this article for hobby programmers like myself but it can be interesting for any programmer involved in terrain mapping out there. I don't consider myself to be an excellent programmer. It could very well be that to guru programmers out there, my opinion about terrain mapping is utterly ridiculous but 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" at a random search engine on the net, you'll get a huge amount of hits. All about terrain mapping and all about making it faster and better looking. The last few year computers have become increasingly fast and terrain mapping is one of the fields that benefit greatly from it. If you sift through all the info you can see that there are basically 2 types of rendering terrain.

• Pre-build terrain: Which is used in games like Unreal and other action games. With this type of terrain, it it usually pre-build 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 sort are no problem. Just build some brushes and poly's and there they are.

Heightmap terrain: This type of 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 generating has benefitted the most from increased computer capacity in recent years. The only real drawback of this type is that the terrain is in effect flat 2D. So therefor 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.

Example of a heightmap

My focus is purely on the second type of terrain. 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 called Brute Force. 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 was extremely slow. In order to fix the speed problem new algorithms were invented like 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, etc, etc, 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 therefor faster while the quality is still high (maximum error of 3 pixels).

Comparing BF with CLOD

There are two main differences between BF 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. BF always displays the same set of triangles and can therefor precompile all the triangles of the terrain on the 3D accelerator (DisplayLists in OpenGL). On 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 BF and CLOD use triangles to display terrain. Both algorithms can handle approximately the same amounts of triangles. BF slightly more because they are precompiled on the 3D card. CLOD however uses more triangles in the area's up close to the camera and less near the horizon. BF uses the same amount everywhere, independent of the camera's position. Therefor BF cannot display the same quality landscape as CLOD although both landscapes are made up of the same amount of triangles.

High speed Brute Force

Computer capacity has increased greatly over the last couple of years. 3D accelerators can process huge amounts of polygons per second. Because of this BF 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 BF is not a real option, but in some cases BF 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 bypass 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 Rai3D'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: BF cannot handle very far clipping distances. The amount 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 BF this can be 8 times 256 triangles makes 2048 extra triangles. For CLOD this would be 8 times 8 is 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 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 on before. In this view, good candidates for BF 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 therefor ill suited for BF. 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. BF is therefor 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 BF a poor candidate for Outdoor First Person Shooters where you want lots of detail, but still suitable for strategy and god games.

3D hardware: BF 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 BF on. I haven't had the opportunity to test with higher end cards like GeForce 4 but BF should do better on those.

Frustum culling: Finally BF 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 BF this can be as much as 256. Therefor CLOD benefits the most from high speed culling, sacrificing some accuracy. BF really needs high accuracy to cull away as much 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 Willem de Boer for the e-mersion project. It's much like ordinary texture mipmapping. Terrain patches are precompiled with different levels of detail. On 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 Bryan Turner's ROAMsimple demo for this. You can find it at his web site at http://www.fractalscape.org 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 adjacent 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 well 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 build every frame. Finding the exact (interpolated) height on BF is easier than in CLOD. Maps can be bigger and finally: Brute Force is easier to implement (very good for hobby coders like me). On the flip side, CLOD simply gives higher quality and detail levels, and 3D accelerators need to become much faster before BF can do the same. In the end, the choice totally depends on your needs for the engine.

Conclusion

Computing 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, BF can become faster than CLOD when the size of the triangle quads rise above approximately 1/50th of the distance to the horizon, but this value will become smaller as technology advances.

References

ROAM simple demo by Bryan Turner, http://www.fractalscape.org
GeoMipmapping paper by Willem de Boer