Hilbert Curve

DEFINITION

a bijection [0,1] → [0,1]²
built by recursive quadrant subdivision

NOTES

A line that visits every point of a square. Hilbert published it a year after Peano found the first such curve, and Hilbert's version has the useful property that points close together on the line stay close together in the square — which is why it is now used for image tiling, database indexing and heatmap layouts.

PROVENANCE

Origin

D. Hilbert, Mathematische Annalen 38, 1891

Standing

Public domain

Constants

Order n visits 4ⁿ cells

Source

doi:10.1007/BF01199431

HOUDINI · VEX

The same published mathematics as a Detail Wrangle body. Paste it into a Wrangle with Run Over set to Detail; every constant is the published value plus a tweak channel, so Create Spare Parameters gives a slider that starts where the paper does.

// FORMA — PL. 18 · HILBERT CURVE — David Hilbert, 1891
//   a bijection [0,1] → [0,1]²
//   built by recursive quadrant subdivision
// Paste into a Detail Wrangle (Run Over: Detail), no inputs needed.
// Written from the published mathematics, not adapted from any code.
// Constants arrive at their published values. Press the node's Create
// Spare Parameters button and every tweak becomes a slider — starting
// at 0, the published figure, and moving in the constant's own units.
// https://forma-gen.com/#plate=hilbert

float p_order = 6 + chf('order_tweak');       // order · live 2 .. 8

// The plate's own colour: FORMA's FRACTALS accent as a cosine ramp,
// brightest near t = 0 and t = 1, near-black around t = 0.5.
vector forma_ramp(float t){
  return set(
    0.46 + 0.5 * cos(6.28318530718 * (t + 0)),
    0.1389 + 0.151 * cos(6.28318530718 * (t + 0.05)),
    0.1912 + 0.2078 * cos(6.28318530718 * (t + 0.1)));
}

// Hilbert's quadrant subdivision as the standard d → (x, y) bit walk: at
// each scale, two bits of the index pick the quadrant and the lower bits are
// reflected into it. Written with /2 and %2 rather than shifts — the low bit
// of a xor is just parity, and VEX has no << to lean on anyway. Coordinates
// are the n × n lattice cells themselves — scale to taste.
int order = int(rint(p_order));

int n = 1;
for (int g = 0; g < order; g++) n *= 2;
int total = n * n;
int prim = addprim(0, "polyline");
for (int d = 0; d < total; d++){
    int x = 0, y = 0, tt = d;
    for (int s = 1; s < n; s *= 2){
        int rx = (tt / 2) % 2;
        int ry = (tt + rx) % 2;    // low bit of tt ^ rx — xor is parity there
        if (ry == 0){
            if (rx == 1){ x = s - 1 - x; y = s - 1 - y; }
            int tmp = x;  x = y;  y = tmp;
        }
        x += s * rx;  y += s * ry;
        tt /= 4;
    }
    // canvas y runs down; negated so the curve sits as the plate shows it
    int pt = addpoint(0, set(float(x), -float(y), 0.0));
    // colour sweeps the bright lobe of the ramp along the line's own order,
    // which is the bijection the curve exists to exhibit
    float u = float(d) / float(total - 1);
    setpointattrib(0, "Cd", pt, forma_ramp(0.8 + 0.3 * u));
    addvertex(0, prim, pt);
}

AFTER EFFECTS · EXPRESSION

The same published mathematics as a Shape Layer path expression. Paste it onto a Path property; every constant is the published value plus a Slider Control named _tweak, so a bare paste already draws the figure and each slider moves one constant in its own units. Trim Paths is the comet.

// FORMA — PL. 18 · HILBERT CURVE — David Hilbert, 1891
//   a bijection [0,1] → [0,1]²
//   built by recursive quadrant subdivision
// After Effects port — paste onto a Shape Layer's Path property
// (Contents › Shape › Path). Written from the published mathematics, not
// adapted from any code. Constants arrive at their published values; add a
// Slider Control (Effect › Expression Controls) named <k>_tweak and that
// constant moves in its own units, starting at 0 — the published figure.
// The plate's comet and its reveal are Trim Paths; the stroke colour is
// FORMA's FRACTALS accent, #FF4D6A. Animation runs on time.
// https://forma-gen.com/#plate=hilbert

// A missing slider reads 0, so a bare paste already draws the figure.
function forma_tweak(n){ try { return effect(n)("Slider"); } catch (e){ return 0; } }
var p_order = 6 + forma_tweak("order_tweak");     // order · live 2 .. 8

// The frame: the plate's W × H canvas is this comp, with the origin at the
// layer's anchor; canvas y already runs down, as After Effects' does.
var forma_W = thisComp.width, forma_H = thisComp.height, forma_t = time;
var forma_phase = 0.42133405059576035;   // this plate's own fixed phase, as the page has it
function forma_pt(x, y){ return [x - forma_W / 2, y - forma_H / 2]; }

// The Hilbert curve of the given order by the standard distance-to-point
// decoding: at each scale, read two bits, reflect or transpose the quadrant,
// and accumulate. 4^order vertices on a grid filling 0.9 of the frame. The
// page draws it in over ~22 s: Trim Paths, End 0 → 100%.
var order = Math.round(p_order), n = 1 << order, total = n * n;
var s = Math.min(forma_W, forma_H) * 0.9 / n;
var ox = (forma_W - n * s) / 2 + s / 2, oy = (forma_H - n * s) / 2 + s / 2;
var pts = [];
for (var d = 0; d < total; d++){
  var rx, ry, x = 0, y = 0, tt = d;
  for (var sc = 1; sc < n; sc *= 2){
    rx = 1 & Math.floor(tt / 2);
    ry = 1 & (tt ^ rx);
    if (ry === 0){
      if (rx === 1){ x = sc - 1 - x; y = sc - 1 - y; }
      var tmp = x; x = y; y = tmp;
    }
    x += sc * rx; y += sc * ry;
    tt = Math.floor(tt / 4);
  }
  pts.push(forma_pt(ox + x * s, oy + y * s));
}
createPath(pts, [], [], false);