GAMES104-Lecture 10 游戏引擎中物理系统的基础理论和算法

Physics Actors and Shapes

Actor

• static actor

• dynamic actor

• Trigger：触发器

• Kinematic(No Physics Law) Actor：根据游戏需要进行运动

Actor Shapes

• Soheres

• Capsules：用于角色

• Boxes

• Convex Meshes：凸包多面体

• Triangle Mesh：静态物体，动态的话开销会很大

• Height Fields：用于地形

• 使用上面这些shapes将object包起来

• Shape Properties：

  • Mass、Density

  • Center of Mass质心

  • Friction & Restitution摩擦力、弹力

Forces

• Gravity、Drag、Friction

• Impulse冲量（爆炸explosion center -> explosion impulse）

Movements

• 牛顿第一第二定律

• Movement under Varying Force

  • Time Integration

  • Explicit(Forward) Euler’s Method:显示欧拉积分，用当前的力算下一时刻的速度，用这一时刻的速度来计算下一个时刻的位置，问题就是积分过程是不收敛的，能量不守恒

  

  • Implicit(Backward)Euler’s Method：隐式欧拉法，用下一个时刻的力算出下一时刻的速度来计算下一个时刻的位置，但是能量会衰减。这是稳定的，并不会爆炸

  

  • Semi-implicit Euler‘s Method：半隐式欧拉法，用当前时刻的力计算下一时刻的速度，用下一时刻的速度计算下一时刻的位置，此时是假设这一时刻的力没有变化，稳定性高，计算效率高，但是在做简谐运动的时候，使用半隐式计算出来的周期会比ground truth的略长。目前这个方法是性价比最高的

  

Rigid Body Dynamics

• Particle Dynamics：质点动力学

• Rigid Body Dynamics：刚体动力学

• Rotational Inertia：转动惯量

• Angular Momentum角动量，角动量守恒

• Torque力矩

• 台球案例

Collision Detection

Two Phases

Broad Phase初筛

• 用AABB计算碰撞的可能性

• BVH：当环境中的物体发生变化时，更新的成本非常低

• Sort and Sweep：把每一个物体的bounding的每个轴的min和max排序，当至少两个轴产生交错的时候，就发现可能有交集；因为大量物体是不动的，所以只对局部会动的物体进行排序

Narrow Phase精细地判断

• 判断是否重叠

• 生成碰撞信息：估计橡胶的顶点、相交处的法线、相交的深度

• Narrow Phase方案：

• Basic Shape Intersection Test

  • 球球相交，计算距离和两个球的半径和

  • 胶囊和球相交、胶囊相交

• Minkowski Difference-based Methods

  • 点集A+点集B会构造一个新的点集C

  • 比如一个三角形点集B加了一个点A，得到新的点集就相当于三角形B加了一个位移

  • 一个三角形点集B加了一条线点集A，得到新的点集相当于三角形B位移后相对于线进行了一个拖拽而形成了一个凸包

  

  • 一个三角形点集B加了一个三角形点集A，得到新的点集相当于三角形B位移后相对于三角形A进行了一个拖拽而形成了一个凸包

  

  • 点A减去三角形点集B，相当于A+（-B）

  • 如果两个三角形点集有交点的话，那么他们相减得到的凸包点集一定会过原点，反之亦然

  

• GJK Algorithm-Walkthrough

  • 将两个凸包求交问题转换为一个凸包是否过原点问题

  • 从A、B中选一个相反的方向，相减能得到凸包的一个顶点C

  • 从顶点连接原点，从这个方向再从AB找两个顶点，获得凸包上一个点D

  • 然后从CD垂直方向继续重复上面的方法，直到得到最后一个三角形CEF，若还没有找到原点，就说明不相交

• Separating Axis Theorem(SAT)-Convexity

  • 分离轴定律

  • 判断两个凸多面体是否相交，如果两个没有相交，一定可以找到一个轴，使得两个凸多面体的投影被轴分开

  

• 所有的边都要找一遍

• 在三维case下，不仅要每个面检测，还要检测每一条边

Collision Resolution

• 在一些碰撞检测后，如何将碰撞的物体分开，是需要解决的问题

• Applying Panalty Force：给物体添加力

• constraints：约束，当发生碰撞时，给小冲量，然后使用拉格朗日约束进行迭代，迭代冲量

Scene Query

Ray Cast

• Mutiple hits：一条射线出去，返回所有穿过的排序好的object

• Closest hit：最近的

• Any hit：返回所有穿过的不用排序的object

Sweep

• 一个体横扫过去

Overlap

• 给一个shape，问在世界中有没有物体跟这个形状发生了碰撞

Efficiency, Accuracy, and Determinism

Simulation Optimization

• island：将世界分成一个个的island
• sleep：如果一个地方的物体长时间不会动，那么在外力作用前会使其sleep

Continuous Collidion Detection(CCD)

• 连续碰撞检测

• 解决穿墙问题，物体速度太快，墙体太薄导致穿墙

  • 把墙做厚一点

  • CCD方法：做一个保守估计，即物体和环境碰撞的一个安全距离是多少，在安全距离外可以任意移动，在安全距离内就会把substep调密，做更精细的检测

Deterministic Simulation

• 确定性模拟

• 也就是说对物理的模拟，相同的操作结果相同（为了使得联网游戏中每个玩家看到的世界相同）

requirement

• 希望不同的终端，物理模拟的步长是一致的（如每秒是60帧）

• 确定性的模拟顺序

• 浮点数的稳定性