《英雄联盟》设计师:如何在保证酷炫效果的前提下进行游戏动画压缩
《英雄联盟》设计师:如何在保证酷炫效果的前提下进行游戏动画压缩
不论是哪个平台的游戏，游戏包体都是开发商最头疼的问题之一，因为它不仅影响玩家硬件的存储空间，还直接决定玩家从发现到体验游戏的时间差。而游戏动画则是占用资源最大的部分，所以如何压缩动画是所有开发者都需要面对的问题。
最近，《英雄联盟》开发商Riot Games发布了相关的技术贴，设计师Jaewon Jung通过博客的形式讨论了如何在不降低动画质量的情况下进行动画压缩的话题，并且在文章中讲述了Riot公司所使用的一些技巧，希望给遇到这类问题的开发者提供一些帮助。
以下是Gamelook编译的完整博文（小编非技术出身，翻译失误之处恳请大牛指正）：
《英雄联盟》的英雄数量已经超过了125个（目前正式推出126个），每个都有一套独特的动画设定，要问我最喜欢的是哪个？毫无疑问是亡灵勇士-塞恩的跳舞动画（下图），而这只是他38个动画中的一个。这些动作的加入才让英雄们变得栩栩如生，从角色的移动到强大技能的释放以及悲惨的死亡动画，都可以让英雄变得更有个性。随着我们不断的增加和重做英雄，动画数据的总量已经形成了很大的资源负担，比如运行内存、补丁大小以及存储空间等等。
除了动画数据之外，最近发布的《召唤师峡谷》视觉更新则增加了内存需求，这次的更新使用了Unique-texel的做法，比此前的Tiling方式更能带来优秀的视觉效果，然而它也不可避免的增加了地图对于内存的占用。
我们认为支持多种不同配置的硬件是非常重要的，这样所有人才能同时享受到游戏的乐趣。随着新的动画和地图更新的内存需求不断增加，我们开始寻找降低内存使用的方法。我们发现的其中一个方法就是压缩游戏内骨骼动画数据来减少内存占用，同时维持最低的质量损失，还要保证不对性能产生任何影响。
我们可能用了很多方式进行动画数据压缩，但在这个博客中，我会介绍我们主要使用的2个：量化（Quantization）和曲线拟合（Curve Fitting）。压缩的做法总会带来质量降低和释放内存空间两者的矛盾，所以，我会讲述我们发现的可以让人接受的方案，还会解释我们是如何管理数据并且做到最大化性能的。我会使用一些像四元数（quaternions）以及样条曲线（Spline Curves）这样的概念，所以，如果你们对这些不熟悉的话，可以参考博客结尾中非常有用的参考资料。
我需要说明的是，这篇博客里提到的所有东西都不是什么新技术，而是从事游戏开发的伙伴们分享的一些非常实用的知识，我还想补充的是，游戏引擎开发商BitSquid（已被Autodesk收购）的博客是非常有帮助而且值得一看的。
量化（Quantization）
量化指的是把一系列连续的可能性限制在相对小而分离的设定的处理过程。骨骼动画（Skeletal animations）有位置、旋转和量化数据，我们很容易量化3D矢量（用于表示位置和量），只要通过获得他们的最大/最小值范围并且在这个范围内统一分割即可。但骨骼动画数据的复杂性通常来自于旋转。
我们这里使用四元法指代3D空间里的旋转，我们量化旋转数据的方式使用了四元数的特殊数学性质，我们使用了单位四元数（unit quanternions），所有组件的范围都是[-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，通过我们的处理，原本的128 bits降低到了48 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进行更多优化等等。动画压缩是一个广泛而且非常深度的话题，我们本文讨论的还只是冰山一角。不过，我仍旧希望这些是对你们做动画压缩有帮助的，下面是一些参考文献的链接，祝你们好运。
参考文献
动画压缩
The BitSquid low level animation system
Bitsquid Dev Blog – Low Level Animation — Part 2
Digital Rune Blog – Character Animation Compression
Unreal Engine 3 Animation Compression
Reducing Cumulative Errors in Skeletal Animation, Bill Budge (Game Programming Gems 7)
曲线适配
Curve fitting, Wikipedia
Catmull-Rom spline
Least Squares Fitting
通用压缩方法
Working With Compression, by Fabian Giesen
为准备本文材料所用到的工具
http://jsfiddle.net/6u7hm0m9/16/
https://screentogif.codeplex.com/