Interpolation and smoothing

Why you need this

A noise field starts as random numbers placed on a coarse lattice, one every 8 or 16 cells. Every cell in between needs a value too, and the way you fill those in decides whether the terrain looks like rolling hills or like a quilt with visible stitching. Filling in is interpolation. Making the seams disappear is smoothing. Both are two lines of arithmetic, and both matter more than any other single choice in a noise-based generator.

The idea

Linear interpolation

Given two values $a$ and $b$ and a fraction $t$ between 0 and 1, linear interpolation returns the value that is a fraction $t$ of the way from $a$ to $b$:

$$\mathrm{lerp}(a, b, t) = a + (b - a)\, t.$$

At $t = 0$ it returns $a$, at $t = 1$ it returns $b$, and at $t = 0.5$ it returns the midpoint. With numbers: $\mathrm{lerp}(10, 20, 0.25) = 10 + 10 \times 0.25 = 12.5$. Think of it as a straight line drawn between the two known points; lerp reads the height of that line at position $t$.

const lerp = (a, b, t) => a + (b - a) * t;

Bilinear interpolation

On a grid you have four known values at the corners of a square, not two at the ends of a line. Bilinear interpolation applies lerp three times: once along the top edge, once along the bottom edge, and once vertically between those two results.

Name the corner values by position on a unit square, with $x$ increasing to the right and $y$ increasing downward: $v_{00}$ top-left, $v_{10}$ top-right, $v_{01}$ bottom-left, $v_{11}$ bottom-right. For a point $(t_x, t_y)$ inside the square, both fractions between 0 and 1:

$$\text{top} = \mathrm{lerp}(v_{00}, v_{10}, t_x), \qquad \text{bottom} = \mathrm{lerp}(v_{01}, v_{11}, t_x), \qquad \text{result} = \mathrm{lerp}(\text{top}, \text{bottom}, t_y).$$

Doing the two horizontal lerps first and then the vertical one gives the same answer as vertical first and then horizontal. Either order is fine.

The crease problem

Lerp produces straight segments. Where two segments meet, at a lattice point, the value is continuous (no gap) but the slope changes abruptly. Along a line of lattice values 0.2, 0.8, 0.3, the height climbs at a steady rate, then the instant it passes the middle point it starts falling at a different steady rate. Your eye is very good at spotting where a slope changes, so a noise field built from plain bilinear interpolation shows a faint grid of straight lines and diamond-shaped hills exactly at the lattice spacing. Coastlines come out as chains of straight segments with corners at lattice lines.

Smoothstep

The fix is not to change the corner values but to change how $t$ is used. Before calling lerp, pass $t$ through a curve that starts flat, speeds up in the middle, and ends flat:

$$s(t) = 3t^2 - 2t^3.$$

This is smoothstep. It still maps 0 to 0 and 1 to 1, and $s(0.5) = 3(0.25) - 2(0.125) = 0.75 - 0.25 = 0.5$, so the midpoint does not move. What changes is the slope at the ends: it is zero at $t = 0$ and zero at $t = 1$. A flat approach on both sides of every lattice point means the slope on the left of the point matches the slope on the right (both zero), so there is no crease. The hills become round.

