PhysicalBasedAnimation

• mesh 由顶点和元素构成。顶点就是节点，元素可以是三角形、多边形、四面体等等
  
• 三角形 mesh 是当前图形学的基础。显卡都是基于三角形 mesh 所设计的
  
• 相关的问题 :
  
  • 构建 mesh(meshing) : Delaunay triangulation
    
  • 简化 mesh、细分 mesh
    
  • mesh 优化 : smoothing, flows
    
  • volume mesh
    
• mesh 又分为两种类型：Structured Mesh 和 Unstructured Mesh
  

• 点云表示几何体很简单，表面扫描就可以得到点云表示的几何体
  
• 相关的问题 :
  
  • 从点云构造 Mesh
    
  • 对点云进行采样
    

• 使用 grid 对整个空间进行分割，每个 cell 存储对应点的物理信息
  
• 体积扫描(如 CT)可以获得 grid 表示的几何体
  
• 相关的问题 :
  
  • grid 表示几何体内存占用比较大，如何优化？
    
  • 体积渲染
    

动画分为角色动画(Character Animation)和基于物理的动画(Physics-Based Aniamtion)

渲染分为两大类：真实感渲染和非真实感渲染
材质是渲染相关的一个重要话题。材质扫描（物体、人）

动画的目的是在每段时间间隔内更新物体的状态。被更新的状态可以是 位置、朝向、速度、外观、密度等等。time step 不必和 frame rate 相匹配，通常动画的 time step 要比渲染的 time step 要小，即动画帧率大于渲染帧率。

下图展示了基于物理动画的研究内容：

SIGGRAPH 2013 A Material Point Method for Snow Simulation 论文中使用 Hybrid Method 来模拟雪。

下图展示了本课程所涉及的内容：

一个矩阵 A 可以被分解为 UDV^T。U和 V 为正交矩阵，D为对角矩阵。
奇异值分解的直观解释： 任何一个线性变形都可以被分解为三个步骤，1 旋转(U),2 缩放(D),3 旋转(V^T)

图形学中只考虑对称矩阵的特征值分解。对称矩阵（Symmetric Matrices）是指以主对角线为对称轴，各元素对应相等的矩阵。
一个对称矩阵 A 可以被分解为 UDU^-1。U为特征向量组成的正交矩阵，D为特征值组成的对角矩阵。

非对称矩阵 A 也可以进行特征值分解，此时特征值和特征向量为虚数。

• https://baike.baidu.com/item/%E7%89%B9%E5%BE%81%E5%88%86%E8%A7%A3
  

对于任意不等于 0 的向量 v，如果 v^TAv > 0, 则对称矩阵 A 对称正定(symmetric positive definiteness)
对于任意不等于 0 的向量 v，如果 v^TAv >= 0, 则对称矩阵 A 对称半正定(symmetric semi-definite)

上面定义的直观理解：

• 矩阵 A 特征值都大于 0 则矩阵 A 是正定的(Positive Definiteness)。通常不使用特征值分解来判断矩阵是否是正定的，因为这样特征值分解比较耗时
  
• 对角占优的矩阵是正定的，但正定矩阵不一定是对角占优的
  
  
• s.p.d 矩阵是可逆的
  
  

很多数值计算问题最终都会被化解为求解一个线性系统，一个线性系统可以被形式化地表示为：

• A 为方阵
  
• x 为未知量
  
• b 为边界条件
  

如果可以直接计算 A^-1 ，则 x = A{-1}b
但是，A^-1 的计算通常比较耗时，而且如果 A 为稀疏矩阵，A{-1} 可能不是稀疏矩阵，则存储 A{-1} 占用的空间会比较多。

通常有两种方法来求解线性系统：直接法(direct)和迭代法(iterative)

一元函数的微分、导数
二元函数的偏微分、方向导数、梯度

多元向量值函数、多元向量值函数的偏微分组成的雅可比矩阵、散度(通量密度)、旋度(环流量密度)

• 向量值函数 https://baike.baidu.com/item/%E5%90%91%E9%87%8F%E5%80%BC%E5%87%BD%E6%95%B0
  
• 梯度、散度、旋度 https://zhuanlan.zhihu.com/p/97545154
  
• 矩阵求导 https://zhuanlan.zhihu.com/p/263777564
  
• 雅可比矩阵 ../theory/AdvancedMathematics.html#org0fee413
  
• 图形化理解什么是雅可比矩阵？正确理解导数和积分的另一种方式 https://www.bilibili.com/video/BV1Wq4y1T7Qo/?spm_id_from=333.337.search-card.all.click&vd_source=36597ac15683c2bddfe189d605ca1fa4
  
• 雅可比矩阵是什么东西 https://www.bilibili.com/video/BV1NJ411r7ja/?spm_id_from=333.337.search-card.all.click&vd_source=36597ac15683c2bddfe189d605ca1fa4
  

多元函数的二阶偏微分组成的 Hessian 矩阵、Lapacian

