Chapter 17 · Part V · Color & computer fractals

Orbit traps, distance & light

Escape-time coloring keeps one number per pixel: how many steps the orbit took to leave. But the orbit is a whole journey, and it carries much more. Where did it pass? How fast was it stretching? Which way does the slope face? Ask those questions instead and the same Mandelbrot set comes back woven, outlined, glowing or lit like a relief map.

+1 multiplythe extra complex multiplication per step for the derivative dz′ = 2·z·dz′ + 1, which buys distance estimates and lighting
½× to 2×how far off the distance estimate can be for points near the set, by Koebe's quarter theorem
2the Hausdorff dimension of the Mandelbrot set's boundary (Shishikura, 1998), which is why filaments need special care

Common mix-up: none of these methods changes the fractal. An orbit trap, a distance estimate and a lighting model all paint the same set of points; they only choose different numbers to turn into color. The "3D" look from lighting is a shading trick on a flat picture, not a third dimension.

What escape time throws away

The orbit is the data

Every Mandelbrot picture starts the same way (Chapter 8). Each pixel stands for a complex number c. Start at z = 0, apply z → z² + c again and again, and watch where z goes. The sequence of points it visits, z₁, z₂, z₃ and so on, is the pixel's orbit. If the orbit ever gets farther than 2 from the origin, it is certain to run off to infinity, and the pixel is outside the set.

Classic escape-time coloring (Chapter 15) records only when that happened. A pixel that escaped on step 17 gets color 17. The smooth iteration count improves on that by reading how far past the bailout circle the last point landed, which turns the integer into a continuous number and removes the bands. Either way, the rest of the journey is thrown away: the dozens or hundreds of points the orbit visited before it left, or forever, if it never leaves.

Those points are full of structure. Orbits from neighboring pixels are nearly identical, so any smooth summary of the orbit gives a smooth image. But orbits also change character abruptly at the boundary of the set and inside every miniature copy, so any summary of the orbit also inherits the fractal's detail. That combination, smooth almost everywhere but structured where it matters, is exactly what a good coloring wants.

So a fractal renderer can be seen as a three-stage pipeline. First, iterate: compute the orbit. Second, summarize: collect some number or numbers from it, such as the escape step, the smallest distance to a shape, an average of some quantity, or the derivative. Third, map: turn those numbers into a color, through a palette (Chapter 16) and perhaps a lighting model. This chapter is about the middle stage, and the many things you can choose to summarize.

color = palette( summary( z₁, z₂, z₃, … ) )
Every method in this chapter has this shape. Escape time is the summary "the index of the first point outside radius 2". Everything else is a different choice of summary.
Catching the orbit

Orbit traps

An orbit trap is a shape placed somewhere in the complex plane. As each pixel's orbit hops around, you measure how close it comes to the shape, and keep the smallest distance. That minimum is the pixel's color value. Pixels whose orbits brush right past the trap get one end of the palette; pixels whose orbits never come near get the other.

The shape is entirely up to you, and it shows. A point trap measures distance to a single point; it paints bright spots and soft round blobs, and because the dynamics copy the neighborhood of the trap all over the picture, each blob is a distorted image of a disc. A line trap measures distance to a straight line and fills the picture with filaments and ribbons. A cross, two perpendicular lines, combines both directions into a weave. A circle trap measures distance to a ring, not a center, and fills the set with rings and eyes.

Traps work inside the set as well as outside. A pixel inside never escapes, but its orbit still wanders, usually settling into a cycle, and the smallest distance along that wandering is still a perfectly good number. That is why orbit-trap pictures are often colored all the way through, where an escape-time picture just paints the interior black.

The idea is older than its name. Peitgen and Richter's The Beauty of Fractals (1986) showed interiors colored by how close each orbit came to the origin, which is a point trap at 0. The DOS program Fractint later offered those two styles as inside-coloring options called bof60 and bof61, after the pages of the book where they appeared: one colors by the size of the closest approach, the other by the step on which it happened.

