对于基于八叉树的稀疏体素八叉树渲染器，我希望能够旋转和镜像八叉树的各个节点。虽然它不是真正的八叉树，但由于节点被共享并被允许将自己作为子树包含。否则，我可以简单地将转换应用于八叉树本身。
在不损失一般性的情况下，假设立方体是一个单位立方体，其一个角位于原点，即 (0,0,0(，而另一个角位于 (1,1,1(。我已将立方体的角编码为 3 位整数。所以 0 (=0b000( 表示原点处的角，1 (=0b001( 表示 (0,0,1( 处的角，7 (=0b111( 表示 (1,1,1( 处的角。唯一允许的旋转和反射是围绕立方体的中心(1/2,1/2,1/2(，并且角将最终位于整数坐标处。这意味着只有 48 种不同的可能转换。(第一个角可以映射到 8 个可能的位置，下一个角可以映射到 3，第三个角可以映射到 2，这将固定其余角的位置。
我还没有决定如何对转换进行编码，尽管应该可以将其编码为单个 32 位整数(甚至是 6 位整数，因为只有 48 个可能的转换(。然后，可以将转换作为函数应用，该函数将多维数据集的每个角映射到转换后的位置。即
int transform(int corner, int transformation) {
// magic happens here
return result;
}
此外，我还应该有一个组合变换的函数combine，这样transform(corner, combine(a,b))等于transform(transform(corner, b), a)。
由于这些函数每秒将被调用大约十亿次，因此它们应该很快。虽然转换的调用频率大约是组合的 4 倍。该算法是递归的，因此如果转换编码使用多个 32 位整数，则将其放在堆栈上会产生额外的运行时成本。
到目前为止，我已经发现这个问题可以分解为位翻转，这可以通过单个异或操作和位排列(我还不知道如何有效地完成(来完成。但是，同时执行这两项操作的操作可能更有效。
我打算在C++代码中使用它，该代码已经在使用 SSE4.1 内部函数。尽管不使用内部函数或只需要 SSE3 的解决方案是首选。最后，速度是最重要的。我将尝试使用 http://quick-bench.com/来比较解决方案。
(注意：我使用了仿射变换标签，因为没有正交变换标签，我不想创建它(。
您可以将转换存储为 8 个字节的数组，该数组对立方体角的排列进行编码。transform方法就像数组查找一样简单。组合其中两个转换可以循环完成，但这将相当慢。但是，事实证明，SSSE3 有一个内在函数，可以在单个指令中执行此操作：_mm_shuffle_pi8。
因此，必要的方法可以按如下方式实现：
#include <tmmintrin.h>
int transform(int corner, __m64 transformation) {
uint8_t array[8];
memcpy(array, &transformation, 8); // This call is optimized away by the compiler.
return array[corner];
}
__m64 combine(T a, T b) {
return _mm_shuffle_pi8(b, a);
}
从我的基准测试结果中，我得到四次调用转换并组合一次，花费大约 2ns 的 CPU 时间。这仍然有点慢，但只要有足够的内核，这可能是可行的。
我还实现了一些不同的比较方法：
- 将排列打包为 in32 中的半字节(4 位整数(，并使用循环来计算
combine的结果。虽然使用一半的内存，但它大约慢了 3-5 倍。 - 直接研究米洛·勃兰特提出的 6 位编码。但是，我未能正确实现这一点。
- 将允许的变换限制为仅轴对齐反射的组合。这些可以使用按位 XOR 快速计算。这大约快 30-50%。
我创建了一个快速工作台页面，尽管它不支持使用 SSSE3 指令，所以我不得不禁用使用_mm_shuffle_pi8的方法。不过，您仍然可以在本地编译和运行它们。