3D Hilbert curves

A JavaScript port of fast LUT-based 3D Hilbert curves from threadlocalmutex.com, illustrated with Zdog.

Hilbert curves establish a mapping between multi-dimensional and one-dimensional space and are widely used in computer science (in particular, for spatial indexing) because they preserve locality well, meaning Hilbert values of points that are spatially close to each other will also be relatively close.

side = 16

coords = Array(4096) // Array of coordinates

mortonIndices = Uint32Array(4096) // Array of Morton indices

transformCurve = (index, bits, lookupTable) => { /* function implementation */ }

hilbertToMortonTable = Uint8Array(96) // lookup table for Hilbert to Morton

compact1By2 = (x) => { /* function implementation */ }

Appendix

// Example implementation of decoding Morton indices into 3D coordinates
coords = [];
for (const c of mortonIndices) {
    const x = compact1By2(c >> 0);
    const y = compact1By2(c >> 1);
    const z = compact1By2(c >> 2);
    coords.push({x, y, z});
}

return coords;

// Convert sequence of Hilbert values into Morton indices
mortonIndices = new Uint32Array(side ** 3).map((v, i) => transformCurve(i, order, hilbertToMortonTable));

// Lookup table for converting a Hilbert value to a Morton index
hilbertToMortonTable = Uint8Array.of(
    48, 33, 35, 26, 30, 79, 77, 44,
    // ... additional values
);

// Extract every 3rd bit from a number to decode a component of a Morton index
compact1By2 = (x) => {
    x &= 0x09249249;
    x = (x ^ (x >> 2)) & 0x030c30c3;
    x = (x ^ (x >> 4)) & 0x0300f00f;
    x = (x ^ (x >> 8)) & 0xff0000ff;
    x = (x ^ (x >> 16)) & 0x000003ff;
    return x;
};

Zdog = require('zdog');