Basic ConceptsHow to Touch the Ground?Intuitive Idea: Adjust Feet Position for Each StepTwo Bones IKMore Complicated IK ScenariosComplexity of Multi-Joint IK SolvingCheck Reachability of the TargetConstraints of JointsNeed Treat Constraints SeriouslyHeuristics AlgorithmCCD (Cyclic Coordinate Decent) 循环坐标下降Optimized CCDFABRIK (Forward And Backward Reaching Inverse Kinematics)FABRIKF with ConstraintsMultiple End-EffectorsIK with Multiple End-EffectorsJacobian Matrix 雅可比矩阵Using Jacobian Matrix to Present Joint RotationsJacobian Matrix with Multiple End-effectorsApproaching to Target Step by StepOther IK SolutionsIK is still ChallengeIK Hot Research AreasUpdated Animation Pipeline with Blending and IK
我怎么样保证我手永远能抓到一点？
在你面前放个苹果，你去抓它这个东西我是不需要训练的。但是在游戏里面如何让这个动作整个一气呵成，实际上是非常非常复杂的。当小朋友在只有 0 到 6 个月的时候，你在他面前放个东西，他其实是抓不住的，他要练习很久才能够准确地一下子抓到苹果。我们人也可以认为是通过深度学习方法经过了以年为单位的训练，终于练就了那种准确的抓取能力。
实际上今天我们在游戏里面就能用 IK 来模拟出人的这种聪明。
Basic Concepts
IK 的全称叫反向动力学。也就是给定一个指定点，这个角色该怎么运动看上去才最自然。
比如游戏中怎么从最近点抓到一个把手，摔跤的时候抓到一个人。
- End-effector（末端的效果器）。希望角色的某一个骨骼的运动符合反向动力学的约束。
- 最经典的案例就是：当角色在一个颠簸不平的地上走的时候，我们希望它的脚总是踩在地面上。
动画师做动画的时候，都假设面前是一望无垠的平地。
How to Touch the Ground?
Intuitive Idea: Adjust Feet Position for Each Step
我们希望角色迈出去每一步的时候，都能够有东西帮助这个角色把他的脚摁在地面上。
最简单的解决办法就是 Two Bones IK。
Two Bones IK
Two Bones IK 就是只有两个 Bone 的 IK。
角色的大腿和小腿，两根骨头代表了三角形的两个边。目标点确定了，那目标点离大腿根部的距离也就确定了。有了三条边长就可以唯一确定一个三角形。通过三角函数就可以知道大腿要迈多少度，小腿要迈多少度，就可以算出动画。
但这里面也有问题。
当给定一个大小腿的两个骨骼（约束点）的时候，其实解出的是一个圆环。也就是在圆环上的任何一个点，这个解都是有效的。
以上图的角色为例，他无论是内八字还是外八字，他的动作都能保证脚能踩到那个点。
解决办法也简单，给一个 reference vector，告诉他做 IK 时腿应该朝向的方向。
前面说解出的是圆环，在圆环上的平面，有了 reference vector 就可以得到两个交点，一个正向一个反向（向量点积算，大于 0 就是同向）。
这样基本上可以非常完美地解决脚踩在地上的问题，而且这也是 IK 最简单的方式。
但事实上，IK 的 scenario 比这个要复杂多了。
More Complicated IK Scenarios
上面都是 IK 用的场景。IK 真正难的地方在于，参与 IK 的 Joint 可能不止两个，当它们是一条链的时候，如何去写？
Complexity of Multi-Joint IK Solving
- Computation cost: high dimension non-linear function solving in real-time
- May have multiple solutions, unique solution or no solution
这里有两个问题：
- 自由度太高
- 在方程中就是表示它的话就得是 high dimension 高维方程。而且它是个非线性的方程，因为它有大量的旋转角度在里面。
- 它的解有无穷多个
- 以上图为例，连接了起点和目标点，它的 joint 实际上有很多种可能性。
如何解长链的 IK？
Check Reachability of the Target
比如说要让身体去拿一个苹果，但这时候可能刚好胳膊够不着，整个身体还要前倾。这时候判断够不够得着的最简单的方法，就是把所有的骨骼全拉直了，看看长度够不够。如果长度不够，肯定够不着（上图上方）。
第二种可能性是，把最长的一根骨骼放在起点，把其他所有骨骼对着它去折。如果这些骨骼无论怎么折都没有办法覆盖那个最长的骨骼，那其实也有一个盲区（上图左下）。
但这方法后面会讲到，它其实是不完整的。
这个是在写 IK 的时候经常会忽略的事情。有时候会发现解了很久，但就是得不到一个解。有的时候如果算法写得不好，它就会无限次迭代下去。
Constraints of Joints
更难的一个问题是什么呢？就是对于一个人形的角色来讲，我们的骨骼是不能乱动的。
我们每一个 joint 的活动范围都是有自己的约束的。比如说我大腿和胯的地方，是一个标准的球状的关节。大腿上的骨头像个小圆球，在盆骨那边可以来回转。脚踝和小腿骨的关节可以平移，脖子像 pivot 可以转来转去。手掌部分叫 saddle 是马鞍型的关节，可以前后转，但是手掌向下左右平移的时候好像活动范围就有限了。
当我们去做人体的 biped skeleton 的时候，每个 joint 都是有一个特定的活动范围的，放到一起再去解它们的话就很痛苦，这就是长链 IK 很麻烦的事情。
Need Treat Constraints Seriously
这里就是解 IK 解错了，join 的约束没有控制好。
特别是受击动画、特别是那种特别剧烈的动画，很容易会遇到 IK 导致的很奇怪的情况，这就是为什么 constraint 在 IK 系统中非常重要。
Heuristics Algorithm
- Why
- Too many joints + constraints, difficult to solve with analysis method
- Basic Idea Designed to solve problem in faster and more efficient fashion by sacrificing optimality, accuracy, precision, or completeness for speed
- Approximation
- Global optimality is not guaranteed
- Iteration is usually used with a maximum limit
我们首先用最 heuristic 启发式的算法去解决它，因为要真的解决那么复杂的高维非线性方程会很麻烦。当然可以用有些现成的数值方法，但是这些方法本身它不一定稳定，而且会非常的 expensive。
最著名的一个算法是 CCD 算法。
CCD (Cyclic Coordinate Decent) 循环坐标下降
- Principle
- From joint-to-joint, rotates the end-effector as close as possible to the target, solves IK problem in orientation space
- Reachability
- Algorithm can stop after certain number of iterations to avoid unreachable target problem
- Contraints
- Angular limits is allowed, by checking after each iteration
这个算法想法非常的简单，为了够到目标点，先把节点最末端 joint 往上一根的 joint 的和目标点之间的连线方向去翻，这样就靠近目标点了。然后再去翻下一根骨头，以此类推。
总的来说起始端点不变，然后尝试往目标去向内翻滚，再把算法再从端点再外翻做一遍。进行若干次这样迭代的时候，会发现越来越接近目标点，最终几乎是完全重合在目标点上了。
在上图示例中，可能会觉得好像第一次基本就翻到了，但在真实的游戏里，这种 CCD 迭代个十几次很正常，但它每一次计算其实也不复杂，这也是一个目前行业里面大家觉得最经典的也是最简单的一个多链的 IK 算法。
我们当然可以对 CCD 做很多的优化。
Optimized CCD
Add tolerance regions to each bone's goal
- Each bone stops rotating and moves onto the next bone within tolerance region
- Helps to produce poses that are less rigid and more comfortable looking
这个算法会出一个问题，比如一开始翻得太猛烈了，到后面就可能会感觉这个人上半身已经歪得不行了，但是腰好像还是笔直的，这就不对。（上图第二行）
这里会做很多的优化，比如说每一次翻的目标点，一开始在目标点做一个相对大的一个范围，让它大致翻到那个目标点就差不多了。第二次迭代的时候，再逐渐往中心点去收缩，让它看起来更像一点。（上图第一行）
或者每一次翻的时候，给角度变化设个上限，这样也能够让旋转在整个骨骼上均摊一点。
它的数学原理是什么？首先这全是 hack。其实这是假设我们原始的骨骼状态是一个已经固定好的一个弹簧。去掰每个 joint 的时候，掰的角度越大，弹性的系数，势能就越大，就储存在了弹簧里面。想象一条无数个弹簧连起的链条，如果我们掰它两头，它能相对均匀地把这个 joint 的形变在 joint 之间去分散。
在理解各种 IK 算法的时候，用弹簧的连接棒的模型的话，就能理解它的算法到底为什么会这么设计。
如果我们想做更自然的一些旋转的话，其实也是这个原理。
Use under-damped angle scaling
- Each joint moves only a small amount toward the goal and distributes the movement across multiple bones
- Produce less abrupt joint changes and more smooth and casual poses for character movement
比如我们会约定越靠近根节点，它的旋转幅度就越小，越在叶节点的话，旋转幅度越大。这其实也符合总体的势能向偏小的方向去旋转的原则。
FABRIK (Forward And Backward Reaching Inverse Kinematics)
- Principle
- Instead of orientation space, solves IK problem in position space
- Reachability
- Algorithm can stop after certain number of iterations to avoid unreachable target problem
根据名字解释就是：向前去迭代一遍，向后再去迭代一遍，然后反复地来来回回，就解决了 IK 问题。
它不同于 CCD 老把骨骼掰来掰去的想法，它只做它的位移。
它的想法是先从端点开始，把第一个 joint 强行地拉到目标点去。然后再根据它的上一根还没有动的 joint 和那个目标点之间连一根线，再把骨骼旋转到那个连线上去。因为骨骼的长度固定，因此就会突出去，下一根骨骼要连，就得把突出骨骼的反向的端点作为它的目标点，再去对上，最后因为长度固定，根节点也凑了上去移动了位置。到了 Backward 部分，就把整个链条倒过来，从根节点开始，先把根节点拉回到原来的原点，因此又发生了一个平移，然后依次一路拉到端头，这样端头就会出现误差。
一般这样迭代，经过一来一回，首先原始骨骼根节点还是锁住了，同时整个骨骼链满足了我们的约束。这个时候最远端的那根骨骼离目标点的距离明显就会近很多，除非达不到这个目标点。这个时候再来一遍，forward、backward、forward、backward 经过若干次迭代，就会发现端点会非常接近于目标点。
这两个算法无论是 CCD 还是 FABRIK ，老师觉得它都得设置一个 error tolerance，它也不能完全保证一定能够 hit 到目标点。但是基本上能够得到一个我们可以接受的结果。
这两个算法是做简单的长链 IK 最主流的两个算法。
FABRIKF with Constraints
Re-positioning
- Joint restrictions can be enforced at each step by taking the resultant orientation and forcing it to stay with in the valid range
FABRIKF 其实跟 CCD 一样，也能处理一些约束问题，但它们共同的问题是，都需要无数次的来回迭代。
第一个链条动的时候，根据约束的转动范围，去求一个垂直平面。然后在上面的投影点作为 target 点，这样先动第一个 joint。然后如果每一个骨骼都有约束，就依次这样去投影。
Multiple End-Effectors
- May result in conflict between goals, which can not be achieved simultaneously
- May use a priority or a weighted approach
刚才讲的所有的约束都比较简单，都是一个单一的约束点。但是真正在游戏引擎中，我们经常会发现约束点特别多。举个例子，比如说攀岩，这个时候左脚右脚都要分别踩到岩石的某个地方，手还得勾到另外一个点。那整个角色的 skeleton 是整个被拉伸的。
实际上要做一个爬墙的时候活灵活现的 character 的话，从动画系统来讲，门槛其实是非常高的，因为最难的就是它整个 IK 和动画混合的体系。
以塞尔达作为例子，当角色去攀岩的时候，他同时要控制的 IK 点可能要达到三个甚至到四个以上，那么这个时候角色的行为会怎么样？
IK with Multiple End-Effectors
If a shared bone needs to be moved, the end-effector that is updated last will get priority and the other bones will be pulled away
多控制点的 IK ，也就是多 end effector 末端式效果器的时候，这个 IK 最大的难点就是：当我们用刚才那些简单的算法去够到一个点的话，其他的点再去够那个点本身的目标点时，就会把原来这个点偏来偏去。
CCD 和 FABRIKF 都有多 constraint 的解决办法，这里不展开。
行业内最经典的一个解法是叫雅克比矩阵的解法。
Jacobian Matrix 雅可比矩阵
In vector calculus, the Jacobian Matrix of a vector-valued function of several variables is the matrix of all its first-order partial derivatives
非常复杂有趣的雅克币矩阵会放到后面两节课讲物理系统的时候讲。
一个长链条，假设每个轴都有个 theta 旋转。
其实旋转之后，端点在空间就是一个坐标值，就是一个位置。旋转一直在变的话，这个位置点也一直在变，那多个约束点其实就是多个位置点的问题。
我们可以把角度想象成一个向量，比如说 ，然后把最后那些 endpoint，也就是要控制的那些端点在空间上的位置，想象成是一个关于 角度值的一个方程。这个方程的自变量是个向量了，输出其实是一个三维空间的 vector。然后它和目标点之间的距离，或者是空间的位移，可以成为方程的一个结果。
雅可比矩阵对于这样的空间上的高维方程组，其实你可以用它的梯度，也就是任何一个当前的角度，或者当前摆的这个 pose 下动那么一点点，那它对最终的点产生距离的微分，其实可以表达成一个它的趋向性的，也就是它的导数的矩阵。（这里有点抽象，不继续展开了）
核心思想是：优化一个长臂时，假设长臂有三四根骨骼，要到手指上方一段距离的一个点（目标点）。既然知道了移动的趋势，其实我们可以解这个矩阵。比如先把目标点设置的离手指非常的近，这时候可以反向求出来每个角度要动的小 delta theta 是多少，让长臂离这个点再近一点。然后再去往前走一小步，再去求出每一个 joint 走的小小的 delta theta，又再往前进一点。经过一次次地构造这个矩阵，然后再反向求解这个矩阵，就求出了每一根轴的一点一点的变化，最后让长臂能碰到目标点。
听上去简单，但是雅可比矩阵解起来很复杂。
Using Jacobian Matrix to Present Joint Rotations
Jacobian Matrix with Multiple End-effectors
Approaching to Target Step by Step
最简单的一个理解就是，用雅克比矩阵方法去优化多目标点，实际上是一个逐渐逼近的过程。每一次从当前的端点向目标点靠近这么一小步。然后求解一个每个 joint 应该转的角度数，这个其实是有误差的，转完之后我算出我真实的位置，然后再去构造一个雅可比矩阵，然后再去求解。
这是游戏引擎行业在过去非常标准的多 joint 多约束的 IK 的一个解法。当然它的计算非常的复杂，而且也比较费。所以有很多的工作就是在讲怎么样能快速地去解雅可比矩阵。
Other IK Solutions
Physics-based Method
- More natural（IK 不仅要解决约束问题，还要解决物理的合理性）
- Usually need lots of computation if no optimization
PBD(Position Based Dynamics)
- Different from traditional physics-based method
- Better visual performance
- Lower computational cost
Fullbody IK in UE5
- XPBD（Extended PBD）
雅可比矩阵是一个经典解法。但是 physics based 、基于 position base 等方法也越来越热。所以其实 IK 是一个非常难的问题。
IK is still Challenge
- Self collision avoidance
- IK with predication during moving
- Natural human behavior
- Data-driven and deep learning
到现在为止 IK 还是有很多挑战。
IK 会假设骨骼是纯抽象的，没有空间的体积。比如说解完一个 IK，当我们给其蒙上蒙皮的时候，这些 IK 解出来的结果会自我穿插，自我交叠，这个问题其实还是比较难解决。
IK 很多时候都有个约束点，但是以上图乐队的例子，前面的约束还没有到小人的面前，但是人实际上是有 perception 预知的，所以小人会早早地弯下腰，让自己能够穿过去。这件事情说起来很简单，但是在游戏里面做起来并不简单。
我们看到很多 3A 大作的角色会能根据环境很聪明地做出不同的0互动，实际上都是 designer 老早在那边放了很多的检测体。比如要靠近一个洞了，这个时候就让角色很聪明地知道怎么去弯下腰，当然这个检测可以自动生成。但是真的能够 perception 预知这个 environment，然后能够非常 human like 的去控制角色的身体姿态，这件事情其实也是个非常难的问题。
还有就是更自然的人类的行为学。比如说 IK 解出来是不会管平衡的问题的，但是我们做出的每一个动作实际上重心都是要平衡的，都要符合动力学的规律。而这一点在刚才讲的所有的 IK 算法里面都不会去解决。这就是为什么现在游戏里面很多的 IK 看上去不是那么的自然。
IK Hot Research Areas
所以 IK 是一个现在还在快速演进的一个研究领域。
课程组找了上面的资料，发现其实在过去的十几年里面，IK 方面的文章是越来越多，特别是最近的这十年。为什么最近十年 IK 的算法大爆发呢？
因为随着我们的 3A 游戏要求越来越高，我们希望角色更加真实可信。
我们知道三个比较经典的算法：CCD、FABRIK、还有个数学工具叫雅可比矩阵就可以了。最好能理解透 CCD 和 FABRIK。平时做一个简单游戏的话，用 Two Bone IK 基本上就可以了。
IK 为什么重要？因为在一个实战型的游戏引擎里面，IK 会实实在在地改变动画的 pipeline。
Updated Animation Pipeline with Blending and IK
上一节课讲的动画 pipeline 比较简单。就是把动画的 clips 拿到之后，导成各种各样的 pose，再把 pose 一起去 blend。
但是有了 IK 之后，就要先把这个 blend pose 反向算到模型坐标系，还要把它反向算到世界坐标系。这个时候在世界坐标系里面，也就是在环境里面，各个约束在一起去反向地去解算 IK ，也就是每根骨骼该怎么去调整。然后根据这个 IK，再去调整要提交给渲染器的动画。所以这个过程在动画开发里面我们叫做 post process，这个地方的后处理和在渲染课的后处理讲的不是一个概念。但是动画系统 post process 很多时候指的就是 IK，也就是说要让动画符合对于环境的各种各样的约束。
所以加上 IK，才是一个基本完整的动画 pipeline。
可参考：
