Unfortunately, we don't have billions of years to spare on our computers. We want realistic-looking, eye-catching terrain

There are many different terrain generation algorithms winging their way around the world of computer graphics, some more complex than others, and each one with their own characteristic results. In this article, I'll explore some of the more popular ones (and show some nice little rendered pictures of them implemented) and explain just what makes them tick.

Let me firstly explain how terrains are represented. A landscape can be represented as a grid of points, each one with its own height. The grid is rigid (each point is the same distance from the other in the X and Z axes) and each point has a height (its position in the Y axis), giving a terrain. This grid is represented in what's called a heightmap - simply an image, where each pixel is one element of the grid (one vertex in the terrain). This is what gets generated by each algorithm.

So, without further ado, let's launch into the first algorithm:

To understand this algorithm, it's easier to take a 2D analogy first. Imagine that you have a line (figure 1). You then take the middle of that line and move it up or down by some random amount, giving you two lines at an angle to one another (figure 2). You then do this again to those two lines, giving you four lines (figure 3), then again, and so on. If you keep doing this, you end up with a varied view, containing valleys and hills. Figure 1 Figure 2 Figure 3

This is exactly how the algorithm operates, except on a 2D grid. You start off with one large square. You then split each side in half and raise/lower the midpoints by random values (or, rather, random values scaled down depending on how 'deep' the algorithm has gone - the more squares have been created, the smaller the amount will be, to preserve the features of the landscape generated at the coarser resolutions and give little details at finer resolutions). The midpoints are then connected up with new lines to split the original square into 4 squares. Those two new lines then have the same process applied to them. Then, the process repeats itself, except this time it happens on each of the 4 squares. This keeps happening until the desired resolution of heightmap is generated. And that's it. Pretty simple for a powerful and realistic algorithm.

You start off with a blank heightmap, every height value at 0. Now, strike a random line across the landscape and raise the terrain on a random side of that line by an amount (figure 4). Keep doing that a number of times, decreasing the amount you add to the heightmap each time (the more you do it, the more detailed and less 'jagged' the terrain will be) (figure 5). Then, a smoothing/blurring filter should be applied (unless you specifically want the jagged effect) such as a FIR filter or a gaussian blur, giving the final result (figure 6). Figure 4 Figure 5 Figure 6

To create a Perlin noise-generated heightmap, you need to add together lots of different heightmaps, some very coarse, some fine, some very fine. The coarsest ones define the basic shape of the landscape, whilst the finest ones define the small details. I won't go into detail with this algorithm, as it can be quite complex, but I'll give a basic overview of how the different heightmaps are constructed.

Basically, at each level, random 'noise' is generated - random numbers are assigned. The coarser the heightmap is, the less numbers are assigned, and the bigger areas that have the same number assigned - the coarsest level would be simply 4 patches, each at a different level. Then, the different numbers are interpolated between using a special interpolation function to get a smooth change from one to the other. This is done at each level, then the resultant heightmaps are all added together to generate the end result.

A much more in-depth and accurate description, with examples, of Perlin noise is available here (Link: m_perlin.htm) .

You must log in to post a comment. You can login or register a new account.