Animation-动画
Historical Points in Animation
最早的动画可以追溯到公元前3200年，那是的人们已经意识到动画就是不同的时间播放不同的图像
19世纪人们已经能够做出真正可以被人所看到的动画
1878年，诞生了人类历史上第一段电影
关于动画发展的其他重要产物与事件还有很多，比如第一部手绘的Feature-Length的动画——迪士尼的《白雪公主与七个小矮人》诞生于1937年，第一个计算机生成的动画诞生于1963年，等等，此处不再赘述。
Keyframe Animation-关键帧动画
关键帧动画本质上是一种插值技术
Simulation-模拟
physical Simulation-物理模拟
基于物理模拟实现动画，其最基础的理论就是牛顿的运动定律
基于物理的动画可以模拟布料、流体等
Mass Spring System-质点弹簧系统
Spring-弹簧
理想情况下的弹簧没有长度，其产生的力的大小与其长度变化量有关，即遵循胡克定律(Hooke’s Law)
如果弹簧不是0长度的而具有一定的原始长度，那么可以有如下的定义
由于能量守恒，在不考虑能量损失的情况下，被拉开的弹簧会永远振动下去。
为了让弹簧振动能够如真实情况一样停下，需要引入阻尼(Damping)，以引入能量损失。阻尼作用的方向是运动的反方向
如上定义的阻尼存在一个问题：它会使得所有的运动减慢直至停止。它只能描述外部的阻力，而无法描述弹簧内部的能量损耗。
于是引入弹簧内部的阻尼。其内部的阻尼遵循的原则是，它总是按照将弹簧恢复原始长度的方向进行作用，其大小与弹簧两端质点的相对速度有关
上图红框中表示a和b的相对速度在a到b方向上的投影的长度大小，是个标量
弹簧质点系统可以组合成不同的形状
如何用弹簧质点系统模拟一块布呢
可以将其连成如下的形状
这种结构存在两个主要问题：
- 结构在切变时会有错误，因为其中没有抵抗切变的力，从而错误地改变形状；
- 对于超出平面的力，比如将布对折，这种结构没有与其对抗的力，而真实的布通常不能像纸张一样这么容易地被对折。
于是加入对角线方向对抗切变的弹簧
这种结构虽然能对抗切变，但是不对称，并且也不能完全抵抗上述第二种情况的力，于是进一步增加另一方向的对角线
这种结构解决了切变问题，但是仍然不能完全解决超出平面的力，比如竖向折叠可能出现没有响应的对抗的力的情况
再次改进
其中红线弹簧是对抗非平面的力，比如弯折等，其力较弱，而先前蓝色弹簧的力较强。
此时上述两个问题终于得以解决。
Particle System-粒子系统
粒子系统是对大量粒子进行建模和模拟，其中有粒子间的相互作用，也有外界对粒子的作用。粒子系统很适合模拟雾、灰尘等效果。
粒子系统中的作用力可以非常复杂，可以有引力、电磁力、摩擦力、粘滞力、空气阻力等等，同时粒子也可能发生各种碰撞。
进一步，粒子系统还可以描述其他复杂粒子群，通过定义个体的行为和个体间的相互作用，粒子系统还可以模拟鸟群等。
Kinematics-运动学
Forward Kinematics-正向运动学
利用运动学也可以实现模拟动画。
我们可以利用运动学描述骨骼动画系统，这种系统可以正确表示骨骼相连的拓扑结构，同时定义了各种不同的关节(1D旋转的Pin、2D旋转的Ball以及可以拉长的Prismatic Joint)
于是利用这种系统，可以用以下方式简化表示一个手臂关节
正向运动学的定义是基于物理的，因此实现较容易，但是对于创作动画的艺术家而言，这种方法不够直观且耗时，于是逆运动学由此诞生
Inverse Kinematics-逆运动学
逆运动学可以简单理解为先确定子骨骼位置，然后反向逐级推到其前面各骨骼、关节的位置。
逆运动学也有存在一些问题，比如其求解很困难、解不唯一等
因此逆运动学需要引入一些优化方法，如牛顿法、梯度下降法等等
Rigging-绑定
Blend Shapes可以混合控制点及其周围区域，常用于人物表情的控制
Motion Capture-动作捕捉
动作捕捉可以将真人的动作反映到虚拟人物上去。
动作捕捉的优势在于其可以在短时间内获取大量真实数据，并且其生成的动作真实感很强；但是动捕也存在一定缺陷，比如其较为复杂且准备工作繁琐，其捕捉到的真人动作不一定能满足艺术家预期的需求。
The Production Pipeline
Single Particle Simulation-单点模拟
模拟单个粒子在速度场中的运动，可以建立常微分方程(Ordinary Differential Equation, ODE)
根据起始点求解常微分方程就可以得到任意时刻粒子的位置。
Euler Method-欧拉方法
欧拉方法是将时间离散化，利用上一时刻的位置与速度求出下一时刻的位置，利用上一时刻的速度与加速度求出下一时刻的速度。
利用上一时刻的信息估算下一时刻信息的欧拉方法称为前向欧拉方法(Forward Euler)或显式欧拉方法(Explicit Euler)
当选择的时间步长较长时，欧拉方法就会产生较大的误差，这个问题可以通过减小来缓解
欧拉方法还常存在稳定性问题，考虑如下两个情形。第一个情形中，粒子在螺旋形速度场中运动，无论取多大的时间步长，欧拉方法模拟出的粒子都无法沿着螺旋形速度场运动，最终粒子一定会离开该速度场，但是实际情况粒子应该始终做圆周运动；第二个情形中，粒子在速度场中振荡应该逐渐减小直至最后水平运动，但是使用欧拉方法模拟粒子会一直来回振荡，并且幅度可能会越来越大。
Combating Instability-对抗不稳定性
Midpoint Method / Modified Euler-中点法/改进的欧拉方法
为了改进原始的欧拉方法，使得其模拟结果不要与实际情况越来越远，人们发明了中点法。
具体做法如下：
首先使用原始欧拉方法模拟出下一个位置a，取当前点与a点的中点b，计算中点b位置的速度，利用该速度从原始出发点重新进行欧拉方法的计算，模拟出新的终点c
中点的核心思想就是使用两次欧拉方法，第一次为了得到中点的速度，第二次计算真正的终点位置。
于是，利用中点法改进后的欧拉方法可以写成如下形式：
Adaptive Step Size-自适应步长
在中点法的基础上更进一步，不对起点直接应用中点速度移动时间，而是将分成两半，前与欧拉方法做法一致，后对中点应用新估算的中点速度。
比较此方法与传统欧拉方法得到的下一点的位置，如果两点位置接近，说明此时划分的效果已较好，无需进一步再分，但是如果两点结果相差较远，则需要继续对做更多更细致的划分
Implicit Euler Methods-隐式方法
隐式欧拉方法又称为后向欧拉方法(Backward Euler)，其每一点使用的都是下一个点的梯度，
由于下一点的速度与位置尚不知道，因此上式实际上是建立了一个方程组，通过求解该方程组可以得到下一点的位置与速度。上式看起来求解较为简单，但是当不是线性关系时，求解就会非常复杂。不过，虽然求解困难，但是隐式的欧拉方法可以提供较好的稳定性。
“稳定性”的定义
对于数值方法可以定义如下两个概念：局部截断误差(Local Truncation Error)，即每一步会产生多少误差；总累积误差(Total Accumulated Error)。稳定性就是通过这两个概念来衡量的。
通常，我们认为研究这两个值的绝对大小是没有什么意义的，应该研究的是这里两个量的阶。
隐式欧拉方法是一阶的
Runge-Kutta Families-龙格库塔法
在数值计算领域中，龙格库塔法是十分有名且常见的方法，龙格库塔并非一种方法，而是一类方法，这类方法十分适合解常微分方程，尤其是对于非线性情况。
龙格库塔法中有一个叫做RK4的四阶方法是其中最为广泛应用的方法。
Position-based / Verlet Integration
非基于物理的方法是一种简化方法，在模拟中非常实用。它根据位置来计算速度，这种方法计算快速且较简单，由于不是基于物理的方法，因此它会引入能量的损耗。在作业8中有这种方法的应用。
Rigid Body Simulation-刚体模拟
刚体不会产生形变，因此对于刚体来说，其内部所有点按照同一种方式运动。
Fluid Simulation-流体模拟
Position-Based方法在流体模拟中就是通过模拟组成水体的小球的位置来模拟浪花等整体状态
这种方法有几个假设前提：
- 水是有许多不可压缩的刚体小球组成的
- 水在任何地方都是不可压缩的
基于这样的假设，当水体运动时，水体各处的密度应当与平静时候相同，但是水体运动时候某些位置的密度会发生改变，因此小球的位置就需要进行改变调整，以“修正”这种密度的变化。
为了实现上述修正，需要知道各处密度对于所有小球位置的梯度，根据梯度更新小球位置。这也就是机器学习中的梯度下降法。
Eulerian vs. Lagrangian-欧拉方法 vs. 拉格朗日方法
对于大规模物质的模拟(如水的模拟、鸟群的模拟)通常有两种方法/视角，分别为欧拉方法(不同于前面所述的欧拉方法，不是一个概念，这里指的是一种模拟大规模物质的视角)与拉格朗日方法
Material Point Method(MPM)
MPM是一种欧拉方法与拉格朗日方法的混合。
