GPU Terrains

Introduction

I’ve improved the Fault Formation algorithm further.

Now I can obtain a more detailed heightmap with half iterations, this is a huge improvement for performances and quality!

The problem

The original algorithm says that, for each generated random line, one side of the map has to be raised adding some value and the other side has to remain unchanged.

This algorithm gives not so good results with big maps, look at the following image to understand what I mean:

the heightmap in the left panel shows a terrain generated by 1000 iterations of the original algorithm, as it’s possible to notice there are too much mountains and too few plains. The blur (right panel) doesn’t fix this problem.

In order to improve the variedness of the terrain I changed the algorithm subtracting the same value that is added to one side of the map to the other side. This didn’t sort the problem out, so I tried to clamp the height values inside the shader to the range [0.0 - 1.0]. Clamping the values improved the generation a bit, but it gave more coarse maps, like showed in the following image:

The left panel shows a terrain generated by 1000 iterations of the modified algorithm with clamping. It’s easily possible to see the lines that determine the terrain, also in the blurred version (right panel).

In order to give more detailed heightmaps the modified algorithm requires about 50% more of iterations (so 1500).

Another problem inherited by the original algorithm is the almost totally lack of control on the generated terrain.

The new algorithm

The new algorithm I’ve developed fixes all the described problems and it’s really simple, the only difference with the original one is that now I subtract a different value to the other side of the map, this value is just the value added to the other side multiplied by a constant in the range [0.0 - 1.0].

So the code that modifies the map now is something like this:

if(fragment is on the left side)
	h += inc;
else
	h -= (inc * dec_mult);

The new algorithm gives more detailed maps using less iterations and allows to control the results varying the dec_mult value as showed in the following image:

The top-left panel shows a map generated by 1000 iterations of the new algorithm setting dec_mult = 0.1, the top-right panel shows the blurred version. The bottom-left panel shows the same map setting dec_mult = 0.01, the blurred version is on the right.

Of course setting dec_mult = 0.0 gives the same results as the original algorithm.

The new algorithm sometimes generate some weird results using some values of dec_mult, an example is showed in the left panel of the following image:

but this problem can be easily solved using a fixed value to add/subtract to the heights (in the original algorithm the added value is decreased with each iteration), obtaining so a standard map as showed in the right panel of the previous image.

Now the algorithm requires a normalization phase after the generation, but the normalization takes a short time and so the new algorithm can be considered faster than the previous version because it generates more detailed maps using half the iterations. A normalization phase takes about 70 ms. for a 1024×1024 heightmap, instead 500 iterations take about 500 ms. so it’s definitely faster!

UPDATE 19/04/2008

I’ve found the original paper about the Fault Formation algorithm, the author says to change the values on both sides of the map after a line is drawn. So my implementation follows the original algorithm!

I’m wondering why Jason Shankel (author of a chapter about the FF in Game Programming Gems 1) describes the “different” algorithm with just the raising operation. Maybe for a performance issue.

Introduction

My first thermal erosion algorithm has a lot of good features, and it’s faster than other ones, but I’m not totally satisfied by the timing performance, so I’ve developed a new thermal erosion algorithm that aims to be as fast as possible and to give good visual results as my first one.

Some technical info

In order to have a shorter execution time I’ve abandoned the reversed structure based on two phases of the previous implementations.

Now all the fragments can compute how much terrain has to go out and how much terrain has to come in without any data computed by the neighborhoods, this allows to reduce the execution times more than 50% (because the first phase disappear), as I’m going to show in the next benchmarks post.

Of course the new model is more empirical than my first one, and requires some assumptions that can give results that are less realistic, from a simulation point of view, but the results are good enough from the visual view, so this algorithm is a good compromise between performance and realism.

Erosion in action

As my first algorithm, also the new one continue the erosion for any number of iterations:

The previous group of images shows the same terrain eroded by 100, 200, 400 and 800 iterations. More iterations means a smoother and lower (on average) terrain.

The next image shows how the new algorithm erodes a (blurred) cube of rock:

