XYZQuadkey

XYZQuadkey is a hierarchical spatial indexing concept designed to encode three-dimensional coordinates within a cube using an octree-like subdivision. Similar in spirit to the 2D QuadKey used in map tiling, XYZQuadkey produces a unique, compact string key by recording the octant chosen at each refinement level. The approach is intended for organizing voxel data, 3D GIS, and real-time rendering caches where fast hierarchical queries and prefix operations are valuable.

Encoding and structure: At each level, the cube is subdivided into eight equal subcubes (octants). The octants are assigned indices 0 through 7 based on the bits of the coordinate at that level: octantIndex = (xBit<<2) | (yBit<<1) | zBit, where xBit, yBit, and zBit are the bits of the coordinates corresponding to the current refinement level. To form the XYZQuadkey, a maximum depth D is chosen, and for level i from 0 to D-1 the corresponding bits are extracted (typically from most significant to least significant) to compute an octantIndex, which is then appended as a single decimal digit. The resulting string length is D, and the path encodes the voxel's location within the D-level grid.

Applications and characteristics: XYZQuadkey supports efficient hierarchical queries, neighbor discovery, and level-of-detail management in 3D datasets. It is particularly suitable for volumetric data, 3D geographic information systems, gaming engines, and simulations that benefit from compact, human-readable keys and straightforward prefix-based filtering. Compared with linearized 3D space encodings like Morton/Z-order, XYZQuadkey emphasizes hierarchical locality and readability, at the potential cost of non-uniform spatial ordering.

See also: QuadKey, Z-order curve, octree indexing.