Skip to main content

Indexing the World with Morton Codes: How Our Quadtree Finds Overlaps in O(1)

· 6 min read
merca.earth
Team

A new parcel arrives on-chain. Before the protocol writes it to the Index, it must answer one question: does this shape overlap anything already registered? A naive answer is to compare the newcomer against every existing parcel — but that's O(N), and N grows with every registration. On a blockchain, O(N) means gas that grows with the map's popularity. The more successful the protocol, the more expensive it becomes to use.

In our previous post, we showed how dynamic fields make the Index unbounded — the Index itself being a shared object that holds every registered parcel. Now the question is how to query it.

Collapsing Two Dimensions Into One​

Morton codes map 2D coordinates into 1D integers by interleaving the bits of X and Y. The result is a Z-order curve — a path through 2D space where a contiguous range of Morton codes corresponds to a spatial rectangle.

Take x = 5 (0b101) and y = 3 (0b011). Interleaving works bit by bit:

  • Bit 0 of x = 1 → position 0
  • Bit 0 of y = 1 → position 1
  • Bit 1 of x = 0 → position 2
  • Bit 1 of y = 1 → position 3
  • Bit 2 of x = 1 → position 4
  • Bit 2 of y = 0 → position 5

Result: 0b010111 = 23.

No tree structure needed — neighbors are found arithmetically. (Hilbert curves achieve even tighter locality, but they require trigonometric math that can't run inside a Move contract.)

That locality property is what makes the broadphase possible. A rectangular region in 2D space maps to a bounded range of Morton codes, so the algorithm finds all cells in a region by iterating integers — no pointer traversal, no tree walk.

The Code: interleave_n()​

Here's the implementation:

// onchain/protocol/sources/math/morton.move, lines 29-41
public fun interleave_n(x: u32, y: u32, bits: u8): u64 {
    assert!(bits <= 32, EBitsOverflow);
    let mut result: u64 = 0;
    let mut i: u8 = 0;
    while (i < bits) {
        result =
            result
            | ((((x as u64) >> i) & 1) << (i * 2))
            | ((((y as u64) >> i) & 1) << (i * 2 + 1));
        i = i + 1;
    };
    result
}

For each bit position i, the function extracts bit i from x and places it at position 2i in the result, then extracts bit i from y and places it at position 2i + 1. Even-numbered positions hold x bits; odd-numbered positions hold y bits.

The bits parameter controls how many bits to interleave. interleave_n(cx, cy, depth) at depth 3 only interleaves the bottom 3 bits, since depth-3 cells need only 3 bits per axis to address an 8×8 grid.

No lookup tables, no multiplication, no division. Pure bit manipulation — the cheapest operation a Move VM can execute.

The Broadphase: Searching All Depths​

A parcel's natural depth is the coarsest level where its bounding box fits inside a single cell. A city block lands at depth 15 or 16. A national park lands at depth 8. Each parcel lives in exactly one cell — but the broadphase must find parcels at every depth that could overlap the query box.

Here's the traversal:

// onchain/protocol/sources/core/index.move, lines 897-953 (core)
let mut depth: u8 = 0;
while (depth <= index.max_depth) {
    let shift: u8 = index.max_depth - depth;
    let cmin_x = min_gx >> shift;
    let cmax_x = max_gx >> shift;
    let cmin_y = min_gy >> shift;
    let cmax_y = max_gy >> shift;

    let mut cy = cmin_y;
    while (cy <= cmax_y) {
        let mut cx = cmin_x;
        while (cx <= cmax_x) {
            let key = morton::depth_prefix(
                morton::interleave_n(cx, cy, depth),
                depth,
            );
            if (table::contains(&index.cells, key)) {
                // collect parcel IDs from this cell
            };
            cx = cx + 1;
        };
        cy = cy + 1;
    };
    depth = depth + 1;
};

The outer loop runs from depth 0 to max_depth. At each depth, the query box's finest-level grid coordinates shift right by max_depth - depth, projecting the query box onto that depth's coarser grid. At depth 0, the entire world is one cell — shift = max_depth, so every coordinate collapses to 0.

The inner loops walk every cell in the projected range and look up the corresponding Morton key. The depth_prefix function (covered in the previous article) turns (morton_code, depth) into a unique Table key.

The ancestor/descendant discovery is the critical part. A city block's bounding box covers a single cell at depth 15. At depth 4, that same box projects to a single coarse cell — and any continental territory stored there appears in the candidate set. The broadphase finds large parcels that contain small ones, and small parcels that fall inside large ones, without any tree pointers. One bit-shift per depth level does the work.

The traversal is complete by construction. Every depth is checked, every cell in the projected range is looked up — a parcel stored at any depth appears in the candidate set if its cell intersects the query box. No second pass, no missed ancestors.

O(D), Not O(N)​

The outer loop runs max_depth + 1 times. max_depth is 20 — a fixed constant set at Index creation, not a function of how many parcels exist. At each depth, the inner loops cover $(c_{\max x} - c_{\min x} + 1) \times (c_{\max y} - c_{\min y} + 1)$ cells. For typical parcels this is 1–4 cells per depth. A safety cap (MAX_BROADPHASE_SPAN = 1024 per axis) prevents pathological queries from iterating enormous cell ranges.

Each hit is one Table lookup — a single dynamic field read, O(1) in gas.

Total cost: $O(D \times \text{span}^2 \times k)$ where $D = 20$, span is typically 1–4, and $k$ is parcels per cell (typically 1–3). In practice: roughly 50–100 dynamic field reads per registration.

A map with 10 registered parcels and a map with 10 million cost the same gas to query. The Index grows without bound — dynamic fields make that possible — and the broadphase cost stays flat regardless of how many parcels exist.

What Happens Next​

The broadphase returns candidate IDs — parcels that might overlap. AABB intersection rejects candidates whose bounding boxes don't touch. Then the Separating Axis Theorem runs a precise convex collision test on the survivors. If any true overlap exists, registration aborts.

We covered SAT in detail in Geometry as a Blockchain Invariant.

From Coordinate to Answer​

The full path: geographic coordinates → AABB → grid cell range → Morton codes → depth-prefixed Table keys → candidate IDs → SAT collision tests → true overlaps.

Every step is integer arithmetic. No floats, no approximations, no oracles. A deterministic path from coordinate to collision — the same on every validator, in every epoch, for every parcel on Earth.