GAMES104：10+11游戏引擎中物理系统的基础理论算法和高级应用-学习笔记

概览

一，物理对象与形状

1.1 对象 Actor

一般来说，游戏中的对象（Actor）分为以下四类：

1. 静态对象 Static Actor：不动的物体，环境桌子等
2. 动态对象 Dynamic Actor ：可能受到力/扭矩/冲量的影响，比如主控角色等
3. 检测器 Trigger：与GamePlay高度相关的触发开关，比如走进范围内就触发效果的这个“范围”
4. 运动学对象Kinematic Actor ：忽略物理法则表现的对象，根据游戏的需要由游戏逻辑控制，比如跑步动画。但反物理的表现经常出现bug，比如碰到一个箱子结果箱子飞了

1.2 对象形状Actor Shape

因为真实世界中物体形状是非常复杂的，其物理求交也非常复杂，所以游戏中通常会用简单形状的物理对象来替代表达，常见形状有：

1. 球Spheres：各种类球形物体
2. 胶囊Capsules：角色
3. 盒Box：建筑家具等
4. 凸包体Convex Mesh：精细一点的物体比如岩石
5. 三角网格Triangle Mesh：如精细一点的建筑（静态）
6. 高程图形成的地形Height Fields：地形

• 用这种简单几何体去模拟物理对象时有两个原则：
  1. 形状差不多就好，不用完美贴合
  2. 简单性。几何形状越简单越好（比如避免用Triangle Mesh），几何体个数越少越好。
• 这里课件里有个很漂亮的石头受光焦散图，放一下：
  

二，力与运动

• 物理概念：
  1. 质量和密度 Mass and Density
  2. 质心（做载具时很重要，比如卡车）Center of Mass
  3. 摩擦和恢复（弹性） Friction & Restitution
  4. 力Forces：有直接的拉力、重力、摩擦力以及Impulse 冲量（比如爆炸导致的冲击力，其实是力x时间）两种

2.1 牛顿定律

高中知识就不记了

2.2 欧拉法

2.2.1 显式欧拉法Explicit (Forward) Euler’s Method

这是与积分直觉最接近的算法，思路简单，即下一时间的速度和位置都用上一时间的量去计算：

• 但由于显示欧拉法一直用当前状态值去预估未来状态，在实际模拟时Δ t 不会无限小，会有误差导致能量不守恒（变大），如上右图，在模拟绕点旋转的时候速度越来越快逐渐甩出去，能量也凭空变多，导致能量爆炸。（Δ t 很小可以避免，但实际做不到）

2.2.2 隐式欧拉法 Implicit (Backward) Euler’s Method

思路是用未来的力和速度去求未来的位置，但未来的力怎么计算呢，需要假设力是位置的函数去反向计算，如下图：

• 如图，隐式欧拉法的能量虽然也不守恒，但是至少能量是衰减的，符合现实物理规律（受空气阻力摩擦力影响等），因此在游戏中更容易接受。
• 但其也有计算成本高（反向计算未来值）并且运动非线性时难以计算的缺点

2.2.3 半隐式欧拉法 Semi-implicit Euler’s Method

半隐式欧拉法就是结合了前两种方法，新速度用旧的力去算，新位置用新速度算：

• 前提假设：力是不随着位置改变的（很危险的假设，实际上力跟物体位置是相关的，比如橡皮筋弹射过程）。
• 优点：大部分稳定、计算简单有效、随着时间的推移能够保存能量
• 缺点：在做一些sin cos等运动时，积分出来的周期会比正确值长一点点，所以在相位上会有偏移差

三，刚体动力学

之前的内容都是把物体看作一个质点，但真实世界中大部分物体是有形状的，即刚体（柔性模拟另说）。刚体动力学中比普通质点的计算多一些概念，比如自转、旋转等，概念对应见下图：

这part在部分场景下很重要，比如台球游戏，不仅需要旋转还要自转还要移动，了解即可，详情见高中物理

四，碰撞检测

碰撞检测一般分为两个阶段：

1. Broad phase 初筛 – 利用AABB判断刚体有没有相交
2. Narrow phase – 计算详细碰撞信息（碰撞点、方向、深度等）

4.1 Broad phase 初筛

常用有两种方法：

1. BVH Tree – 动态更新成本低，方法成熟
   