trap value = min over n of dist( zₙ , T )
Walk the orbit, measure each point's distance to the trap shape T, keep the smallest. Distance to a point is |zₙ − p|; to a circle of radius r it is ||zₙ − p| − r|; to a line it is the perpendicular distance.

More than one number from a trap

The minimum distance is the obvious summary, but a trap can report more. When the orbit made its closest approach, where on the trap was it? The angle of the closest point around the trap's center gives a value that wraps around, perfect for a cyclic palette. When did it happen? The step number of the closest approach separates orbits that were caught early from those caught late, which tends to paint the picture in nested layers. And if the trap has several parts, which part caught the orbit? Color by that and a cross splits into two interleaved families of filaments, one for each arm.

These choices can be mixed. A common recipe takes the angle or the part for the hue and the distance for the brightness, so the image shows both what caught each orbit and how tightly.

Go deeper: why the trap's shape gets copied everywhere

The map z → z² + c is holomorphic: on a small scale it acts like a rotation and a uniform scaling, so it preserves angles and small shapes. Near any pixel, the function "where is the orbit after n steps", written zₙ(c), is also holomorphic, and over a tiny patch of pixels it behaves almost like multiplication by its derivative.

So if the n-th orbit point of some pixel falls inside the trap, nearby pixels' n-th points fall in a slightly rotated, slightly shifted, uniformly scaled patch around it. Pulled back to the picture, the trap appears as a small, rotated, shrunken copy of itself. Every pixel whose orbit hits the trap on some step carries such a copy, at the scale set by how fast the orbit was stretching on that step. That is why a circle trap fills the set with little circles that shrink toward the boundary, and why distorted copies pile up wherever the dynamics compress the most.

Renderers such as Ultra Fractal take this to its conclusion with image traps: the trap is a bitmap, and the orbit's position inside the trap's frame is used as texture coordinates to look up a pixel of the image, which then appears, distorted and repeated, throughout the fractal.

Instrument 1

An orbit-trap renderer

A real renderer: every pixel's orbit is iterated, and its distance to the trap is measured at every step. Pick a trap shape. Drag the round handle to move the trap and watch the picture rebuild (a fast low-resolution pass while you drag, then the full picture). Tap anywhere else to draw that pixel's orbit, with its closest approach to the trap marked. Then change what the color means: the distance, the angle of the closest point, the step it happened on, or which part of the trap caught it.

Trap–
Probe orbittap the picture
Closest approach–
Render–

Distances are in the units of the complex plane. Changing the width or the coloring only re-shades stored numbers, so it is instant; moving, resizing or reshaping the trap re-iterates every orbit. Iterations rise automatically as you zoom.

Smooth relatives

Stalks, triangles and stripes

Pickover stalks, named after Clifford Pickover, who popularized them, are a cross trap in disguise. Put the two lines on the real and imaginary axes, color only the pixels whose orbits came within a small distance of either axis, and thin glowing stems sprout from every bulb of the set, curling into the spirals of the valleys. In the instrument above, the "Pickover stalks" button sets that up: a cross at the origin with a narrow width.

Traps take a minimum, and a minimum is jumpy: a tiny change in c can hand the record to a different step. A different family of methods takes an average instead. Average some quantity over the whole orbit and the result is smooth, because every step contributes a little and no single step dominates. Two averages have become standards.

The triangle inequality average, usually credited to Damien M. Jones, who wrote it for the Ultra Fractal program, uses a fact from school geometry. For the step zₙ = zₙ₋₁² + c, the size of the result can be no smaller than the difference of the sizes of the two pieces and no larger than their sum. Where in that range |zₙ| actually falls depends on the angle between zₙ₋₁² and c, so it is a number between 0 and 1 that tracks the geometry of each step. Averaged over the orbit, it paints soft, layered folds outside the set.

