3D 网格的 Morton 逆向编码
Morton Reverse Encoding for a 3D grid
我有一个 3D grid/array 说 u[nx+2][ny+2][nz+2]
。尾随的 +2 对应于每个三维 x,y,z
中的两层 晕细胞 。我有另一个允许细化的网格(使用四叉树)因此我有每个单元格的莫顿索引(或 Z 顺序)。
假设没有细化,这两个网格在物理现实中是相似的(除了第二个代码没有光环单元),我想要找到的是一个单元 q
和 morton id mid
3D网格中对应的索引i
、j
和k
是什么。基本上是 mid
或 Z 顺序的解码以获得 u
矩阵的相应 i,j,k
。
正在寻找 C 解决方案,但任何其他编程语言的一般注释也可以。
对于前向编码,我遵循魔术位方法,如中所示
Morton Encoding using different methods
Morton 编码只是交织两个或多个分量的位。
如果我们按重要性递增的顺序对二进制数字进行编号,则无符号整数中最低有效二进制数字为 0(二进制数字 i 的值为 2i), 然后 k 的分量 i 中的二进制数字 i 24=]N对应二进制数(iN+k)莫顿代码。
这里有两个简单的函数来编码和解码three-component莫顿码:
#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_
常量以其二进制数字模式命名)和移位操作,以详细了解编码和解码是如何发生的。
两个函数虽然效率很高,但没有优化。
以上函数已经过验证测试,使用数十亿 round-trips 使用随机 21 位无符号整数分量:解码 Morton-encoded 值会产生原始的三个分量。
我有一个 3D grid/array 说 u[nx+2][ny+2][nz+2]
。尾随的 +2 对应于每个三维 x,y,z
中的两层 晕细胞 。我有另一个允许细化的网格(使用四叉树)因此我有每个单元格的莫顿索引(或 Z 顺序)。
假设没有细化,这两个网格在物理现实中是相似的(除了第二个代码没有光环单元),我想要找到的是一个单元 q
和 morton id mid
3D网格中对应的索引i
、j
和k
是什么。基本上是 mid
或 Z 顺序的解码以获得 u
矩阵的相应 i,j,k
。
正在寻找 C 解决方案,但任何其他编程语言的一般注释也可以。
对于前向编码,我遵循魔术位方法,如中所示 Morton Encoding using different methods
Morton 编码只是交织两个或多个分量的位。
如果我们按重要性递增的顺序对二进制数字进行编号,则无符号整数中最低有效二进制数字为 0(二进制数字 i 的值为 2i), 然后 k 的分量 i 中的二进制数字 i 24=]N对应二进制数(iN+k)莫顿代码。
这里有两个简单的函数来编码和解码three-component莫顿码:
#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_
常量以其二进制数字模式命名)和移位操作,以详细了解编码和解码是如何发生的。
两个函数虽然效率很高,但没有优化。
以上函数已经过验证测试,使用数十亿 round-trips 使用随机 21 位无符号整数分量:解码 Morton-encoded 值会产生原始的三个分量。