Heightmap

2mins-europe

Now, when we got a Voronoi graph (see the previous post), we can create something resembling a map, like this “Europe…khe-khe” one above created in a two minutes.

It is a pure heightmap as all the colors just represent the height of the particular polygon. It looks like a map even without coastline and rivers being drawn. So let’s explore how to create a heightmap in a  few steps.

It sounds a bit ridiculous but the easier heightmap generation algorithm I use the better result I get. Frankly speaking I didn’t try to use the most obvious variant — noise function. I’m going to try some noise in the future, but it’s not a priority. So the easiest algorithm I can imagine is:

  1. Select a random polygon
  2. Assign a value from 0 to 1 as the polygon height
  3. Set height of the neighbor polygons with a small decrement
  4. Repeat for the new (unused) neighbors while height is significant

As a result you will get a cute blob (‘island’).

To implement the algorithm above we need to create a queue and poke the next and next neighbor polygons to the function that will calculate the height. Calculation formula is parentHeight *  decrement.

ParentHeight (height) is a currently used height value derived from the initial (start) polygon height. Decrement (radius) is a less-than-1 number which make the island to be sloped and to nullified in a several polygons from the start point. It is a constant for every blob and actually controls the blob radius.

Sounds confusedly, so let’s algorithmize it:

  1. Define initial (peak) height value
  2. Select start polygon and mark it as used
  3. Assign initial height to start polygon
  4. Decrease height by multiplying on Decrement
  5. For each unused neighbor
    1. Assign current height to this polygon
    2. Add polygon to the queue
    3. Mark polygon as used
  6. Repeat steps 4-5 for all elements in queue while current height > 0.01 (it won’t be zero as we use multiplication)

ParentHeight (height) and decrement (radius) are user defined, so we will add inputs to vary that values. You may play with code and inputs in JSFiddle.

function addIsland() {
  // locate start polygon as closest to mouse point
  var point = d3.mouse(this),
    start = diagram.find(point[0], point[1]).index,
    // get options from inputs
    height= heightInput.valueAsNumber,
    radius = radiusInput.valueAsNumber,
    queue = [];
  polygons[start].height = height;
  polygons[start].used = 1;
  queue.push(start);
  for (i = 0; i < queue.length && height > 0.01; i++) {
    height *= radius;
    polygons[queue[i]].neighbors.forEach(function(e) {
      if (!polygons[e].used) {
        polygons[e].height += height;
        // max height is 1
        if (polygons[e].height > 1) {polygons[e].height = 1;}
        polygons[e].used = 1;
        queue.push(e);
      }
    });
  }
  // re-color the polygons based on new heights
  polygons.map(function(i) {
    $("#" + i.index).attr("fill", color(1 - i.height));
    i.used = undefined; // remove used attribute
  });
}

As you may notice the blobs are smooth and there is no way to make them sharp and irregular. But in the real-word big islands usually look different. Just take a look on the shape of Ireland and Iceland: both isles have sharp coast with a lot of long, narrow inlets from one side while another coasts are smooth, straightened. Even I’m not a specialist in coastal geomorphology, I realize that it is not the only possible island form. But this shape is interesting with all of its inlets, peninsulas and harbors.

To resolve this issue let’s change the code a bit to add some randomness. Each time before the height is assigned to polygon we will multiply the height by random modifier. Modifier is calculated based on sharpness variable and should be slightly less or greater than 1. In the case it is less than 1 height will decrease faster, greater – height can increase. This minor chance of increasing provides a lot of form irregularity and allows small accompanying isles generation.

The sharpness is not enough by itself. We the need change the code to support the irregularity. The height calculation should be based not on the current height, but on the height of the parent polygon – this will allow ridges and valleys sprawling from the blob center. Compare two blobs below. Left blob is generated without a modifier (actually modifier is 1), so it is smooth. Right blob is created with modifier varying from 0.9 to 1.1 and it’s sharp.

Take a look on the code below (FSFiddle):

function addIsland() {
  // locate start polygon as closest to mouse point
  var point = d3.mouse(this),
    start = diagram.find(point[0], point[1]).index,
    // get options from inputs
    height = heightInput.valueAsNumber,
    radius = radiusInput.valueAsNumber,
    sharpness = sharpnessInput.valueAsNumber,
    queue = [];
  polygons[start].height = height;
  polygons[start].used = 1;
  queue.push(start);
  for (i = 0; i < queue.length && height > 0.01; i++) {
    height = polygons[queue[i]].height * radius;
    polygons[queue[i]].neighbors.forEach(function(e) {
      if (!polygons[e].used) {
        // calculate the modifier
        var mod = Math.random() * sharpness + 1.1 - sharpness;
        // if sharpness is 0 modifier should be ignored (=1)
        if (sharpness == 0) {mod = 1;}
        polygons[e].height += height * mod;
        // max height is 1
        if (polygons[e].height > 1) {polygons[e].height = 1;}
        polygons[e].used = 1;
        queue.push(e);
      }
    });
  }
}

There is a problem in this approach. In case of using more that one blob there is a big chance that blobs will overlap each other. And, as polygon height is derived from parent’s polygon, in case of overlapping summary height will be off-scaled. So we need to change the line 21 to re-define the height in case of overlapping. This will not resolve the problem as new blobs won’t cover each other and won’t provide a more complex shape.

It’s a good idea to create big high blob using the 2nd code variant and then add a couple of smaller and lower ones using the 1st code variant. The smaller blobs will ‘cover’ the initial sharp blob in some places and this will change the landform in the desired direction. For my generator I create one big blob as a first step and then add 10 small blobs. Compare the shapes below:

Use this JSFiddle playground for the experiments (1st blob will be a big ‘island’).

You need to realize one more thing. The calculations and map look depend on the graph size. For my maps I use 8000 polygons, just because this amount still runs smoothly in my browser with the already added details. As an experiment I’ve tried 100k polygons with rather interesting look (JSFiddle), but it needs to be tested more.

Advertisements

5 thoughts on “Heightmap

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