下图为一元函数和多元函数的泰勒展开。泰勒展开的本质是利用多项式函数逼近目标函数，目标函数可以是任意函数(自然也包含积分函数了)。

• 怎样更好地理解并记忆泰勒展开式？ https://www.zhihu.com/question/25627482/answer/313088784
  
• 如何通俗地解释泰勒公式？ https://www.zhihu.com/question/21149770
  
• 如何通俗地解释泰勒公式？ https://www.matongxue.com/madocs/7
  

向量长度的偏导数为向量转置后的单位向量，梯度的方向为偏导数向量的转置，因此向量长度的梯度为向量对应的单位向量，即沿着向量方向生长，向量的长度变长。

能量求导得到力，力求导得到 stiffness（stiffness 是 Hessian 矩阵）：

上面 Tangent stiffness 的推导如果看不懂，可以直接看视频讲解。

弹簧两端都可以移动的情况：

显式 Euler 方法求积分如下：(该方法一阶正确)

隐式 Euler 方法求积分如下：(该方法一阶正确)

上述泰勒展开的推导：

Mid-point 方法求积分如下：(该方法二阶正确)

显式、隐式方法（半隐式方法）：

Leapfrog 方法：

矩阵表示旋转的优缺点：

• 优点:
  
  • 使用矩阵和向量的乘法就可以表示物体的旋转
    
• 缺点
  
  • 3x3 矩阵有 9 个元素，而旋转只有 3 个自由度，因此矩阵表示旋转有很多冗余
    
  • 不直观
    
  • 定义旋转速度比较困难
    

欧拉角表示旋转的优缺点：

• 优点：
  
  • 直观
    
  • Unity 用户操作界面中使用了欧拉角表示旋转，euler 角所使用的旋转顺序为：Z，X，Y
    
• 缺点：
  
  • 存在万向锁问题
    
  • 定义旋转速度比较困难
    

在复数系统中，a+bi 可以表示一个二维的点，a+bi+cj+dk 可以表示一个三维的点。

四元数计算法则如下：

四元数表示旋转可以避免万向锁、而且定义旋转速度比较容易。
关于四元数详情，请参考 ComputerGraphicMath 中 Quaternions 部分

力矩描述了力所引起的旋转的趋势。力矩越大旋转越强烈、力矩越小旋转越弱。(等价于平移运动中的力)

转动惯量(Inertia)描述了对旋转趋势的抵抗。和质量不同，转动惯量不是一个常数，其为一个矩阵。(等价于平移运动中的质量)

// 下面代码用来计算 I_ref
I_ref = Matrix4x4.zero;
for (int i = 0; i < vertices.Length; i++)
{
    mass += m;
    float diag = m * vertices[i].sqrMagnitude;
    I_ref[0, 0] += diag;
    I_ref[1, 1] += diag;
    I_ref[2, 2] += diag;
    I_ref[0, 0] -= m * vertices[i][0] * vertices[i][0];
    I_ref[0, 1] -= m * vertices[i][0] * vertices[i][1];
    I_ref[0, 2] -= m * vertices[i][0] * vertices[i][2];
    I_ref[1, 0] -= m * vertices[i][1] * vertices[i][0];
    I_ref[1, 1] -= m * vertices[i][1] * vertices[i][1];
    I_ref[1, 2] -= m * vertices[i][1] * vertices[i][2];
    I_ref[2, 0] -= m * vertices[i][2] * vertices[i][0];
    I_ref[2, 1] -= m * vertices[i][2] * vertices[i][1];
    I_ref[2, 2] -= m * vertices[i][2] * vertices[i][2];
}
I_ref[3, 3] = 1;

Tips:
这里说的转动惯量，其实是惯性张量。当然，也有人说转动惯量和惯性张量是同一个概念。

• 转动惯量 https://baike.sogou.com/v64484710.htm
  
• 惯性张量 https://baike.baidu.com/item/%E6%83%AF%E6%80%A7%E5%BC%A0%E9%87%8F
  
• 转动惯量是标量还是矢量？ https://www.zhihu.com/question/348221712
  
• Moment of inertia https://en.wikipedia.org/wiki/Moment_of_inertia
  

Penalty 方法首先检测当前是否发生碰撞，若发生则应用一个力将粒子弹开。
当使用的力和粒子进入物体的距离为线性关系时，此时的能量和进入物体的距离为二次关系，因此称该 Penalty 方法为 Quadratic Penalty Method.

上面的方法中，无论 k 多大都无法严格避免穿透，因为只有穿透时，才会应用 Penalty 力将粒子弹开。因此，可以在表面之上增加一个缓存区，进入缓冲区就对粒子应用 Penalty 力。

上面的方法中，当 k 比较小时，若粒子猛烈撞向物体时，粒子依然有可能进入物体内；当 k 比较大时，粒子缓缓撞向物体时，粒子可能会被弹很远（overshooting 问题）。
为了缓解这些问题，可以将 k 和碰撞距离关联起来，碰撞距离越小 k 越大，碰撞距离越大 k 越小。新的方法被称为 Log-Barrier Penalty Method。

