Heightmap Terrain Smoothing/Interpolation Results

Hi all,
Been a couple years since I’ve dropped in. I’ve learned a lot about using JME while tooling around with it off and on. I’m finally considering making my own project.

To that end, I recently completed a more thorough terrain smoothing algorithm for use in image based heightmaps, as I was getting some results with the current smoothing capability that I wasn’t very fond of. It functions very well in concert with the current smoothing algorithm to achieve much better results.

I’m not especially certain what my next steps should be if anyone else even finds this interesting or useful. Maybe I reinvented a wheel that was already invented. I am not what you might call “a good programmer,” so I imagine that my code also looks very poor from a best practices perspective. But I wanted to at least attempt to share what I’ve implemented. And if it is useful, look for direction about what to do // how to share it.

For instance, the following is a heightmap and texture of some avocados (although the internet seems to think these are mangos):

Here is the render unsmoothed, and smoothed with the integrated algorithm to the best extent I could:

And here are my results (don’t mind the roads, I used the tutorial’s alphamap):


Background:

When importing an integer-based heightmap into JME, several users have observed a “stairstep”-like effect. This is caused by relatively low bit-depth in the import heighmap in comparison to a combination of the maximum elevation desired for display and the scope of relatively flat areas in the terrain. Even 16-bit heightmaps aren’t entirely immune to this effect. Here is an 8-bit example for ease of visualization:

This terrain is a subset of this heightmap.

Which was created from this Blender model.

Workarounds typically involve generating terrain files in JME-specific tools, which may untenable or effectively impossible, depending on where the terrain data is coming from (e.g. real-world data from a RADAR or LIDAR DEM). For those who can only use or only have access to externally-generated heightmaps, there are some built-in options to mitigate the problem.

As can be seen in the following threads{threads}, most of the body of past advice for smoothing image-based greyscale heightmaps consists of applying the integrated smoothing capability with various values (value that aren’t significantly different), while also usually recommending setting the terrain’s local vertical scaling to 0.5. Here is the above example, using ImageBasedHeightmap.smooth(1f, 1) and Terrain.setLocalScale(2,1,2):

This is decent, though the end-state is still observably stepped. Even “better” smoothing can be achieved by fiddling with the parameters used. This link shows smooth(1f, 2), although if you know what you’re looking for, you can still see a little bit of shading on the “stairsteps.” And while massaging the parameters can yield some acceptable results visually, there may be other unacceptable tradeoffs.

For instance, this can severly limit the observable height-to-terrain size. With an 8-bit heightmap, the maximum elevation presentable through these techniques was quite low. If you want to make mountains (Mountains, Gandalf!), you may not be able to work with a technique that requires lowering the vertical scale of the terrain. In fact, you may need to raise the vertical scale to achieve acceptable elevations. This is setLocalScale(2,4,2) with smooth(1f, 2):

As you can see, raising the vertical scale causes the stairstep effect to emerge again. So, you need to adjust your smoothing parameters again. Smooth(1f, 8) as seen here, again yields a possibly acceptable view from this location. Unfortunately, now there are other problems. Each time the radius of the smoothing algorithm increases (the second parameter in the method call), the more plateau terrains become eroded. And the greater the radius of integrated smoothing, the more distorted the elevation profile becomes. Basically, the contour lines become heavily distorted. Here is a look at an aerial view of another portion of this same heightmap, both unsmoothed and smoothed:

The shoreline is pulled all the way back to the road intersection, as a tradeoff for minimizing the stairstep effect throughout the scene. To demonstrate these tradeoff effects, here is a very simple 2-bit heightmap with only 3 height values (0,1,2). The height values are exaggerated in scale with setLocalScale(1,8,1).

Here is another simple example showcasing the tradeoffs with 5 height values:

At the end of the day, there are three identifiable issues with the integrated smoothing that function as something of a performance and results tradeoffs:

  1. Distortion of the contour elevation profile.
  2. Range limits on nearby elevations that can potentially contribute to an individual pixel’s smoothing are absolute, rather than relational.
  3. The number of pixels between contour lines that those lines contribute to for smoothing.

If you resolve problem 3, by limiting the smoothing radius, problems 1 and 2 tend to get worse. And so on.


Criteria:

My criteria for an effective solution in my case follows:

  1. The contours themselves must be preserved (the elevation profile).
  2. Contour lines must contribute to the smoothing of all pixels between them, no matter how far apart.
  3. Limits on nearby elevations that could potentially contribute to an individual pixel’s smoothing should be relationally based, rather than based on an absolute distance range.
  4. These cannot be tradeoffs with each other.

Here is a very basic example result:

Now we have a heightmap that can be traditionally smoothed:

While this example may look like some kind of linear interpolation at first glance, it isn’t. Linear interpolation is just the approached special case as the Power parameter of this algorithm is set closer to 1. Here are more results achievable by changing the Power parameter with this algorithm:

Here is an image of this algorithm applied to the earlier 5-value heightmap.

And here is the aerial view also shown earlier, with this new smoothing method applied, fixing both the distortion of the elevation profile along the shoreline, as well as more effectively clearing up any remaining “stairstep” effects:

For further examples, scroll past the Methodology section.


Methodology:

The algorithm begins by spending a minimimal amount of time extracting and identifying all unique surfaces and edges from the input heightmap (effectively making topographical contour maps). Second, I perform a much more significant and involved amount of relational processing for each point in the heightmap to select a subset of appropriate points among the contours to be used in the final calculation. The vast bulk of the processing occurs in the second step. The last step, which is at least as quick as the first step, is to perform an Inverse Distance Weighting calculation for every pixel in the heightmap using the previously found relationships with other points. Because the final calculation in the third step is IDW-based, you can flexibly set the power, which yields different interpolation curvatures. I tend to have a preference for power 1.5.

Currently my code doesn’t allow for occlusion barriers, and it doesn’t make any assumptions about the curvatures of absolute plateaus and valleys. Though both of these features could be added, they would take time to implement.

Additionally, I only perform first-degree relational processing: I only consider the effects of surfaces adjacent to the surface containing any particular pixel in the heightmap. There is some value in considering second-degree processing, but not much beyond that. And most of the value that could be gained by second-degree processing can be approximated by running the first-degree results through the current smoothing process, as I have shown in my examples. There’s also some gains that could be had by curve-fitting, but those would probably require a much longer amount of processing time.

The bulk of the improvement that could be had currently is making the scaling more efficient through better parallelization of a particular loop in the process, thus making the relational processing more efficient.

The process works in seconds on 256x256 heightmaps, but can take many minutes on 1024x1024 heightmaps (the longest it took on a rather complex 1024x1024 heightmap for me was just shy of an hour), and many hours on 2048x2048 heightmaps. Even larger maps scaling similarly exponentially.

However, this smoothing does not need to be done on the fly. If given a heightmap that doesn’t function well with the current smoothing process, this process can be prerun as a utility to generate a new heightmap file. To that end, I’m also in the process of writing an exporter/importer set of methods, modelled off of the current JME class (e.g. ImageBasedHeightMap.java) for saving and loading floatmaps generated by this smoothing algorithm.

There are some other “fun” quirks of my implementation that I can resolve if I ever get around to it.

Pros of using this method:
– No contour fall-offs: Pixels on a contour line maintain absolute elevations. This is a sort of “loss-less” processing of the heightmap. The contour lines can be absolutely re-surveyed from the finished heightmap.

– Simple heightmaps: Very basic heighmaps, even those with very low bit-depth, can yield complex and elegant terrain surfaces suitable for smooth character movement.

Cons:
–Processing time can be significantly larger: If a heightmap is of dimension NxN, basic smoothing scales at N^2 – 1 operation per pixel in the heightmap, looking at exactly C other pixels). However, this sort of relational smoothing scales at up to N^4 (though this can be made more efficient, it won’t ever be N^2) – 1 operation per pixel in the heightmap, looking at up to every other pixel in the heightmap.

– More difficult to ensure level surfaces that you actually want to be level: There are techniques to force a particular surface to resolve as absolutely level terrain post-IDW, even in this implementation, but they require an understanding of how to do it, and it isn’t always easy. Nor does it always yield expected results without occlusion (and this implementation does not have occlusion).


Additional Notes:

The implementation currently smooths only a 2d surface, as it expects only a 2d array of points. The math under the hood, though, could technically be used for any number of dimensions. But, again, would require additional time to implement.


Further Examples:

The first example is extremely simple. This is a heightmap with 3 values (0,1,2), then exaggerated in the renderer through Terrain.setLocalScale(1f,8f,1f).
{https://imgur.com/a/kq2bNcC}

The second example is also extremely simple. This is a heightmap with 5 values (0,1,2,3,4), then similarly vertically exaggerated.
{https://imgur.com/a/l3ZrS3J}

The third example has only 6 values, but is more “complicated” in terms of contours.
{https://imgur.com/a/oMIAIBY}

The fourth example is the earlier fully 8-bit heightmap, similarly vertically exaggerated. Both to show the “stairstep” effect, and to show my own results.
{https://imgur.com/a/cbUt1Zl}

The fifth example is the original 5-bit depthmap of a group of avocados as seen above. I found this data from Depthy, a site that makes minor 2-d interactive animations using depthmaps.
{https://imgur.com/a/0iFHuLo}

This final example is from real-world data in Colorado. It’s 8-bit elevation data, of two separate locations. Some of these images include DirectionalLight and/or AmbientLight.
{https://imgur.com/a/ZxOJOE2}

6 Likes

Wow, first off welcome back after 2 years! This looks very interesting, especially for me as my current project is requiring large areas of vast terrain and I was hoping to avoid 16 bit textures and scaling as extremely large features are absolutely required.

If you are interested in sharing @jayfella has implemented an awesome “Software Store” (located at the top of the page under links or here) I am still a ways off from really cracking down on my terrain implementation, but when I do finally get there I would love to give your smoothing a try.

Whether or not you choose to share, this was a very informative post, so thank you for taking the time to write this.