Terrain Erosion

3DWorld's terrain generation looks pretty interesting with domain warp noise, but there's one thing that's missing: erosion. I already have erosion working for individual terrain chunks in ground/gameplay mode.  I'm using this erosion implementation from Ranmantaru Games which I've slightly modified to make it more efficient and configurable, and to make it work with a global water height value. The way this algorithm works is by placing one unit of water randomly on the map for each iteration, and computing the path that this water follows to a "sink". A "sink" can be an ocean, a local minima in the mesh, or the edge of the map. Material is removed from steep path segments and deposited when the path levels off, forming a series of peaks and valleys. Local minima eventually form lakes.

It currently takes 36ms to apply 5000 erosion iterations to a 128x128 vertex/texel heightmap. Here is an example of what this looks like. It's not too interesting, though this is proof that the system works.

Erosion on a single 128x128 vertex mesh tile.

This is fine for a single tile, but I want to be able to erode an infinite terrain consisting of an endless grid of tiles. I started working on erosion of large terrains as soon as I finished the previous blog post. My first attempt was to just apply the erosion algorithm independently to each terrain tile as it was generated, after the height values were assigned but before they were used for normals and object placement. Of course, this simple idea doesn't work. There are huge gaps between tiles where heights have been eroded to very different values. There are no constraints that force the edges of the tiles to line up. Take a look at the screenshot below.

Erosion applied independently to each tile produces terrible seams at the tile borders (erosion values are discontinuous).

The problem is that the water and sediment crossing each tile boundary isn't being tracked. Each tile starts out completely dry. There may be a large river valley in one tile that accumulates most of the water for the tile, but the adjacent tile doesn't see a single drop. The valley is deep in the first tile and nonexistent in the adjacent tile. When the river reaches the next tile, it basically stops flowing, and the sediment is lost.

One possible solution is to store data at the boundaries of each generated tile and use that as seed data for any adjacent tiles that are generated later. This has been suggested in a Reddit thread I started on the topic of Procedural Generation, but I haven't implemented it because I don't think this is an ideal solution. There are several problems. First, this only works when downstream tiles are generated after upstream tiles. If the downstream tile is generated first, there's no way to push the valley back up to the water source.

Second, the results will depend on the order in which tiles are created, which itself depends on the order in which tiles are visited by the player. The problem here is that if objects such as buildings are placed via editing operations on the terrain and saved, they may not be at the correct height later when the tile is approached from a different direction. If the user takes a longer route to the building, it may be floating in the air or buried under the ground. No, this isn't acceptable.

Another approach is to blend the heights between adjacent tiles to remove the gaps. While this is efficient and will produce seamless terrain, the results don't look realistic. River valleys may contain segments that go uphill. This is also unacceptable.

In the end, I decided that I only need erosion to work on island maps, at least for now. Islands are surrounded by water. Erosion stops at the water's edge, so there can be no underwater seams between tiles. All I have to do is clip the island out of the infinite world and generate the erosion solution for the entire heightmap mesh at once. I had to add two features to accomplish this: an option to write a terrain image file from the area visible in overhead map view, and an option to apply erosion to a terrain heightmap during import. This requires some extra steps, but the result is still fully procedural. While not infinite, it would be possible to automate this process for each island visited by the player. Below is an overhead map view of my selected island.

The island of interest. The island isn't exactly square, so some parts have been truncated and part of an adjacent island is visible in the upper left corner. The red dot is the current player position and the black dot shows player orientation.

I've taken a square clip of the terrain. The island itself isn't quite square; I've managed to clip off some small parts of it and included a bit of the adjacent island in the top left corner. This is close enough. The heightmap image will be tiled using mirroring to create a seamless terrain with no gaps between the edges of the image. When the player walks to the edge, the height values will be mirrored and repeat in another copy of the image. The resulting terrain is still infinite, but it repeats a finite amount of unique data. This solution may not work for fully infinite terrains, but it's close enough. The erosion results look just fine using this flow.

The island itself is pretty large. The square area I clipped out was 7085x7085 pixels, for around 49M pixels of data representing 7x7 km of data. This is 200MB of floating-point data, or 65MB when compressed to a 16-bit PNG image. Image writing time is 22s. The compression doesn't help much, so I may be better off using a raw BMP image format to reduce read/write times. However, I don't have any image viewers that can load a 16-bit BMP image of this size, which makes debugging difficult. Reducing bit depth from 16 bit to 8 bits loses too much resolution and makes the height values appear stairstepped like in Minecraft. That's not the look I'm going for. This image may see very large, but it's still a fraction of the size of the 16,384 x 16,384 Puget Sound dataset that has appeared in other blog posts such as this one.

I ran the erosion algorithm using OpenMP with 8 threads on 4 CPU cores including hyperthreading. Runtime was 18s for 10M iterations/samples. I just put an "omp parallel for" around the iterations loop. This implementation can suffer from thread race conditions, but I don't really care because there are so many random numbers used there anyway. This gives me a 5x runtime reduction. 18s is long compared to most of the other operations, but not unreasonable for a map of this size. It should be possible to save the post-eroded terrain back to an image for fast reloading at a later time.