上面方法无法完全避免 overshooting。而且当粒子穿透物体时，会越陷越深，因此需要小步长来保证不会发生穿透。

Penalty 方法是通过施加力来起作用的，力的影响会在下一帧生效，其不会在当前帧影响物体的位置和速度。
Impulse 方法则是在碰撞发生时立刻对位置和速度进行修改。

刚体一般使用 Impulse 方法，衣服和弹性体一般使用 Penalty 方法。物理世界中，本质上碰撞是由于分子之间的互斥导致的，摩擦是由于表面的不平整导致的。

• 易于实现，和其他质点系统容易结合（如：衣服，软体，粒子流体, 前面这些都是基于质点进行模拟的）
  
• 不易于严格满足所有的约束（例如，摩擦的约束）
  
• 通常不需要精确的摩擦、或碰撞时，可以使用该方法（例如：衣服上的扣子）
  

牛顿法解优化问题：

1. 首先，第一步是将问题转化为优化问题，即构造 f(x), 使得 f'(x)=0 为我们的非线性方程
   
2. 其次，使用一阶泰勒展开近似 f'(x)，通过多次迭代，求出 x
   

所以，关键是要构造 f(x) 函数，使得 f'(x) f''(x)都可以方便计算。

对于求 a 的平方根这个问题来说，假设 a 的平方根为 b（即 √a = b)，则 b^2 = a。所以可以将 f'(x) 构造为 b^2-a，即 f'(x)=x^2-a，f''(x)=2x
对于求多项式的根这个问题来说，可以直接将 f'(x) 构造为多项式。如对于 ax^2+bx+c=0, 可构造 f'(x)为 ax^2+bx+c，即 f''(x)=2ax+b

但是，牛顿迭代法对于某些问题是不收敛的。课程视频中也对牛顿法有详细说明。

• 如何通俗易懂地讲解牛顿迭代法？ https://www.matongxue.com/madocs/205 有道云备份
  
• 一文看懂牛顿法（附 Python 实现）https://zhuanlan.zhihu.com/p/105265432 有道云备份
  
• Newton-Raphson Method geogebra https://www.geogebra.org/m/DGFGBJyU
  

• 欧拉定理 https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86
  

目前为止，我们讨论模拟模型(质点弹簧模型、其他弯曲模型)时，假设拉伸和弯曲是互相独立的。现实情况也是如此，例如，纸可以弯曲但不可以拉伸。

投影函数有两个要求：

1. 可以对模拟后的顶点进行移动使的新的位置符合约束要求
   
2. 移动的距离要最小
   

mi 和 mj 分别为两个质点的质量。质量大的移动距离应该小，质量小的移动距离应该大。

PBD 本身没有什么物理含义，物体的 stiffness 是由下面两个因素所决定的：

1. 迭代次数
   
2. 模型的分辨率（顶点数量）
   

PBD 速度快的一个原因是，PBD 涉及到的变量少，所以内存访问少，从而速度就很快。对于现在的 GPU 和 CPU 来说，物理模拟中内存访问对性能影响很大。

下面论文使用了层级化的 PBD，来加速模拟速度:

• 2008-Hierarchical Position Based Dynamics https://matthias-research.github.io/pages/publications/hpbd.pdf
  

下面的约束为对拉伸比例的约束，|xi-xj|/L 为拉伸比例。
Strain 在物理里是表示描述形变的量，拉伸比一定程度上可以描述形变的程度。Strain 可以是 1 维的也可以是 2 维 3 维的，这里的弹簧是 1 维，后面的有限元就是 2 维 3 维。

这里的 Spring Strain Limit 相当于放宽了的 PBD，PBD 相当于拉伸比为 1 的 Spring Strain Limit。

下面的约束为对面积的约束，对面积的约束可以转化为对三角形缩放的约束。

布料通常拉伸比较小时弹性比较小，此时不怎么抵抗拉伸，当拉伸比较大时，弹性会很大，此时对拉伸的抵抗很强。利用 Strain Limiting 可以模拟这样的效果，将模拟过程分为两个阶段，拉伸比较小的时候，做正常的物理模拟，拉伸比较大时，就增加 Strain Limiting。

当把模拟过程分为两个阶段的时候，我们可以在第一个阶段模拟中使用小的弹性系数，这样就减弱了 Locking Issue。

结合下面压强的定义，可以更容易上面的公式。

前面刚体动力学中位置的更新方式为:
x(t0+dt) = x(t0) + v(t0)*dt
v(t0) = (x(t0)-x(t0-dt))/dt
x(t0+dt) = x(t0) + x(t0) - x(t0-dt)

结合上面推导，可以理解下面公式：

流体和刚体的耦合是双向的。流体对刚体有浮力，刚体会占用流体的空间。

刚体对流体的影响如下：

流体对刚体的浮力影响如下：

• 泊松方程 https://baike.baidu.com/item/%E6%B3%8A%E6%9D%BE%E6%96%B9%E7%A8%8B