毫不怀疑的游戏开发者的拓扑和综合分析：压缩单个3D向量

正如您从我以前的文章中已经可以理解的那样，我喜欢以游戏开发为借口来演示复杂的数学，否则大多数人都不会使用。 而且这篇文章也不例外！ 我想展示一种非常酷的技术，对应于我感兴趣的几点：

• 这个过程很清楚
• 它比执行相同任务的常规技术快得多
• 它使用一个非常不寻常的属性以浮点格式表示浮点数，这意味着...
• 在经典分析中不起作用 。 为了使该算法在理论上起作用，您需要进入非经典数学的奇妙世界！ 如果这没有引起您的好奇心，那么我不知道该怎么办。

本文篇幅长且理论性强，因为它需要对这些解释进行深入研究，因此，请花点时间重新阅读您认为不是第一次的显而易见的部分。

有关上下文（GPU）的一些知识

GPU的带宽是您在游戏开发中应注意的重要方面之一，并且在更广泛的意义上（在活跃使用图形的任何领域中）都是如此。 中央处理器和GPU是独立的物理设备，它们需要同步才能交换数据。 如果您已经完成了并行处理，那么您知道当两个设备需要同步时，这意味着要浪费大量时间。 在这方面，CPU-GPU的交互作用没有什么不同，因此我们努力在操作数量和数据传输量方面尽量减少数据传输。

通常使用缓冲来最小化数据传输操作的数量：我们努力将所有数据放入尽可能少的数组中，然后立即传输所有数据，因此我们不再需要担心它们。 在传输操作中最大程度地减少数据量是一个完全不同的主题，并且针对此问题的解决方案几乎总是个别的。 作为一个极端的例子，您可以看到Destiny渲染引擎如何设法适应位置，表面法线，材质标记和96位全各向异性BSDF参数，即 三个浮点数 （第62页起）。 但是，通过常规方法可以获得良好的结果，然后在其中添加用于优化的单个解决方案。

今天，我们将讨论单个3D矢量的无损压缩 。 这句话包含几个关键字：

• 单个3D向量 ：长度为1的3D向量
• 无损压缩 ：在不损失准确性的情况下减小单个3D向量的描述大小。 这与有损压缩相反。
• 单独的 ：执行矢量编码和解码时，不会获得有关其邻居的信息。 如果情况相反，则可能类似于批处理压缩，其中不是单个向量被压缩，而是它们的数组被压缩。

在继续之前，我必须提到Cigolle，Donow，Evangelakos，Mara，McGuire和Meyer撰写的出色文章“独立单位 向量 的有效表示调查 ” ，从中我汲取了灵感。 我必须马上说，我将要讨论的算法比本文介绍的oct算法效率低 。 如果要获得最大效率，请阅读文章并使用oct 。 我的文章的目的是展示使用非常不寻常的数学的美妙之处，同时我们将在后面创建一个非常方便的算法。

视频游戏中的拓扑

在单位球的情况下，只有θ和φ很重要，因为ρ始终为1，因此是多余的。

该算法的起点是观察到单位3D向量等效于球体上的点。 您可能知道，球是二维表面，也就是说，对于球上点的唯一标识，只需要两个坐标。 一个非常常见的例子是球坐标，球上的一个点由两个角度θ和φ定义。

有趣的是，一个不愉快的特性是，尽管球体和实心正方形（一个可能的2D坐标空间）是2D对象，但它们之间确实没有对应关系。 这意味着无法将球体上的唯一点附加到正方形的每个唯一点上（至少以连续的方式）； 它们被称为非同胚的 （换句话说，一个具有边界，而另一个则没有边界）。 令人不快的结果是，某些2D坐标丢失了，因为不同的坐标对应于球上的相同点（例如，对于球坐标，当φ为0时，无论坐标θ如何，对应点将成为北极）。 在压缩方面，我们失去了可用来描述球体点的宝贵位模式！

如果您需要更多的数学知识，并且想要证明正方形和球形不是同胚的，则可以使用这样一个事实，即与正方形相比，球形不是可收缩的，可收缩性是一种拓扑性质； Borsuk-Ulam定理也可用于证明。 他们还告诉我，同伦小组可以帮助证明，但这已经超出了我的专业领域。

但是，不仅在球坐标系中也会产生该问题。 球体点的任何连续2D表示都将受到影响。 但是，请记住这一点，以备将来使用。

球坐标还具有其他不良特性：

• 它们在整个领域分布不佳。 如果生成随机球坐标并将其转换回3D点，则它们将在极点周围形成簇，并且在赤道附近将非常稀少。 这是由于以下事实：赤道附近的3D向量将难以准确区分。
  
  
  
  
  在10,000个均匀分布的球坐标上的球上分布
