Heightmap rendering

One of my first posts was devoted to a heightmap generation and now it’s time to talk about heightmap rendering. Most map generators consider heightmap as a technical thing only, but I believe it’s beautiful as is and with some improvements could be used as one of the main map layers.

As of now I’ve added 5 different heightmap styles, 2 optional features and some usable color schemes. The problem is that I need to select only one as I tend to keep things simple. I’m still at the crossroad not knowing which of the styles is the best and I hope this post and your comments will help me decide.

Polygonal

The first style I want to talk about and the most obvious one is polygonal style. If heightmap is based on Voronoi polygons, the simplest way to render it is to draw the polygons by filling each polygon with the color depending on its height.

all polygons map
Polygonal map with both land and water cells rendered

Heights we have are in a range 0-1, while 0.2-1 range is for land and 0-0.19 is for water. We have two options here: draw all the cells (polygons) or draw the land ones only. In my reality the alternative is contrived. I want map to be scalable and hence render it in svg. Meanwhile I need map to be fast on scaling and dragging and I cannot push so many elements as I want. Why not? SVG is a great format, but it becomes externally laggy with a lot of elements added. As of now my maps contain about 9k polygons, so it’s a not a variant to draw them all. Frankly speaking, even 1.5k land polygons is too much and it is not clever to draw them as a separate elements.

Greys color scheme
Polygonal heightmap with monochrome color scheme applied

One more issue is colors. It promised a lot of a work, but thankfully D3 has some built-in color schemes. I cannot say I’m fully happy with any of them, but Spectral and RdYlGn look quite suitable for a heightmap. Both schemes go from red to yellow and green, while we have a greater height value for mountains and don’t want them to be green. So to use the scheme we need to return its order subtracting height value form 1, i.e. color(1 – height).

There is a problem with elements rendering to svg. In case of drawing without or with thin strokes svg will leave odd spaces between elements. It could be resolved by setting stroke-width to 0.7, but this breaks the beauty of polygons shapes due to strokes overlapping. Another variant it to change the default svg shape-rendering to optimizeSpeed (i.e. turn off the anti-aliasing). This is much faster than default and render the elements without extra-spaces, but resulting shapes are not precise. The third variant it to draw polygons filled with optimizeSpeed and then draw the strokes only with default geometricPrecision option. It looks great, but means doubling of rendered elements.

anti-aliasing issue
Anti-aliasing issues. Most are considerable on a big scale only

I prefer the variant with overlapping strokes as of now, but will think on using optimizeSpeed option for a big maps as this variant is fastest.

Triangled

The main problem with polygonal style is that polygons are too big and color difference between neighboring cells is too significant. It looks not bad, but a bit weird on a big scale. To avoid this we could either use more polygons on map generation or divide the existing polygons into smaller shapes. The easiest way is to split the polygons into triangles.

New Triangulation
Triangled style structure

D3-Voronoi provides not only Voronoi polygons, but also a built-in Delaunay triangulation. Delaunay triangles have almost the same size as polygons, so instead or Delaunay I use triangles based on polygons edges and sites.

For each edge D3 already provides references for both left and right related cells and we don’t need any calculations to render two triangles for every edge. Triangle color depends on both color of its own polygon and the opposite one. Knowing height values for both polygons we can calculate the triangle color as an 2 values interpolation with a 0.33 rate. It means each triangle has a color representing related polygon, but with a significant influence of the opposite cell.

The resulted map is very smooth, maybe even more than I want. It looks polished and flat. We can add some discrepancy and slight 3D shading effect. Right-side triangles should be darker if they are lower than left-side ones. The color difference should be more obvious when heights are great, i.e. in the mountains, while plains should look more flat. I’m not sure this naive approach is the best variant, but it works better than other ones I’ve tried.

triangled map mid look 3
Triangled map on a middle scale

Should be also noted that triangled style rendering is significantly slower than polygonal as it requires much more elements to draw. The advantage is a good looking on both large and small scales.

Contours

In cartography one of the most used approach to show the terrain elevation is a contour mapContour line joins the points with equal height above a given level, producing a visual representation of the relief.

Polygonal base of our map is not suitable for a contouring as it contains not enough elements. To implement the contouring we need to turn polygonal graph into a regular structure. To keep it simple I use 1:1 xy coordinate grid, i.e. 640×360 grid for a test version. For each grid point I assign height value based on the height of the polygon current point is in. The easiest way is do this is to loop thought array, calculate xy coordinates from point’s position in array and then use D3 find method to locate the closest polygon and take its height. But this approach is extremely ineffective. Find method is not fast and using it 230k times is a waste of time.

xy grid
Rendered Coordinate grid

To make the time loss adequate I have to implement some wiles. First, we know coordinates and heights of polygons sites, so there is no need to find them. Second, we use Poisson-disc sampling and know a minimum distance between sites, which is about 4 points. We can assign the same height not only to the points in Voronoi sites, but also to their neighbors in the grid.

