Leveling Lakes

This post will advance the water saga.

You may want to check out the previous post about water. It ended up producing a 2D map of booleans, where true meant there was water in that location of the map. That was great, but we still had a nasty problem ahead. We needed to level the lakes.

It will be easier if we look at some pictures. Imagine this is the tile we need to compute. Initially it is just the terrain height and the sea map (in this case using a sea-level value):

And here you can see the lake and river location phase from the earlier post in pretty pink:

As you can see in the zoomed portion, these lakes often span over very irregular terrain. We knew the shoreline points for the same lake were at similar height. Figuring out the water level from A to B was the problem. We know A-B should be as flat as possible and the same applies to A and any other point in the shoreline. That's a lot of potential points.

If we had all the time in the world, we could try discovering individual lakes in one phase and then do some sort of iterative leveling by relaxation and or filtering. We had only a fraction of a second for this so we knew it had to be hacked.

We tried many different things. (When I say "we", it is not modesty plural. Michael Coates who recently joined Voxel Farm got to implement these desperate things we tried.) Most had to do with rasterization and interpolation, first from shore to shore, then we got looking into water height derivatives. Nothing really worked.

As a last recourse attempt, we tried an approach that involved a Quadtree. The idea was to encode the water bodies in a Quadtree and apply the same leveling algorithms we knew would be too slow if we were operating in individual water samples.

The shorelines produced a lot of small quads, but as we moved inside the lake we started getting larger quads.

We could see that the larger a patch, the more "detached" it was from the shore. That we liked. We could raise or sink those points much more to achieve the level we needed.

Once the water height of the larger patches is decided, we rasterize them into the water heightmap. This is a simple, fast bi-linear interpolation over the quad. Then we do the same for the smaller quads. There is a reason why you need to process all quads of a given size before processing the next level of smaller patches: You need to make sure the small quads match the interpolation values along the edges they share with a larger quad.

This overall process is quite fast. Here is a rendering of the new found water volumes. It is a bit exaggerated, but hopefully you get the idea:

We still need to work out on some of the heuristics, but it looks we are pretty much on our way.

If there is any lesson to be drawn from this, it would be when in despair, apply a Quadtree and everything will be alright.

Water bodies

There is a good reason why I have postponed doing water. It is not because I consider it particularly difficult. Water is bound to simpler rules than other systems I have already looked into. I had a different reason.

Water is less dense than buildings and terrain. A damn or a mountain will determine where water goes. In my mind, the heavy stuff must be there first, then comes the water. You may say water does have a significant effect in terrain features. It is true, but as you will see in my next post I think there is a way around that.

Anyway I wanted to have a better idea about my buildings and terrain. I did not want the water solution getting in the way. I think I have reached this point now, it is time to look again into the water generation.

This is about generating large water bodies like rivers and lakes. This is not about water flowing downhill. I think I will have two different systems for this. Even if the water looks the same, it will be handled by different parts of the code. Ideally you would like to make no distinction between a lake and water inside a bucket. In reality it is all the same, but sadly our hardware is eons away from that. As usual we need some clever hacks.

I am trying this system now:

You start from a heightmap. Your terrain does not have to be heightmap based. It could be full voxel with caves, overhangs, etc. The heightmap defines the surface visible to the water simulation, it must register with the terrain volume. This heightmap looks like this:

Nothing fancy here, this is your run-of-the-mill heightmap. But how you section this work is important. I chose to generate tiles approximately 50 km wide at once. That means all the rives and lakes will be enclosed in that tile. You won't have a river going for 100 km with this approach. If you want that, the tile size would have to be bigger. In my case 50 km was a good starting point.

The next step is to add some water sources to it. You do not do this everywhere, just where the terrain is high enough. For a 50 km tile I add around 200 points.

Then you find the closest path from each point to a lower plane, which you can consider to be the ocean level. You can use any path finding algorithm, like A-star. This gives you rivers, which show in blue below. You can see ocean water in a darker blue:

The red points show the water sources. As you can see the rivers follow the path of least effort over the terrain, always looking for the ocean.

I also wanted to have lakes, but did not see a simple way to add them. That until one day I was debugging the river path-finding. To find that bug (which I already forgot what was about) I chose to highlight the exploration the river algorithm was doing before selecting a particular course. I noticed the path-finding would spread its search whenever encountering flat surfaces. It was behaving pretty much just like water.

Once I added the areas where path-finding searched, I got lakes!

I liked how lakes could appear at different altitudes. Also if you notice the heightmap values in the lake shore, you will see they do not diverge by much. This means the lake surface is mostly flat. In real life often lake surfaces are not entirely flat. This is because the lake actually flows.

I will finish this topic in my next post, where you will get to see how to come up with the actual water surfaces. Also how you find out where waterfalls should go. You got to have those waterfalls.