[译]英雄联盟是如何压缩骨骼动画数据的?

原文：COMPRESSING SKELETAL ANIMATION DATA

译者：刘晓鹏

英雄联盟(lol)有125位以上的英雄，每位英雄拥有自己特有的动画属性集。(我最喜欢的是哪个?Sion(英雄联盟中的一个英雄) 的舞蹈，如下所示，仅仅是他38个动画效果中的一个)。这些动作使得每个英雄栩栩如生：从坚定的动作到强大的魔法释放到悲惨的死忙(我经常看到最后的那一幕)。随着我们不断的引入和修订英雄，动画数据的总量已经成为资源的一个很大的负担：如运行时内存、包大小及存储空间。

除了动画数据，视觉数据还包括最近更新Summoner’s Rift的位置，这需要更多的内存。为了获得更好的视觉效果，更新采用了独特纹理效果的方式，而不是原来的拼接方式。但是，这大大增加了纹理效果映射在内存中的大小。

我们将重点放在继续支持最大范围玩家硬件层面上，以至于每个人可以享受可怕剑圣的不死之身。随着新的动画效果及更新映射对内存需求增长，我们需要找到减少内存使用的方法。通过调研，我们找到一条途径：压缩游戏中骨骼动画数据来减少内存，但是要尽可能减少质量损失，并且尽量不影响性能。

我们可能有很多种方式来压缩动画数据。在这篇文章中，我将介绍两种我们主要采用的技术：量化和曲线拟合。压缩算法总需要在质量损失和内存占用之间进行权衡，所以我将会讨论在什么范围内是我们能够接受的，同时我也会讨论一下我们是如何组织数据以获取最大的性能。我将会使用一些概念如四元组和样条曲线，如果你不熟悉这些概念，我将在文章末尾处给出一些有用的资源列表。

我想指出的是，这里我提到的技术是全新的。这些技术是下列游戏开发人员所分享的，使他们在实践中所获得的知识。我将他们放在游戏引擎开发者BitSquid的博客中，这非常有用和值得一提的。

量化

量化是一个数值处理的过程，这些数值包含了连续可能性集合到相对较小的离散集合。骨骼动画包含位置、旋转以及尺寸数据。我们能够很容易量化3维向量，它通常用来表示位置、大小，并通过获取最大/最小值来来在这个范围内均匀的分配。但是 lion 分享的骨骼动画数据通常来自于旋转。

我们使用四元组来表示3D空间中的旋转。量化旋转数据的方式是利用四元组的特殊数学性质来实现的。假定一个四元组单位中所有的元素都在[-1,1]范围内，首先，我们确定x,y,z,w中绝对值最大的元素，然后丢弃该元素并保存其他三个值。因为我们可以通过x2 + y2 + z2 + w2 = 1恒等式，很容易计算出删除的元素。通过删除最大的元素，我们可以将其他三个元素的范围限制在[-1/sqrt(2), 1/sqrt(2)]之间——记住，在一个四元组单位里，如果我们没有排除最大的元素，一定存在一个绝对值最大的元素在这个范围之外。我们通过量化一个比[-1, 1]更小的范围来最大化提高精度，[-1, 1]是在我们没有排除最大元素时的范围。这也避免了我们重新创建一个小值元素，这种创建容易引起错误。

使用这种方法，我们为保存的三个元素中每个元素分配15位的空间，用另外2位的空间来指定删除的元素。因此每个四元组单元占48位(有1位没用到)的空间，如上图所示。相比之下，一个原生的四元组，需要为每个元素分配一个32位的浮点型数字，总共需要占用128位。从128位减少到48位，我们实现的压缩比为0.375。

48位量化的四元组能保证的数值精度为0.000043。你能感觉到(如果你对浮点型数敏感的话)这应该满足大多数情况。事实上，当我们将这种量化运用到所有动画时，没有动画绘制者能发现转化后的质量损失。此外，我们可以在加载的时候进行这种转换，而不是后续对其进行批量转换和修订，因为量化是一个非常轻量级的处理过程。

曲线拟合

