Fractals at work

An antenna works best when its size matches the wavelength it handles. The classic example is the quarter-wave monopole, a straight wire a quarter of a wavelength long standing on a ground plane. At 100 MHz, in the FM band, that is 75 centimeters. At 900 MHz it is about 8 centimeters. Phones need to cover several bands at once, and they have to fit the antennas inside a case alongside a battery and a screen.

One way to get a long wire into a short space is to fold it. In the 1990s the radio astronomer and amateur radio operator Nathan Cohen tried folding wires into fractal shapes, and published the idea in 1995 as "Fractal antennas" in Communications Quarterly. A Koch curve is a good folding pattern: each iteration replaces every straight piece with four pieces a third as long, so the wire grows by a factor of 4/3 while the distance between its ends stays fixed. After four iterations a wire is about 3.2 times longer than the straight line it replaces. A Koch monopole resonates at a lower frequency than a straight monopole of the same height, so the same frequency fits into a smaller antenna.

The second property is multiband behavior. Carles Puente and colleagues in Barcelona built antennas shaped like a Sierpinski gasket and showed in 1998 that they resonated at several frequencies spaced by roughly a factor of two, which is the scale factor between the gasket's copies of itself. The big triangle handles the lowest band, the half-size triangle at the feed point the next one up, the quarter-size one the next. A self-similar shape behaves in a similar way at each of its scales.

Fractal antennas did go into products, and Cohen's company holds patents on them. But the claims grew faster than the physics, and later careful work cut them down to size. In 2002 Steven Best compared Koch monopoles with simple meandered and zigzag wires of the same height and total length, and found they performed very similarly: what mattered most was how much wire was packed into how much space, not that the folding was a fractal. Modern phone antennas are an engineering mix of meanders, slots, folded strips and tuning circuits. Fractal shapes are part of that toolbox, not the whole of it.

In 1980 Loren Carpenter, an engineer at Boeing, showed a two-minute film called Vol Libre at the SIGGRAPH computer graphics conference: a flight through mountains that no one had modeled by hand. The mountains were made by a recursive rule. Two years later he and his colleagues at Lucasfilm used the same kind of technique for the "Genesis effect" sequence in Star Trek II: The Wrath of Khan, where a dead planet is transformed into a living one. Also in 1982, Alain Fournier, Don Fussell and Carpenter published the method in Communications of the ACM.

The rule is midpoint displacement. Start with a straight line. Find its midpoint and move it up or down by a random amount. Now you have two lines; do the same to each, but with a smaller random amount. Repeat. Each round halves the segments and shrinks the random kicks by a fixed factor. If that factor is 2^(−H), the finished line is a good approximation to fractional Brownian motion with Hurst exponent H. In two dimensions, the same idea on a grid of squares is the "diamond-square" algorithm.

Midpoint displacement is fast and easy, but not quite right. The points created early never move again, so their positions are special, and in two dimensions faint creases appear along the original grid lines. Mandelbrot made this point himself in a published comment on the 1982 paper. For a lot of work since, the preferred tool has been to build fBm by adding up layers of smooth noise, which has no special points. Both are in the instruments below.

Ordinary Brownian motion is the path of a particle kicked about at random, like a grain of pollen in water. Plot its position along one axis against time and you get a jagged line. In 1968 Mandelbrot and John Van Ness generalized it into a family, fractional Brownian motion, with one knob: the Hurst exponent H, between 0 and 1. It sets how the typical change in height grows with the distance you look across.

The practical recipe used in film and games builds fBm from octaves. Take a smooth random function, called noise, that wiggles on one particular scale. Add a copy squeezed to wiggle twice as fast but at a smaller height, then another twice as fast again and smaller again, and so on. Three numbers control it. Octaves is how many layers you add, which sets the range of scales where the result is fractal. Lacunarity is how much the frequency goes up from one layer to the next, usually about 2. Gain, sometimes called persistence, is how much the height goes down from one layer to the next. Gain and lacunarity together set the roughness: for a true fBm, gain = lacunarity^(−H).

The "noise" in the recipe is usually Ken Perlin's gradient noise, invented in the early 1980s after he worked on the film Tron and published in 1985. It puts a random slope at each point of a grid and blends between them smoothly, so it has no sharp edges and almost all its wiggles are about one grid cell wide. That narrow band is what makes it a good building block: each octave adds detail at one scale and leaves the others alone. "Value noise", which puts random heights at the grid points instead of slopes, is cheaper but blobbier, and its grid shows through more. The terrain instrument has both.

The terrain generator hides a lesson worth pulling out on its own. The Hurst exponent is a dial for roughness, and the dimension D = 2 − H is the same dial read the other way. H = 0.9 gives D = 1.1, a line that is barely more than a line: rolling hills. H = 0.5 gives D = 1.5, a random walk. H = 0.1 gives D = 1.9, a line so jagged it almost shades in the strip it lives in.

There are two common ways to measure D from data, and the instrument below does both. The variogram asks how big the typical height change is across a gap of 1 sample, 2 samples, 4, 8 and so on. On log axes those points line up with slope H. Box counting covers the graph with boxes of shrinking size and counts how many it takes; the slope of that count is D directly. On a perfect fBm the two agree. On real data they often don't quite, which is itself useful information.

