代码之家 › 专栏 › 技术社区 › datapanda

三维网格的莫顿反向编码

z-order-curve numerical-methods physics bit-manipulation c

datapanda · 技术社区 · 6 年前

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

假设在没有细化的情况下,两个网格在物理现实中是相似的(除了第二个代码没有晕细胞),我想找到的是一个细胞 q 莫顿id mid 对应的索引是什么 i ,则, j 和 k 三维网格中的索引。基本上是对 中期 或Z顺序以获得相应的 i,j,k 对于 u 矩阵

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

对于正向编码,我遵循的是魔术位方法,如中所示 Morton Encoding using different methods

1 回复 | 直到 3 年前

Nominal Animal 6 年前

莫顿编码只是将两个或多个组件的位交织在一起。

如果我们按重要性递增的顺序对二进制数字进行编号,那么无符号整数中的最低有效二进制数字是0(和二进制数字我具有值2 ^我 ),然后是二进制数字我 in组件 K 属于 N 对应于二进制数字( 我 N + K )在莫顿密码中。

这里有两个简单的函数来编码和解码三分量莫顿码:

#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位无符号整数分量进行数十亿次往返测试,验证了上述函数的有效性:对莫顿编码值进行解码会产生原来的三个分量。