The stripe average, introduced by Jussi Härkönen in his 2007 thesis on smooth coloring, averages ½·sin(k·arg zₙ) + ½, a value that rises and falls with the angle of each orbit point. Its picture is a set of stripes that follow the field lines running out from the set, like the grain in a polished stone; the whole number k sets how many stripes there are.

tₙ = ( |zₙ| − mₙ ) / ( Mₙ − mₙ ), mₙ = | |zₙ₋₁²| − |c| |, Mₙ = |zₙ₋₁²| + |c|
The triangle-inequality step value: 0 when zₙ₋₁² and c point in opposite directions, 1 when they line up. The color is the average of tₙ over the orbit.
Go deeper: why averages need one more interpolation

An average over an escaping orbit has a hidden step: the number of terms. A pixel that escapes after 20 steps averages 20 values; its neighbor that escapes after 21 averages 21. That jump in the count puts a faint seam where the escape count changes, the same bands that plain escape time has.

The fix borrows the fractional part of the smooth iteration count (Chapter 15). Compute the average both with and without the last term, then blend between the two using that fraction. Because the fraction runs continuously from 0 to 1 across each band, the seams disappear. Härkönen's thesis works this out for both averages, and adds a third, the curvature average, which averages how sharply the orbit turns at each step.

Averages are also cheap. Each step adds one value to a running total, and only the last term or two need remembering, so the cost is a few extra operations per iteration, with no extra memory per pixel.

How far is the edge?

Distance estimation

Here is a problem every Mandelbrot renderer runs into. The set is connected, as Douady and Hubbard proved in 1982, so the little copies of it are joined to the main body by filaments. Those filaments are far thinner than a pixel. A pixel is sampled at one point, and that point almost always misses the filament, so escape time reports "outside" and the filament vanishes. Zoomed-out pictures look like a main body with islands floating around it, which is wrong.

The cure is to ask a different question: not "is this point in the set?" but "how far is this point from the set?" If the answer is less than half a pixel, something of the set passes through the pixel, even if the sample point missed it, and the pixel can be painted as boundary. That turns the invisible filaments into crisp one-pixel lines.

The answer comes from the derivative. Alongside the orbit zₙ, keep track of how fast zₙ changes as c changes: the derivative z′ₙ = dzₙ/dc. Differentiating zₙ₊₁ = zₙ² + c with the chain rule gives its own little recurrence, which starts at 0 and costs one extra complex multiplication per step.

z′ₙ₊₁ = 2·zₙ·z′ₙ + 1, z′₀ = 0
The derivative of the orbit with respect to c. Update it with the old value of zₙ, before zₙ itself is updated. It grows enormous near the set, because there tiny changes in c make a huge difference to where the orbit ends up.
d ≈ |zₙ| · log|zₙ| / |z′ₙ|
The distance estimate, using the last orbit point once it has escaped (natural log). Near the set, the true distance to the set lies between d/2 and 2d. Use a large bailout radius, a few hundred or more, so zₙ has really settled into its escape.

Read the formula as a ratio. Near the set, orbits escape slowly and the derivative is huge, so d is small. Far away, orbits escape fast with a modest derivative, and d is large. The logarithm and |zₙ| correct for how far past the bailout the orbit happened to land.

Once every pixel knows its distance, several things become easy:

  • Crisp boundaries. Paint every pixel with d under about a pixel's width as ink and the rest as paper. The result is a clean line drawing of the set with every filament connected, the look of the classic black-and-white Mandelbrot plates.
  • Glow. Map distance through a falloff, bright near the set and fading with distance, and the set seems to emit light. Because d is measured in pixels, the glow has the same width at every zoom.
  • Smarter rendering. A pixel with a large distance can be filled without further work, which some renderers use to skip blank regions, and a distance below a threshold can trigger extra samples for anti-aliasing exactly where the edges are.
  • 3D fractals. The same idea in three dimensions lets a ray take safe steps of size d toward a Mandelbulb without ever passing through it. That is ray marching, the subject of Chapter 14.

