《英雄联盟》设计师Jaewon Jung：游戏动画压缩如何保质量

不论是哪个平台的游戏，包体大小都是开发商最为头疼的问题之一。因为它不仅影响玩家硬件的存储空间，还直接决定了玩家从发现到体验游戏的时间差。而游戏动画是占用资源最大的部分，因此如何压缩动画是所有开发者都需要面对的问题。

最近，《英雄联盟》开发商Riot Games发布了相关的技术贴，设计师Jaewon Jung通过博客的形式讨论了如何在不降低动画质量的情况下进行动画压缩的话题，并在文章中讲述了Riot公司所使用的一些技巧，希望能给遇到这类问题的开发者提供一些帮助。

《英雄联盟》的英雄数量已超过125个（目前正式推出126个），每个英雄都有一套独特的动画设定。例如亡灵勇士 - 塞恩的跳舞动画就十分有趣，而这只是他38个动画中的一个。这些动作让英雄们变得栩栩如生，从角色的移动、强大技能的释放到悲惨的死亡动画，都赋予了英雄独特的个性。随着英雄的不断增加和重做，动画数据总量形成了很大的资源负担，包括运行内存、补丁大小以及存储空间等。

除了动画数据，最近发布的《召唤师峡谷》视觉更新也增加了内存需求。这次更新采用了Unique - texel的做法，相比此前的Tiling方式，能带来更优秀的视觉效果，但也不可避免地增加了地图对内存的占用。

Riot公司认为支持多种不同配置的硬件非常重要，这样所有人才能同时享受到游戏的乐趣。随着新的动画和地图更新带来的内存需求不断增加，他们开始寻找降低内存使用的方法。其中一个方法就是压缩游戏内骨骼动画数据，以减少内存占用，同时将质量损失控制在最低限度，并且保证不对性能产生任何影响。

他们采用了多种方式进行动画数据压缩，在这篇博客中，主要介绍了两种：量化（Quantization）和曲线拟合（Curve Fitting）。压缩过程中总会出现质量降低和释放内存空间的矛盾，因此，设计师会讲述他们发现的可接受方案，并解释如何管理数据以实现性能最大化。文中会使用四元数（quaternions）以及样条曲线（Spline Curves）等概念，不熟悉这些概念的读者可以参考博客结尾的有用参考资料。

需要说明的是，这篇博客里提到的内容并非新技术，而是游戏开发伙伴们分享的实用知识。此外，游戏引擎开发商BitSquid（已被Autodesk收购）的博客也很有帮助，值得一看。

量化（Quantization）

量化是指将一系列连续的可能性限制在相对小而分离的设定的处理过程。骨骼动画（Skeletal animations）包含位置、旋转和量化数据，量化3D矢量（用于表示位置和量）相对容易，只需获取它们的最大/最小值范围，并在该范围内进行统一分割即可。但骨骼动画数据的复杂性通常来自于旋转。

这里使用四元法表示3D空间里的旋转，量化旋转数据时利用了四元数的特殊数学性质。使用单位四元数（unit quaternions），其所有组件的范围都是[-1, 1]，找出绝对值最大的元素定义为x、y、z或w，然后舍弃该元素（绝对值最大的），保留其余三个。因为只要单位四元数满足x² + y² + z² + w² = 1方程式，就可以很容易计算出被省略的组件。通过省略最大的组件，可以将其余三个组件的范围限制在[-1/sqrt(2), 1/sqrt(2)]之间。在单位四元数中，这个范围之外的组件必然具有最大的绝对值，也就是会被忽略的组件。通过将范围量化到比[-1, 1]更小的区间，可以最大化精确度，避免对较小价值的组件进行处理而产生更多错误。

通过这种方式，为每三个保留下来的组件分配15 bits，被省略的组件分配2 bits，每个四元数总共占据48 bits（其中1 bit不使用）。相比之下，未经处理的四元数每个组件需要使用32 bits的浮点数（floating - point number），总共需要128 bits。经过处理后，压缩率达到了0.375。

这种48 - bit的四元数量化能保证数值精度（numerical precision）达到0.000043，几乎适用于所有案例。实际上，将这种量化方式应用到所有动画时，没有任何一个动画出现质量下降。而且，这种转化可以在加载时间完成，而无需持续进行大批量转化，也不需要后续打补丁，因此该量化方式简单可行。

样条曲线适配（Curve Fitting）

为了进一步压缩，采用了样条曲线适配的方式来改变四元数的值。这是一个创建曲线或数学函数的过程，使其能最佳适应一系列的数据点。特别使用了Catmull - Rom样条曲线，它可以用一个三阶多项式（3rd - order polynomial）表示。确定Catmull - Rom样条曲线需要四个控制点，可参考维基百科提供的数据图。

为了实现准确适配，使用迭代（iterative）方式来减少误差。该过程最初只有2个关键帧（keyframes），包含动画的开始和结束。通过迭代不断增加关键帧，将曲线的整体误差降低到可接受的水平。每次迭代中，找出关键帧之间的最大误差，并插入一个中间点关键帧作为替代，不断重复这个找错并替代关键帧的过程，直到每个部分的误差都降低到可接受程度。

可以对比上图中的红色适配曲线和绿色初始曲线在迭代过程中的变化。黄点代表每次迭代过程中增加的（新的）关键帧。经过88次迭代后，最初的661帧降低到了90帧。