(Optional, one line of calculus: the derivative is $s'(t) = 6t - 6t^2 = 6t(1 - t)$, which is 0 at $t = 0$ and $t = 1$. You do not need this to use the curve.)

const smoothstep = (t) => t * t * (3 - 2 * t);

A stricter version, the quintic smoothstep $6t^5 - 15t^4 + 10t^3$, also makes the curvature match at the ends, not just the slope. Perlin switched to it in 2002 because the plain version still shows a faint second-order pattern under strong lighting. For a tile map sliced into a few bands you will not see the difference.

Ease curves in animation ("ease in", "ease out", "ease in-out") are the same idea applied to time instead of space: run $t$ through a curve before lerping the position, so motion starts and stops gently.

Worked example

Corner values on a unit square: $v_{00} = 0.2$, $v_{10} = 0.8$, $v_{01} = 0.5$, $v_{11} = 0.1$. Find the value at $(t_x, t_y) = (0.25, 0.5)$.

Plain bilinear:

Step	Formula	Value
top	$\mathrm{lerp}(0.2, 0.8, 0.25)$	$0.2 + 0.6 \times 0.25 = 0.35$
bottom	$\mathrm{lerp}(0.5, 0.1, 0.25)$	$0.5 - 0.4 \times 0.25 = 0.40$
result	$\mathrm{lerp}(0.35, 0.40, 0.5)$	$0.375$

With smoothstep applied to both fractions first: $s(0.25) = 3(0.0625) - 2(0.015625) = 0.1875 - 0.03125 = 0.15625$ and $s(0.5) = 0.5$.

Step	Formula	Value
top	$\mathrm{lerp}(0.2, 0.8, 0.15625)$	$0.2 + 0.6 \times 0.15625 = 0.29375$
bottom	$\mathrm{lerp}(0.5, 0.1, 0.15625)$	$0.5 - 0.4 \times 0.15625 = 0.4375$
result	$\mathrm{lerp}(0.29375, 0.4375, 0.5)$	$0.365625$

The smoothed result sits closer to the left-hand corners, because $t_x = 0.25$ is near the left edge and smoothstep flattens the approach to an edge. Along a whole row, the table below shows how the two treatments differ. Values are $\mathrm{lerp}(0, 1, \cdot)$, so the table is really $t$ against $s(t)$ and the quintic $q(t)$.

$t$	linear $t$	smoothstep $s(t)$	quintic $q(t)$
0.00	0.000	0.000	0.000
0.10	0.100	0.028	0.009
0.25	0.250	0.156	0.104
0.50	0.500	0.500	0.500
0.75	0.750	0.844	0.896
0.90	0.900	0.972	0.991
1.00	1.000	1.000	1.000

Read down the smoothstep column: it lingers near 0, catches up by the middle, and lingers near 1. That lingering is the flat slope at the ends.

Putting it together, here is the interpolation core of a value-noise function. The lattice value at integer coordinates comes from a hash of the seed and the coordinates, which Pseudo-random numbers covers.

function sampleValueNoise(latticeAt, x, y) {
  const x0 = Math.floor(x), y0 = Math.floor(y);
  const tx = smoothstep(x - x0), ty = smoothstep(y - y0);
  const top    = lerp(latticeAt(x0, y0),     latticeAt(x0 + 1, y0),     tx);
  const bottom = lerp(latticeAt(x0, y0 + 1), latticeAt(x0 + 1, y0 + 1), tx);
  return lerp(top, bottom, ty);
}

In a map generator

This is the smoothing step inside value noise. Noise fields places one random number per lattice point, then calls the code above for every cell, then slices the result by thresholds into water, sand, grass, and rock. Every tile between lattice points owes its height to bilinear interpolation, and every round hill owes its shape to smoothstep.

In the pipeline: noise lives in the layout stage when the lattice is coarse (one value per chunk, deciding biome) and in the fill stage when it is fine (one value per few cells, deciding elevation or moisture within a chunk). Interpolation is also how Layered generation blends two chunks' values across a seam so that the biome boundary is a gradient rather than a hard line. Ease curves show up in the regime over time stage whenever a region fades from one palette to another over several ticks instead of snapping.

Common mistakes

• Skipping the smoothing curve. Symptom: the terrain shows a faint square grid at the lattice spacing, and every hill is a pyramid or diamond.
• Applying smoothstep to the output instead of to $t$. Smoothing the final height compresses everything toward the middle and does nothing about creases. The curve goes on the fraction, before lerp.
• Using $t$ outside $[0, 1]$. Lerp extrapolates happily, giving values below the lower corner or above the upper one. Smoothstep outside the range shoots off toward infinity. Clamp $t$ first if the input can stray.
• Off-by-one on the lattice. Reading corner $(x_0 + 1, y_0 + 1)$ past the last lattice column returns undefined, which becomes NaN after lerp, which renders as one solid color along the right and bottom edges. Allocate one extra lattice row and column, or hash on demand.
• Mixing up which corner is which. Swapping $v_{01}$ and $v_{10}$ transposes every hill across the diagonal. The map still looks like terrain, so the bug hides until you compare against a reference render.
• Interpolating tile ids. Lerping between tile id 3 (grass) and tile id 7 (water) gives id 5, which is whatever happens to be fifth in the sheet. Interpolate heights, then pick tiles from the height.

Cost

One bilinear sample is three lerps and two smoothsteps, about a dozen multiplications, so $O(1)$ per cell and $O(W \cdot H)$ for a map $W$ cells wide and $H$ cells tall. Memory is the lattice only, $O(W/L \cdot H/L)$ for lattice spacing $L$, or nothing at all if lattice values are hashed on demand. A $256 \times 256$ map with four noise octaves is about a quarter million samples, which runs in a few milliseconds. It starts to hurt when you resample every frame for an animated field; cache the base field and animate only the threshold or the palette.

Going further

• Noise fields, which wraps this page in octaves and thresholds to produce terrain.
• Cubic Hermite and Catmull-Rom splines, the next step up when you want smooth curves through more than two points.
• Perlin's gradient noise, which interpolates dot products of gradient vectors instead of raw values, and why that removes the blotchy look of value noise.
• Bicubic interpolation, which uses 16 neighbors instead of 4 and is the standard for image resizing.