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

I’ve done new benchmarks to test how the latest optimizations have improved the performance of the generation shaders.

All the benchmarks are made using a 1024×1024 16-bits floating points texture.

I’ve run the benchmarks on my graphic card, a GeForce 7600 GT, and on the graphic card of my friend Encelo, a GeForce 8600 GT.

The following data are the execution times needed to complete a different number of iterations of the generation phase, for each group of iterations you can see the slowest, the average and the fastest time on 10 tests.

Fault formation

These are the results for the 7600 GT:

iterations = 250 -> min = 271 ms. - avg = 273 ms. - max = 276 ms.

iterations = 500 -> min = 543 ms. - avg = 545 ms. - max = 548 ms.

iterations = 1000 -> min = 1089 ms. - avg = 1090 ms. - max = 1093 ms.

iterations = 2000 -> min = 2179 ms. - avg = 2180 ms. - max = 2183 ms.

The optimized shader is about 12% faster than the previous version.

These are the results for the 8600 GT:

iterations = 250 -> min = 235 ms. - avg = 237 ms. - max = 239 ms.

iterations = 500 -> min = 471 ms. - avg = 473 ms. - max = 477 ms.

iterations = 1000 -> min = 942 ms. - avg = 945 ms. - max = 951 ms.

iterations = 2000 -> min = 1883 ms. - avg = 1885 ms. - max = 1889 ms.

The shader is about 14% faster on this graphic card.

Circles

These are the results for the 7600 GT:

iterations = 250 -> min = 338 ms. - avg = 340 ms. - max = 243 ms.

iterations = 500 -> min = 676 ms. - avg = 678 ms. - max = 682 ms.

iterations = 1000 -> min = 1355 ms. - avg = 1356 ms. - max = 1359 ms.

iterations = 2000 -> min = 2710 ms. - avg = 2712 ms. - max = 2715 ms.

The optimized shader is about 1% faster than the previous version.

These are the results for the 8600 GT:

iterations = 250 -> min = 238 ms. - avg = 239 ms. - max = 242 ms.

iterations = 500 -> min = 475 ms. - avg = 477 ms. - max = 481 ms.

iterations = 1000 -> min = 951 ms. - avg = 952 ms. - max = 955 ms.

iterations = 2000 -> min = 1900 ms. - avg = 1902 ms. - max = 1906 ms.

The shader is about 30% faster on this graphic card.

Perlin Noise

These are the results for the 7600 GT:

octaves = 2 -> min = 31 ms. - avg = 32 ms. - max = 32 ms.

octaves = 4 -> min = 61 ms. - avg = 62 ms. - max = 63 ms.

octaves = 6 -> min = 92 ms. - avg = 92 ms. - max = 93 ms.

octaves = 8 -> min = 121 ms. - avg = 122 ms. - max = 123 ms.

The optimized shader is about 61% faster than the previous version.

These are the results for the 8600 GT:

octaves = 2 -> min = 12 ms. - avg = 13 ms. - max = 13 ms.

octaves = 4 -> min = 23 ms. - avg = 24 ms. - max = 24 ms.

octaves = 6 -> min = 36 ms. - avg = 36 ms. - max = 36 ms.

octaves = 8 -> min = 47 ms. - avg = 48 ms. - max = 49 ms.

The shader is about 60% faster on this graphic card.

Introduction

I’ve made several 3D renderings with Blender to show how my new thermal erosion algorithm affects real terrains.

In order to appreciate the effects of the erosion, I suggest to open the images of each group in different tabs and view them in sequence, enjoy!

Fault formation

The following image shows how the original map (top-left square), generated by 1500 iterations of the fault formation algorithm, is modified by 25, 50 and 100 iterations of thermal erosion:

These are the 3D renderings from the SOUTH-EAST view:

As it’s possible to notice, the erosion algorithm changes the “block of rocks” in a mountain chain.

Circles

The following image shows how the original map (top-left square), generated by 1000 iterations of the circles algorithm, is modified by 25, 50 and 100 iterations of thermal erosion:

These are the 3D renderings from the NORTH-WEST view:

