Posts In: heightmap

Selective Erosion of Heightmaps Using Density Maps

In an improvement on the original heightmap erosion algorithm, which (roughly) approximates fluvial erosion in terrains, I have incorporated a density map as an input to the erosion shader.  This is almost identical to the algorithm explained several months ago, though it seems to work far better and produces very interesting results.

Given a simple Perlin noise density maps, interesting effects can be achieved in the final, eroded terrain:

The left map represents the heightmap, whereas the right image represents the terrain density map.  It is easy to see that parts of the height map have been severely eroded; while other parts have stayed intact (white areas on the density map correspond to areas of high terrain density where erosion will have less of an effect).  The effect in this case seems rather unrealistic, since real terrains would not erode in such a non-uniform way.  The threshold values in the shader, however, can be used to control the degree to which the density map influences the erosion factor of the shader.

With more tweaking, I believe that this algorithm will be able to produce some very interesting features in terrains, as well as add a heterogeneous feel to them.

Multifractals: Great Success!

In a rather old textbook I read recently (Texturing and Modeling: A Procedural Approach; though note that I actually have the 1991 edition), the author mentioned briefly at the end of the book a type of fractal called the multifractal.  The idea of a multifractal is to actually vary the fractal dimension of the fractal at each point based on, guess what, another fractal map!  In a sense, it adds another level of recursion within the fractal.

So why should we care? Well, if perlin noise makes good terrains, multifractal perlin noise makes them 100x better!  The explanation for it is simple.  In real terrain, we see features like mountains, but we also see features like plains.  Mountains have a high fractal dimension, while plains have a low fractal dimension.  Perlin noise, in and of itself, has a relatively constant fractal dimension.  Multifractal noise doesn't.  For this reason, it serves much better for the purpose of generating terrains!

Here's a sample multifractal perlin noise heightmap generated with a home-brewed HLSL shader:

Notice that, in comparison to previous heightmaps, this terrain is far more varied - we can clearly see mountainous features as well as low features.

Perlin Noise Shader

I did it!!

After hours and hours of reading tutorials on HLSL coding, I finally managed to write a perlin noise shader. The result? Unbelievable speed. At least 100x faster than the CPU-based implementation I coded a few months ago. It can easily display a new 512 by 512 heightmap at 60 FPS. Yes, that's 60 unique heightmaps in one second.

With this kind of raw power now available to me for procedural content generation, I know that great things lie ahead in terms of my work with virtual worlds.

For reference (since I lost the old one and had to rewrite from scratch), here's the noise function I used:

float Noise2D(float x,float y)
float a = acos(cos(((x+SEED*9939.0134)*(x+546.1976)+1)/(y*(y+48.9995)+149.7913)) + sin(x+y/71.0013))/PI;
float b = sin(a*10000+SEED) + 1;
return b*.5;

An Original, Realistic Algorithm for Terrain Erosion

February 23, 2010 Algorithmic Art 0 Comments

Yes, another non-music digression. I can't stand not to write about this though, considering the fact that I've had a serious breakthrough today with a new algorithm.

Here's the problem: erosion algorithms tend to produce a sort of homogeneous soup of terrain without recreating some of the more true-to-life effects such as fractal coastlines and such.  The solution? A terrain density map.  As far as I know, this is a completely original algorithm.  I've seen nothing like it in the literature, so I'm quite excited about having invented it.  The initial test runs also produced exciting results!

Here's the basic concept: real terrains are not homogeneous.  Not all dirt is created equal. So, along with a 2-dimensional array representing the heightmap of a terrain, we should also create an equally-sized 2-dimensional array representing the density (or integrity, if the term is preferred) of the terrain at each given point. The density array can be filled with a low-octave perlin noise function (I found two to three octaves to give optimal results, with a persistence of between 1.5 and 2).

Now, we perform an erosion algorithm as usual, except that we use the density of the terrain at each point as the threshold value for erosion. That is, if the amount of potential erosion at a point is less than the density of the terrain at that point, then the point will resist erosion. Ideally, this algorithm erodes terrain in a more coherent, less uniform way than typical thermal erosion algorithms. For example, coasts display some fractal dimension now since some areas of the terrain erode more easily than others.

A sample heightmap using the new algorithm:

The difference is most notable around the rivers, where the coasts clearly display some fractal coherence absent in thermal erosion algorithms. Notice that "noise" of the coastlines is clearly more coherent than single-octave noise, thanks to the perlin-based density map.

I am still trying to work out how to make the features appear larger (that is, make the coast even more jagged), since the heightmap, although nice, isn't drastically different from previous ones. I am quite confident, however, that there's a lot of potential in this new density erosion algorithm. Who knows, maybe this will be the future choice algorithm for procedural terrain erosion!

Techniques for Heightmap Synthesis: II

February 14, 2010 Algorithmic Art 0 Comments

I have made a great deal of progress today in my work with virtual terrains!

In the last post I mentioned bucket fill algorithms and how they could contribute to realism by creating isocontours on the heightmap. I have successfully written and applied my own tolerance bucket fill algorithm. Unlike most such algorithms, however, my version actually preserves a set amount of the original surface variation, so as not to create a completely flat contour - which, of course, would be unrealistic.

I have also written a perlin noise generator to give variation to the heightmaps. Perlin noise is simply a linear combination of noise functions with varied frequencies and amplitudes. In practice, perlin noise generators often use a coherent noise function, such as a high-frequency sinusoid. I chose, however, to use only a simple rand() function. By mapping each point on the heightmap to a point on the (increasingly large) noise maps and performing 2-dimensional linear interpolation, one can achieve the desired effect without having to use trigonometric functions.

Now, using an additive combination of Brownian random deposition walks, bucket fills, perlin noise, and softening, I am able to create much more realistic terrains.

Below are a few sample heightmaps created with the aforementioned methods:

A quick summary of what's going on in these heightmaps:

  • Random deposition walks create long, winding rivers and mountain ranges
  • Bucket fills level out parts of the terrain to create isocontours, which give the appearance of defined features like plateaus
  • Perlin noise randomizes the space in between features with coherent noise
  • Softening passes remove rough spots created by deposition and bucket fills

Techniques for Heightmap Synthesis

February 13, 2010 Algorithmic Art 1 Comment

And now, for another deviation from algorithmic music.  As part of my research in building virtual worlds, I am exploring effective methods of creating interesting and detailed heightmaps for procedural terrain.

My earlier posts showed off some landscapes that were created using spectral synthesis and terrain deposition. I am now exploring methods that I hope will bring greater realism to the heightmaps. Having developed a set of algorithms that use Brownian motion (random walks) as well as certain erosion techniques to create features in the land, I began testing various heightmaps by walking over the resulting terrains.

Brownian random-walking deposition seems to create much more believable terrains than spectral synthesis or particle deposition alone.  Application of erosion and smoothing algorithms then reduces the sharpness of the terrains appropriately.

Below are a few of the heightmaps that were generated by my algorithms (note that the colors were chosen arbitrarily by the program):

All of the heightmaps were generated using custom-built random walk, erosion, and smoothing algorithms with varied parameters.  A "randomize" filter was then applied by a third-party texturing program, which helped create isocontours (plateaus, essentially) for added realism.  Though the filter is very nondescript, from what I can tell, it uses a technique much like a tolerance bucket-fill to "randomize" the image.  I will try to write my own version of this algorithm so that it can be applied automatically to the heightmaps.

While these heightmaps represent a great step forward in creating believable terrains (personally, I love number 4), they are still far from realistic.  Real land has far more intricacy and fractal dimension.  I will continue looking for new and better algorithms to create more realistic worlds.