• 它们的包装和开箱成本很高。 对于打包（3D→2D），需要一个运算acos和一个atan2 ，这是非常昂贵的反三角函数，对于解包（2D→3D），则需要两个运算cos和两个运算sin ，这也很不经济。

查看上面的文章，以了解球坐标和其他压缩方法的其他比较。

保留位模式和速度的任务

我们将考虑的方法具有很大的优势-它的计算速度更快，是未优化的朴素基准测试的两倍多（在Intel Core i5第7代上的Visual Studio 19中对C ++中的1000万个随机向量进行打包和解压缩测试）。 另外，该方法不具有奇异性，即，与上述球形坐标相反，每个堆积点对应于单个未堆积点。

如前所述，在单位球体和单位正方形之间没有同胚，也就是说，我们无法将正方形中的每个唯一点正确地附加到球体上的另一个唯一点。 但是，让我们考虑以下结构-到目前为止，只有北半球（其中存在具有正或零坐标Z的点）才会与我们有关。


我们将北半球“展平”到磁盘中， 丢弃每个点的Z坐标 （或将其分配为0）。

我们找到了一种方法，可以将北半球的每个点附加到单个磁盘中的每个点。 一些值得注意的要点：

• 北极落入（0，0）。
• 半球边界上的每个点都保持不变。 更具体地说，半球和盘具有相同的边界。 这是合乎逻辑的，因为半球边界上的点的Z = 0，也就是说，放弃Z坐标，我们什么都不会改变。

磁盘压缩：一个简单而复杂的任务

以下构造需要一些介绍。 以防万一，我要说复数是实数空间的扩展（普通数，如0、1、129、43，pi，335/117，平方根2等），它使用了一个特殊的数字， 我称为虚数单位 。 复数的形式为a + ib ，其中a和b是一些实数（分别是实部和虚部），并且i具有i²= -1的性质。 这使我们能够将复数与2D平面上的点进行匹配。 如果为z取z = a + ib形式的复数，则可以将z表示为在平面上具有坐标（ a ， b ） 的点。 复数z的“实部”和“虚部”的提取函数由Re（z）和Im（z）表示 。


复数z及其值。

除了复数的实部和虚部，还可以考虑由复数与X轴形成的长度和角度，这称为极坐标表示 。 极长和极角为标准| z | 和参数Arg（z） 。 两种表示形式的一个方便属性是， 通过将实部和虚部 相加来完成复数的相加 ，并且通过将范数乘以并添加自变量来完成复数的相乘 。

在这里，我们对两个操作感兴趣：平方和获得复数的平方根。 对复数求平方与实数完全相同：只需将其乘以本身，本质上就是对范数求平方并把参数加倍 。 请注意，如果复数的范数小于1，则对它进行平方时，其长度将保持小于1；否则，它的长度将保持小于1。 因此，如果我们将具有正实数部分的磁盘上的每个复数取为一个整数，然后将它们全部放在一个正方形中，那么我们实质上将获得整个磁盘。


左边是磁盘一半的复数，带有正实数部分（X坐标）。 右边是对所有这些点求平方的结果。 现在，一半的磁盘已填满整个磁盘！

一个技巧与“加倍参数”有关：它取决于该点所在的X轴的一侧。 该规则如下所示。


虚数部分为正（Y坐标）的复数向左旋转，虚数部分为负（Y坐标）的复数向右旋转。

与实数一样，平方根是平方的倒数：对于给定的复数z ，平方根（其中两个）是数字c ，使得c²= z 。 与实数一样，如果c是z的平方根，则-c也是。 其参数等于参数z一半的数字c和-c的值称为平方根的主要值（这类似于取实数的正平方根而不是负平方根）。

如果您了解当复数平方，其范数平方并且其参数加倍时，那么您可以轻松地猜测平方根的主值取范数的平方根并将参数减半（遵循上面显示的规则，但箭头朝上） 。 与平方的情况一样，当取范数小于1的复数的平方根时，范数保持小于1； 因此，它会将单位磁盘“压缩”为一半的正实数。


左侧是单个磁盘上的几个点。 右侧显示了所有这些点的平方根的结果。 现在整个磁盘可容纳一半！

这是算法的基础：实际上，我们将整个单元磁盘压缩为一半-一半为实数部分。 您还记得，最近我们将球体的上半部分展平为一个磁盘。 现在值得一看我们将如何处理它。

全部放在一起

让我们总结一下我们所做的事情：我们将球体的一半展平为一个单位圆盘，丢弃所有点的Z坐标，并使用复数主平方根值将单位圆盘压缩为具有正实部的一半。 实际上，我们将球体的一半夷为平盘！ 现在进行了一些更改，我们可以执行相同的操作以将球的其余一半压缩到磁盘的其余一半中。

