0

我有一个 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 解决方案，但任何其他编程语言的一般注释也可以。

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

4

1 回答 1

2

莫顿编码只是交错两个或多个组件的位。

如果我们按照重要性递增的顺序对二进制数字进行编号，使得无符号整数中的最低有效二进制数字为 0（并且二进制数字i的值为 2 i），那么N的分量k中的二进制数字i对应于二进制数字（i N + k ) 在莫顿代码中。

以下是编码和解码三分量 Morton 码的两个简单函数：

#include <stdlib.h>
#include <inttypes.h>

/* This source is in the public domain. */

/* Morton encoding in binary (components 21-bit: 0..2097151)
                0zyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyx */
#define BITMASK_0000000001000001000001000001000001000001000001000001000001000001 UINT64_C(18300341342965825)
#define BITMASK_0000001000001000001000001000001000001000001000001000001000001000 UINT64_C(146402730743726600)
#define BITMASK_0001000000000000000000000000000000000000000000000000000000000000 UINT64_C(1152921504606846976)
/*              0000000ccc0000cc0000cc0000cc0000cc0000cc0000cc0000cc0000cc0000cc */
#define BITMASK_0000000000000011000000000011000000000011000000000011000000000011 UINT64_C(844631138906115)
#define BITMASK_0000000111000000000011000000000011000000000011000000000011000000 UINT64_C(126113986927919296)
/*              00000000000ccccc00000000cccc00000000cccc00000000cccc00000000cccc */
#define BITMASK_0000000000000000000000000000000000001111000000000000000000001111 UINT64_C(251658255)
#define BITMASK_0000000000000000000000001111000000000000000000001111000000000000 UINT64_C(1030792212480)
#define BITMASK_0000000000011111000000000000000000000000000000000000000000000000 UINT64_C(8725724278030336)
/*              000000000000000000000000000ccccccccccccc0000000000000000cccccccc */
#define BITMASK_0000000000000000000000000000000000000000000000000000000011111111 UINT64_C(255)
#define BITMASK_0000000000000000000000000001111111111111000000000000000000000000 UINT64_C(137422176256)
/*                                                         ccccccccccccccccccccc */
#define BITMASK_21BITS  UINT64_C(2097151)


static inline void morton_decode(uint64_t m, uint32_t *xto, uint32_t *yto, uint32_t *zto)
{
    const uint64_t  mask0 = BITMASK_0000000001000001000001000001000001000001000001000001000001000001,
                    mask1 = BITMASK_0000001000001000001000001000001000001000001000001000001000001000,
                    mask2 = BITMASK_0001000000000000000000000000000000000000000000000000000000000000,
                    mask3 = BITMASK_0000000000000011000000000011000000000011000000000011000000000011,
                    mask4 = BITMASK_0000000111000000000011000000000011000000000011000000000011000000,
                    mask5 = BITMASK_0000000000000000000000000000000000001111000000000000000000001111,
                    mask6 = BITMASK_0000000000000000000000001111000000000000000000001111000000000000,
                    mask7 = BITMASK_0000000000011111000000000000000000000000000000000000000000000000,
                    mask8 = BITMASK_0000000000000000000000000000000000000000000000000000000011111111,
                    mask9 = BITMASK_0000000000000000000000000001111111111111000000000000000000000000;
    uint64_t  x = m,
              y = m >> 1,
              z = m >> 2;

    /* 000c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c */
    x = (x & mask0) | ((x & mask1) >> 2) | ((x & mask2) >> 4);
    y = (y & mask0) | ((y & mask1) >> 2) | ((y & mask2) >> 4);
    z = (z & mask0) | ((z & mask1) >> 2) | ((z & mask2) >> 4);
    /* 0000000ccc0000cc0000cc0000cc0000cc0000cc0000cc0000cc0000cc0000cc */
    x = (x & mask3) | ((x & mask4) >> 4);
    y = (y & mask3) | ((y & mask4) >> 4);
    z = (z & mask3) | ((z & mask4) >> 4);
    /* 00000000000ccccc00000000cccc00000000cccc00000000cccc00000000cccc */
    x = (x & mask5) | ((x & mask6) >> 8) | ((x & mask7) >> 16);
    y = (y & mask5) | ((y & mask6) >> 8) | ((y & mask7) >> 16);
    z = (z & mask5) | ((z & mask6) >> 8) | ((z & mask7) >> 16);
    /* 000000000000000000000000000ccccccccccccc0000000000000000cccccccc */
    x = (x & mask8) | ((x & mask9) >> 16);
    y = (y & mask8) | ((y & mask9) >> 16);
    z = (z & mask8) | ((z & mask9) >> 16);
    /* 0000000000000000000000000000000000000000000ccccccccccccccccccccc */
    if (xto) *xto = x;
    if (yto) *yto = y;
    if (zto) *zto = z;
}


