骨骼动画的插值与融合
花了三天时间搞定了困扰了我半年的事情，心情非常之好。
是这样的。我们的 3d engine 中的骨骼动画的插值融合总有点问题。如果是两个变化比较大的动画想从一个过度到另外一个，效果总是不太对。对于图形程序，很难用测试驱动的方式开发的缘故之一，就是因为对与不对有很大程度是人的视觉感受，而不是可以简单校验的数值。想写一个判定正确与否的程序，估计不比把代码写正确简单。
所谓不对呢，问题其实老早也想明白了。现象就是有些动作之间过度像纸片一样，而不是直觉中，人物用合理的方式运动。这时，只显示骨骼动画信息中的关键帧反而效果更好。（这些关键帧，是美术人员在 max 这样的软件中制作出来并导出的：或是用动作捕捉而来的）
其问题在于，没能对骨骼的变换信息做正确的插值。
原来这部分代码写的很脏乱，且原作者已经离开。后继人员要么知其然而不知其所以然的在上面修补，要么就没心思把这个东西真的弄对。（毕竟暂时看起来，这并不是迫切需要解决的问题。它不会引起程序崩溃，也不影响开发进度。）
我倒是一直很想自己来重新设计制作这一块，可一直忙于更多别的事情。加上，大学线形代数也没学好，把其中的数学基础知识补上，还是颇要些精力的。
拖了这么久，终于，这周一咬牙，求人不如求己。还是自己弄吧。
早期的 3d 实时渲染，都是简单的把顶点连成面，然后附上贴图把模型显示出来的。若是想让模型动起来，就制作若干动作下的模型，在文件中记录下动作每帧的模型造型的顶点信息。简单说，一个动作，就是一系列的独立模型。这就是所谓的顶点动画。Quake 的前几个版本都是这么干的。这样干主要是因为早期的硬件条件有限，让硬件去处理顶点，渲染多边形就已经够吃力了，没多余的计算力去干别的事情。
后来，随着游戏的视觉内容急剧增加，把丰富的动画全部输出成一帧一帧的模型，数据量上已经不太吃的消。慢慢的，还加入一些和环境互动的动作，单纯的用预生成好的帧顶点动画已经不再满足要求。
人们想出一个办法，把 3d 模型抽象成一组关键点的集合。（这个抽象就好比从 2D 到 3D ，把一堆的像素构成的图象，抽象到少一个数量级的三角型上）整个模型的运动，可以想象成这些关键点的运动，而构成模型的顶点及面，都是受这些关键点的影响而已。
这些关键点被称为骨骼，非常之形象，而且在人物动画中，这些点通常也正好在人物关节的位置。
和 max 里制作不同。这种建模软件展现给美术人员的骨骼真的是有体积的实体。而程序处理的时候，所谓的骨骼却是一个个的点，更准确点说，是一组组空间变换。点只是表达了空间位置而已，并没有表达出自身的转动和缩放变换。
使用这些骨骼信息非常简单。只需要把模型上的点，根据它们和骨骼间的关系（被称为皮肤的东西），乘上对应骨骼的变换矩阵即可得到在骨骼摆成特定姿势下的正确空间位置。
这样，我们只需要把骨架摆成特定姿势，就可以计算出蒙皮上所有相关点的空间坐标，并通过显卡硬件渲染出来。在现代显卡中，GPU 甚至可以帮你做最后一步矩阵变换的乘法。
剩下的工作，就是怎样得到骨架的信息了。
3d 人物做任何动作，都可以在 3d 软件里制作好，输出整个动作每个时间点的骨架空间信息。这些是些离散的数据。按我们游戏的制作标准，是一秒 12 到 15 帧。（另一种纸娃娃系统暂且不谈）
当游戏的实际渲染帧率更高，或由于特殊需要，想放慢动作运动速度时。预做好的骨架信息就不够用了。
当然，你可以让动作一格格跳，也不太所谓。只是在不同的动作切换时，会比较奇怪。更好的方法是在两帧动作间做插值处理。
这就是我这几天工作的重点。其实这是项很老的技术。谁让我精力实现有限，直到今天才真正卖力研究它呢。
如上所述，当我们不插值，直接把美术输出的数据来用的时候，一切都是很简单的。无非是在渲染前，把那些顶点数据乘上个骨骼变换矩阵而已。如果我们需要知道两帧图象的中间状态呢？马上能想到的是，对每个骨骼点，两帧的对应变换矩阵做插值。
可惜的是，变换矩阵中的每一项并不可以正交分解，独立插值的。
而且，虽然最后我们用到的变换数据是每根骨骼在绝对空间中的绝对变换。但实际上在制作这些数据时，骨骼之间是有相互关系，相互影响，最后把各级骨骼的空间变换叠加起来的。
综合这两个问题来看，我们需要做的工作，一是尽量把变换矩阵正交分解成可以独立插值的元素。二是将骨骼的变换行为还原到影响到它的上一级骨骼的局部空间内。比如两组动画间要做过度，可能手的位置差别很大，但是对指关节的运动的插值，却只应该考虑指头相对手掌的运动，而不需要考虑手指在绝对空间中的变化量。
假设手指的绝对变换矩阵为 M1 ，手腕的变换矩阵为 M2 。那么可求得手指在手腕空间中的变换为 M1 * M2' 。（哎，上大学时光顾着玩程序去了，线形代数没好好学。这几天补习这方面的时候真累。不过经过自己的推导搞明白后，想忘都比较难了。）
这一步是相对简单的，但是不是要把整个变换还原到父节点呢？经过一番思考后，我的结论是否。
我们先看另一个问题：做美术制作过程中，如果数据来源是动作捕捉仪，那么骨骼做变换无非是自旋和位移。就我目前看到的动作捕捉设备，无非是若干照相器材布置在空房间中，演员穿上特制的衣服，衣服上的关节处安装有若干反射光的小球。照相机拍摄到这些小球在空间中的变化，把数据输出到计算机。所以，我们用这套设备得到的骨骼信息，就是一些点的空间移动和自己朝向的改变了。（小球是否能被感知方向暂时我还没能确认，有空我去公司的捕捉室实地研究一下）
如果是美术在建模软件里手工制作的话，因为骨骼被抽象为有体积的实体了。在美术看来，每次操作的是一段骨头，而数据上，被影响的是骨头的两端。最原始的变换行为，其实是旋转和伸缩。但对应到端点上，就成了位移和旋转（对父节点是旋转，对子节点是位移）以及少量的缩放。据我的美术同事讲，缩放其实是很少用的，因为很难控制。btw, 据我所知，暴雪到目前为止，都是手调动画，没有使用动作捕捉设备。
综上，骨骼的变换矩阵，其实是有若干次的缩放，旋转，和位移变换叠加的结果。
其中，缩放属于形变；而旋转和位移都属于自身在空间中状态的变化。我们应该分开看这个问题，形变往往是不因骨骼的连接关系而继承的，如果有复杂形变，（多次旋转和拉伸的反复叠加）我们就无法从最终的变换矩阵中分离出一个缩放矩阵。好在，一般不会有人刻意去制造这种变换方式（用动作捕捉更是不可能得到这种变换）。所以，我第一步就从全局变换矩阵中分离出缩放矩阵来。这个变换是不受骨骼层级连接而传递其影响的。
剩下的，就只有若干旋转和位移信息包含其中。
我们知道，一个带方向的点（一个向量）在空间中，无论以什么次序，做多少旋转和位移，最终都可以表达为一次旋转加一次位移。
即，我们分离缩放变换后，计算得到的子节点在父节点空间中的相对变换（M1 * M2'）中一定可以把这个矩阵表示为某个旋转变换 R * 另个位移变换 T 。
固然，这里的 M1 和 M2' 中也可分解为R1 * T1 以及 T2' * R2'。但是我尝试找到最终结果 R 和 T 用 R1 T1 R2 T2 的简单表达形式，却失败了。这都怪大学里的线性代数没好好学啊。不过既然我知道最终的结果矩阵中只包旋转和位移，分离结果函数很容易的。他们分别是 4*4 的变换矩阵中的 3*3 项（旋转部分）以及一行位移部分。
对于旋转变换的插值，是不能直接对 3*3 的矩阵线性插值的。正确的方法是把矩阵表达为四元数。话说，搞明白四元数这个东西又颇费了我一些时间，这里就不展开讲了。简单的说，对矩阵旋转插值不可行是因为它的 9 个数值并不正交。而四元数则是的四个部分则是相对独立的。正如在 2D 空间中，2 个数字（复数）可以表达一种旋转，旋转的表达在 3D 空间则扩展到了四个数字。四元数的插值和计算方法，网上能搜出许多。读到这里，我们只需要知道，这是一种方便做插值的描述旋转变换的表达形式即可。
那么，我们分离出一次旋转和一次位移后，分别做插值就可以了吗？
我认为是不完全正确的。尤其是在动作幅度较大，或两个关系疏远的动作之间。
设想一下，如果一个肢势下，手指向左边；而另一个姿势，同一只胳膊，指向了右边。从旋转角度看，胳膊上的变换，方向转了 180 度。如果人的以人的中轴线为 0 看，位置从负变到正。假若我们分别对旋转和位移插值，过度出中间状态。正中间的位置，手就会萎缩到几乎没有，而不是我们直觉中的旋转过来。这也是，我们早先的版本，有时人会变纸片的缘故。
问题出在哪里？
旋转变换和位移依然不是正交的。
我们直觉上正确的骨架，其实，关节之间的距离是几乎不变的，也就是一个刚性的骨架。各个关节其实要么在做自旋，要么在围绕父节点公转。自旋和公转则是相互正交。如果偶尔有距离改变，那么其运动也是沿着公转轴方向靠近或远离，和旋转变换也是正交的。
如果我们可以把每个骨骼变换，分解为相对父亲的公转，相对自己的自转，以及公转轴上的伸缩，那么就可以正确的做插值了。既把一个变换表示为形为 R1 * T * R2 的形式，且这个 T 只有一根轴上的变换。
之前，我们已经可以把变换分解为 R * T ，剩下的工作就是把这个转换一种形式。
这个转换不算太复杂，但需要使用一点点空间几何知识和少许线性代数。推导过程就不详述了。只写写大概思路：取一个坐标轴做主方向，比如 X 轴。如果原来 T 里的位移不仅仅包含 X 分量，就把它和 X 轴做叉乘，得到一个垂直的法向量。以这个向量做旋转轴，以 T 和 x 轴的夹角为旋转角（可以很简单的得到这个角的 cos 值），构造一个旋转变换 R1 ，那么 T 就能表示为 R1' * T1 * R1 ，其中 T1 只包含了 X 分量，值为 T 中位移向量的长度。它的几何意义就是这个骨头到父节点的距离。
整个变换即为 R * R1' * T1 * R1 ，前两个旋转变换可以合并为一个旋转。其几何意义就是骨骼的自转量。后一个 R1 是它绕父亲的公转量。
最后，我们可以放心的做各种混合和插值处理了。看起来貌似很多运算，几乎都是在开发期预生成好的。最终运行时需要计算的东西并不多。
简单谈一下动画数据的压缩。
3D MMORPG 里，动画数据很容易吃掉大量的硬盘。如果非要考虑压缩这些数据了，可以考虑这样几个方面。上面的思路，每个骨骼点，在每个关键帧上需要保存两个旋转和一个轴向位移。这个位移往往在动画中是不变的，所以就是两个旋转变换。保存两个四元数即可。
由于四元数是归一化过的，其实就是三个绝对值小于等于一的数字加一个符号位。我们对旋转的精度要求其实不会特别的高。可以考虑使用定点数。我大致想到的方案是使用一个 32bit 数字保存一个四元数，第四个可计算的量的符号位占用 1bit ，另外三个量分别占用 10 bit 。分摊开来等价于在每个旋转方向上，可以分出 1024 个角度，足够满足一般需求。由于骨骼动画中，大量的旋转都是相对不变的。我们可以简单的做一个 hash 表 cache 这些 32bit 压缩的四元数到四个 float 的转换。应该不需要多大的 cache 就能得到比较高的命中率。
关于骨骼动画模块的设计。
我个人认为不需要太关注单次插值计算的时间效率。
插值和混合应该是一个可选项，对动画模块外做成黑盒子。我们只需要至少能提供关键帧信息即可。关键帧的最终变换也可以预运算好。
对于模块对外的接口，只需要简单的一个：给定指定的动画名字和帧号，返回骨骼变换信息。并允许提供混合帧的动画名及帧号，以及混合比。
真正的性能热点应该在 cache 管理上，而不在生成这些变换信息的计算上。
今天太晚了，就随便写写到这里了。把预想的程序完成真是一大快事。
Comments
Posted by: lch | (29) August 3, 2016 11:58 AM
Posted by: lch | (28) August 3, 2016 11:33 AM
Posted by: mule | (27) August 27, 2012 05:37 PM
Posted by: dayong | (26) February 10, 2012 10:27 AM
Posted by: 孤单 | (25) October 11, 2011 05:37 PM
Posted by: soroman | (24) February 5, 2010 11:23 PM
Posted by: soroman | (23) February 5, 2010 11:23 PM
Posted by: soroman | (22) February 5, 2010 11:22 PM
Posted by: wenbin | (21) December 25, 2009 04:54 PM
Posted by: Anonymous | (20) December 16, 2009 03:30 PM
Posted by: Anonymous | (19) December 16, 2009 03:25 PM
Posted by: tearshark | (18) December 6, 2009 10:31 PM
Posted by: tearshark | (17) December 6, 2009 10:14 PM
Posted by: vêtements femmes | (16) December 3, 2009 04:55 PM
Posted by: Nil | (15) December 3, 2009 02:17 PM
Posted by: 小顺 | (14) December 2, 2009 10:28 AM
Posted by: puzzy3d | (13) December 1, 2009 05:44 PM
Posted by: iTana | (12) December 1, 2009 12:25 AM
Posted by: Anonymous | (11) November 28, 2009 05:33 PM
Posted by: Anonymous | (10) November 28, 2009 05:27 PM
Posted by: Icat | (9) November 28, 2009 10:56 AM
Posted by: sword007 | (8) November 27, 2009 03:13 AM
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (7)
November 26, 2009 04:50 PM
Posted by: Garuda | (6) November 26, 2009 03:37 PM
Posted by: cloud | (5) November 26, 2009 12:53 PM
Posted by: Garuda | (4) November 26, 2009 11:43 AM
Posted by: liuhuanjim013 | (3) November 26, 2009 10:42 AM
Posted by: 3.1415926 | (2) November 26, 2009 04:48 AM
Posted by: btshanji | (1) November 26, 2009 04:46 AM