fast-morton

Fast morton encoding/decoding for 2D and 3D coordinates

About

• Port of a subset of libmorton to Typescript
• Supports 2D coordinates with 15-bit components (0 - 32,767)
• Supports 3D coordinates with 10-bit components (0 - 1,023)
• Two methods are provided:
  • Magic Bits (additional discussion here)
  • LUT (Shifted Lookup Table)

Both are described in this blog post.

The Lookup Table method is a little faster, at the cost of some additional code size and runtime memory (a few KB) for the tables.

These methods are exported separately (see below) so that your bundler can strip out the LUTs if you decide not to use them.

Installation

npm install --save fast-morton

Import

Top-level:

import {
  morton2DEncodeMB,
  morton2DDecodeMB,
  morton2DEncodeLUT,
  morton2DDecodeLUT,
  morton3DEncodeMB,
  morton3DDecodeMB,
  morton3DEncodeLUT,
  morton3DDecodeLUT
} from "fast-morton";

Deep import:

// 2D using magic bits
import {
  morton2DEncode,
  morton2DDecode
} from "fast-morton/2d/mb";

// 2D using LUT
import {
  morton2DEncode,
  morton2DDecode
} from "fast-morton/2d/lut";

// 3D using magic bits
import {
  morton2DEncode,
  morton2DDecode
} from "fast-morton/3d/mb";

// 3D using LUT
import {
  morton2DEncode,
  morton2DDecode
} from "fast-morton/3d/lut";

Usage

2D:

import {
  morton2DEncode,
  morton2DDecode
} from "fast-morton/2d/lut";

const mortonCode = morton2DEncode(1, 2); // 9
const coords = morton2Decode(mortonCode); // [1, 2]

3D:

import {
  morton3DEncode,
  morton3DDecode
} from "fast-morton/3d/lut";

const mortonCode = morton3DEncode(1, 2, 3); // 53
const coords = morton3Decode(mortonCode); // [1, 2, 3]

TODO

• Benchmarks comparing Magic Bits, LUT and a naive method
• Support a broader range of coordinate values with the Morton Code output being either 253-1 or BigInt (currently max output is 232-1)

Development/Contributing

Requirements

• Node 18 (to run this repository, due to node:test usage)

Setup

1. Clone the repository
2. Run npm install installs all required dependencies.
3. Run npm run build to build from TypeScript to common JavaScript distribution formats.
4. Run npm test to run all tests.

npm scripts

• npm run test run tests against built output with Node.js' native node:test module. Important: runs against build output so run npm run build beforehand.
• npm run build run build from TypeScript to UMD, CJS, ESM with microbundle
• npm run watch runs build in watch mode with microbundle
• npm run lint will ensure all of the files are prettier-formatted
• npm run format will run prettier formatting option on all the examples files (and tests).
• npm run release, run clean, production build and release with np.

Acknowledgments

• This package is a Typescript port of a subset of libmorton by Jeroen Baert.
• Build/test uses the microbundle-ts-pkg starter by HugoDF

LICENSE

Code is licensed under the MIT License.