GPU Terrains

After 8 months of silence I’m back on this project.

Yesterday I’ve officially started to work on a paper about my research, I’ll post more detailed info soon.

At the end I’ve graduated with honours in computer science thanks to this GPGPU project.

Soon I’m going to post some charts and the presentation showed during my dissertation (I need to translate it in english).

Now I hope to continue this research project in my spare time, mostly I’d like to improve the terrain engine and implement some hydraulic erosion algorithm, so come back soon for new updates

I’ve registered for the final exam…

If nothing bad happens.. I should get the F degree on June the 17th.

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.

This week I’ve started to write the thesis document, so in the next weeks I’ll be more busy with writing than with something else.

I hope to continue the research in my spare time, and to continue it after I’ll get my degree too, anyway every other news about the project will be posted on this blog.