Fractal Coastlines

Perlin noise is a really simple way to create contiguous regions with a contour that is both smooth and rugged at the same time. However, it is far from perfect. One problem is that Perlin noise has the same rate of change at all areas. Another, that Perlin noise on large scales is dissimilar to Perlin noise on small scales.

A fractal method for generating regions solves both these problems.

Here we see a very intricate coastline that, if you ask me, actually looks pretty natural. Overall, the algorithm is pretty simple and could easily be changed for further control of what parts of the coastline are more rugged and which are smoother.

But with this above example, it still is not very clear how the coastline is generated. Basically, you start off with a simple shape, like a triangle, and then you repeatedly double the amount of edges. This is done by bifurcating every line, then displacing the new midpoint. Or, with an animation:

The way that the coast is folded - that is, the midpoints displaced - is the same with the first iteration as the last iteration. The only thing that changes is the magnitude of displacement. One thing is to be noted - the magnitude is not dependent on the length of the line segment, but rather on the overall step. This means that short line segments are folded proportionally more than long line segments in the same iteration.

The reason this is important is that the coastline is not folded at the true midpoint of each line segment. Rather, a point between 1/4 and 3/4 of the way between the two points is picked. This is what leads to some areas having higher density of folding than others, creating the fractally nature.

What does fractal mean in this case? Well, long story short, that no matter how far we zoom in, there are still more details.

And if that isn't detailed enough, all I need to do is to let the algorithm run for a few more iterations. Infinite detail.

A question that comes up is how much control one should hand over to the fractal folding. The algorithm seems to work quite well as long as you can accept not really having much control over the process at all. Feed it a triangle, it'll make an island that isn't triangular at all. If you're okay with this spontanous creation of geographic features, this might be a better approach than Perlin.

Above is an example of trying to control the shape of the landmass. To the left is a low-poly model of the island of Great Britain, and to the right, the output of the fractal folding. There is a pretty good similarity, to be honest, and the low-poly nature of the input is not apparent at all. Of course, it isn't GB, and especially the Scottish highlands part is quite poor.

The reason the coastline keeps its shape is that the control points are not moved at all during the folding algorithm. This holds true for all iterations, too. Each iteration, the amount of points are doubled, but only the new points are ever moved. Not only does this grant a certain control over the shape of the terrain, it could also be used by cleverer people than I to do LOD loading with some massive landmasses.


Comparison to Perlin terrain

While Perlin noise is great for filling out shapes but is more difficult to use for describing contours, the coastline approach here is the opposite. The land is a list of points that define its contour. Its inside area has to be found post-hoc by a li'l function that counts the amount of line segments to the right of a given point - if the number is odd, the point is inside the polygon, if the number is even, outside. It's not terribly difficult, but it does take some computational ressources.

The biggest benefit of fractal coastlines is their incredibly high amount of detail, that tends to look quite natural, mostly independent of scale. However, Perlin noise doubles as an easy way to describe terrain height, which is an approximation of distance to the coastline. For the fractal coastlines, a more accureate distance can be found using some trigonometry, which might honestly be faster than with Perlin - though again, it will take its own script.

Also, Perlin noise easily creates several islands. Here, they each would have to be a completely seperate data-structure, and attention to be made to ensure they would not overlap. Really, the whole thing with overlapping is a problem I have not quite been able to solve. See the points where the coastline overlaps itself. Oops.

I really want to work more on this approach since it creates such realistic-looking coastlines, but it is just so foreign to me to work with polygons instead of region-grids. Let's see if something won't come of this in the new year.

Anyway, code and demonstration can be found on OpenProcessing. Also, credit has to be given to the Dragons Abound guy for the idea of a different sort of fractal coastline, inspiring this.