The method is old. It appears as the DEM/M algorithm in The Science of Fractal Images (1988), edited by Peitgen and Saupe, where it is usually credited to an argument of John Milnor's. It produced some of the first pictures to show the hairs and filaments correctly.

Go deeper: where the formula comes from

Douady and Hubbard's proof of connectedness built a function on the outside of the set called the potential, or Green's function: G(c) = lim log|zₙ| / 2ⁿ. Think of the set as an electrically charged conductor. G is the electrostatic potential around it: zero on the set and growing smoothly outward. Its level curves are the smooth "equipotential" loops you see in banded escape-time pictures once you smooth them, and its gradient lines are the field lines, the external rays.

For any smooth function that is zero on a set, the value divided by the size of its gradient, G / |∇G|, is a first guess at the distance to where it vanishes: how far you would have to walk downhill at the current slope. Substitute the formula for G after n steps, and the 2ⁿ factors cancel, leaving |zₙ| log|zₙ| / |z′ₙ|.

The guarantee comes from complex analysis. Douady and Hubbard showed that the outside of the set can be mapped conformally onto the outside of a disc. Koebe's quarter theorem limits how much such a map can distort distances, and that turns the guess into firm bounds: in the limit near the set, the true distance lies between ½ and 2 times the estimate. Milnor's Dynamics in One Complex Variable works through the details. A factor of two either way is plenty for drawing: it decides correctly which pixels the boundary passes through, give or take a pixel.

Shading a flat picture

Light from the potential

The potential G is a smooth surface over the plane: low at the set, rising outward. Treat it as a height map, the way a relief map treats elevation, and you can light it. That is the idea behind the embossed, sculpted look of many modern Mandelbrot renders: the picture is still flat, but each pixel is shaded as if it were a tilted patch of surface catching a lamp.

Shading needs a normal, the direction a surface faces, and for a height map the normal comes from the gradient. The gradient of G points straight away from the set, and its direction is available for free from numbers we already have: it is the direction of the complex number zₙ / z′ₙ. Normalize that to unit length, give it a fixed upward component that sets how steep the relief looks, and you have a 3D normal for every pixel outside the set.

u = (zₙ / z′ₙ) / |zₙ / z′ₙ|, N = normalize( u.re, u.im, h ), brightness = max(0, N · L)
The direction u points away from the set; h controls how deep the relief looks; L is the direction toward the light. The dot product is Lambert's cosine law: a surface facing the lamp is bright, one turned away is dark.

The light direction is two angles. The azimuth says which compass direction the light comes from; the elevation says how high it is above the horizon. A low light rakes across the surface and exaggerates every bump; a light overhead flattens everything. Because the gradient direction swings all the way around each bulb and each mini-brot, every one of them gets a lit side and a shadowed side, and the eye reads that as shape. A small specular highlight, the shiny spot where the surface reflects the lamp straight back, adds to the impression of a glossy material.

This is normal mapping, the same trick games use to make a flat wall look bricked: James Blinn's 1978 paper on simulating wrinkled surfaces showed that perturbing the normal, without moving the surface, is enough to fool the eye. Here there is no surface at all, only a field of normals computed from the orbit. Combine it with the palette from the smooth count, and the bands of color seem to drape over a landscape. Combine it with a distance-estimate outline and the filaments read as ridges.

Because the normal is normalized, the steepness is the same everywhere; only its direction varies. That is part of why the look is so even. Some renderers instead let the steepness depend on the size of the gradient, or use the stripe average as the height, which gives ridged, carved effects.

Go deeper: why z / z′ is the gradient direction