The top left panel is the result of 50 iterations, the following ones (in clockwise) are the result of 100, 200 and 400 iterations. As it’s possible to notice, the new algorithm gives results similar to ones obtained by the first and third algorithms, but the eroded terrain is smoother like the one eroded by the second algorithm.

The new algorithm has just one parameter, c, that affects the level of erosion of the algorithm, as showed in the following image:

A lower value of c (0.25 in the top left panel) means more erosion, so a lower terrain, instead a bigger value (1.0 in the bottom right panel) means less erosion and an higher terrain.

Finally I want to compare the result of the erosion of my two algorithms:

On the left (bottom and top panels) there’s the same image of a terrain eroded by 100 iterations of my first algorithm, on the right there’s the terrain eroded by 50 iterations (top panel) and by 100 iterations (bottom panel).

I’ve compared a terrain eroded by 100 iterations with a terrain eroded by the half of iterations because I think they are more similar (on average height) than the two terrains eroded by 100 iterations and this is a good thing because that means I can get results similar to the ones I can get from the first algorithm using half the iterations, so shortening the times any more.

Introduction

I’ve developed a thermal erosion algorithm from scratch, reusing some ideas from the two previous algorithm I’ve implemented and mixing them with some ideas I had working on this project.

A new algorithm is born

I’ve developed a new algorithm because I was not totally satisfied by the visual results of the first two algorithms I’ve implemented, in order to understand what I mean, look at the following image:

This is the result of 200 iterations of the first thermal erosion algorithm on a (blurred) cube of rock, does this look realistic? Is it possible to see a side of a mountain so smooth in nature? I guess no!

The second algorithm gave worse visual results, even if i’s faster than the first one.

So I’ve decided to develop a new algorithm.

Some technical info

In my algorithm I’ve kept the reversed structure used for the other algorithms, so also my algorithm is based on two phases on each step, but my algorithm doesn’t compute the minimum or maximum difference among heights as the other algorithms do, so it’s faster (about 7-10% compared to the first one).

My algorithm uses the talus angle “T” and the “c” constant as they are used in the first algorithm, but I’ve introduced another value “F“, called erosion Factor, that allows me to do some funny things, as I’m going to show you later.

Furthermore it needs just 3 components of a fragment (as the second algorithm), so I guess it’s possible to make it faster using RGB textures instead of RGBA ones that are required by the first algorithm.

New features and differences with other algorithms

The first important feature is that I can generate terrains that are really similar to ones eroded by the first algorithm, look at this image for an example:

The first pyramid has been obtained by 200 iterations of the first erosion algorithm, the second pyramid has been obtained by 200 iterations of my algorithm, it’s really similar to the first one, instead, the last pyramid, has been obtained by 250 iterations of my algorithm, it’s almost the same of the first one.

Another important feature is that the first erosion algorithm can alter the terrain just for a limited number of iterations (about 300), instead my algorithm continue to level the terrain for thousands of iterations as it’s possible to notice in the following image:

The first two squares (from the top) are the results of 200 and 1000 iterations of the first erosion algorithm, while the other two squares are the results of 200 and 1000 iterations of my algorithm.

But the most important feature is that I can obtain different eroded terrains just varying the new parameter F as showed in the following image:

These pyramids are the results of 200 iterations of my erosion algorithm on a cube of rock (not blurred this time), they differ just for the F value (it’s doubled each time) and they look much more realistic, in my opinion!

What does this mean in practice? Here an example:

Changing the T and c values I can obtain just two different kind of eroded terrains using the first algorithm

These two images are the results of 200 iterations of erosion, the first one is based on the values: T = 0.005 - c= 0.5, while the second one on the values: T = 0.003 - C = 0.1, so just two different kind of eroded terrains and they are not so different!

Instead my algorithm can obtain different terrains just varying the F parameter, furthermore it can generate terrains that are quite different changing the other parameters, look at these images:

The first group of images is obtained using the default values for T and c (T = 0.005 and c = 0.05), but varying the F value from 1 to 8 (doubling the value each time), instead the second group of images is generated using the values T = 0.003 - c = 0.1 and varying the F value as in the first group. Visual results are much better than the first algorithm, aren’t they?