Here is a zoomed in overhead map view of the upper right corner of the island, showing some rivers and lakes that have formed. This example uses domain warping for the noise calculation. I'm using a fixed water height here, which means those rivers and lakes have eroded down below sea level. In the future, I may want to have a way of generating higher altitude lakes where water collects. It's currently a rendering limitation related to water waves and reflections, not a generation limitation. This map looks fairly realistic to me.

Zoomed in view of the island's upper right corner showing small rivers and lakes that are a product of erosion.

Here are some screenshots showing erosion on large, smooth, rolling hills. I find that erosion results look cleaner and are easier to debug when domain warping is disabled. Sometimes it's hard to tell which valleys come from the procedural height generation algorithm and which ones come from erosion. The valleys form nice fractal patterns. Perhaps they're too narrow and deep? It would be nice to have the algorithm produce wider rivers/valleys for areas of higher water flow, which would make the results look more natural. Unfortunately, it's not clear how to extend the selected erosion algorithm to do this.

Erosion applied to a large rounded mountain, no trees. No domain warp has been enabled, so the mesh started out smooth.

Here is another view of eroded grassy cliffs at the edge of the ocean. Ambient occlusion really makes the canyons stand out. The erosion continues under the surface of the water. This is probably incorrect, so I better go fix it. ... This has been fixed in the other screenshots below. Does this look physically correct? It could be, compared to photos of Hawaii such as this and this and this and this, any of these, and other ocean cliff photos such as this.

Heavy erosion on the grassy cliffs near the ocean. Maybe too much erosion, especially under the water.

Here is how things look when enabling domain warping noise again. This image shows one end of the island with steep cliffs, some bays, and a few lakes. Trees have been disabled to make it easier to see the terrain itself, including the details of the narrow ravines. The small bits of greenery are other types of plants that are sparse enough that I left them enabled.

This very rugged terrain produced by domain warping noise has been eroded into many small valleys.

Here is a location along the coast that looks very much like Hawaii. The erosion algorithm now stops at the edge of the water to avoid eroding underwater features.

Another view of eroded domain warped terrain, near the ocean.

Here is an overhead view from a mile up showing a small mountain range and some thin lakes. Some areas between the peaks have been filled in with eroded sediment, producing smooth, flat areas.

Overhead terrain view showing some small lakes and small, sharp peaks that remain after erosion.

Erosion produces natural rivers, and lakes at the bottom of large watersheds. There are two lakes visible in the screenshot below. Each lake is fed by a network of short rivers, but the lakes are at local minima in the terrain and there is no place for the water to drain to. The area shown below is between some large mountain ranges and gets a lot of water.

Two small interior lakes with river networks formed from erosion. The water height is constant, so these lakes have been eroded down to ocean height.

I finally have real, physically modeled, procedural rivers. These rivers are a result of the erosion process, rather than accidents arising from the noise function values. Here is an example river surrounded by pine trees for a more natural effect. The trees are probably drawn too large for this terrain.

Finally, a real river that flows to the sea! Or maybe it's just a stream. Pine trees haven been added for a more natural look. No manual effort was made here, the results are purely procedural.

If I increase the number of erosion iterations by 20x from 10M to 200M, much of the terrain is eroded away. All but the tallest, sharpest peaks have been replaced by smoothly sloped hills. All the material in the mountains was turned into sediment and deposited throughout the scene. The lakes and bays become surrounded by deep canyons.

Erosion with 200M iterations rather than the usual 10M. The mountains have mostly eroded away into smooth sloping plains that eventually end in steep ravines and lakes.

Here is a final screenshot that includes a medium density forest of pine trees. All objects placed on the terrain by either an algorithm or a human should be at the correct heights with this approach.

Final terrain with pine trees, grass, and all effects enabled.

I'm pretty happy with the erosion results on this island. However, there are a few things I would like to improve as future work.

First, I think there are too many narrow valleys. I would like to see wider valleys in locations where the water flow is high. I'm not sure how to accomplish this in a clean, efficient, and stable way. It's not clear if the original erosion algorithm can easily be modified to get this effect. Maybe it can be accomplished with multiple passes over the terrain at increasingly larger grid resolution. I'm not sure if this would have too many grid artifacts or not.

Second, I don't like the manual effort involved in clipping out the island and tweaking parameters to make it work. The problem is that the clipping operation changes the min, max, and average height values, and this affects the biome distribution. The height ranges of the various terrain layers (sand, dirt, grass, rock, and snow) as well as water level are derived from the height histogram. This is estimated by taking a large number (~10K) of random height samples prior to generating any of the tiles. If I clip out part of the scene, it may not include the min or max values. For example, my clip might not contain the highest peak or the lowest part of the ocean floor. Texture layers and water level will be assigned differently when reading the heightmap image back in, which will change the look of the island. For example, it can create an island that's all snowy peaks and no water. To compensate for this, I need to experiment with various config file parameters using trial-and-error. I can have the heightmap clipping algorithm create a table with some constants such as real min and max heights, but there's still some manual iteration required. It should be possible to fix this, though it's a trade-off between a large upfront development cost vs. small amounts of manual work over time.