2. Sort and Sweep – 比BVH更快，先沿轴周把每个AABB边界大小值排序，再逐个扫描，如果minmax没按照顺序来就有可能发生了碰撞这时再去判断另一个轴上的情况。这种排序算法可以把静态物体排好序后，只更新动态物体的位置（插入排序），这种方法更快。
   

4.2 Narrow phase

4.2.1 Basic Shape Intersection Test

最简单的球和胶囊体碰撞，去判断距离和半径大小即可判定是否相交

4.2.2 闵可夫斯基距离法Minkowski Difference-based Methods

该方法用于计算两个凸包体是否碰撞，思路是将两个多边形是偶相交问题转换为一个多边形是否过原点问题

前置概念

• Minkowski Sum（闵可夫斯基和）

以两个三角形各自围成的点集为例，两个点集相加的结果是指所有A点集的点加上所有B点集的点，几何表示为B点集的图形作为笔刷，用其原点（0,0）去刷过A点集的边缘所形成的图形，示意图如下：

• Minkowski Difference（闵可夫斯基差）

同样的，集合A-B就相当于集合A+(-B)，也就是A与B的原点对称图形集合的闵可夫斯基和，如下图所示：

而在闵可夫斯基差定义中可知，如果AB两个集合（凸包）有重叠的话，那它们的闵可夫斯基差图形中必定有原点，因此两个凸包是否有交叠（碰撞）的问题就转换为了计算其闵可夫斯基差是否包含原点，那怎么计算呢，见下边GJK算法?

GJK算法

伪代码如下，其中Support函数是指在给定方向上计算闵可夫斯基差图形上边界顶点位置：

• 案例计算过程：

  1. 选取一个初始方向dir，比如（0,1）；

  2. 找到集合A在初始方向dir上的最远点和集合B在反方向 -dir 上的最远点，计算两者差值，称作一个support点，即为闵可夫斯基差图形上的一个边界顶点，如图（3,5），将该点加入simplex中；

  3. 此时将dir反向为（0，-1）；
     
     此时开启第一次循环：

  4. 在此时的dir方向上重复步骤2，计算出新的support点（3，-1）

  5. 新的 support 点（3,-1） 与 迭代方向（0,-1） 的点乘结果大于0，说明跨越原点了，将该点加入simplex中；

  6. 以这两个点的直线的垂线朝向原点的方向（-1,0），作为下一次迭代方向；
     此时开启第二次循环：

  7. 根据新迭代方向 dir（-1,0），得到 support 点（-1,2）；

  8. 新的 support 点（-1,2） 与 迭代方向（-1,0） 的点乘结果大于0，说明跨越原点了，将该点加入simplex中，此时simplex有3个点

  9. 此时simplex里的三个点组成的三角形没有包含原点，删掉离原点最远的点，以剩余两个点朝向原点的垂线方向（-3,-4）作为下一次迭代方向；
     
     此时开启第三次循环：

  10. 根据迭代方向 dir（-3,-4），得到 support 点（-1,-1）；

  11. 新的 support 点（-1,-1） 与 迭代方向（-3,-4） 的点乘结果大于0，说明跨越原点了，将该点加入simplex中，此时simplex有3个点

  12. 此时simplex里的三个点组成的三角形包含了原点，说明这两个凸包体相交。结束；
      

4.2.2 Separating Axis Theorem分离轴定理方法

该方法用于计算两个凸包体乃至3D凸包体是否碰撞相交。

• 原理：如果两个物体分离，则肯定能找到空间中一根轴把它们分隔开，不然就是相交。

因此可以在两个多边形的边上进行穷举计算，即把凸包A的每条边和凸包B的每条边当分隔线试试（将点都投影到该条边的垂线上，判断是否同侧即可），如果能找到某一条边能分隔两个凸包体，则他们不相交，反之则相交。

如果延伸到3D空间的两个凸多边形体，则需要在找到一个能够分隔两个物体的面，穷举两边所有的面还不够（因为有可能两边没有相交，但面的延伸切割到了几何体），还需要穷举AB两边的边叉乘形成的面，只要能找到一个面可以分隔，则不相交。

五，碰撞解决

碰撞之后应该怎么将碰撞物体分开、进行物理表现呢？最简单的早期方法直接是加一个反作用力（Penalty Force），但这样会导致物体突然分隔开，很假。

现代引擎比较流行的方法是把力学问题变成数学上的约束问题，利用拉格朗日力学对速度进行约束。