为了进一步压缩，我们期望能通过曲线拟合来改变四元组中的数值。这个过程是通过构造一条曲线或一个数学函数使其能够最好的适应一系列的数据点。我们专门使用了Catmull-Rom样条，它可以通过一个三阶多项式来表示。我们需要四个控制点来定义一段Catmull-Rom样条，如下图(来自维基百科)所示：

Source: Wikipedia

来源：维基百科

在执行实际的拟合过程中，我们使用一种迭代的方式来减少误差。该过程最开始只包含两个关键帧，即动画的开始和结束。我们迭代的增加更多的关键帧，以降低曲线的误差到一个可以接受的范围。每次迭代，先识别出最大误差的关键帧之间的部分，然后在其中间点插入一个关键帧。在最大误差部分中间插入关键帧的过程反复执行，直到每部分的误差低于给定的阈值。

你可以从上图看到红色拟合曲线到蓝色的原始曲线的迭代过程。黄色的点代表每次迭代加入的新的关键帧。在这个案例中，我们通过88次迭代，将原来的661帧压缩到90帧。

在做曲线插补前，别玩了调整四元组的四个控制点。一个四元组Q和-Q表示相同的旋转，但是如果不对旋转结果做调整，可能会导致插补不是沿着最短路劲去进行的。例如，一艘船头朝北的船准备向东旋转。没有适当的四元组调整，这艘船可能会逆时针旋转270度，而不是顺时针旋转90度。

曲线拟合对量化结果做了进一步的压缩，压缩比范围在25%到70%之间。我们发现，对位置/旋转/尺寸设置合适的误差阈值，对实现高压缩比、不显著影响视觉效果是至关重要的。

我们也考虑通过节点参数化的样条曲线来实现更好的压缩。在动画数据的案例中，基于给定关键帧时间的参数化是最自然的方式。但是，正如下图(同样来自维基百科)所示，具有同样四个控制点的曲线形状依赖于我们使用的统一的，玄或向心的参数。

Source: Wikipedia

来源：维基百科

Source: Wikipedia

来源：维基百科

这些技术也使得部分动画有明显的质量损失。我们可以使用更严格的误差阈值来减少大部分损失，不过压缩比会受到明显的影响。因此，我们的动画设计师审查了每个案例来寻找质量与压缩比之间的平衡点。此外，与量化情况不同的是，加载时进行转换是不可选的，因为拟合曲线的是一个重量级的计算过程，我们不得不预处理所有已存在的动画数据。

减少损失

最值得注意的问题是由于压缩导致作品脚部的滑动，这是动画中最丑陋的部分，动画中角色的脚或者任何受动器的端点应该是固定不变的。

你可以很容易看到上面视频中的本应该固定不动脚一直在滑动。这是由于自然的骨骼层次结构绑定在一个骨骼装置中，这个地方产生了异常的累计，其来源跟连接点的动画效果。我们减少该问题是使用了一种称之为“自适应错误率”的技术。这意味着如果连接点有更长的子链，就会自动缩小误差阈值，而不是每个点采用相同的阈值。例如，一个受动器终端使用一个给定的误差值，但是它的的父连接点的误差值为它的一半，而它的祖父连接点的误差值只有它的三分之一等等。父连接点的误差值缩紧会级联影响其后续所有的连接点。

《游戏编程精粹 7》介绍另一种称之为“减少骨骼动画累计误差”的方法。我们内部称之为“连接点桩”。对于一个固定的连接点(如脚)，我们不使用源数据流，而是计算一新的局部转换数据，该数据抵消了其祖先在压缩过程中引入的误差。这本书在该主题上包含了更多的资料。

缓存友好的数据组织

最后，我们讨论一下我们是如何有效的实现迄今为止所说的概念。当我们开发这些技术时，我们仍然关注着广大玩家的硬件，非常谨慎的不引入任何性能问题。我的团队关注的一件事情是实现数据组织的有好缓存。

其中关键的一步是我们将所有的关键帧(每个连接点的位置/旋转/尺寸帧)放在一块单独、连续的内存块中。一种通用的做法是为每个渠道的每个连接点创建一个单独的内存块，但是这种看似自然的组织方式，在给定时间内计算一个完整的骨骼姿势时，可能会触发几次缓存失效的情况。我们可以把数据放在一个块中，因为所有渠道类型的有效负载恰巧都为48位。正如我们前面所看到，我们量化四元组到48位，通过将3D向量的位置/尺寸中元素x,y,z赋值为16位，我们将3D向量的量化到相同大小。你可以查看实际代码的结构体，该结构体用来表示一个压缩的帧，代码如下：

