• entries
    17
  • comments
    19
  • views
    21296

Increasing the resolution of heightmaps

Sign in to follow this  

2231 views

One of the reasons for the development of my terrain engine was so that I could go to any point on the world and explore the surrounding terrain. So I downloaded every single heightmap from the Shuttle Radar Topography Mission website (and likely pissed off my ISP in the process.) These heightmaps encompass all land between 60? North and 56? South. Each heightmap is a 1 degree by 1 degree tile made up of 1201 x 1201 elevation points. Each heightmap has a resolution of three arcseconds (about 90 meters.)

As I was playing around with my terrain engine, I began to notice that for ground-level explorations, a resolution of 90 meters wasn't going to cut it anymore. I needed a way to increase the resolution of these heightmaps.

At first, I simply resized a heightmap to 4801 x 4801 (4x in both directions) using bicubic interpolation and added some Perlin noise to it. It didn't look bad, but it didn't look natural either. So I looked for a way to simulate some sort of natural process to apply this detail. That's when I decided to use some sort of water erosion algorithm.

Searching the intarwebs, I found a paper called Realtime Procedural Terrain Generation (PDF warning). It contained an algorithm for hydraulic erosion. I implemented it but I found that the simulation was a little too perfect. It wore down the mountains and spewed the resulting sediment out into the valleys, choking many small lakes in the process. It was definitely cool to see, but it didn't serve my purpose. I just wanted to add some erosion-like features to the terrain.

I took some of the ideas from that paper and made an algorithm that would produce erosion-like features. When run on this heightmap:



it results in this heightmap:



The erosion algorithm in detail

Before running the erosion algorithm, the heightmap needs to be enlarged using bicubic interpolation. I also find adding a small bit of Perlin noise helps.

The erosion algorithm performs a number of iterations specified by the user. Each iteration performs the following three steps:

  1. Select a random point on the heightmap

  2. Make a river starting at that point

  3. Carve out the ground under the river

(The above image comes from a heightmap with 128,000 iterations applied to it.)

The descriptions of these steps uses the following 5 x 5 heightmap in their examples:



Step 1: Select a random point on the heightmap

This step is self-explanatory. It simply selects a random point on the heightmap (in yellow):



Step 2: Make a river starting at that point

This is the most time-consuming step of the algorithm. It makes the river by selecting a series of points such that each point in the series has an elevation that is lower than its previous point.

The first thing it does is retrieve all the point's neighbors (in blue):



Rivers cannot flow uphill, so the algorithm ignores the neighbors (in red) that have a higher elevation than the current point:



Of the remaining neighbors, the algorithm randomly selects one to be the next point in the river. The lower the neighbor, the more likely it will be selected as the next point.

To calculate the probability for each neighbor, the algorithm first sums together all of the elevation differences between the current point and the neighbor points. In this example, the sum of the differences is:

(15 - 14) + (15 - 14) + (15 - 12) + (15 - 10) = 10.

The probability of selecting a neighbor for the next point in the river is equal to the elevation difference between the current point and the neighbor, divided by the sum of all elevation differences. For example:

  • Right neighbor: (15 - 14) / 10 = 0.1 = 10%

  • Bottom-left neighbor: (15 - 14) / 10 = 0.1 = 10%

  • Bottom neighbor: (15 - 12) / 10 = 0.3 = 30%

  • Bottom-right neighbor: (15 - 10) / 10 = 0.5 = 50%

Once it select the neighbor, the algorithm continues step 2 until there are no more lower neighbors (the river enters a "pit") or the river leaves the edge of the heightmap.

Step 3: Carve out the ground under the river

This step subtracts a constant elevation amount from each point in the river, except the last point.

Excluding the last point is important. This last point will have a lower elevation than all its surrounding neighbors, creating a 1 x 1 "pit" at the end of the river. Successive iterations of the erosion algorithm can cause these pits to become quite deep, which generally makes the resulting heightmap look like hell.

Problems with the erosion algorithm

One thing I've noticed about this algorithm was that some rivers were carved much too deeply into the terrain. If I reduced the number of iterations or reduce the carve amount, the main rivers didn't get as deep, but I could barely see the smaller rivers.

Take a look at the following difference map, which is created by taking the difference between the original heightmap and the eroded one:



The areas in red are at least 40 meters lower than the corresponding elevations from the original heightmap, which I found was too deep for a heightmap with a resolution of 22.5 meters. Also, the river edges were too sharp, showing up as aliasing artifacts on the heightmap. If I clamp the difference values to 40 meters (this parameter is user-defined) and blur them to remove the aliasing, the difference map looks like this:



To produce the final heightmap, simply subtract this difference map from the original heightmap.
Sign in to follow this  


3 Comments


Recommended Comments

A very interesting read, I never really thought about how erosion works/could work until now. Thanks!

Share this comment


Link to comment
I'll second the interesting read part. So, are you planning on reconstructing the topology of the entire planet with those height maps?? That seems like it would be a long endeavor. I assume you'll just explore different parts that you fancy.?

Share this comment


Link to comment
Quote:
Original post by O-san
A very interesting read, I never really thought about how erosion works/could work until now. Thanks!

Quote:
Original post by DecipherOne
I'll second the interesting read part.

Glad you liked them. It actually made some sense?
Quote:
So, are you planning on reconstructing the topology of the entire planet with those height maps?? That seems like it would be a long endeavor. I assume you'll just explore different parts that you fancy.?

Not reconstructing the entire planet at this point, just pieces at a time. While I do have all the SRTM heightmap data, I do need the corresponding Landsat image data (bands 2, 3, 4, and 5) to do the vegetation mapping. Those Landsat images are huge and I've only downloaded a few of them. But eventually I want them all!

-- jas

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now