球体的下半部分（球体的所有点均带有负Z坐标）也可以通过重复放置Z坐标而平坦化为单位圆盘，但是，对于盘中所有复数z ，我们取与z的平方根相反的值（即，用-c代替c ） 由于平方根的主值始终具有正实数部分，因此相反的值始终具有负实数部分； 实际上，我们将球的其余一半压平到了磁盘的其余一半，压缩阶段现已完成！


完整压缩步骤。 请注意，将北半球和南半球（蓝色和橙色）压平为单个磁盘的两个副本，然后压缩为单个磁盘的两个半部分。

压缩算法如下：

function packUnitVector(unit) disk = new Complex(unit.x, unit.y) packed = principalSquareRoot(disk) return unit.z < 0 ? -packed : packed 

因此，仅用三行伪代码，我们就应用了所研究的整个理论来创建有效的算法。 如果您的环境没有平方根主值的公式，则可以在Wikipedia上找到它（应特别注意选择虚部的符号）。 这是我在代码中使用的参考C ++实现：

 // Principal complex square root of 'x + iy' float2 csqrt(float x, float y) { float r = sqrt(x * x + y * y); return float2(sqrt((r + x) / 2), (y < 0 ? -1 : 1) * sqrt((r - x) / 2)); } 

回来啦

我们已经解决了压缩问题，现在开始解压缩。

打开包装的顺序与所有压缩步骤的顺序相反：

• 我们将单个磁盘的材料部分的正半部分和负半部分扩展为两个完整的磁盘
• 将每个完整的磁盘与其对应的半球匹配

简而言之，我们从p的压缩值开始，平方它的平方以返回到从半球之一获得的磁盘上的点，然后使用符号Re（p）找出磁盘中的点取自哪个半球。 使用等式x²+y²+z²= 1 ，它定义了单位球面上的点，我们可以重新创建缺少的点的Z坐标。

应该注意的是，计算打包值的平方将始终为我们提供磁盘的正确点，而不管其初始半球（上部还是下部），因为z²= （-z）² 。

解压缩算法如下：

 function unpackUnitVector(packed): disk = packed * packed unit = new Vec3() unit.x = disk.real() unit.y = disk.imag() unit.z = sqrt(1 - unit.x * unit.x - unit.y * unit.y) * (packed.real() < 0 ? -1 : 1) return unit 

因此，我们得到了一种非常有效地创建单个3D向量的2D表示的算法，与球形坐标不同，该算法不会丢失任何位模式并且没有奇异性。 如果您不考虑几个优化技巧来加快计算速度，那么这几乎是该算法的现成版本。

...还是不？ 如果仔细观察，您会发现这里有问题。 我说过，球体和单位平方不是同胚的，但是以某种方式能够将圆盘中的唯一点绑定到球体上的每个唯一点吗？ 此外，我们还没有提到任何非经典数学，那么这是怎么回事？

实际上，我们的算法有一个严重的缺点：它适用于整个球体中的每个点，除了Y = 0和X <= 0的北半球上的点外，当打包和拆包时，它们被错误地与北半球上的对应点进行比较。

其原因是，当舍弃其坐标Z时，相应的复数是负实数，它没有虚部。 当我们取负实数的平方根的主值时，我们又得到一个不具有实数部分的完全虚数（这类似于-1的平方根的主值等于i的事实）。 然后，我们尝试将Z坐标的符号保持在实质上为零的位置。


问题条。 Y = 0且X <= 0的点被打包成纯虚数的行，实数部分不确定。