After n steps, G ≈ log|zₙ(c)| / 2ⁿ. For any holomorphic function f, the gradient of log|f|, written as a complex number, is the complex conjugate of f′/f. That points the same way as f / f′. To see it, write both over real denominators: conj(f′/f) = f·conj(f′) / |f|², and f/f′ = f·conj(f′) / |f′|². Same numerator, different positive denominators, same direction.

So the direction of steepest climb of the potential at pixel c is the direction of zₙ/z′ₙ, and the 2ⁿ only scales its length, which we throw away anyway. The derivative that powers distance estimation powers lighting too.

Instrument 2

A lighting lab

Both pictures come from the same orbits. On the left, plain escape time: color by the step on which each orbit left (or by the smooth count, if you switch it). On the right, the same pixels using the derivative: a normal-mapped light, a distance-estimate glow, a crisp distance-estimate outline, or light and outline together. Drag the dot on the dial to move the light: around the dial is azimuth, toward the center is higher elevation. Tap either picture to zoom in there; hover or touch to read one pixel's numbers.

Plain escape time (banded)
Distance + light
Pixel chover a picture
Escape step · smooth ν–
Distance estimate–
Inside: period · |λ|–

Bailout radius 1,000 so the smooth count and the distance estimate are accurate. Light, relief, width and palette only re-shade stored numbers; zooming re-iterates. The distance readout is in screen pixels.

Coloring the interior

Inside: period and multiplier

Escape-time pictures leave the inside of the set black, because inside there is nothing to count: those orbits never leave. But they do something else that is just as informative. Almost every point inside the set belongs to a hyperbolic component, a bulb or a cardioid, and in each component the orbit settles into a repeating cycle of a fixed length. That length is the component's period. The main cardioid has period 1: the orbit settles onto a single fixed point. The big disc to its left has period 2. The bulbs on top and bottom have period 3, and so on, following the rules of Chapter 8.

To color by period, iterate long enough for the orbit to settle, remember where it is, and keep iterating until it comes back to that point. The number of steps is the period. Give each period its own color and the interior becomes a map of the set's anatomy: every bulb and every mini-brot's cardioid wears the color of its cycle length. Near the boundaries, orbits settle very slowly, and a renderer with a fixed iteration budget gives up and reports "unknown"; you can see that as a dark rim around each bulb in Instrument 2.

The cycle carries a second number. Multiply together the derivative of the map, 2z, at each point of the cycle and you get the cycle's multiplier, written λ. Its size says how strongly the cycle attracts nearby orbits. At a component's center |λ| = 0, and the orbit hits the cycle exactly; at the component's edge |λ| = 1, and the cycle is about to lose its grip, which is exactly where the next bulb is born. Coloring by |λ| shades each component like a dish, darkest at the center and brightest at the rim.

λ = 2z₁ · 2z₂ · … · 2zₚ, |λ| < 1 inside a period-p component
The multiplier of the attracting cycle z₁ … zₚ. For the main cardioid it has a closed form, λ = 1 − √(1 − 4c); for the period-2 disc, λ = 4(c + 1). The instrument uses those two shortcuts and computes the cycle for everything else.
Go deeper: the multiplier is a coordinate

The multiplier does more than shade. Inside each hyperbolic component it is a perfect coordinate: as c moves over the component, λ moves over the unit disc exactly once. For the main cardioid this is easy to write down: c = λ/2 − λ²/4. Put λ on the unit circle, at angle 2π·p/q, and you land at the point where the period-q bulb is attached. That is why the bulbs around the cardioid are arranged by rational angles.

The centers, where λ = 0, are the parameters for which 0 itself lies on the cycle. They are the solutions of zₚ(c) = 0: the polynomial you get by iterating p times from 0. Its degree is 2p−1 and, by a result usually credited to Gleason, all of its roots are distinct, so it has exactly that many centers for components whose period divides p. Instrument 3 below makes those roots visible.

There is also an interior distance estimate, which does for the inside of each component what the exterior estimate does for the outside, using the derivative of the cycle with respect to both z and c. It is more involved and is left out of the instruments here.