• 解约束常用方法：
  1. Sequential impulses顺序推力
  2. Semi-implicit integration半隐式积分
  3. Non-linear Gauss-Seidel Method ：Gauss-Seidel迭代法–现代物理引擎最常用
     相当于给碰撞物体加个小冲量从而影响速度，在看此时是不是还碰撞（是否符合拉格朗日约束、有没有误差），不断重复直到误差可以接受或者迭代次数超过设定。
     

六，场景请求

• Raycast：打出一条光来判断是否与其他物体相交，有3种返回情况：

  1. Multiple hits：所有打中物体都返回
  2. Closest hit：返回打中的最近的物体
  3. Any hit：只要打中就返回（最快）

• Sweep横扫
  比如判断人有没有被挡住时是把人的整个胶囊体进行扫描判断的，只要有一部分被挡住就是被挡住了。
  

• Overlap形状判断：比如设定半圆范围内触发，判断手雷爆炸时能炸到哪些人。

七，效率、准确性与确定性

• Sleeping
  物理计算中常把场景的不同物品或部分分组，计算时让这段时间没有move或不需要计算的组进入sleep，以提高计算效率。
• Continuous Collision Detection（CCD）
  物体快速运动时如果碰撞一个比较薄的物体，如墙等，可能在前后两帧都没有碰撞，就直接穿了过去，导致卡模型bug。
  

1. 朴素点的方法就是把墙等物体做的厚一点。
2. 但规范的做法是CCD：物体在环境移动时先计算一个安全移动距离，在此范围内随便移动，但在靠近碰撞物体时，把碰撞检测计算频率增加，等距离回到安全距离后再恢复正常计算。

• Deterministic 确定性----物理引擎非常重要的难点
  现在很多游戏都是online游戏，那不同玩家看到的世界如何同步呢？就需要在确定的输入和游戏规则下，大家的物理计算是一模一样才行，这就是物理引擎的确定性；如果物理引擎有确定性的话，就可以不需要同步很多的中间状态，只需要同步相同的输入即可。

但确定性非常难以保证，在不同帧率、不同硬件端侧、不同计算顺序、不同的精度计算下结果都会大不一样

目前即使是商业物理引擎也无法做到在不同硬件上结果一致，需要做大量的处理才能保持逻辑一致性

八，角色控制器

Character Controller和普通的动态对象（Dynamic Actor ）是不同的，主要的三个特点是:

1. 可控制的刚体间的交互
2. 摩擦力假设为无穷大（可以站停在位置上），不会被飞来物体撞飞
3. 加速、减速、转向都是瞬时的，甚至可以传送

所以其实角色控制器其实是反物理的，与Kinematic Actor概念很像，不受物理规则的影响，同时可以push其他object

角色控制器的创建

角色控制器本身并不是多复杂的对象，但其拥有很多小细节和设计来模拟各种不同情况下的真实处理。而作为引擎设计者，应在设计角色控制器时留有较多的处理空间给开发者进行不同的细节设计。

• 双层结构

人形角色一般用胶囊来代表，在很多射击游戏里会用到双层胶囊来制作，内层用于碰撞计算，外层用于当做“保护膜”，避免角色离其他东西太近。例如角色高速运动卡到墙里、或是太贴近墙的时看到墙后东西（相机近平面）等问题。

• 角色与环境的碰撞

当我们控制的角色与墙发生碰撞时，不该停下来。更符合我们认知的是该沿着墙进行滑动，即sliding算法，先计算方向切线，在让人物沿着切线移动

• 自动stepping及其问题

游戏世界很难全是连续的，经常会遇到台阶等，就需要用的stepping，即角色上楼梯时，先把角色晚上抬一点，再往前移动；但这个方法如果设计师没有设计好，在角色stepping时，会被建筑物的门卡住，所以一般门都会比设计得比正常大30%左右。

• 斜坡限制和向下滑动

当角色爬坡时，一般有个最大可爬角度，当坡度大于这个值时，就爬不上去角色会往下滑（假物理）。不过这样其实不符合真是情况，真实的上坡应该有上爬的动作，下滑应该有刹车的动作等，精细的物理系统需要在这方面调整很多。

• Controller 的物理体积更新

在切换动作时，角色的碰撞体积也应该对应修改，比如钻下水道等情况。并且在更新之前需要进行重叠测试，以避免物理系统处理的比较快等原因导致动作切换时角色被卡在地道里，比如刚出地道的瞬间。