static inline uint64_t morton_encode(uint32_t xsrc, uint32_t ysrc, uint32_t zsrc)
{
    const uint64_t  mask0 = BITMASK_0000000001000001000001000001000001000001000001000001000001000001,
                    mask1 = BITMASK_0000001000001000001000001000001000001000001000001000001000001000,
                    mask2 = BITMASK_0001000000000000000000000000000000000000000000000000000000000000,
                    mask3 = BITMASK_0000000000000011000000000011000000000011000000000011000000000011,
                    mask4 = BITMASK_0000000111000000000011000000000011000000000011000000000011000000,
                    mask5 = BITMASK_0000000000000000000000000000000000001111000000000000000000001111,
                    mask6 = BITMASK_0000000000000000000000001111000000000000000000001111000000000000,
                    mask7 = BITMASK_0000000000011111000000000000000000000000000000000000000000000000,
                    mask8 = BITMASK_0000000000000000000000000000000000000000000000000000000011111111,
                    mask9 = BITMASK_0000000000000000000000000001111111111111000000000000000000000000;
    uint64_t  x = xsrc,
              y = ysrc,
              z = zsrc;
    /* 0000000000000000000000000000000000000000000ccccccccccccccccccccc */
    x = (x & mask8) | ((x << 16) & mask9);
    y = (y & mask8) | ((y << 16) & mask9);
    z = (z & mask8) | ((z << 16) & mask9);
    /* 000000000000000000000000000ccccccccccccc0000000000000000cccccccc */
    x = (x & mask5) | ((x << 8) & mask6) | ((x << 16) & mask7);
    y = (y & mask5) | ((y << 8) & mask6) | ((y << 16) & mask7);
    z = (z & mask5) | ((z << 8) & mask6) | ((z << 16) & mask7);
    /* 00000000000ccccc00000000cccc00000000cccc00000000cccc00000000cccc */
    x = (x & mask3) | ((x << 4) & mask4);
    y = (y & mask3) | ((y << 4) & mask4);
    z = (z & mask3) | ((z << 4) & mask4);
    /* 0000000ccc0000cc0000cc0000cc0000cc0000cc0000cc0000cc0000cc0000cc */
    x = (x & mask0) | ((x << 2) & mask1) | ((x << 4) & mask2);
    y = (y & mask0) | ((y << 2) & mask1) | ((y << 4) & mask2);
    z = (z & mask0) | ((z << 2) & mask1) | ((z << 4) & mask2);
    /* 000c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c00c */
    return x | (y << 1) | (z << 2);
}

这些功能对称地工作。为了解码，二进制数字和数字组被移动到更大的连续单元；为了编码，二进制数字组通过移位来分割和传播。检查掩码（BITMASK_常量以其二进制数字模式命名）和移位操作，以详细了解编码和解码是如何发生的。

虽然两个函数非常有效，但它们并未优化。

上述函数已通过使用随机 21 位无符号整数分量的数十亿次往返验证测试可以工作：解码 Morton 编码的值会产生原始的三个分量。

于 2018-04-10T11:55:57.650 回答