A different idea

Domain coloring

One more coloring method turns up in the same conversations but answers a different question. Domain coloring is a way to draw any complex function f, not a way to color an orbit. You cannot graph a complex function the usual way, because input and output are each two-dimensional and the graph would need four dimensions. So instead, color each input point by its output: the hue comes from the angle of f(z), and the brightness from its size, often with rings at each doubling.

In a domain-colored picture, zeros of f are the points where every hue meets, like the North Pole on a globe where all time zones meet; the colors go around once for a simple zero and twice for a double one. Poles look the same with the colors going the other way. The name is usually credited to Frank Farris; Elias Wegert's book Visual Complex Functions develops the closely related "phase portraits" in depth.

It is not an escape-time method, but it does meet the Mandelbrot set. Apply it to the polynomial zₚ(c), the orbit's p-th point seen as a function of c, and the zeros it reveals are exactly the centers of the bulbs. Instrument 3 does that.

Degree of zₚ(c)–
Zeros = centers with period dividing p–

Instrument 3. Hue is the angle of zₚ(c), red at angle 0, going through yellow, green, cyan, blue and magenta counter-clockwise. Bright and dark rings mark each doubling of |zₚ(c)|. Count the points where every color meets: there are 2p−1 of them.

Side by side

Which summary, for which look

MethodWhat it keeps from the orbitExtra costThe look
Escape timeThe step it left onNoneBands of color around the set; black inside
Smooth countStep, plus how far past the bailoutOne log per pixelContinuous gradients, no bands
Orbit trapClosest approach to a shape (and where, when, which part)A distance per stepCopies of the trap everywhere; color inside too
Pickover stalksClosest approach to the axesTwo comparisons per stepThin stems from the bulbs
TIA / stripesAn average over every stepA few operations per stepSoft folds or field-line stripes
Distance estimateThe derivative dz/dcOne complex multiply per stepCrisp connected outlines, glow
Normal-mapped lightThe direction of z / z′Same derivative, plus shadingEmbossed relief
Period / multiplierThe final cycleUp to a cycle's length more stepsInterior mapped by bulb
Domain coloringNot an orbit summary: the value of a functionOne function evaluationHue wheels around zeros and poles

In JellyDazzle, whatever number a fractal mode computes is looked up in the live palette, which the C key changes; Chapter 16 covers that side.

Cheat sheet

Terms from this chapter

Orbit
The sequence of points z₁, z₂, z₃, … visited by repeatedly applying the map from a starting point.
Coloring function
The rule that summarizes an orbit as a number, which a palette then turns into a color.
Orbit trap
A shape in the plane; a pixel is colored by how close its orbit comes to it.
Pickover stalks
A cross-shaped trap on the two axes with a narrow width, giving stems that grow from the bulbs.
Triangle inequality average
The average, over the orbit, of where |zₙ| falls between its triangle-inequality limits.
Stripe average
The average of ½ sin(k·arg zₙ) + ½ over the orbit; draws stripes along the field lines.
Derivative z′
dzₙ/dc, tracked by z′ → 2·z·z′ + 1. Measures how sensitive the orbit is to the pixel.
Distance estimate
|z| log|z| / |z′|: an estimate of the distance to the set, good to a factor of two.
Potential
The Green's function G = lim log|zₙ| / 2ⁿ: zero on the set, rising smoothly outward.
Normal mapping
Shading a flat picture with per-pixel surface directions, here from the gradient of the potential.
Azimuth / elevation
The compass direction of the light, and its height above the horizon.
Period
The length of the cycle an interior orbit settles into; constant across each bulb.
Multiplier λ
The product of 2z around the cycle. |λ| is 0 at a bulb's center and 1 at its edge.
Domain coloring
Drawing a complex function by coloring each input by the angle and size of its output.
Where this comes from

Sources