物理系统的基础理论和算法

June 25, 2023About 18 min

物理系统的基础理论和算法

物理对象与形状 Physics Actors and shapes

游戏中常见的物理对象如下：

静态对象 Static Actor
- 不会移动的固定物体
动态对象 Dynamic Actor
- 符合动力学原理的游戏对象
- 会受到 forces 力/ torques 扭矩 / impulses 冲量的影响
检测器 Trigger — 游戏世界的触发器
- 和静态物体相似，不会移动
- 不会阻止其他物理移动
- 在actor进入离开时发送对应的消息
Kinematic Actor 运动学对象
- 忽略物理规则
- 由游戏逻辑直接控制（可能表现的反物理）

游戏世界常见的物理对象的形状如下：

每一种形状都有常用的实际游戏对象，比如Height Fields用来做地形等。

当我们利用这些对象去组成实际需要的物体对象时，有两个原则：

形状接近就好，不一定要完美
简单性。要尽量用简单的对象去拼接（比如尽量少用三角网格），且越少越好.

物理材质参数：

质量和密度 Mass and Density
质心（做载具时很重要）Center of Mass
摩擦和恢复（弹性） Friction & Restitution

Forces 力

一般我们把力分成两种：

Force 可以理解为直接的重力、拉力、摩擦力等

Impulse 冲量，比如说爆炸导致的冲击力等（虽然其实冲量就是力乘以时间（恒力条件下））

Movements 移动

牛顿第一定律无外力 —> 匀速直线运动

牛顿第二定律 F = ma （质量的本质是改变物体物理状态的倾向性）

当这个力是恒力时：

当这个力是变力时：

图中下方公式v(t’)的t是二次积分（位移和时间关系公式就是二次的）

游戏中运动模拟

具体以圆周运动为例，如果简单去模拟物体随时间变化，并不是很困难。
但实际游戏中时间不是连续的，而是由一帧帧实现的，所以通常需要解决的问题
是在已知当前物体位置和速度的前提下获取之后某时刻的物体位置和速度信息。

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

最简单的评估方法，假设在这个时间片里力是恒定的

每一时刻仍按照传统的牛顿力学方法去计算：

这种方法下，由于实际游戏中的时间片Δt不可能和现实中一样小，所以会导致能量不守恒（变多）----（如图中所示，实际位移是偏多的），误差越来越大，物体逐渐甩出去。

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

与显示近似，不过将力的值和速度的值以未来（终点）为参考，如下图：

其中未来的值是假设能够通过解析解强行算出来的。
和显示方法类似，该方法的问题是能量会衰减，但由于这个衰减相对较慢，所以用户可能会认为是摩擦力、空气阻力等其他力的影响导致，从而使得这个衰减在游戏实际中相对不明显。
从另一个角度来说，我们在游戏引擎中设计中认为衰减肯定是好过增多的，前者顶多最后停下来，但后者会不可控会爆炸。

优点:

无条件稳定

缺点：

求解花费大（计算未来值）
当非线性时难以实现
能量随着时间的推移而衰减

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

综合前两者的特点：

计算未来速度时用当前的力，计算未来位移时用未来的速度。
前提假设：力是不变的（很危险的假设，因为实际上力跟物体位置是相关的）。

优点：

条件性稳定
计算简单有效
随着时间的推移能够保存能量

缺点：

做一些sin/cos等运动时，积分出来的周期会比正确值长一点点，所以在相位上会有偏移差。

Info

总结

半隐式欧拉：简单，快，大部分情况稳定（刚体模拟首推）

刚体动力学 Rigid Body Dynamics

前面所说的所有内容都是把物体看作一个质点的前提，然而事实上真实世界中大部分物体是有形状的。

一般来说，我们在引入旋转时大都针对刚体（因为柔体太难了），因为刚体就是假设物体的所有粒子之间绑定相对不动。

所以我们在刚体动力学中常常会比普通的线性计算多一些概念，同一行概念有对应性：考虑旋转，角加速度，转动惯量，角动量，力矩。

在这里也只用考虑刚体的相关的知识，如果要对一个软体。比如橡皮糖进行模拟（不用铰链），所付出的代价非常高。

刚体旋转（使用四元数）

角速度（绕轴的转速）

角加速度

转动惯量（3*3的惯量）

角动量

角动量守恒

力矩：

样例：球杆从侧面击打一个球，这样的运动极其复杂

碰撞检测 Collision Detection

碰撞检测的两个阶段：

Broad Phase

一般常见的有两种方法：

BVH Tree – 更新成本低，适合动态场景。
Sort and Sweep – 先排序再逐个扫描，效率高，更符合大部分为静态物体小部分为动态物体的现实。更好。(但只试用于AA)

BVH

简单来说,BVH就是将BV用树的方式组织在一起,每个父节点是所有子节点BV的合并,并尽量保持每个节点的BV最小..

BVH可以非常方便地进行碰撞求交,射线求交.只需要从根节点开始逐渐向下遍历,就可以轻松得到结果.

BVH的一个很强大的优点是,构建完成后不仅可以用来做碰撞检测,同时可以用来做视锥裁剪,遮挡裁剪,光线追踪等操作.

一种以树状结构划分的空间结构

Sort and Sweep

https://www.toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects

