The Hilbert curve is a continuous space-filling fractal introduced by David Hilbert in 1891. At each iteration n the curve visits every cell of a 2ⁿ × 2ⁿ grid exactly once, and in the limit it passes through every point of the unit square — giving it a fractal dimension of exactly D = 2, matching the plane itself, despite being a single continuous one-dimensional path. Its most important property is locality preservation: points that are close together along the 1D curve index tend to map to points that are close together in space, making it vastly superior to row-major or column-major scans for cache-friendly memory access and geospatial indexing. The same construction generalises to three dimensions, threading a single path through every cell of a 2ⁿ × 2ⁿ × 2ⁿ cube — which is what this simulation renders in real 3D.
This simulation builds the 3D Hilbert curve at order 1 through order 5, colours the path by progress so you can track the space-filling sweep, and lets you orbit the structure freely. You can trace the curve in or scrub through its draw progress to see exactly how the 1D order maps onto the 3D grid.
What makes the Hilbert curve "space-filling"?
A space-filling curve is a continuous surjective mapping from a line segment onto a higher-dimensional region. The Hilbert curve is the limit of a sequence of piecewise-linear approximations; at each order n the curve passes through all cells of the grid (4ⁿ in 2D, 8ⁿ in 3D), and as n → ∞ the path becomes dense in the cube — every point is a limit of curve points. Counterintuitively, this means a 1D object can "fill" a higher-dimensional region without volume, because "filling" here means density, not measure.
How does the Hilbert curve preserve locality?
For a Hilbert curve of order n, if two 1D indices d₁ and d₂ differ by 1, their corresponding coordinates differ by exactly one cell. More formally, the maximum spatial distance between two points with indices within distance k of each other along the 1D curve grows much more slowly than the O(k) worst case for row-major scans. This locality property is exploited in spatial database indexing, CPU cache-oblivious algorithms, and image dithering.
What is the Hilbert curve used for in computing?
The primary applications are spatial database indexing (e.g., GeoHash uses a Z-order variant; PostGIS uses Hilbert ordering for BRIN indexes), cache-oblivious matrix operations, parallel computation load balancing on meshes, and fractal image compression. The curve is preferred over Z-order (Morton) because it has no diagonal jumps — every step moves to an adjacent cell — giving smoother spatial locality, in both 2D and 3D.
The 3D Hilbert curve recursively subdivides a cube into 8 sub-cubes and visits them in a Gray-code order so that consecutive sub-cubes share a face. Each sub-cube is itself a smaller Hilbert curve, but rotated and reflected so that its entry point touches the exit of the previous sub-cube and its exit lines up with the next. The standard implementation applies these per-octant rotations recursively (or equivalently uses Skilling's transpose/Gray-code algorithm) to generate the index → (x, y, z) mapping for all 8ⁿ cells.
Both are space-filling curves, but they subdivide differently. The Hilbert curve divides each square into 4 sub-squares (base-2 grid) and uses a U-shaped path with two reflections at each step. The Peano curve divides into 9 sub-squares (base-3 grid) with an S-shaped scan, and was the first space-filling curve published (Giuseppe Peano, 1890 — one year before Hilbert). Hilbert's version is generally preferred in computing because the power-of-2 grid aligns naturally with binary addressing.
The Z-order or Morton curve is constructed by interleaving the binary representations of the coordinates. It is extremely fast to compute — requiring only bit-interleaving operations — and is used in many spatial indexes including S2 geometry and some GPU texture layouts. However, it has a locality defect: it makes diagonal jumps between quadrants, so clusters of nearby points can map to widely separated 1D indices more often than the Hilbert curve does.
The Hausdorff (fractal) dimension of the 2D Hilbert curve is exactly 2; for the 3D Hilbert curve it is exactly 3. This is computed from the self-similarity: in 3D each step replaces one segment with 8 scaled copies at factor 1/2, so D = log(8)/log(2) = 3. A dimension equal to the embedding space means the curve is as "space-filling" as that region, though it still has zero volume in the Lebesgue measure sense.
At order n the 3D Hilbert curve visits every cell of a 2ⁿ × 2ⁿ × 2ⁿ grid, so it has 8ⁿ points connected by 8ⁿ − 1 segments. Order 1 has 8 points, order 2 has 64, order 3 has 512, order 4 has 4,096, and order 5 has 32,768 points. This simulation caps the order at 5 to keep the vertex count and rendering performance reasonable in the browser.
Yes — the Hilbert curve is a mathematically proven continuous function from [0, 1] onto the unit square (or cube in 3D). The proof uses the fact that each finite-order approximation is uniformly continuous and the sequence converges uniformly, so the limit function is also continuous by the uniform limit theorem. However, the limiting curve is not differentiable anywhere — it has no tangent at any point — making it an example of a continuous-but-nowhere-differentiable function.