Octave An interactive monograph on procedural noise

Octave

How a short function generates the texture of mountains, clouds and coastlines, by producing randomness that varies smoothly instead of jumping from point to unrelated point.

An interactive monograph in seven sections, with five live figures. Reading time roughly forty minutes. The figures are operable by mouse, touch and keyboard, and the document conforms to WCAG 2.2 AA. Built as a single static page in vanilla HTML, CSS and JavaScript, with no framework and no build step.

Abstract

Procedural noise is a function that, given a position, returns a random-seeming value that nonetheless varies smoothly from one position to the next. That smoothness, called coherence, is what makes the function useful for generating the appearance of natural surfaces. This document develops the subject from its foundations. It begins with the distinction between raw randomness and coherent noise, and reviews the historical development of the field, in which each construction repaired a definite flaw in the one before it. It then treats the principal methods in turn: value noise, which interpolates random numbers on a lattice; gradient noise, which stores directions rather than values and so removes value noise's lattice bias; and fractal noise, which sums copies of a noise function at many scales to reproduce the detail of natural objects. A final section turns the fractal field into terrain.

Every figure is interactive and renders a genuine noise field. The hash, the interpolation and the octave summation are computed exactly, and a keyboard-movable probe reports the value at any point, so the behaviour the document describes can be confirmed directly.

1Randomness and coherence

A computer asked for random numbers returns a fresh, unrelated value on each request. Displayed as brightness across a grid of pixels, such values produce the static of an untuned screen. The image is genuinely random, and it is useless for representing a natural surface, because nothing in nature jumps from one value to an unrelated value across an arbitrarily small distance. A point on a mountainside is random in some sense, but it closely resembles the point beside it.

That resemblance is the property procedural noise must supply, and it has a name: coherence. A coherent noise function is random when sampled at points far apart and smoothly varying when sampled at points close together. The figure below renders a coherent field. Its frequency control sets how rapidly the field varies, and raising it far enough is instructive. At the highest setting neighbouring samples cease to resemble one another and the field decays into static. Coherent noise contains raw randomness; it is what remains when the smooth structure is removed.

The probe makes the point precise. Move it a small distance across the field at a low frequency and the value barely changes, which is coherence. Move it the same distance at the maximum frequency and every step is an unrelated jump. The task of the document is to construct a function with the first behaviour and to do so cheaply, since the function will be evaluated once for every pixel of every frame.

2A history of procedural noise: a literature review

The methods this document describes were developed over roughly two decades, and each addressed a specific shortcoming of its predecessors. This section traces that development. As in any literature review the emphasis is causal: the concern is which earlier limitation each contribution was introduced to remove.

The motivating problem belonged to early computer graphics. Surfaces rendered in the late 1970s and early 1980s needed texture, and the obvious way to supply it, by storing a photograph and wrapping it onto the surface, was expensive in memory and produced visible repetition where the image tiled. Working on imagery for the 1982 film Tron, Ken Perlin sought a way to generate texture by computation instead, and in 1985 he published the result [1]. His noise function was the first practical source of coherent randomness for graphics: a function of position, reproducible, smoothly varying, and cheap enough to evaluate per pixel. It is described in section four.

Two ideas developed nearby were soon combined with it. The first was fractal geometry. Benoît Mandelbrot's account of fractals [2] argued that natural forms, coastlines and mountains and clouds, carry detail at every scale in a statistically self-similar way, and Alain Fournier, Don Fussell and Loren Carpenter showed in 1982 [3] that summing random displacement across many scales produced convincing terrain. Applied to a noise function, this becomes the octave summation of section five, the technique that gives the document its name. The second nearby idea was an alternative construction of the noise function itself: the value noise described by J. P. Lewis in 1989 [4], simpler than Perlin's and the subject of section three.

Perlin's original function, for all its influence, had two defects that became apparent with use. Its interpolation was not smooth enough, producing faint creases along the lattice, and its set of gradient directions introduced a slight axis-aligned bias into the result. In 2002 Perlin returned to the function and corrected both [5], replacing the interpolating curve with one whose second derivative is also continuous and replacing the gradient set with one free of directional bias. A separate defect was cost. Classic Perlin noise interpolates among the corners of a cube, and the number of corners doubles with each added dimension, so the function grew expensive in three and four dimensions. Perlin's simplex noise [6] replaced the cube with a simpler cell whose corner count grows only linearly, and it removed the directional artifacts at the same time.

Later work continued the same pattern of identifying a limitation and repairing it. Steven Worley introduced in 1996 a noise of an entirely different character [7], based on the distance to scattered feature points, which produced cellular and stone-like patterns that the lattice-based functions could not. Robert Cook and Tony DeRose observed in 2005 that noise summed over octaves aliases badly when a textured surface is viewed at a distance, and their wavelet noise [8] was constructed to occupy a controlled band of frequencies and so to minify cleanly. The document treats the central line, from value noise through gradient noise to fractal summation, because that line is the one a reader must hold before any of the variants make sense.

Return to contents

3Value noise

The first construction of coherent noise is value noise, and most of it is contained in the word interpolation. Begin with a lattice, a coarse grid of points, and assign each lattice point a random value between zero and one. The value at a lattice point is not drawn afresh on each request; it is produced by a hash of the point's integer coordinates, so that the same coordinates always yield the same value and the field is reproducible.

To find the noise at a position lying between lattice points, take the values at the four surrounding lattice points and interpolate among them. The frequency control of the figure sets how many lattice cells span the field: a low frequency gives few large cells and broad features, a high frequency many small cells and fine ones.

