使用 2 维的幂转换 1D -> 3D 的更快方法

Question

我正在尝试优化访问和更改 3D 环境的数据，因为某些操作必须执行数百万次。目前我有以下优化：

使用平面阵列 (1D)
维度是 2 的幂
位移，如果可能，而不是multiplication/division

3D向量的索引如下：

X 向量的变化会使索引 increase/decrease 增加 1
Y 向量的变化会使索引 increase/decrease 3DEnvironmentSize.X
Z 向量的变化将 increase/decrease 索引 3DEnvironmentSize.X * 3DEnvironmentSize.Y

给定以下伪代码：

mapSize.X = 4
mapSize.Y = 4
mapSize.Z = 2

Xdif = 1
Ydif = mapSize.X = 4
Zdif = mapSize.X * mapSize.Y = 16

Xexponent = log2(Xdif) = log2(1) = 0 (2^0 = 1 = Xdif)
Yexponent = log2(Ydif) = log2(4) = 2 (2^2 = 4 = Ydif)
Zexponent = log2(Zdif) = log2(16) = 4 (2^4 = 16 = Zdif)

一个人会从 3D -> 1D 给定 Vector(1,2,1) 使用以下方法：

location.X = 1
location.Y = 2
location.Z = 1

shiftIndex.X = location.X << Xexponent = 1 << 0 = 1
shiftIndex.Y = location.Y << YExponent = 2 << 2 = 8
shiftIndex.Z = location.Z << Zexponent = 1 << 4 = 16

index = shiftIndex.X + shiftIndex.Y + shiftIndex.Z = 1 + 8 + 16 = 25

如您所见，我正在使用位移来提高处理速度。现在我知道如何使用给定索引 30 的除法和除法余数来转换 3D -> 1D，如下所示：

index = 30

location.X = index % mapSize.X
location.Y = (index / mapSize.X) % mapSize.Y
location.Z = ((index / mapSize.X) / mapSize.Y) % mapSize.Z

有没有什么方法可以在这里使用位移（或其他任何与此相关的方法）来使速度更快？一段时间以来，我一直在尝试破解它，但我无法破解它，如果它一开始是可能的话。

Answer 1

你只是想把 3 个数字打包成一个更大的数字吗？

如果是这样，你为什么不转移并遮住？

ThreeToOne(v3) -> v3.x | (v3.y << 8 ) | (v3.z << 16)

OneToThree(v) -> v3(v & 0xFF, v >> 8 & 0xFF, v >> 16 & 0xFF)

Answer 2

我在别处得到了答案。

当你除以一个 2 的幂的数时，你可以用一个右移操作代替那个除法，它是 2 的幂的指数。模数运算可以用按位运算符和 n - 1 替换（同样，如果它是 2 的幂）。其中 n 是你潜水的数字。所以总结代码：

mapSize.X = 4
mapSize.Y = 4
mapSize.Z = 2

Xdif = 1
Ydif = mapSize.X = 4
Zdif = mapSize.X * mapSize.Y = 16

XDifExponent = log2(Xdif) = log2(1) = 0 (2^0 = 1 = Xdif)
YDifExponent = log2(Ydif) = log2(4) = 2 (2^2 = 4 = Ydif)
ZDifExponent = log2(Zdif) = log2(16) = 4 (2^4 = 16 = Zdif)

XSizeExponent = log2(mapSize.X) = log2(4) = 2 (2^2 = 4 = mapSize.X)
YSizeExponent = log2(mapSize.Y) = log2(4) = 2 (2^2 = 4 = mapSize.Y)
ZSizeExponent = log2(mapSize.Z) = log2(2) = 1 (2^1 = 2 = mapSize.Z)

Vector3D -> Index example:
location.X = 1
location.Y = 2
location.Z = 1

shiftIndex.X = location.X << XDifExponent = 1 << 0 = 1
shiftIndex.Y = location.Y << YDifExponent = 2 << 2 = 8
shiftIndex.Z = location.Z << ZDifExponent = 1 << 4 = 16

index = shiftIndex.X + shiftIndex.Y + shiftIndex.Z = 1 + 8 + 16 = 25

Index -> Vector3D example:
index = 30

location.X = index & (mapSize.X - 1) = 2
location.Y = (index >> XSizeExponent) & (mapSize.Y - 1) = 3
location.Z = ((index >> XSizeExponent) >> YSizeExponent) & (mapSize.Z - 1) = 1

使用 2 维的幂转换 1D -> 3D 的更快方法

Faster way to convert 1D -> 3D using powers of 2 dimensions

3d

pseudocode

data-conversion