Terrains generated by the circles algorithm are usually smoother than terrains generated by another algorithm, so the new erosion algorithm modifies less the shapes, anyway 100 iterations give the same a good result.

Perlin Noise

The following image shows how the original map (top-left square), generated by the Perlin Noise algorithm (6 octaves), is modified by 25, 50 and 100 steps of thermal erosion:

These are the 3D renderings from the SOUTH-EAST view:

As in previous images, more iterations means a lower terrain.

Introduction

Thanks to my friend Encelo and to some online tutorials, I’ve made my first animations with Blender.

The animations are quite simple, the only object moving around is the camera that rotates around the 3D scene, I’m planning to do some more interesting animations, but these are the first ones and I like them enjoy!

Fault Formation

The terrain has been generated by 1500 iterations of Fault Formation algorithm and eroded by 100 iterations of my thermal erosion algorithm using the default parameters: T = 0.005, c = 0.5

The video is available on:

• vimeo
• youtube

Circles

The terrain has been generated by 1000 iterations of Circles Algorithm setting r = 100 and eroded by 100 iterations of my thermal erosion algorithm using the following parameters: T = 0.005, c = 0.25

The video is available on:

• vimeo
• youtube

Perlin Noise

the terrain has been generated by a Perlin Noise made summing 6 octaves and eroded by 100 iterations of my thermal erosion algorithm using the following parameters: T = 0.0025, c = 0.25

The video is available on:

• vimeo
• youtube

Introduction

I’ve started a study about how the various algorithms are affected by their parameters.

In these days I’ve made hundreds of 3D renderings to have a visual feedback of the results, these latest renderings are much better than the previous ones because I’ve improved a little bit my knowledge of Blender thanks to some guys from Blenderartists forum and some experiments, I hope you’re going to enjoy the following images.

All the maps are generated using a 1024×1024 16-bits texture.

Generation

The fault formation algorithm doesn’t have significant parameters to control the generation, so I’ve generated a terrain using 1000, 1250, 1500 and 1750 iterations just to check if there’s some connection among the results.

All the terrains are the result of the generation followed by 5 iterations of blur (blur radius 10.0) .

The following images are the views from SOUTH-EAST, SOUTH-WEST, NORTH-EAST and NORTH-WEST:

As it’s possible to notice from these images there’s not a real connection among the generations, so varying the iterations gives just different visual results.

Blur vs No-Blur

The first question I’ve asked to myself is what happens eroding a terrain not blurred, the following images are the answer to that question:

the left part of the images is the result of 100 iterations of my thermal erosion on a blurred map, the right part is the result of the erosion on a not-blurred map. As it’s possible to notice the images are not so different, but the blurred map gives more smooth terrains, while the not-blurred one gives terrains more “wavy”.

I think the blurred map gives a better visual result, so I’m going to use blurred maps for all the following tests.

Erosion

After the first test I’ve started to study how the parameters of my thermal erosion algorithm affect the map, all the following terrains are generated by 1500 iterations and eroded by 100 iterations of my thermal erosion algorithm.

The first test is about the T parameter, the values of the following images follow this schema:

|  T = 0.01    |  T = 0.0075  |

|  T = 0.005   |  T = 0.0025  |

As for the generation section, these are the views from SOUTH-EAST, SOUTH-WEST, NORTH-EAST and NORTH-WEST:

The images suggest that a bigger value of T (0.01) gives smaller changes, while a smaller value (0.0025) gives bigger changes and a very smooth terrain.

The second parameter tested is c, the values of the following images follow this schema:

|  c = 0.25  |  c = 0.50  |

|  c = 0.75  |  c = 1.00  |

As it’s possible to notice the c parameter doesn’t offer much control over the erosion results, even if a smaller value (0.25) gives more erosion than a big value (1.0).

Finally I’ve tested what happens varying the two parameters in the same time, the following images follow this schema:

| T = 0.0075 - c = 0.25  |  T =  0.0075 - c = 1.0  |

| T = 0.0025 - c = 0.25  |  T =  0.0025 - c = 1.0  |

As showed in the previous group of images the parameter c doesn’t affect much the result, the parameter T gives much more changes in the terrain appearance.