The interpolation is where the care is required. Joining the lattice values with straight ramps would make the field's brightness continuous but its slope discontinuous, leaving a faint diamond grid pressed into the result wherever the ramps met at an angle. Value noise avoids this by interpolating along a smooth curve, an S-shaped polynomial that arrives at each lattice point with zero slope, so that adjacent cells meet without a crease. The figure shows the result, and it also shows the construction's residual flaw. The brightest and darkest points of the field fall on lattice points and never between them, because every value in the interior of a cell is an average of its corners. That faint lattice bias is what the next section's method was designed to remove.

4Gradient noise

Perlin's gradient noise removes the lattice bias by storing, at each lattice point, not a value but a direction. The stored object is a random unit vector, a gradient, which can be read as the statement that near this point the field increases fastest along this direction.

To evaluate a position, take the four surrounding lattice points. From each, form the vector pointing to the position, and compute its dot product with that lattice point's stored gradient. The dot product is a single number recording how far the position lies in the direction the gradient favours. Interpolate the four such numbers with the same smooth curve that value noise used.

The construction has a property that fixes value noise's flaw. The vector from a lattice point to that same lattice point has zero length, so the dot product there is zero, and gradient noise is therefore pinned to the same mid-value at every lattice point. Its peaks and troughs form between the lattice points, wherever the surrounding gradients happen to agree, rather than being trapped on the grid. The field flows organically and shows no preferred direction. This is the function that, in one refined form or another, has supplied the texture of computer-generated surfaces for four decades. It has one limitation of its own, visible in the figure: every feature in it is roughly the same size, set by the single frequency, whereas natural surfaces carry detail at many scales at once. That is the subject of the next section.

5Fractal noise

A single layer of gradient noise has a single scale of detail. The remedy, drawn from the fractal terrain work of the literature review, is to add the noise function to itself at many scales. Take the gradient noise; add to it a second copy evaluated at twice the frequency and half the amplitude; add a third at four times the frequency and a quarter of the amplitude; and continue. Each layer is called an octave, the term borrowed from music, where an octave is a doubling of frequency.

The construction is known as fractal Brownian motion. The first octave lays down the broad form; the second adds a coarser texture upon it; each further octave adds detail at a finer scale, and because each octave is weaker than the last, the broad form continues to dominate and the fine octaves only roughen it. Two numbers govern the sum: the factor by which the frequency rises at each step and the factor by which the amplitude falls. The conventional choice, frequency doubling and amplitude halving, is used in the figure. The doubling ensures each octave fills detail into the gaps the previous one left; the halving ensures the sum settles to a stable result rather than dissolving into static. That balance is the reason fractal noise resembles the world. It does not imitate any particular natural object; it reproduces the statistical signature, detail spread across scales in a steady falloff, that natural objects share.

6From noise to worlds

A fractal noise field is a grid of numbers between zero and one. It becomes a landscape through a single act of interpretation: the numbers are read as elevation, and each elevation is assigned an appearance. The figure below applies such a mapping. Below a threshold the value is water; just above it, a narrow band of shore; higher, lowland; higher still, rock; at the top, snow.

The noise itself is unchanged from the previous section; only the interpretation differs. That one mapping does a great deal of work. The sea-level threshold turns a continuous field into coastlines, and because the edges of fractal noise are themselves fractal, those coastlines are intricate at every scale. The high band becomes snow-capped peaks only where octaves of detail happened to accumulate. Raising the octave count roughens the coast and sharpens the mountains; changing the seed produces an entirely different and equally plausible continent. The same field, read through different mappings, also serves as a map of temperature, of moisture, or of the placement of vegetation and ore. The large procedurally generated worlds of contemporary games are layers of such mappings over exactly the noise this document has built.

7Conclusion

Procedural noise begins from a deficiency of raw randomness, which has no structure, and ends at a function with exactly the structure a natural surface displays. Value noise supplied coherence by assigning random values to a lattice and interpolating among them along a smooth curve. Gradient noise removed the lattice bias that value noise retained, by storing a direction at each lattice point so that the field's extremes fell between the grid lines rather than on them. Fractal noise summed the function across octaves, each finer and fainter than the last, until the field carried detail at every scale. A mapping from value to appearance turned the result into terrain.

The literature review placed this line of work in its history. It began with Perlin's need to texture a surface without storing an image, drew the octave summation from the fractal-terrain research of the same period, and continued through Perlin's own corrections of his function's interpolation, its directional bias and its cost in higher dimensions. A reader who has followed the argument here holds the question that organises the field: how to manufacture randomness that is, at small scale, not random at all.

Return to contents

RReferences

  1. Perlin, K. (1985). An image synthesizer. ACM SIGGRAPH Computer Graphics, 19(3).
  2. Mandelbrot, B. (1982). The Fractal Geometry of Nature. W. H. Freeman.
  3. Fournier, A., Fussell, D. and Carpenter, L. (1982). Computer rendering of stochastic models. Communications of the ACM, 25(6).
  4. Lewis, J. P. (1989). Algorithms for solid noise synthesis. ACM SIGGRAPH Computer Graphics, 23(3).
  5. Perlin, K. (2002). Improving noise. ACM Transactions on Graphics, 21(3).
  6. Perlin, K. (2001). Noise hardware. In Real-Time Shading (SIGGRAPH course notes); the simplex-noise construction.
  7. Worley, S. (1996). A cellular texture basis function. Proceedings of SIGGRAPH.
  8. Cook, R. and DeRose, T. (2005). Wavelet noise. ACM Transactions on Graphics, 24(3).