libmorton: A High-Performance C++ Library for Morton Code (Z-Order Curve) Encoding and Decoding

libmorton is an open-source C++ library designed for efficient computation of Morton codes (also known as Z-Order curves, Lebesgue curves, or Z-Indexes). It provides highly optimized functions for fast conversion between multi-dimensional coordinates (typically 2D or 3D) and one-dimensional Morton indices.

Project Address: https://github.com/Forceflow/libmorton

1. What is Morton Code?

Morton code is a mathematical technique for mapping multi-dimensional data to one-dimensional space. It generates a unique integer index by interleaving the binary bits of coordinate values.

Example (2D)

Convert the 2D coordinates (x=3, y=2) to Morton code:

2. The binary of x = 3 is 011
4. The binary of y = 2 is 010
6. Interleaved bits: starting from the least significant bit, alternate between x and y bits → 0 0 | 1 1 | 1 0 → 001110
8. Result: Morton code is 0b001110 = 14

The key feature of this encoding method is that spatially adjacent points often have similar Morton codes. This makes it very useful in many scenarios that require spatial locality optimization.

2. Core Features of libmorton

libmorton provides Morton encoding/decoding functions for different data types and dimensions, optimized for bit manipulation instructions on modern CPUs (such as the BMI2 instruction set).

Supported Dimensions

• 2D: Encodes (x, y) coordinates into a single integer.
• 3D: Encodes (x, y, z) coordinates into a single integer.

Supported Data Types

• uint32_t (32-bit unsigned integer)
• uint64_t (64-bit unsigned integer)

Core API Function Example

#include "morton.h" // Include main header file

int main() {
    uint32_t x = 3, y = 2;

    // 2D Morton encoding (32-bit)
    uint32_t morton_index_2d = morton2D_32_encode(x, y);
    std::cout << "Morton Code: " << morton_index_2d << std::endl; // Output: 14

    // 2D Morton decoding
    uint32_t decoded_x, decoded_y;
    morton2D_32_decode(morton_index_2d, decoded_x, decoded_y);
    std::cout << "Decoded: (" << decoded_x << ", " << decoded_y << ")" << std::endl;

    // 3D example
    uint32_t z = 1;
    uint32_t morton_3d = morton3D_32_encode(x, y, z);
    std::cout << "3D Morton Code: " << morton_3d << std::endl;

    return 0;
}

3. Performance Optimization

The main advantage of libmorton lies in its superior performance. It achieves high-speed computation through the following methods:

2. Bit-level parallel algorithms: Using lookup tables (LUT) and bit manipulation techniques (such as “magic bits”) to process multiple bits in parallel.
4. BMI2 instruction set support: On CPUs that support the Intel BMI2 instruction set, the library automatically uses PDEP (Parallel Bits Deposit) and PEXT (Parallel Bits Extract) instructions, which can disperse and gather bits in a single instruction, achieving very high speed.
6. Compile-time selection: The library detects the best algorithm path at compile time to ensure good performance across different hardware.

4. Application Scenarios

Morton codes and libmorton have wide applications in the following fields:

1. Spatial Indexing and Databases

• Encoding geographic coordinates (longitude, latitude) into Morton codes for fast range queries and proximity searches.
• Used as part of row key design in NoSQL databases (such as Google Bigtable, Apache HBase) to maintain spatial locality.

2. Computer Graphics

• Texture Mapping: Performing Morton order traversal on textures to improve cache hit rates.
• Ray Tracing: Used to build and traverse BVH (Bounding Volume Hierarchy) or KD-Tree, accelerating intersection calculations.
• Voxel Rendering: Managing the storage and access of 3D voxel data.

3. High-Performance Computing (HPC)

• Using Morton codes for spatial decomposition of grids in distributed memory systems, optimizing data locality and communication patterns.

4. Image Processing

• Performing Morton order scanning on image pixels for specific compression algorithms or analysis.

5. Game Development

• Used for spatial partitioning in Quadtrees or Octrees to manage game objects.

5. How to Use libmorton

Installation and Integration

libmorton is a header-only library, making integration very simple:

2. Download the source code:

   git clone https://github.com/Forceflow/libmorton.git

4. Include the header file: Add the libmorton/include directory to your compiler’s include path.
6. Write your code: In your C++ file, #include "morton.h".

Compilation Requirements

• C++11 or higher.
• Compilers that support built-in functions like __builtin_clz / __lzcnt (GCC, Clang, MSVC all support this).

6. Conclusion

libmorton is an excellent C++ library focused on solving the specific problem of efficient computation of Morton codes. With its simple API, zero-dependency header file design, and extreme optimization for modern CPUs, it is an ideal choice for applications that require frequent conversions between spatial coordinates and one-dimensional indices.

If your project involves spatial data indexing, graphics algorithms, or spatial traversal in high-performance computing, libmorton can significantly enhance the performance of related operations. For most users, simply calling functions like morton2D_encode or morton3D_encode is sufficient, with the underlying complex optimizations handled automatically by the library.