Morton codes for .NET

Interleave coordinates.
Preserve locality.

Encode two- and three-dimensional unsigned coordinates as compact Z-order values. The API is allocation-free and selects BMI2 intrinsics when the processor supports them.

View on NuGet Examine memory locality

Two and three dimensions
32-bit and 64-bit codes
LGPL 2.1 licensed

INTERACTIVE ENCODER

Inspect the bit interleave.

Exact integer arithmetic

X Y

Low three bits of X and Y

Method: Encode(x, y)
Decimal: 27
Hexadecimal: 0x0000001B
Binary: 0000 0000 0000 0000 0000 0000 0001 1011

Each coordinate uses its least significant 16 bits.

2D + 3DCoordinate overloads

32 + 64 bitMorton code widths

BMI2Automatic PDEP and PEXT dispatch

0 allocationsStatic value-type API

Spatial locality in linear memory

Store neighborhoods together, then read them together.

A Morton code interleaves coordinate bits so that each aligned octant is a contiguous code interval. When records are sorted or indexed by that code, spatial queries tend to read compact memory ranges instead of widely separated rows.

Encoding is the address key, not the storage policy. Cache locality changes only when payloads are stored, sorted, indexed, or traversed in Morton order. Calculating a code while retaining another layout does not reorganize memory.

01EncodeInterleave X, Y, and Z bits.
02ArrangeOrder records by Morton code.
03TraverseRead spatial ranges sequentially.

INTERACTIVE 3D LATTICE

One 2 × 2 × 2 octant

Drag to rotate

Mouse or touch: drag the lattice to inspect the coordinates.

Exact address comparison

Ready: eight spatial neighbors

Select a naive or Morton address to locate the same coordinate in all three views; select “Run demo” to compare the eight neighbors.

Naive storagenon-linear access for this region · address = x + 4y + 16z

0, 1, 4, 5, 16, 17, 20, 21

Morton-ordered storageaddress = interleave(x, y, z)

0–7

2Naive cache lines

1Morton cache line

Illustration: 8-byte payloads and 64-byte cache lines. A compact address run can reduce cache-line fragmentation and gives a sequential hardware prefetcher a more useful access stream.

LOCAL RANGE

Octants become intervals.

The low octant shown above occupies Morton addresses 0–7. The same coordinates occupy 0, 1, 4, 5, 16, 17, 20, 21 in naïve x-major storage: a non-linear access pattern for this local region.

CACHE BEHAVIOR

Fewer unrelated lines.

Compact ranges can increase useful bytes per fetched cache line and can make sequential prefetch more effective. The actual gain depends on payload size, query shape, and traversal order.

BOUNDARY CONDITION

Locality is hierarchical.

Z-order is not globally distance-preserving. Nearby points can be separated at interval boundaries; the representation favors recursive regions rather than every possible neighborhood.

Defined coordinate capacity

Select the code width for the data domain.

Morton encoding distributes each coordinate across fixed bit lanes. Unsupported high coordinate bits are masked to keep the hot path free of validation branches.

API	Dimensions	Capacity per axis	Morton code
`Encode` / `Decode`	2D	16 bits0–65,535	`uint`
`Encode` / `Decode`	3D	10 bits0–1,023	`uint`
`Encode64` / `Decode64`	2D	32 bitsfull `uint` range	`ulong`
`Encode64` / `Decode64`	3D	21 bits0–2,097,151	`ulong`bit 63 unused

Lane assignment

Adjacent output bits identify adjacent axes.

X occupies bit positions 0, 2, 4, … in two dimensions and 0, 3, 6, … in three dimensions. Y and Z occupy the subsequent positions in each group.

Small surface area

Encode, store, and recover coordinates.

The static API accepts unsigned integers and returns unsigned Morton codes. Decoders write coordinates through out parameters.

No object lifecycle. Call static methods directly.
No managed allocation. Inputs and outputs are value types.
Explicit software path. Fallback methods are available for deterministic comparison.

using Tedd;

uint x = 10;
uint y = 20;

uint code = MortonEncoding.Encode(x, y);
MortonEncoding.Decode(code,
    out uint decodedX,
    out uint decodedY);

ulong code3D = MortonEncoding.Encode64(
    1_000_000, 1_500_000, 2_000_000);

Runtime-selected implementation

One API. Two execution paths.

The dispatcher selects an implementation from processor capability and target framework. The encoded representation remains identical.

Supported x86 and x64 processors

BMI2 intrinsics

Concrete .NET Core and modern .NET assets use PDEP for encoding and PEXT for decoding when BMI2 is available.

PDEPINTERLEAVEPEXT

Portable and non-BMI2 environments

Shift-and-mask software

The portable assets use deterministic bit spreading and compaction. The fallback methods expose this path directly.

SHIFTMASKMERGE

Benchmark methodology Review hypotheses, controls, and interpretation

Broad runtime coverage

Use the package from established and current .NET applications.

NET461.NET Framework 4.6.1Portable software path

NETSTANDARD1.0.NET Standard 1.0Broad compatibility

NETSTANDARD2.0.NET Standard 2.0Broad compatibility

NETCOREAPP3.0.NET Core 3.0BMI2 when supported

NET8.0.NET 8BMI2 when supported

NET10.0.NET 10BMI2 when supported

NuGet package

Add Morton encoding to the project.

Install the current stable package from NuGet.org. Package symbols and XML documentation are included.

TERMINAL dotnet add package Tedd.MortonEncoding

Open NuGet package Browse source

Interleave coordinates.Preserve locality.