一些流行的包围体类型是定向包围盒 (OBB)、2D 圆和 3D 球。让我们看一下最简单的边界体积之一：轴对齐边界框 (AABB)。
一个AABB在单个坐标轴上的投影，本质上就是一个区间[b,e]（即开始和结束）。
在我们的模拟中，我们会有很多刚体，因此会有很多 AABB，这意味着很多间隔。我们想找出哪些区间相交。

在排序和清除算法中，我们将所有b和e值插入到一个列表中，并按它们的标量值升序排序。
然后我们扫描或遍历列表。每当遇到b值时，其对应的区间存储在单独的活动区间列表中，每当遇到e值时，其对应的区间从活动区间列表中删除。（从前往后遍历列表,当遇到b点,就将该间隔添加到一个当前的激活间隔列表中,再次遇到这个间隔的e点,将这个间隔从激活间隔列表中移除.）
遇到 b点时,同时检查当前的激活间隔列表, b对应的间隔和当前的激活间隔列表中的所有间隔是存在重叠的.

在所有三个轴上都有重叠的AABB就是有重叠的AABB对.

实际的碰撞检测中,不需要每帧都对所有点都进行排序,只需要在初始化时进行排序,后续每帧更新时,大部分AABB的相对位置不会发生变化,只需将需要更新的AABB重新执行插入排序即可.
这样创建的时间复杂度是 O(NlogN),每帧更新的期望时间复杂度是O(N).

在三维的碰撞检测时,使用这种方法容易遇到在某个轴上聚集的问题(比如在地面上有很多物体,在Y轴上是聚集的),可能会使每帧的时间复杂度提升到O(N^2).这种情况下,可以考虑舍弃一个轴的检测.

Narrow Phase

当我们已经检测到碰撞物体的大致区域接下来需要对这个区域的物体开始求交，下面是运用距离场进行的（碰撞）接触检测。

下面会介绍三种检查方法:

Base shape intersection Test

比较简单，把所有物体看作球或胶囊状去判断相交即可。

闵可夫斯基方法

minkowski Sum（闵可夫斯基和）

点加面实际上是面加上了一个位移
面加上线实际上将原本面拉伸后再位移

面加上面实际上相当于绕面在空间中扫过的面积之和。

实际上，Minkowski 集合之和相当于顶点相加所形成的的顶点形成的凸包

闵可夫斯差

简单讲就是化A-B为A+(-B)。而-B是利用对原点的对称获得。
这样一来就获得了一个很重要的结论（方法）：如果两个凸包有重叠，则它们的闵可夫斯基差必定包含原点我们把闵可夫斯基差这些点形成的形状叫slmplex（单纯形）

Gilbert-Johnson-Keerthi 算法

由此问题转换为了如何判断两个凸包的闵可夫斯基差包含原点。使用的方法为GJK算法。可以参考：
https://zhuanlan.zhihu.com/p/511164248

在许多碰撞物理案例中，我们不仅要考虑对象在实际相交时发生碰撞，而且要考虑它们是否彼此非常接近，这需要我们知道它们之间的距离。
Gilbert-Johnson-Keerthi (GJK) 算法计算两个凸形之间的距离以及它们的最近点。这是一种优雅的算法，通过支持函数、闵可夫斯基和和单纯形来处理凸形的隐式表示，如下所述。

使用Gilbert-Johnson-Keerthi（GJK）算法计算凸包（Convex Hull）的交点。令人惊讶的是，这种算法包含的数学思想非常的简单。
算法通过计算它们的Minkowski差是否包含了原点来确定物体是否相交。

Info

两个核心思想

闵可夫斯差

把两个凸包求交的问题转换成一个多面体是否穿过圆心的问题

GJK算法

一个迭代思想，快速地沿着趋势最快地方向去逼近原点直到靠不动为止来解决多面体穿过圆心的问题(Yes or No)

分离轴定理 Separating Axis Theorem

分离轴定理(SAT) 指出两个凸形不相交当且仅当存在至少一个轴，其中形状在该轴上的正交投影不相交。

游戏物理引擎有许多不同类别的形状，例如圆形（3D 中的球体）、边（单线段）和凸多边形（3D 中的多面体）。
对于每一对形状类型，它们都有特定的碰撞检测算法。其中最简单的可能是 circle-circle 算法（上面有）：

尽管 SAT 适用于圆，但仅检查圆心之间的距离是否小于半径之和要简单得多。
出于这个原因，SAT 用于特定形状类对的碰撞检测算法，例如凸多边形对凸多边形（或 3D 中的多面体）。
对于任何一对形状，我们可以测试无数个轴的分离度。因此，确定首先测试哪个轴对于有效的 SAT 实施至关重要。
幸运的是，在测试一对凸多边形是否碰撞时，我们可以使用边缘法线作为潜在的分离轴。边的法向量n垂直于边向量，并指向多边形之外。
对于每个多边形的每条边，我们只需要找出其他多边形的所有顶点是否都在边的前面。

如果任何测试通过——也就是说，如果对于任何边，另一个多边形的所有顶点都在它前面——那么多边形不相交。
线性代数为这个测试提供了一个简单的公式：给定第一个形状上的一条边，顶点为 a和b，另一个形状上有一个顶点v，如果 ( v - a ) · n大于零，则顶点在前面的边缘。
（对于2D物体，其潜在的分离轴候选为物体每条边的法线，因此我们分别遍历两个物体的每条边，计算出其法线然后将两物体都投影到这条法线上，如果不存在相交则两物体不相交；否则继续遍历。当遍历结束后仍未找到一条分离轴，则两物体相交。）

对3D物体的处理如下图