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.

Current State of Terrain Generation

I haven't done any major work on terrain or vegetation lately, but I'm constantly tweaking parameters and fixing minor problems. This post shows screenshots and a video of the current state of tiled terrain mode. The technical details have been mostly covered in previous blog posts, so I won't repeat them all here. Feel free to review some of my earlier posts if you're interested.

I've settled on Simplex noise with domain warping as the primary source of noise for procedural terrain height generation. The noise functions are all user configurable from a text config file in case I want to revisit them later. Take a look at my post from May 2017 for more information. Once the terrain is generated, trees, grass, and other scenery objects are placed on the landscape. The type and distribution of objects depends on terrain height/altitude and slope. These first three screenshots show how the noise algorithm can generate realistic looking rivers and lakes using a parallel algorithm where all height values are computed independently. Note that I'm using a 2D sine function here to form a grid of unique islands within an infinite ocean. This is why the terrain is often bordered by water. There's no technical reason why I have to use islands; the generation and rendering system works fine with an infinite forest. I just like the look and feel of islands.

Procedurally generated terrain with sandy lake surrounded by grass, plants, and trees.

Rivers aren't explicitly generated or properly connected based on water flow. They're just the product of narrow ravines produced by the domain warping function. All of the water is drawn at a constant Z height without regard for interior (lakes) vs. exterior (ocean) water. I've experimented with specialized river generation algorithms, but so far I haven't gotten them to work well in tiled terrain mode. In particular, there are heightmap seams at the borders between tiles (which are generated independently). River generation for infinite heightmaps is very difficult.

Procedurally generated terrain with a river that happens to appear.

I've switched from deciduous trees to pine trees in the next two images. 3DWorld can cycle through four tree modes using the F5 key: none, deciduous, pine, and mixed deciduous/pine/palm. In mixed mode, palm trees are placed near the water line, pine trees are placed on mountains, and deciduous trees are placed in between. This provides more vegetation variety, at the cost of increased generation time for new tiles and increased rendering time due to more draw calls. The increased generation time is due to calling multiple tree distribution functions per tile. The increased rendering time comes from extra draw calls and shader state setting for each visible tile.

Hilly terrain with lakes and pine trees.

I used the realtime terrain editing feature of 3DWorld described here to cover almost the entire surface of the ground above the water line with pine trees. I believe there are around 500K trees on the island and 50-100K trees visible in the screenshot below. 3DWorld uses 2D texture billboards to draw distant trees using only one quad (two triangles) each, which allows this scene to be drawn in realtime at 200 Frames Per Second (FPS). It's also possible to zoom out and create a larger landmass that contains 2M trees, 500K of which are in view, which can be drawn at over 60 FPS. This scene looks more like a dense pine forest, though the underlying terrain can hardly be seen.

Forest covered by around 100K pine trees placed with a large editing brush.

I recently optimized palm tree drawing using hardware instancing + Vertex Buffer Objects (VBOs) on the GPU. This allowed me to adjust the view distance of palm trees so that they're visible to the far fog distance, almost out to the horizon. Unlike pine trees, palm trees aren't usually rotationally symmetric about the Z (up) axis. I haven't been able to get billboards to work well with them. Therefore, each one is drawn in native polygon format using 20 palm fronds = 40 quads = 80 triangles each. In addition, trunks are drawn at various Levels of Detail (LODs) from single lines to 32-sided cylinders consisting of 32 quads = 64 triangles each. This allows me to draw more than 10K palm trees at over 100 FPS, as shown in the image below.

Tens of thousands of palm trees drawn out to the horizon at 143 FPS.

To finish off the screenshot gallery, I'll add an image of a sunset with long shadows and water reflections. If you look carefully, shadow maps are only used for nearby terrain tiles. You can tell which trees have shadows by looking at the lighting changes for distant trees. Terrain drawn beyond the shadow distance uses a more efficient, precomputed, low-resolution ambient occlusion lighting texture. These two modes are linearly blended to make a smooth transition for the player.

This is required to save GPU memory and CPU time for shadow map generation. I haven't used Cascaded Shadow Maps (CSMs) here because the overhead of drawing the scene multiple times (once per cascade) is too high, especially for the trees. Note that rendering tree billboards into the shadow map doesn't look correct; I have to use the full 3D polygon model of each tree, which is slow. There are a lot of polygons in all of those tree models! This is why I decided to precompute a separate static shadow map for each nearby tile instead.

Sunset on procedurally generated landscape and vegetation showing tree shadows and water reflections.

Finally, here is a video where I walk around the terrain and view some deciduous trees up close. You can watch me walk through a river similar to the one featured in the second image above. Then I enable flight mode and fly across the terrain at high speed. This demonstrates how quickly tiles can be generated as the player moves around in the world. In reality the framerate is a bit erratic, which can't actually be seen from a video played back at a fixed 60 FPS. The frame rate drops during frames where more than one tile needs to be generated, and the GPU must split its time between tile generation and scene rendering. In the end, I change the time of day. The sun goes down and the moon comes up, making interesting light reflections in the water.

This video shows that the grass blades are more than single triangles now when viewed from close up. This is a relatively new feature that was visible in some of my grass/tree fire screenshots but maybe not mentioned until now. I implemented this using tessellation shaders on the GPU. That's also how water waves are implemented in tiled terrain mode.

That's all for this post. Next time I'll probably talk about erosion simulation and water flow. I've experimented with these in the past but never mentioned them in the blog. I already have some interesting screenshots prepared. I haven't gotten erosion to work for infinite terrain tiles though. It currently only supports a single square tile at a time. I wonder if I'll be able to fix this in time for the next post.