标签: z-order-curve

我正在寻找一种快速计算3D Morton数的方法.这个网站有一个基于幻数的技巧,可以用于2D Morton数字,但是如何将它扩展到3D似乎并不明显.

所以基本上我有3个10位数字,我想用最少的操作交错成一个30位数.

从32位int解交织比特的最有效方法是什么？对于这种特殊情况,我只关注奇数位,尽管我确信将两个集合的任何解决方案概括为简单.

例如,我想转换0b01000101成0b1011.什么是最快的方式？

编辑:

在这个应用程序中,我可以保证偶数位都是零.我可以利用这个事实来提高速度或减少空间吗？

这个问题:如何解交织比特(UnMortonizing？)有一个很好的答案,可以提取莫顿数的两半中的一个(只是奇数位),但我需要一个解决方案来提取两个部分(奇数位和尽可能少的操作.

对于我的使用,我需要采用32位int并提取两个16位整数,其中一个是偶数位,另一个是奇数位右移1位,例如

input,  z: 11101101 01010111 11011011 01101110

output, x: 11100001 10110111 // odd bits shifted right by 1
        y: 10111111 11011010 // even bits

似乎有很多解决方案使用带有幻数的移位和掩码来生成Morton数(即交错位),例如Binary Magic Numbers的Interleave位,但我还没有发现任何反向(即去交错) .

UPDATE

在重新阅读Hacker's Delight中关于完美洗牌/洗牌的部分后,我找到了一些有用的例子,我改编如下:

// morton1 - extract even bits

uint32_t morton1(uint32_t x)
{
    x = x & 0x55555555;
    x = (x | (x >> 1)) & 0x33333333;
    x = (x | (x >> 2)) & 0x0F0F0F0F;
    x = (x | (x >> 4)) & 0x00FF00FF;
    x = …

我需要以偶数索引落在低位字节中的方式对16位无符号整数进行混洗,奇数索引落在高位字节中.

input:
fedcba98 76543210 (contiguously numbered)

output:
fdb97531 eca86420 (even and odd separated)

我的代码目前看起来像这样:

typedef unsigned short u16;

u16 segregate(u16 x)
{
    u16 g = (x & 0x0001);
    u16 h = (x & 0x0004) >> 1;
    u16 i = (x & 0x0010) >> 2;
    u16 j = (x & 0x0040) >> 3;
    u16 k = (x & 0x0100) >> 4;
    u16 l = (x & 0x0400) >> 5;
    u16 m = (x & 0x1000) >> 6;
    u16 n = (x …

如何在范围搜索中使用Morton Order？从维基中,在"使用一维数据结构进行范围搜索"一节中,

它说

"被查询的范围(x = 2,...,3,y = 2,...,6)由虚线矩形表示.其最高Z值(MAX)为45.在此示例中,值在以增加的Z值方向搜索数据结构时遇到F = 19. ...... BIGMIN(示例中为36).....只搜索BIGMIN和MAX之间的间隔...."

我的问题是:

1)为什么F是19？为什么F不应该是16？

2)如何获得BIGMIN？

3)是否有任何网络博客演示如何进行范围搜索？

在研究粒子相互作用的模拟时,我偶然发现Morton-order(Z-order)(维基百科链接)中的网格索引,这被认为是提供有效的最近邻细胞搜索.我读过的主要原因是内存中空间紧密单元的几乎顺序排序.

处于第一个实现的中间,我无法围绕如何有效地实现最近邻居的算法,特别是与基本的统一网格相比.

1. 给定单元(x,y),获得8个相邻单元索引并计算相应的z索引是微不足道的.虽然这为元素提供了恒定的访问时间,但是要在预定义的表中计算或查找z-index(对于每个轴和OR'ing分开).这怎么可能更有效率？是否正确,按顺序访问数组A中的元素说A [0] - > A 1 - > A [3] - > A [4] - > ...比A顺序更有效[1023] ] - > A [12] - > A [456] - > A [56] - > ......？

2. 我预计存在一种更简单的算法来查找z次序中的最近邻居.顺便说一句:找到邻居的第一个单元格,迭代.但这不可能是真的,因为这只能在2 ^ 4大小的块内很好地工作.然而,存在两个问题:当小区不在边界上时,可以容易地确定该块的第一个小区并且遍历该块中的小区,但是必须检查该小区是否是最近邻居.当细胞位于边界上时,情况更糟,而不是必须考虑2 ^ 5个细胞.我在这里错过了什么？是否有一个相对简单而有效的算法可以满足我的需求？

第1点中的问题很容易测试,但我不太熟悉所描述的访问模式生成的基本指令,并且非常希望了解幕后发生的事情.

在此先感谢任何帮助,参考等...

关于第2点:我应该补充一点,我理解如何为R ^ d中的点云构建Morton有序数组,其中索引i = f(x1,x2,...,xd)是从逐位交织等获得的.我试图理解的是,是否有比下面的天真ansatz更好的方法来获得最近的邻居(这里是d = 2,"伪代码"):

// Get the z-indices of cells adjacent to the cell containing (x, y) 
// Accessing the contents of the cells is irrelevant here
(x, y) \elem R^2 …

如果我有一个数据集,其中键是3D中的点,由3个带符号的64位整数表示.我想使用(排序的)键值存储来存储它们,其中键只是字节数组(但我可以指定一个比较器).我想我可以通过使用位交错将所有这些点转换为字节数组,就像在Z/Morton命令中一样,如在如何计算3D Morton数中那样

除了获取单个点,这可以更简单地完成而无需Morton排序,我想做范围搜索,我在一个与轴对齐的框中搜索.我将A和B分别定义为所有坐标最低的方框角,以及所有坐标最高的对角.

现在我的问题是:

1. 对于在逻辑上介于A和B之间的任何点C,C的Morton数也将介于A和B的Morton数之间吗？(这不是莫顿的命令吗？)

2. 如果1为否,A和B是否可以"舍入"到保证包含C的值？

3. 假设1或2是可能的,搜索返回也指向该框之外,我必须"后过滤"了吗？"错误集"有多大(它取决于搜索的大小或位置)？

4. 整数是否签名的事实会导致问题吗？如果是这样,是否有解决方法？

回顾一下,使用Morton Numbers只是实际问题的一种可能解决方案:当3D点必须映射到一维值时,如何有效地在3D整数空间中进行范围搜索？我希望通过在数据库中执行单个范围选择,使用最小键和最大键来获得A和B之间的所有点,理想情况下,尽可能少地获取框外的点.

我想生产一个32位,64位和128位的morton密钥,具有最佳代码!解决方案是什么？

对于我当前的输入数据，即 3D 中的点，我使用Morton 代码来提高访问点列表时的缓存一致性。

我还有一些其他的 6D 和 7D 数据。对于这些维度，莫顿代码仍然是一种很好的技术吗？或者还有其他的技巧吗？其他空间填充曲线技术比 3D 本身的 Morton 计算更复杂，我想知道人们是否使用 6D/7D 或更高版本的替代技术。

我有一个 2D 点，看起来像这样：

class Point
{
    float m_x, m_y;

public:

    int mortonIndex()
    {
        // what would go here?
    }
};

我知道如何处理整数，但我需要使用浮点数。我还想避免缩放任何特定的网格大小。

维基百科上的相关页面：

莫顿指数，或 Z 阶曲线

如何编码/解码morton代码(z-order)给定[x,y]为32位无符号整数,产生64位morton代码,反之亦然？我确实有xy2d和d2xy,但仅适用于16位宽的坐标,产生32位莫顿数.在网上搜索了很多,但找不到.请帮忙.

第一个函数将[x,y]编码为64位宽的Morton代码,其中x和y是32位宽整数,使用Binary Magic Numbers的Interleave位.

反向功能是什么？

void xy2d_morton_64bits(uint64_t x, uint64_t y, uint64_t *d)
{

    x = (x | (x << 16)) & 0x0000FFFF0000FFFF;
    x = (x | (x << 8)) & 0x00FF00FF00FF00FF;
    x = (x | (x << 4)) & 0x0F0F0F0F0F0F0F0F;
    x = (x | (x << 2)) & 0x3333333333333333;
    x = (x | (x << 1)) & 0x5555555555555555;

    y = (y | (y << 16)) & 0x0000FFFF0000FFFF;
    y = (y | (y << 8)) & 0x00FF00FF00FF00FF;
    y = (y | (y …

第一个函数将 [x, y] 编码为 64 位宽 Morton 代码，其中 x 和 y 是使用二进制幻数交错位的 32 位宽整数。

反向函数是什么？

void xy2d_morton_64bits(uint64_t x, uint64_t y, uint64_t *d)
{
    x = (x | (x << 16)) & 0x0000FFFF0000FFFF;
    x = (x | (x << 8)) & 0x00FF00FF00FF00FF;   
    x = (x | (x << 4)) & 0x0F0F0F0F0F0F0F0F; 
    x = (x | (x << 2)) & 0x3333333333333333;
    x = (x | (x << 1)) & 0x5555555555555555;

    y = (y | (y << 16)) & 0x0000FFFF0000FFFF;
    y = (y …