这里，我们也将关键时间量化为16位。成员变量jointIndex指向本帧数据所属的连接点。数组v包含了量化后的有效负载。区分是否是有效负载的位置，旋转或尺寸是非常重要的，我们通过jointIndex中最重要的两个位来完成该任务。用这种方式来使用这些位，可以将jointIndex限制在14位或总数为16384个连接点——肯定可以满足lol的英雄，lol中英雄一般要求要少于100个连接点。

恰当的对关键帧进行排序是非常重要的，无论是连接点还是渠道类型，都在同一个桶中。我们可以很简单的根据关键时间对它们排序(如上面的成员变量keyTime)，但是很快就会出现问题。我们想象一下运行时动画执行的内容，可以通过下图来帮助想象：

你可以看见四个关键帧(根据关键时间进行排序)和一个指向当前时间执行的位置的时间游标。你需要的信息有Tn, Tn+1, Tn+2, 和 Tn+3，因为计算一个样条需要四个控制点。给定游标的当前位置已经过了Tn和Tn+1，游标应该已经知道这两个点。但是Tn+2和Tn+3，哪个点是游标将要经过的呢?你可能认为可以快速的扫描它们，因为这两帧紧跟在后面。

但是，这种方式不是最佳方式。我们称Ts为位置帧。如果动画大部分是通过旋转来完成，则在相邻的位置帧之间可能存在很多旋转帧(正如你在这个例子中看到的)。结果是要扫描从当前位置到一个桶中的所有的帧，因此这种通过线性扫描来查找Tn+2和Tn+3的方式可能是低效的。

让动画的播放发生在一个单一的线性扫描中(和通过缓存获取最大利益)，其技巧在于要根据所需时间来排序帧，而不是关键时间。一旦游标经过了Tn的关键时间，我们就需要Tn+2的信息;因此，我们应该根据Tn的关键时间来对Tn+2进行排序。通过这种排序方式，任何时间点，游标都能获取到当前计算所需要的信息，所以缓存失效也可以最小化。下图阐述了一个由四个位置帧和9个旋转帧组成的动画的排序方式：

希望这次深入了解我们压缩的实现能够帮助任何遇到类似问题的人。

结论

总而言之，这篇文章中我讨论了通过量化技术将英雄联盟的英雄对内存的要求减少了一半。我们还讨论了应用曲线拟合技术的过程，虽然要求预处理所有的数据，但是早期的结果表明，这种方式可以实现进一步50%的压缩，也就是意味着堆内存的要求下降到原来的25%。对于这个结果我非常高兴，并且这次改进所有玩家的任何硬件类型都是有效的。

我们可以进一步探索更多的方向，如32位(代替48位)的四元组量化，曲线拟合的不同节点参数化，最小二乘法代替迭代法，更优的选择如何在迭代中增加关键帧等等。压缩是一个广泛而又深入的话题，在这篇文章中，我们也仅仅是浅尝辄止。但是，我还是希望你在处理动画压缩时能发现本文的有用之处。我在下面的参考文献部分链接了一些相关的文章。祝你好运!

参考资料

Animation compression

1、The BitSquid low level animation system

2、Bitsquid Dev Blog – Low Level Animation — Part 2

3、Digital Rune Blog – Character Animation Compression

4、Unreal Engine 3 Animation Compression

5、Reducing Cumulative Errors in Skeletal Animation, Bill Budge (Game Programming Gems 7)

Curve fitting

1、Curve fitting, Wikipedia

2、Catmull-Rom spline

3、Least Squares Fitting

Compression in general

1、Working With Compression, by Fabian Giesen

Tools used to prepare materials for this article

1、http://jsfiddle.net/6u7hm0m9/16/

2、https://screentogif.codeplex.com/

3、Least Squares Fitting

Compression in general

1、Working With Compression, by Fabian Giesen

Tools used to prepare materials for this article

1、http://jsfiddle.net/6u7hm0m9/16/

2、https://screentogif.codeplex.com/

via：杰微刊

End.