• Controller 推动物体

角色碰到动态actor时，触发回调函数，根据角色的速度、质量等计算出一个冲量加到动态actor上。

• 站在移动的平台上

在这种情况下，一般用raycast 检测角色站到哪个物体上，并在逻辑上把角色控制器和平台物体绑定在一起（除非要进行更高标准精细计算的情况），来防止平台移走角色下落的情况以及因为帧率问题导致的角色处在上下移动平台上时不断弹动的情况。

九，布娃娃系统Ragdoll

为什么需要布娃娃系统？当一个角色被刺杀后需要播放对应的死亡动画，但这个动画与环境没有互动关系；引入布娃娃系统，刚开始用动画，后面将动画作为物理的输入，让物理引擎去模拟，就可以自然很多。

9.1 具体实现

• 将关键的骨骼映射成刚体，一般为了减少计算就十几个。然后限制彼此之间的约束关系（TA完成），形成合理的转变动作。

• 驱动骨骼，骨骼在布娃娃系统里可以分为以下3种

  1. Active joints — 布娃娃刚体和原本骨骼重叠的部分，直接用原骨骼变化
  2. Intermediate joints — 在两个布娃娃刚体之间的原骨骼，插值均分来获取信息
  3. Leaf joints — 在布娃娃刚体尽头外未被覆盖的原骨骼，使其保持动画设定跟着布尽头的刚体变化
     

• 混合动画和布娃娃系统：一般在角色死亡前后会进行从动画转到布娃娃系统的物理计算的转变。那么这个边界在哪里呢：一般边界没有那么清晰，都是相互blending使用，比如把动画的状态作为物理的初始速度计算，再叠加回动画（类似支持蒙皮骨骼动画的物理解算）
  

十， 布料模拟

游戏开发发展过程中出现过三个布料模拟方面的经典方法，分别为：

• 基于动画的衣料模拟

动画驱动骨骼驱动顶点，类似于原神的骨骼预烘焙动画。优点是廉价可控，能上移动端；缺点在于不够真实、和环境没有交互以及设计上受限

• 基于Bone的衣料模拟

即基于骨骼的物理模拟，基础的物理解算加上约束。优点是廉价有交互；缺点是效果一般

• 基于mesh的衣料模拟
  这部分是重点，需要专门说：

10.1 基于mesh的衣料模拟

本质是逐顶点物理计算的方式。由于性能问题，一般计算布料模拟的网格会比实际渲染网格稀疏很多，一般面数是0.1倍就行。

• 移动范围约束，比如披风，越靠近肩膀可移动范围越小（需要美术刷权重），这样既能更符合物理实际，又可以减少穿模概率（目前游戏引擎都很难解决）
• 设置物理参数
• 实现计算：弹簧质点系统，计算公式有下面几种
  1. 使用verlet积分计算（半隐式欧拉法转换得到，不需要计算速度）
  2. PBD(Position Based Dynamics)—最主流，可以直接由约束计算出位置，而不需要再由约束得出力再算出速度位置，最后一章单独讲。

10.2 自穿插问题

• 即衣服自身或者衣服之间相互穿模的情况，当前角色衣服经常穿好几层，所以这个问题对高品质游戏很重要，目前还是非常前沿的领域，解决方案有4个：
  1. 单纯把衣服加厚（即使有一定穿模也不影响）
  2. 增加计算精度（1step里解算多个substep，至少不会穿透很深）
  3. 设置最大速度值，防止衣料之间穿模的过深
  4. 3的基础上再设置一个反向力，穿模还能弹回来

十一，破坏系统Destruction

• 制作步骤
  1. 设计数据结构( Chunk Hierarchy)，一般是自动生成树状结构来将未被破坏的物体分割成不同大小的块，对不同层级设置同步的破坏阈值。
  2. 构建碎片间的连接关系，指同一层的不同块之间的关系。
  3. 给连接关系设置破坏值（硬度），每次破坏后计算伤害值（ D = I冲量 / H硬度 ）更新破坏累积值。
  4. 造成伤害时，在比较小的范围内物体收到的伤害相同，在此之外伤害随半径增加而递减。

• 步骤一中的树状结构怎么自动生成?

Voronoi Cell算法。简单讲就是在物体上随机撒一些种子，每个种子以相同的速度不断扩大半径，直至撞到其他种子区域，当全部稳定下来后就形成不同的块（类似细胞）。「3维物体的切割也是类似。只是最后要用一个分割四面体的方法。」

