问题标签 [z-order-curve]

我在 3D 网格上使用 morton 编码，以便一组点 (x,y,z) 给我一个 morton 编码 M(x,y,z) 的 1D 数组，其中 x,y,z 是整数。对于每个 M(x,y,z)，我的计算还需要网格上的 26 个最近邻，即。M(x-1,y-1,z-1), M(x-1,y-1,z+0), M(x-1,y-1,z+1), M(x-1 ,y+0,z-1)...

我的问题是，我如何直接从 M(x,y,z) 计算这些邻居编码？我知道维基百科有一个二维 8 位整数的解决方案：

M(x,y-1) = ((M(x,y) & 0b10101010) - 1 & 0b10101010) | (M(x,y) & 0b01010101)

3 维网格的等效算法是什么样的？

在优化光线追踪器时，我尝试使用 Morton 空间填充曲线来改善相交数据结构的数据局部性，但我的 3D 空间不是立方的（例如 512x512x256）。所有边都是 2 的幂，但并非所有边的长度都相同。

我一直找不到任何边为 2 次方的非方形莫顿曲线的例子。如果重要的话，我可以保证 x/y 轴的大小相同，只有 z 轴的长度不同。

请注意宽度如何是 2x 高度，但它也可以是 3x 或 4x 或任何其他。我一直无法找到一种方法来做到这一点。

理想情况下，解决方案会很快，因为必须大量计算 Morton 码。所以我的问题是：如何为非立方空间生成空间填充莫顿曲线？这是专门针对 GPU (Cuda) 的。

维度的条件是：
x, y, z 是 2 的幂
x == y
x, y >= z
或者如果更容易
x, y > z

我目前正在玩弄网格化体素块，这是一个N^3的体素值列表。由于在我的用例中，大多数体素将属于同一类型，因此许多邻居将共享相同的值。因此，使用 RLE（运行长度编码）是有意义的，因为它以随机查找（即块中的运行数量）为O(log(n))代价大幅降低了实际存储需求。n同时，我将每个体素位置编码为 z 阶曲线，具体使用 morton 编码。这一切都适用于我的用例，并提供了所需的预期空间减少。

问题在于对各个块进行网格划分。生成网格最多需要 500 毫秒（N=48），这对于流畅的游戏玩法来说太长了。我当前的算法大量借鉴了这里和这里描述的算法。

伪代码算法：

网格生成本身非常快（<<< 1ms）并且不会从优化中获得太多收益，但是构建遮罩本身的成本非常高。正如在下面的跟踪输出中可以看到的，每个mesh_mask_building平均需要约 4 毫秒，每个网格发生 3*N 次！

我的第一个想法是优化这个，是使用块的固有运行并简单地遍历它们并为每个块构建一个掩码，但这没有成功，因为 morton 编码在整个原语中缠绕了很多，因此不会更擅长构建网格。当考虑一个只有一层设置为可见体素的块时，它也将是非常次优的。当前方法生成一个简单的长方体，因为它不关心运行，但在我建议的方法中，每次运行将是单独的并生成更多面。

所以我的问题是，如何使用 morton-run-length 编码来生成网格？

我正在尝试将 Z 阶曲线与 Accumulo 表一起使用。如果我想找到经纬度边界框内的所有点（经度可以穿过 0 度子午线），我将如何使用 Z 曲线来解决这个问题？我已经尝试进行研究以找到类似的示例，但我就是不明白。我了解散布点（例如：（37.892, 161.243）= 013671.829423），但如果有人可以用英语（不是代码）引导我完成使用 z 阶曲线找到所有这些点的步骤，我会这样欣赏！我很绝望。