teaching machines

CS 488: Lecture 17 – Heightmaps

March 24, 2021 by . Filed under graphics-3d, lectures, spring-2021.

Dear students:

We’ve been applying images to existing surfaces. Today, let’s turn things around a bit. Let’s generate a surface using an image. We’ll consider the image to be a grayscale map of elevations, which is sometimes called a heightmap. From this raster, we’ll generate geometry that we can traverse interactively with a camera.

Convert RGBA to Grayscale

The benefit of using the browser for our GUI system is that it can load in images of so many different types. The cost is that all images get converted to a 4-channel RGBA image, even if the original image only had a single grayscale channel, as a heightmap does. A further cost is that the native Image object doesn’t grant us access to the raw pixel data. This isn’t a concern when we’re just using the image as a texture. WebGL knows how to extract out the pixel data to send it up to the GPU. But when we’re generating a heightmap, we’re building the terrain mesh on the CPU. We need those pixels.

We overcome both of these costs by writing a little utility method that converts an Image into a 1D array of grayscale values. The raw RGBA pixel data is extracted using canvas, and then we extract out only the red channel using a loop that skips over the green, blue, and alpha channels.

export class ImageUtilities {
  static htmlImageToGrays(image) {
    const canvas = document.createElement('canvas');
    const context = canvas.getContext('2d');
    canvas.width = image.width;
    canvas.height = image.height;
    context.drawImage(image, 0, 0, image.width, image.height);
    const pixels = context.getImageData(0, 0, image.width, image.height);
    const grays = new Array(image.width * image.height);
    for (let i = 0; i < image.width * image.height; ++i) {
      grays[i] = pixels.data[i * 4];
    }
    return {grays, width: image.width, height: image.height};
  }
}

In the renderer, we load in a heightmap at a given URL with this code:

async function loadHeightmap(url) {
  const image = new Image();
  image.src = url;
  await image.decode();
  const {grays, width, height} = ImageUtilities.htmlImageToGrays(image);
  // ...
}

Heightmap

To help organize our code, we’ll write a Heightmap abstraction that will encapsulate the one-dimensional array of heights. We maintain the convention that the y-axis points up from the ground.

Constructor

The constructor receives the heightmap’s dimensions and the array of heights and hangs on to them. As an image, we think of the grayscale raster as having dimensions width and height. But the terrain is the image rotated to lie flat on the ground. What was the height of the raster becomes the depth of the terrain.

Height Getter and Setter

Since the array of heights is a 1D array, we want to provide a more natural 2D interface for accessing it. We add this getter and this setter:

get(x, z)
  return this.heights[z * this.width + x]

set(x, z, height)
  this.heights[z * this.width + x] = height

We expect x and z to be integers. These methods should only be called to determine the height at integer locations on the terrain’s lattice.

To Triangular Mesh

The heightmap isn’t really a texture; it’s just a compact way of expressing the shape of the terrain. What we need is a triangular mesh. Generating the geometry is a lot like generating a plane. The only difference is that we use the heights.

Our algorithm might look something like this:

toTriangleMesh()
  positions = []

  for z in 0..depth
    for x in 0..width
      y = this.get(x, z)
      positions.push(x, y, z)

  faces = []
  for z to depth - 1
    nextZ = z + 1
    for x to width - 1
      nextX = x + 1

      faces.push([
        z * this.width + x,
        z * this.width + nextX,
        nextZ * this.width + x,
      ])

      faces.push([
        z * this.width + nextX,
        nextZ * this.width + nextX,
        nextZ * this.width + x
      ])

  // calculate normals

  return {positions, faces}

The normal generation algorithm is omitted from this code. We described how those might be computed in an earlier lecture.

Once this method is written, we can render our terrain.

Lerp

As our camera moves across the terrain, we will not be confined to just the integer locations. We need a way to determine the height within a cell of the terrain. Bilinear interpolation will do the trick. Our general height lookup function lerp might look like this:

lerp(x, z)
  floorX = floor(x)
  floorZ = floor(z)
  fractionX = x - floorX
  fractionZ = z - floorZ
  nearHeight = (1 - fractionX) * this.get(floorX, floorZ) + fractionX * this.get(floorX + 1, floorZ)
  farHeight = (1 - fractionX) * this.get(floorX, floorZ + 1) + fractionX * this.get(floorX + 1, floorZ + 1)
  y = (1 - fractionZ) * nearHeight + fractionZ * farHeight
  return y 

You may need to add some logic to this code to prevent out-of-bounds indexing.

Camera

As we move across the terrain, we want our camera to float across the surface, automatically adjusting its height as we advance and strafe. We extend our existing camera class, overriding advance and strage to automatically adjust the camera’s height using the helper method elevate.

class HeightmapCamera extends Camera {
  constructor(from, to, worldUp, heightmap, eyeLevel)
    // construct superclass
    // save instance variables
    this.elevate()
    this.orient()

  elevate() {
    // clamp this.from.x to valid terrain coordinates
    // clamp this.from.z to valid terrain coordinates
    this.from.y = this.heightmap.lerp(this.from.x, this.from.z) + this.eyeLevel
  }

  advance(delta) {
    offset = this.forward * delta
    this.from = this.from + offset
    this.elevate()
    this.orient()
  }

  strafe(delta)
    offset = this.right * delta
    this.from = this.from + offset
    this.elevate()
    this.orient()

Elevation

We shade our terrain using standard diffuse shading. What about its albedo? We could use a solid color or apply a texture. But let’s trying coloring the terrain by its elevation. In our favorite image editor, we create a n-by-1 gradient image that has the low elevation colors on the left and the high elevation colors on the right. Then we load it in.

How do we get the texture coordinates? One option is to generate them in the vertex shader:

// ...

out float proportionalY;

void main() {
  // ...
  proportionalY = position.y / maxHeight;
}

We look up the color for this proportional height in the fragment shader:

// ...

uniform sampler2D lut;
in float proportionalY;

void main() {
  // ...
  vec3 albedo = texture(lut, vec2(proportionalY, 0.5)).rgb;
  // ... 
}

This creates very uniform banding. To disrupt the uniformity, we can perturb the height with a bit of random noise. Some noise is purely random, and it looks too chaotic. Other noise is coherent and appears more organic. Later we may investigate noise in more detail, but for today, we’ll just load in a 2D noise image that we make in an image editor.

We need texture coordinates to know our location on the terrain. These can be generated at the same time as our positions and uploaded as another vertex attributes, or we can generate them in the shader from the position. Let’s try the latter:

out vec2 proportionalXZ;

void main() {
  // ...
  proportionalXZ = position.xz / vec2(width, depth);
}

In the fragment shader, we look up the noise value and use it to offset the height:

// ...

uniform sampler2D noise;
in vec2 proportionalXZ;
const float perturbationFactor = 0.1;

void main() {
  // ...
  float offset = texture(noise, proportionalXZ).r * perturbationFactor;
  vec3 albedo = texture(lut, vec2(proportionalY + offset, 0.5)).rgb;
  // ...
}

TODO

Here’s your TODO list:

See you next time.

Sincerely,

P.S. It’s time for a haiku!

I climbed a mountain
At the top, I wasn’t tired
So I went back down