• 那切割模型之后断口处纹理怎么处理呢（尤其是3D物体）？一般有两种方式：

  1. 直接制作对应的3D纹理，切割时直接用，但从生成到采样都复杂
  2. 离线计算好这些纹理，一旦破碎则切换到对应的纹理，这种需要瞬时处理，也很复杂。
     

• 破碎时怎么表现呢？有许多方式，均匀的、随机的、中心往外碎等，还需要有对应的声效、粒子效果等

• 破坏掉的碎片间的物理互动、相互碰撞：慎用，开销巨大。

• 一些Popular的破坏模拟引擎：

  1. NVIDIA APEX Destruction
  2. NVIDIA Blast
  3. Havok Destruction
  4. Chaos Destruction（Epic Games.）

十二，载具模拟Vehicle

XX飞车系列游戏必备的技术

12.1 载具模型

形状模型=一个刚体+一些弹簧等组件。

12.2 受力

• 驱动力Traction Force

扭矩大，加速度大，只要不打滑基本都是静摩擦在起作用。由引擎扭矩经过一系列操作获得轮胎扭矩，再从而获得摩擦力F。

• 悬挂力Suspension Force：轮胎对车来说有个类似弹簧的弹力，随着轮胎离车体距离影响弹力。
• 轮胎力Tire Force：分两个：一是向前的纵向力，由向前的驱动力和反向阻力组成（驱动轮）；二是横向力（用于转弯），是由滑动摩擦力（与重心相关）和角度构成。最终方向由两个力的合力构成。

12.3 重心

重心也很影响车的设计和体验，重心正常时是两轮中心点。

• 在跳跃、转弯时重心靠前和靠后结果会很不一样，重心靠后会让车更稳定、转弯时更容易转大弯。（因此后驱车比前驱车稳定）
  
• 在车子行驶时中心也会变化产生Weight Transfer：加速时重心会后移，减速时前移
• Steering angles 驾驶角度：如果前面两个轮胎转动一样角度时，靠外的轮胎会发生空转。所以实际驾驶中转弯时两个轮胎的转动角度是不一样的，用轮胎到转动圆的圆心切线决定转动角度—Ackermann steering，这样转弯时才能转出完美曲线。
  
• Advanced Wheel Contact轮胎与环境的交互，比如在过减速带时，如果简单的进行raycast（当前轮胎被减速带穿模过了就往上抬，否则下降），会出现穿模。实际处理中要用spherecast，将轮胎整体以圆的形式去判断。
  
• 部分游戏中还有坦克的履带模拟、飞行器的空气动力学模拟，就非常复杂了

十三， 高级：PBD 与 XPBD

• 拉格朗日力学：不同于牛顿力学中提到的物体的运动会受到规律（比如能量守恒）限制，拉格朗日力学把力学规律描述成一系列力学约束，用约束反向定义运动，结果运动规律可以被反向定义回来。从而把很多力学问题化成了求解约束（Solving Constraints）的问题。

13.1 PBD

• 以圆周运动为例，分别对位置和速度进行约束，其中dC/dx就是也可比矩阵，数学背景知识补充——雅可比矩阵：
  
• PBD是其实就是根据雅克比矩阵求出某点移动的倾向，再用步长去不断迭代优化约束状态，去尽量逼近约束为0（或小于设定值）的过程----类似梯度下降法。不需要计算速度等中间量。
• △X是沿着雅克比矩阵的方向去走的，并确定步长。
• 伪代码：（流程和自己做的pbd一模一样，只是求解约束是用了雅可比矩阵去迭代）

• PBD的优势：技术目前非常热，因为求解收敛快且稳定

13.2 XPBD

Chaos自称使用的就是XPBD

• XPBD在 PBD 的基础上增加了刚度（ stiffness) 来描述约束的软硬程度，例如硬币的刚度就比较大，布的刚度就比较小。
• XPBD相当于把PBD的约束方程升级为Compliance Matrix服从度矩阵，见下式里的U(x)；土法理解：stiffness类似弹簧的硬度，C(x)理解为误差偏移量，那么弹簧势能就是$\frac{k{x}^2}{2}$，当约束很多维时就算变为矩阵，也就是说下图的公式可以理解为约束的势能
  
• XPBD近几年刚兴起，还没有经过大规模工业化的检验；它同时有物理的真实性和可控性