让我们看看打包两个这样的点时会发生什么（不要忘记x <= 0）。

  | 北角| 南点
 单位|  （x，0，z）|  [x，0，-z）
 磁盘  x + 0i |  x + 0i
包装好的  0 +√（-x）i |  -0-√（-x）我 

由于投影到两个点的圆盘上的虚部等于零，因此我们无法将Z坐标的符号存储在平方根主值的实部的符号中，因为它本身等于零。 我们可以简单地讨论这一点，接受算法不适用于这些点的事实-否则我们可以继续。

忘记我们学到的东西

在我所知道的数学的每个领域和分支中，都假定0 = -0。 这来自于-a的定义，它与a相反，指出“ -a是唯一与a相加时给出0的数字” 。 由于0也是加法的零元素（ 0 + a = a + 0 = a ），因此您唯一需要添加到0以获得0的事情就是0本身。

但是，在软件开发中，一切都不同。 在浮点数的大多数表示形式中，连同指数和尾数一起使用了额外的一位来存储字符。 这意味着当指数和尾数均为0时，符号位可用于区分正零和负零。 在大多数编程语言（如果不是全部）中，这两个零都被视为一个单个零（只需尝试0 == -0 ），但是存在区别，如果您尝试向终端输出“ -0”和“ 0”，则可以看出这一点。 ”-这就是推论的方式。

这对我们来说非常重要：零值实际上可以用来存储有关符号的信息！ 实际上，它仍然正确存储； 在我们的情况下，问题在于它无法正确读取。 如果我们查看拆包算法中的倒数第二行，将会看到以下内容：

 packed.real() < 0 ? -1 : 1 

此操作读取打包值的实数部分的符号，以确定该点属于哪个半球-北或南。 但是，在packed.real（）为0或-0的情况下， 比较运算符将忽略该字符，而三进制运算符始终返回1。正确读取该字符的方法是对符号位状态的真实请求，例如，使用C ++或np中的 std :: signbit .signbit从Numpy到Python-该函数取决于语言。 请记住，当数字为负数时，符号位为1；当数字为正数时，符号位为0。

因此，我们得到了一个经过纠正的百分之一百的工作函数：

 function unpackUnitVector(packed): disk = packed * packed unit = new Vec3() unit.x = disk.real() unit.y = disk.imag() unit.z = sqrt(1 - unit.x * unit.x - unit.y * unit.y) * (signbit(packed.real()) ? -1 : 1) return unit 

仅此而已！ 至此算法完成。 非古典数学表现为以下事实：我们使用0不同于-0的事实，这对于我所知道的所有数学领域都是错误的。 但是，有一种方法可以使这种奇怪现象在理论上，数学上严格的意义上成为逻辑。

不受规则约束的空间：具有两个原点的直线

为了更好地理解以下内容，您应该了解等效类和邻域的概念。 这是可选的，但会更清楚。

我们可以从一个有趣的拓扑空间：一个带有两个原点的直线开始，以“零号”确保这种奇数的一致性。


具有两个原点的直线是普通的实数轴，以某种方式为其自身增加了0。

当我们取两个实数值轴并用相反的数字粘合每个数字（除0之外）时，将获得具有两个原点的直线。形式上，具有两个原点的直线是商空间R²，其等价关系确定两个数字相等， 并且不为0。结果是一条实数直线，其中两个不同的零点与任意点的距离相等，但同时彼此不同。 形式上，每个零的任何两个邻域始终具有非空交集。

我们可以对此进行扩展，并尝试定义本文中使用的“类似磁盘”的对象。 早些时候，即使该实数部分为0，我们也将点的Z坐标的符号强制保留在投影到复数盘上的主平方根的实数部分中，即使该实数部分为0。这意味着我们没有使用复数，而是使用了一个与之相似的概念：复数，的虚部为实数，且其虚部为具有两个原点的直线上的点，因此我们可以区分等于+0和-0的实部。 实际上，我们使用具有两个原点的复数！

实际上，我们没有发现球体和单位圆盘之间的双射（一对一映射），但是我们发现了球体和单位圆盘之间有两个原点的双射。 我没有检查这个双射是否是同胚（同胚是在两个方向上连续的双射），但是也许有一天我会做到这一点。

最后一点拓扑

总而言之，我想强调一点，尽管我们使用两个原点的复杂平面与具有两个坐标的直线的结构不同，但实际上，它等效于另一个具有两个原点的复杂平面，其结构类似于具有两个坐标的直线。两个起源。

在具有两个原点的直线的情况下，我们在除0以外的所有位置上粘贴了两个实数轴副本。我们可以对复数平面的两个副本进行相同的处理，将每对相等的非0相等的复数粘合在一起，并且类似地得到复数具有两个原点的飞机。 这种构造不同于通过具有两个原点和一条普通实数值轴的直线构造的新复平面：前者是因子空间，后者是空间的乘积。 但是，这两个结果空间之间的唯一区别是在每个空间中写入不同零的方式：在第一个中，它们被计为（ 0 + 0i）a和（ 0 + 0i）b （两个零从两个未粘合在一起的不同空间获取），在后者中，它们分别被读取为（0a + 0i）和（0b + 0i） 。 实际上，两个空间都是同胚的，因此您可以在需要另一个的地方安全地使用一个。

结论

我希望您喜欢这个奇异而晦涩的数学世界。 我再次强调一个事实，严格来说，该算法的性能要比我在开头提到的文章中的oct算法差。 尽管它的执行时间接近甚至更快，但它在球体上的点分布远不是那么好。 然后，我写了这篇文章，以说明看似外来的数学，类似于抽象的废话，在现实世界中实际上如何具有非常有趣的应用。 而且，我发现这种抽象的废话令人愉快。 希望您从这篇文章中学到了一些有用的东西，谢谢阅读！