For all these reasons I think that my algorithm is better than the other ones I’ve implemented.

Introduction

I’ve developed another thermal erosion algorithm originally proposed by Benes, Marak, Simek and Slavik using a fragment shader.

Also this time I’ve used the reversed approach showed in the first erosion algorithm.

The original algorithm

The algorithm is executed examining each cell of the map and its 8 neighbours according to a Moore scheme like showed in the following picture:

For each neighbour it’s computed the difference between the processed cell and the neighbour:

d[i] = h - h[i];

the minimum positive difference is stored in d_min, and the sum of all the positive differences (this number is n) is stored in d_tot.

Now it’s possible to update all the n cells (where d[i] is bigger than 0.0) using this formula:

h[i] = h[i] + h_out * (d[i] / d_tot);

where h_out is the amount of material redistributed from the central cell (h) to its neighbours, this value is computed by the following formula:

h_out =  n * d_min / (n + 1.0);

so the central cell is updated removing h_out from its height:

h = h - h_out;

My reversed version

My implementation uses two phases to perform the erosion as in the previous algorithm:

in the first phase the shader inspects all the neighbours according to the Moore scheme so to compute d_min, d_tot and n, then, using these values, it computes the amount of material to redistribute h_out. Finally, the values: h, h_out and d_tot are stored in the first three components of the fragment (R, G, B) so to be used in the second phase.

the second phase (another execution of the shader) uses the values stored in all the neighbours to compute how much material has to be moved to the current fragment using the formula:

h_in = h_in + h_out[i] * d[i] / d_tot[i]);

Finally the height is updated summing the two values to the original one:

h = h + h_in - h_out;

A graphical example

The following image shows the erosion performed on a cube of rock, the 4 squares are the results of 50, 100, 150 and 200 steps of erosion:

As it’s possible to notice, this thermal erosion is less effective then the first one, it acts more like a blur.

Introduction

I’ve developed the thermal erosion algorithm originally proposed by Musgrave, Kolb and Mace using a fragment shader.

I’ve altered the algorithm in order to get over the limits of the shaders, in fact a fragment shader can’t scatter data, it can just gather (a shader can read all the fragments, but it can write just the current one).

The original algorithm

The algorithm is executed examining each cell of the map and its 8 neighbours according to a Moore scheme like showed in the following picture:

For each neighbour it’s computed the difference between the processed cell and the neighbour:

d[i] = h - h[i];

the maximum positive difference is stored in d_max, and the sum of all the positive differences that are bigger than T (this numer is n), the talus angle, is stored in d_tot.

Now it’s possible to update all the n cells (where d[i] is bigger than T) using this formula:

h[i] = h[i] + c * (d_max - T)  * (d[i] / d_tot);

and the main cell with this other formula:

h = h - (d_max - (n * d_max * T / d_tot));

The Talus angle T is a threshold that determines which slopes are affected by the erosion, instead the c constant determines how much material is eroded.

My reversed version

As I’ve mentioned in the introduction I can’t implement the original algorithm with a fragment shader because it can’t update the neighbour fragments.

My implementation uses two phases to perform the erosion:

in the first phase the shader inspects all the neighbours according to the Moore scheme so to compute d_max, d_tot and n, then these values are stored in the last three component (G, B, A) of the texel, instead the first one (R) stores the height value.

the second phase (another execution of the shader) uses the values stored in all the neighbours to compute how much material has to be moved to the current fragment using the formula:

h_in = h_in + (c * (d_max[i] - T) * d[i] / d_tot[i]);

then it’s computed how much material should be removed from the current fragment using this formula:

if(n > 0)
	h_out = d_max - (n * d_max / d_tot * T);
else
	h_out = 0.0;

Finally the height is updated summing the two values to the original one:

h = h + h_in - h_out;

A graphical example

The following image shows the erosion performed on a cube of rock, the 4 squares are the result of 50, 100, 150 and 200 steps of erosion:

I’ve got this result setting T=0.005 and c=0.5 .

Useful resources

• Jacob Olsen, Realtime procedural terrain generation