Introduction

There are many ways of generating terrain. Some use a simple randomise-and-smooth technique [1], whereas others use more complex techniques that use fractal methods to achieve realistic terrain [2, 3, 4]. While each individual method has its own advantages, it can be hard to control just how "bumpy" the terrain is.

In this article, I propose a new method of terrain heightmap generation that uses an iterative process, treating the heightmap as a highly viscous and rubbery fluid. The parameters to the fluid simulation equation enable the quality and quantity of features in the generated heightmap to be varied as desired.

Fluid Simulation

Before I explain the process of generating a satisfactory heightmap, it will be helpful to the reader to know about methods of fluid simulation, as it is one of these methods that is behind the algorithm.

Simulating fluids is a very CPU-intensive operation. The more accurate and boundless you want the simulation to be, the more CPU power that is required. Some methods use a fast Fourier transform to achieve believable results [5], whereas others extend equations for tensioned strings into 3D [6, 7].

To keep the algorithm relatively simple and fast to compute, I have chosen to use the method described in [7]. After extending tensioned strings into 3D and computing partial derivatives, the method gives the following equation for the height of the point i, j, at frame k:

c is the speed at which waves travel across the surface, t is the constant time-step between each iteration, d is the distance between each node of the surface and μ is the viscosity of the fluid. Note that this method uses the previous two time-steps, not just one, to compute the next one, although only one point is sampled from the time-step k-1.

Generating a Heightmap

To actually generate the heightmap, the process is fairly simple. Roughly, the steps are:

• Pick constants c, μ, d and t
• Fill heightmap with random values between two boundaries
• Iterate fluid simulation equation over the heightmap as many times as desired
• Normalise heightmap values to bring them into the range [0...1].
• Multiply heightmap values by 255 and output as greyscale image.

Let us examine the stages in detail.

Pick constants c, μ, d and t

This is simply a case of trial and error. It is important that the fluid is very viscous for the method to work; values that I have found to produce satisfactory results are:

• c = 100
• d = 10
• t = 0.033
• μ = 100

Fill heightmap with random values between two boundaries

First, pick two upper and lower boundaries for the height values - -500 to 500 are values that produce satisfactory results. Then, fill a floating-point heightmap (array of floats, width * height in size) with random numbers between those two values. Note that you should not initialise the edges to random numbers - they should be left at zero.

Iterate fluid simulation equation over the heightmap as many times as desired

The fluid simulation equation given in the previous section should be used to generate new heights for each point in the heightmap. This operation should be repeated as many times as desired - the more iterations done, the fewer features (hills, etc.) the terrain will have, and the smoother it will be. Note that again, the edges of the heightmap should not be iterated through the equation, as they do not have neighbours on all sides.

Normalise heightmap values to bring them into the range [0...1]

Iterate through each value in the heightmap, finding the minimum and maximum values. Then, for each value in the heightmap:

This brings each value between 0 and 1.

Multiply heightmap values by 255 and output as greyscale image

To generate a traditional heightmap image, where the highest points are white (255) and the lowest are black (0), multiply each value in the heightmap by 255 before outputting to a file, array or other output medium as a greyscale image.

Here are some examples of heightmaps generated using the algorithm. The parameters are those specified in the step-by-step description unless otherwise stated.

Standard parameters

μ = 50

c = 50

Notice how lowering μ produces a smoother terrain, and how lowering c produces a terrain much like those generated with c=100 but with the features less well-defined (compare c=50, 1000 passes with the standard parameters, 100 passes heightmap).

If you wish to try the method out yourself, then take a look at the sample application (and source) included with this article. The application takes various parameters and outputs the heightmap to your specification as a simple raw image file. The supplied source file shows how to implement the algorithm.

References
[1] Lecky-Thompson, Guy W., "Real-Time Realistic Terrain Generation," Game Programming Gems, pp. 484-498
[2] Shankel, Jason, "Fractal Terrain Generation - Fault Formation," Game Programming Gems, pp. 499-502
[3] Shankel, Jason, "Fractal Terrain Generation - Midpoint Displacement," Game Programming Gems, pp. 503-507
[4] Shankel, Jason, "Fractal Terrain Generation - Particle Deposition," Game Programming Gems, pp. 508-511
[5] Jensen, Lasse Staff and Robert Golias, "Deep-Water Animation and Rendering," Gamasutra.com GDCE Proceedings, http://www.gamasutra.com/gdce/2001/jensen/jensen_01.htm
[6] Gomez, Miguel, "Interactive Simulation of Water Surfaces," Game Programming Gems, pp. 187-194
[7] Lengyel, Eric, "Fluid Simulation," Mathematics for 3D Game Programming and Computer Graphics, pp. 328-342