Sunday, March 5, 2017

Super-simple fractal terrain generator

Here's a very simple algorithm for generating random terrains: Start with a equilateral triangle in the x-y plane. Add a uniformly and symmetrically distributed random z-offset to each vertex. Bisect each resulting edge and add a random z-offset at the newly added point, half of the magnitude of the random offsets earlier. Repeat several times.

The algorithm is no doubt known, but some quick searches for terrain generation algorithms didn't turn it up, so I am posting for people's convenience.

There are some artifacts at internal triangle boundaries that better algorithms presumably don't have, but the algorithm is super simple to implement, and because it is based on triangles it directly makes a triangular mesh. Here is some code which does this, starting with a hexagon divided into six equilateral triangles, and putting out an STL file.


3 comments:

Alexander R Pruss said...

Some of the grid artifacts are reduced by averaging in the values from the opposite vertices in the triangles that meet in the edge being bisected in the case of interior edges. The code has been revised to do that, with an adjustable weight.

Alexander R Pruss said...

But of course the algorithm isn't so simple any more...

Alexander R Pruss said...

The base algorithm is known as midpoint-displacement, though I've only seen 1D versions online.