问题标签 [z-order-curve]

我目前正在编写一个 opengl 2d 粒子系统，但我遇到了更多需要帮助的一般编程问题。

基本上，我需要一种方法来查找粒子是否可能发生碰撞，即广泛的相碰撞检测。

我已经阅读了大量关于使用 Morton 代码和 kd 树进行空间划分的文章，以便剔除许多不需要进行碰撞测试的点。但是，在我看来，kd 树仅在进行最近邻搜索时才有用。相反，我想获得半径内的所有邻居。关键问题是我想对每一点都这样做。

所以我的问题是：使用我的 Morton 代码创建 kd 树有什么好处，或者排序的 Morton 代码列表就足够了吗？理论上，如果我有一个排序后的 Morton 代码数组，对应于排序后的粒子 id，我可以简单地在 Morton 数组中查看当前粒子周围的元素并检查距离吗？我想我会一直这样做，直到距离大于我定义的半径。

那有意义吗？或者我应该选择某种类型的树结构？

我需要从它的 2 个坐标 x，y 计算平面上一个点的 Z-Index (Morton)。

传统上，这只是通过比特交错来解决。

但是我有边界，我希望该点的 z-index 仅在其位于活动区域内时增加 morton 计数，而在外部时跳过计数。

需要明确的是，4x4 正方形中的典型 z 顺序是：

但是，如果我有一个 3x3 的活动区域，我希望索引计算如下：

如您所见，00-11 四边形已满，02-13 跳过了落在活动区域​​之外的 2 个点的计数，对于 20-31 和 22-33 也是如此。

重要提示：我想在不迭代的情况下执行此操作。

这个问题有已知的解决方案吗？

我正在尝试交错（用于计算 morton 代码）2 个带符号的长数字 x和y（32 位）值

情况1 ：

结果将是：

案例2：

二进制表示是，

对于交错，我只考虑 32 位表示，我可以使用以下代码将 31 位x与 31 位交错y，

上面的代码工作正常，如果我们有x正面和y负面但案例2失败，请帮助我，出了什么问题？负数使用 64 位，而正数使用 32 位。如果我错了，请纠正我。

我已经实现了decode/encode一种将 2d 点转换为各自的morton code.

我正在寻找的是找到最近的邻居（在 a 下min_distance）所以例如这样的：

这可能吗？

我正在为空间索引构建 Morton 数，我有 8 个无符号 16 位数，它们将变成 __int128 数。效率至关重要，因此天真的解决方案（循环遍历所有内容）或构建单独的 8 个 128 位数字太昂贵了。

我正在使用 GCC，目标机器是 64 位但不支持 BMI2。

如何加快计算速度？

我有一个 3D 网格/数组说u[nx+2][ny+2][nz+2]。尾随的 +2 对应于三个维度中每个维度中的两层晕细胞x,y,z。我有另一个允许细化（使用四叉树）的网格，因此我有每个单元格的 morton 索引（或 Z 顺序）。

假设没有细化，这两个网格在物理现实中是相似的（除了第二个代码没有光环单元），我想要找到的是一个q具有 morton id的单元，mid对应的索引是什么i，j以及k3D 网格中的索引。基本上是解码mid或 Z-order 以获得对应i,j,k的u矩阵。

寻找 C 解决方案，但任何其他编程语言的一般注释也可以。

对于前向编码，我遵循 莫顿编码中所示的魔术位方法，使用不同的方法

我希望以快速有效的方式为 Morton Z-Order Encoding 和 Decoding 在 C 中编写两个函数，即。

我之前已经关注了这些问题

如何计算 3d morton 数交错 3 个整数的位

我目前基于 SO 和开源代码的解决方案是

我最近遇到了这个 SO 问题（在尝试使用 2D morton 代码时）：2d morton code encode decode 64bits

据我了解，这不是一个可移植的解决方案，但由于我（将）运行我的代码的每个系统都有 Haswell CPU（甚至在 HPC 集群上）。我的问题：

1. 如何为 3D 系统修改此代码或这些 BMI 指令集是否可用于编码解码 3D 莫顿数？
2. 考虑到我需要在每个时间步解码几百万个莫顿数字并且有数百万个这样的时间步长，使用这些指令是否比我现在使用的标准解决方案更有效。

编辑：对于第一季度，我非常接近解决方案，但仍然无法弄清楚

很明显，掩码是交替的 x 和 y 位。所以对于 3d 我需要得到一个像

我对 64 位 morton 代码的 ^ 标记之前的位有点困惑，只有 x、y 和 z 的前 21 位是 32 位整数应该很重要。

我想在给定空间信息或时空信息的情况下找到点 q 的最近邻居。为此，我想使用基于 Z 阶曲线或希尔伯特曲线的键创建 B 树索引。然而，我发现希尔伯特曲线比 Z 阶更难实现。我的问题是：

在最近邻查询中是否值得在 Z 阶曲线上使用希尔伯特曲线？

我想知道如何交错浮动坐标。这个网站描述了如何做交错部分，但它只适用于整数。

我尝试了以下方法：

纬度 = 5.01，液化天然气 = 6.01

新纬度 = (5.01+90) * 100

newLng = (6.01+180) * 100

但它似乎没有正确的位序列。有人知道将 lat 和 lng 表示为 32 位序列的更好方法吗？

本文解释了如何计算 bigmin 和 litmax（大最小值和小最大值）。

我很难理解第 4 步的措辞，以了解它如何转换为伪代码、C 或 python。

第4步

一个水平分割我们知道我们需要计算最接近yn的分割线的Latitude值。取最小值和最大值的最高有效位，直到它们最初不同的位置 yn，并将其称为 y[1..m] 我们知道在分割线上方的纬度值将被二进制编码为 y[1..m ] 0111... 和 y[1..m] 1000... 转换为 LitMax 和 BigMin 的纬度值。

由于在我们的示例中不同的最重要位是 y4，因此我们的 LitMax 和 BigMin Latitude 值等于 0111 和 1000。

在垂直除法中，我们只需将其反转为 x 位和经度。

我从 coord 转换 z 顺序索引没有问题，反之亦然。

我只是对计算 bigmin 和 litmax 感兴趣，因为它们可以大大加快速度。我已经搜索过，但找不到关于那些特定位掩码操作的详细信息（此处的答案How to use Morton Order(z order curve) in range search?并没有真正涵盖它，链接的 dynamodb 文章也没有） .