Turn the detail levels down and watch the measured dimension fall below the target. With only a few levels, the line is smooth at small scales, so a measurement that reaches down to those scales sees a dimension near 1. That is the computer version of the previous chapter's warning: a fractal is only fractal across the range of scales where its process actually acts.

Michael Barnsley's iterated function systems (Chapter 4) showed that a fern, an image full of detail, could be stored as a couple of dozen numbers: the coefficients of four affine maps. The obvious next question was whether every image could be stored that way. Barnsley and Alan Sloan announced fractal image compression in Byte magazine in 1988 and founded a company, Iterated Systems, to sell it.

The early method needed a person to help find the maps. The breakthrough came from Barnsley's student Arnaud Jacquin, whose 1992 paper made it automatic with "partitioned" iterated function systems. Chop the image into small range blocks. For each one, search the same image for a larger domain block that, shrunk, flipped or rotated, and with its brightness and contrast adjusted, looks like it. Store only the address of that block and the adjustment. The file holds no pixels at all.

To decode, start from any image whatsoever, even random noise, and apply all the stored maps at once. Each map shrinks its domain block, so the whole operation is a contraction, and a contraction has one fixed point that every starting image is drawn toward. After about eight or ten passes the result is a close copy of the original. The fifth walkthrough scene does exactly this on a small test image, with a real encoder and decoder running in your browser.

It worked, and it had a lovely side effect: since the code describes shapes rather than pixels, it can be decoded at a larger size than the original, inventing plausible detail as it goes. But three things held it back. Encoding was slow, because every range block meant searching many domain blocks in eight orientations. Compression quality was in the same general range as JPEG, which had been standardized in 1992 and was free to use, better at some extreme compression ratios and worse at others. And the method was tied up in patents. When wavelet coders, and then JPEG 2000, matched or beat it, there was little reason to choose it. Fractal compression survives mostly as a teaching example and an occasional upscaling trick.

The Hurst exponent is named after Harold Edwin Hurst, a British hydrologist who spent decades studying the Nile to size the reservoirs that became the Aswan High Dam. In 1951 he reported that the river's yearly flows had long memory: wet years clustered with wet years over spans much longer than expected for independent years. His statistic gave about 0.7, where independent years would give 0.5. Many other natural records showed the same. That puzzle was part of what led Mandelbrot to fractional Brownian motion.

Heart rate. The time between heartbeats is never quite constant, and its variation has structure across many time scales. In 1995 Chung-Kang Peng and colleagues introduced detrended fluctuation analysis, a way to estimate a scaling exponent from a series that drifts, and reported that healthy heartbeat intervals showed long-range correlations with an exponent near 1, while some patients with heart failure showed a different pattern. Later work by Ary Goldberger and others described a loss of this complex, fractal-like variability with aging and some diseases. These are real research findings. They are not a diagnostic test: the measures need long, clean recordings, they vary between people and with activity, and a single number says little about a single person. Clinical heart-rate-variability practice still relies mostly on standard time- and frequency-domain measures.

Markets. In 1963 Mandelbrot studied cotton prices and showed that large price changes were far more common than the bell curve allows. Daily returns have "fat tails". Since then, careful studies have settled on a set of stylized facts. The returns themselves have almost no memory: the Hurst exponent of the price path is close to 0.5, so yesterday's direction tells you essentially nothing about today's. But the size of the moves, the volatility, has long memory: calm periods cluster, and so do turbulent ones. Mandelbrot later built multifractal models to capture both. Their value is in describing risk more honestly, how big a bad day can be and how bad days bunch together. They do not predict which way the price will go, and anyone selling fractal charts as a way to call the market is selling something else.

Perlin's 1985 paper, "An Image Synthesizer", did not just introduce noise. It showed what to do with it. Use fBm directly and you have clouds, smoke or dirt. Add up the absolute values of the octaves instead, which he called turbulence, and the result has sharp creases where each octave crosses zero: good for fire and veined rock. Feed turbulence into a sine wave, sin(x + turbulence), and the straight stripes of the sine get pushed around into marble. Wrap the stripes into rings and you get wood. The final walkthrough scene shows four of these.

The advantages are why the method took over visual effects. A procedural texture has no fixed resolution, so it can be sampled at any distance without blurring or repeating. It costs a few lines of code instead of megabytes of image. It wraps itself around any shape in three dimensions, so a block of marble carved into a statue has veins that run through it. And it is controlled by meaningful numbers, so an artist can ask for "rougher" or "larger veins" and get it. Perlin's 1997 Academy Award recognized exactly that: textures that look natural on computer-generated surfaces in film.

The ideas kept developing. Perlin himself followed up with simplex noise in 2001, which is cheaper in higher dimensions, and "improved noise" in 2002. Steven Worley's cellular noise (1996) adds cell-like patterns for stone, scales and skin. F. Kenton Musgrave made terrains with "multifractal" variants where roughness changes with altitude, smooth valleys and craggy peaks, since real landscapes are not one fBm everywhere. Games that build their worlds from a seed, so that the same number always produces the same planet, use the same machinery. Every slider in Instrument 1 has a counterpart in those tools.