在进行曲线插值（curve interpolation）之前，必须调整四个四元数控制点。一个四元数Q和它的相反数 - Q代表的是同样的旋转，但如果不调整，最终旋转可能无法实现最短途径的插值。例如，一艘向北行驶的船准备转向东方，如果没有合适的四元数调整，它可能直接逆转270度，而不是顺时针转90度。

曲线适配可以对量化结果进行进一步压缩，压缩率在25% - 75%之间。为定位、旋转和量化数据设置合适的误差值，对于在不损失视觉体验的情况下获得最大化压缩率至关重要。

为了更好地压缩，还考虑了样条曲线节点参数。在动画数据的案例中，基于关键帧时序（keyframe timings）的参数是最自然的。不过，同样的四个控制点，曲线形状会取决于使用的节点参数，如uniform、chordal或者本文使用的centripetal （可参考维基百科的数据）。

这些技术可能会对某些动画造成明显的质量损失，但通过使用严密的误差值，可以将损失降到最小，不过这样做的压缩率也会降低。因此，动画师会对每个案例进行审查，以平衡质量和压缩率。而且，与量化过程不同，曲线适配过程需要大量计算，无法在加载时间完成，必须对所有现存的动画数据进行预处理。

降低损失

压缩过程最明显的问题是foot sliding，即动画中角色的脚或任何末端执行器（end - effector）保持不动。

从图中可以明显看到本应摆动的脚却静止不动。这是因为skeletal rigging中的骨骼是分等级的，错误的累积会造成很大影响。解决这个问题的方法是使用“可适应错误率（adaptive error margins）”技术，即如果一个节点有较长的派生数，需要将误差值降到最低，而不是为所有节点使用相同的误差值。例如，末端执行器使用特定比例的误差值，其母单位使用半数，更上一级使用三分之一，以此类推。这种自上而下降低误差率的方法可以最大程度限制派生值发生错误的概率。

《Game Programming Gems 7》一书介绍了另一种“在骨骼动画中减少累积误差”的方法，内部称之为“连接销（joint pinning）”。对于连接销（如足部），不使用源数据流（source data stream），而是计算新的本地转换数据，以抵消早代数据压缩中产生的误差。这本书中关于这个话题的内容很不错，值得同行阅读。

允许缓存的数据结构（Cache - friendly Data Organization）

最后，讨论有效实现上述概念的方法。在研发这些技术时，充分考虑到玩家硬件存在很大差异，对降低性能的做法十分谨慎。团队专注的一件事就是实现允许缓存的数据结构。

关键的一步是将所有的关键帧（每个连接销的位置、旋转和量化帧）放到一个相连的存储块里。常见的做法是为每个连接销创建不同的存储块，但这种看似自然的结构在特定时间段评估一个完整骨骼姿势时会导致严重的缓存丢失。将数据放到一个存储块是因为所有渠道类型的有效负荷都是48 bit，此前已将四元数量化到48 bits，还为3D矢量的每个x、y以及z组件分配了同样的16 bits。可以从下面的压缩帧数代码看到实际的代码连接销结构：

这里，还将key time量化到了16 bits，连接索引（jointIndex）根据各自帧数数据而不同。V箭头包含了量化的有效负荷，确定有效负荷是属于旋转、位置还是量化非常重要，通过两种最重要的连接索引来完成。这种方法可以将连接索引控制到14 bits，《英雄联盟》一共有16384个连接销，对于英雄来说足够用了，因为通常一个英雄使用不到100个。

因此，对这些连接销进行恰当的关键帧排序非常重要，无论连接销的类型如何。原本可以用key time进行简单排序，但会出现问题。想象一下动画运行时的情况，从下面的图片可以看出问题：

可以看到被key time分开的四个关键帧以及一个标明了目前重放时间的计时针。评估一个样条曲线需要四个控制点，所以需要Tn、Tn + 1、Tn + 2以及Tn + 3的信息。如果计时针的当前位置已经过了Tn和Tn + 1，这两个帧是已知的，但Tn + 2和Tn + 3怎么办？可能会认为可以进行线性扫描来快速找到它们，但这种方法并非最优。假如这些T是帧数位置，当动画包含很多旋转变化时，很多旋转帧可能会存在于两个临近位置的帧数之间（如下图）。这样所有的帧都放在一起，通过线性扫描寻找Tn + 2和Tn + 3效率非常低。

要让每一次线性扫描都能实现回放，关键是按照时间需要的顺序组织帧数，而不是根据key time。计时针通过Tn的key time后就需要Tn + 2，因此应将Tn + 2根据Tn的关键数据进行安排。这样任何时候都能获得所需信息，从而将缓存丢失最小化。下面的图表展示了这个工作原理：

希望所使用的压缩方法能够帮助到所有遇到类似问题的开发者。

结论

平均而言，文中讨论的量化技术基本上让《英雄联盟》的英雄内存需求减半。团队还在努力优化曲线适配技术，虽然它需要预处理所有数据，但从初期结果来看，很可能实现另外50%的压缩率，即有可能将最初的内存需求降低到25%。这令人兴奋，因为有机会提高各种玩家设备的游戏体验。

未来还可能探索更多方向，如32 - bit四元数量化、对不同的曲线适配采用不同的节点参数、用最小二乘法适配替换迭代做法、对增加新的key进行更多优化等。动画压缩是一个广泛且深入的话题，本文讨论的只是冰山一角。希望这些内容对进行动画压缩的开发者有所帮助，下面是一些参考文献的链接，祝好运。