We use regular grid now, so detecting neighbors is trivial. Each not bordering point has 8 direct neighbors and 18 non-direct ones. Using this approach we can define 27 point for each polygon, or less if we are worrying about approximation quality. Having about 9k sites we can pre-define almost all 230k points and use find for remaining ones onlyThe result is not ideal, but close to it and much faster than you could get with find. I have prepared fiddle for the method demonstration.

Having an array of heights we can easily apply noise pattern to it. Not sure I really need it, but it adds some diversity into a terrain build on just a dozen of blobs. I’m not going to describe how to get the noise as I’m still not completely satisfied with the result and cannot describe it better than Amit whatever. Generally speaking I use SimplexNoise library by Jonas Wagner. If you are interested, I have also created three fiddles for a noise testing: singleoctaved curtains, multioctaved pattern and the same with biomes rendering.

Now it’s time to draw the contours. D3 has it’s own contouring, which is based on marching squares. The only thing we need is to provide a rectangular array of values. Hopefully, we already did it. The layers count depends on the thresholds values. Our land elevation ranges from 0.2 to 1, so I decided to create a contour level for each 0.04 elevation points. This is about 20 layers at all, not too much and hence fast on rendering. Each contour has its own color depending on threshold point height. I use the same color schemes as were used for a polygonal style.

Implementation is pretty straightforward. The only unobvious moment is a contours shade, needed for a 3D effect. We have to apply contours in a distinct order, so the highest layers should be on the top of the lower ones. The shade element should be added right before its parent layer, in this case it will not overlap highest layers. The shade color is derived from the layer color with a significant lightness reduction. To get a 3D effect shade layers should be drawn with a small offset. Here is the D3 code:

// define the data
var data = d3.contours()
  .size([width, height])
  .thresholds(d3.range(0.2, 1, 0.04))
  (heightsArray);
// apply separate group for each contour
var contours = map.selectAll("p")
  .data(data).enter().append("g");
// render contours shade
contours.data(data).append("path")
  .attr("d", d3.geoPath())
  .attr("class", "shade")
  // calculate shade color turning it to HSL and reducing lightness
  .attr("fill", function(d) {return d3.hsl(color(1 - d.value)).darker(2)});
  // offset the shade
  .attr("transform", "translate(0.5 0.6)");
// render colored contours
contours.data(data).append("path")
  .attr("d", d3.geoPath())
  .attr("fill", function(d) {return color(1 - d.value);})
contours map step 01 with noise
Contour map with step 0.01 and noise

The result looks quite interesting. I would prefer more relaxed lines, but this is the only smooth function available by default and I don’t want to rewrite the basics as of now. We can render the map with any count of contours. Even rendering with step 0.01 requires 160 elements only and works fast. The same for shade, we can change shade offset, color or opacity and gain very different result.

Contour map close look
Close look to a contour map

The only demur is that shaded map looks not so great on a large scales. To resolve it I have changed the zoom function. Besides changing the viewpoint now it shrinks the offset and increase opacity of the shade elements on zooming. Not a big deal, but now the map is almost flat on a big scale and got 3D looking on zooming out.

Noisy

This style is also based on contouring method, but designed especially for a big scale. The idea is to take height array and make it a bit more noisy. The implemented noise function is just a simple multiplier by a random value in a 0.95-1.05 range. This randomization is too noisy to be used with shades, but has natural look in case on flat rendering.

noisy map close look
Close look to a noisy map style

Pixel

pixel style with 4 points side
Pixel map with 4 points pixel size

The idea is to draw heightmap in a nostalgic pixel style. As I mentioned above it’s not a good idea to render a lot of elements into svg, so I’m not going to draw all the 230k points. It could be acceptable in the case of considering a bigger square, let’s say with a side of 4 points, as one pixel. Works pretty well, but I don’t like the result (even with added shades) and don’t see a possibility to make it look good.

Features

Two optional features I mentioned before are slope hatching and blur effect. The first is my try to implement the slope shading method described by Martin O’Leary. The reality showed me that my maps with all these big polygons and almost the same slopeness along the map are not eligible for this kind of shading. We can do this on a regular grid instead of polygons, but in this case we also need to randomize the coordinates to get rid of grid regularity. The main problem with slope hatching is that it’s incompatible with scaling. On a big scales we expect the shading to be more detailed, while I’m not sure how it could be easily done.

polygonal map with slope hatching and blur
Polygonal map with slope hatching and blur effect

Blur effect is self-describable. The idea is to use feGaussianBlur svg filter to smooth the map. Initially it was implemented for a polygonal style and worked well, even I don’t really like its fuzziness and it’s a bit slow. But I’ve already got a good smoothness with other heightmap styles, so I’m not sure I will use the blur for a base styling. At the same time it’s very useful for a relief shading or separate elements blurring, e.g. to blur coastlines and river shades.

That’s all for today. Map examples for all of the described styles are in the slideshow below. I would much appreciate if you take a look and suggest the best variants for both small and large scales. For this reason all the styles are shown on the same map.

This slideshow requires JavaScript.

Advertisements

One thought on “Heightmap rendering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s