莫顿码与空间填充曲线

莫顿码 (Morton code) 把多维整数坐标的二进制位交错排成一个整数，得到沿"Z 形"路径（Z 序，z-order）访问空间的一维顺序：二维/三维中相近的点在这条曲线上通常也相近。图形学用它做线性 BVH 构建（按莫顿码排序代替空间划分）、纹理内存的 swizzle 布局（提高缓存命中），以及各种空间哈希。

定义

二维坐标 $(x,y)$ 的位记为 $x_i$、$y_i$，莫顿码为 $\cdots y_3x_3y_2x_2y_1x_1y_0x_0$；三维时三个坐标的位轮流交错。PBRT 4e 用每轴 10 位、共 30 位的三维莫顿码，正好放进 32 位整数（7.3.3 节）。

位与空间区域的对应

以 4 位坐标（$x,y\in[0,15]$）、8 位码为例（PBRT 图 7.9）：

• 最高位 $y_3=1$ 等价于 $y\ge8$：点在 $y$ 轴中线以上；
• 次高位 $x_3$ 把 $x$ 轴对半分；$y_3=1,x_3=0$ 时点落在左上四分之一；
• $y_2$ 再把 $y$ 轴分成四段。

一般地，高位相同的一组码对应一个边长为 2 的幂、轴对齐的空间区域。于是在排好序的码数组里，同一区域的点是连续的一段，用二分查找就能找到区间端点。自行穷举验证：8 位码中 $y\ge8$ 的码落在 $[128,255]$，$y\ge8$ 且 $x<8$ 的码落在 $[128,191]$；高 4 位分别是 $[8,15]$ 和 $[8,11]$（PBRT 书中给的就是高 4 位的区间）。

应用

• 线性 BVH（LBVH/HLBVH）：把图元质心量化后算莫顿码、基数排序，按位从高到低二分就得到中点划分的树，构建时间近似线性、易并行，适合 GPU。PBRT 取高 12 位聚类成 $16^3=4096$ 个网格单元，各簇并行建小树，顶层再用 SAH（见 空间数据结构）。
• 纹理存储：交错 $u$、$v$ 的位得到 Morton 序的纹素布局，使二维邻域在内存里更集中（见 硬件深度剔除与纹理单元）。

取舍与坑

• 精度有限：每轴 10 位只有 $2^{10}=1024$ 级。场景尺度跨度很大时，很多图元会量化到同一格；PBRT 习题 7.5 建议改成 64 位整数、63 位莫顿码。另外归一化坐标为 1.0 时乘 $2^{10}$ 得 1024，需要 11 位，实现中要钳制到 1023。
• 只看点：用质心排序时不考虑图元尺寸，大小悬殊的场景建出的树比 SAH 差。Vinkler 等（2017）的扩展莫顿码通过改进坐标到莫顿码的映射来缓解。
• Z 曲线有跳跃：相邻码偶尔对应相距很远的点（Z 形拐角处），局部性不如希尔伯特曲线 (Hilbert curve)，但编码只需位运算，快得多。
• 来源：Morton（1966）IBM 技术报告首次描述；LBVH 由 Lauterbach 等（2009）提出，HLBVH 由 Pantaleoni 与 Luebke（2010）提出（PBRT 4e 第 7 章延伸阅读）。

PBRT 的视角：位交错实现（PBRT 4e B.2.7）

EncodeMorton3() 接受各分量在 $[0,2^{10}]$ 的浮点坐标（转为 10 位整数），LeftShift3() 用一串"移位 + 掩码"把 10 位分散到每 3 位一位：先把第 8、9 位左移 16 位（第 8 位落到最终的第 24 位），再依次处理更低的位，最后三个分量分别左移 2、1、0 位后按位或。EncodeMorton2() 对两个 32 位整数做类似处理。Morton 码在 pbrt 中用于 LBVH 构建。