GAMES104课程笔记10-Basics Concepts in Physics System

这个系列是GAMES104-现代游戏引擎：从入门到实践(GAMES 104: Modern Game Engine-Theory and Practice)的同步课程笔记。本课程会介绍现代游戏引擎所涉及的系统架构、技术点以及引擎系统相关的知识。本节课主要介绍游戏引擎中物理系统的基本概念。

Introduction

物理系统是游戏引擎的重要组成部分。在游戏中玩家和整个游戏世界的互动都是依赖于物理系统的实现，同时在现代游戏中大量的粒子效果也都是通过物理系统来进行驱动的。显然物理系统非常复杂，甚至于有很多公司专门去研究物理引擎的高效实现。而在本课程中我们同样把物理系统拆分成两节，这一节课主要介绍物理引擎的基本概念而在下一节课中则会更多地讨论游戏业界更前沿的物理仿真技术。

Physics Actors and Shapes

Actor

在物理引擎中根据对象自身的特点我们可以把它划分为静态对象、动态对象等。其中静态对象是指在仿真过程中不会发生改变的对象，比如说游戏中的地面、墙壁等等；与之对应的是动态对象，它们的运动状态会在游戏过程中动态地进行变化，而且它们的运动过程需要符合相应的动力学模型。

除此之外游戏角色和场景的互动还需要相应的trigger，它可以用来改变对象的各种状态。

最后一个常见的物理对象是kinematics，它是指不完全基于物理法则的物理对象，但往往与玩法高度相关。

不同类型的物理对象其特点可以总结如下：

Actor Shapes

物理对象最重要的属性是它的形状(shape)。比较规则和简单的形状可以通过解析的方法来进行描述：

在进行物理仿真时我们首先会把物理对象进行一定的包裹，使用相对简单的几何形状来近似复杂的模型。

Shape Properties

在形状的基础上我们还需要对一些物理量进行定义，包括对象的质量或密度、质心以及物理材质等。

Forces and Movements

Forces

力(force)是改变物体运动状态的原因。在物理引擎中我们同样需要力来驱动整个游戏世界的仿真过程，其中常见的类型包括重力、摩擦力等。

另一种常用的仿真方式是使用冲量(impulse)，它比较适合用来模拟物体运动状态发生剧烈变化的情况。

Movements

有了力或者冲量后就可以利用牛顿运动定律来驱动物体的运动了。

在物理引擎中一般无法使用解析的方式来计算物体的运动，因此我们需要一些数值计算方法来进行求解。

在进行数值积分时，我们可以把时间间隔设置成一个比较小的值然后对被积函数进行累加来近似实际的积分。具体来说，在计算物体的运动轨迹时我们首先计算物体在当前位置上受到的力并且积分得到加速度，然后再利用加速度来更新速度以及物体的位置。这种计算物体运动轨迹的方法称为Euler方法(Euler’s method)，也称为显式积分(explicit integration)。Euler方法实现起来非常简单，但需要注意的是它的本质是使用物体的当前状态来估计下一时刻的运动状态，此时系统的能量是不守恒的。

为了提高数值积分的稳定性，人们还开发出了隐式积分(implicit integration)的技术。隐式积分的实现也很简单，只需要在求解加速度和速度时使用下一时刻而不是当前时刻的值即可，同时可以证明此时系统的能量会不断衰减。当然这又引入了另一个问题，即如何计算系统在下一时刻的物理量，这在很多情况下是比较困难的。

在游戏引擎中更常用的积分方法是半隐式Euler方法(semi-implicit Euler’s method)，即在计算加速度时使用当前时刻的力推导下一时刻的速度，而在计算位置时使用刚才计算出的速度再更新位置。半隐式方法有非常高的数值稳定性，广泛应用于各种类型的物理仿真中。

Rigid Body Dynamics

有了牛顿定律和数值积分算法就可以开始进行物理仿真了，其中最简单的情况是质点动力学(particle dynamics)。在质点动力学中所有的物体都被抽象为没有具体形状的质点，此时我们只需要按照牛顿定律更新质点的运动状态即可。

在游戏引擎中更为常见的仿真场景是刚体动力学(rigid body dynamics)。和质点动力学不同，刚体动力学仿真需要考虑物体自身的形状，也因此需要在质点运动的基础上引入刚体旋转的相关概念。

Orientation

刚体的朝向(orientation)可以使用一个旋转矩阵或者四元数来表示，它表示刚体当前姿态相对于初始姿态的旋转。

Angular Velocity

角速度(angular velocity)表示刚体绕某个旋转轴旋转的速度，需要注意的是在描述角速度时必须要指明旋转轴。

Angular Acceleration

角加速度(angular acceleration)类似于加速度，不过它描述的是角速度的变化。这里需要说明的是角速度的变化不仅包括绕当前轴转速的变化，它还包括旋转轴发生变化的情况。

Rotational Inertia

转动惯量(rotational inertia)类似于质量，它描述了刚体抵抗旋转的能力。转动惯量与质量的一大区别在于转动惯量不是一个常数而是一个张量(矩阵)，当刚体的朝向发生改变时需要利用旋转矩阵来计算当前姿态下的转动惯量；同时转动惯量也与刚体上的质量分布密切相关。

Angular Momentum

角动量(angular momentum)则描述了刚体旋转的状态，它是转动惯量与角速度的乘积。

Torque

当外力不通过刚体的质心时会产生力矩(torque)，从而导致刚体发生旋转。

在质点动力学的基础上把旋转部分也考虑进来对物体的运动状态进行更新就得到了刚体动力学的仿真方法。

Application：Billiard Dynamics

以台球游戏模拟为例，我们假设台球自身与桌面没有摩擦，这样台球的运动可以简化为二维平面运动。在进行仿真时需要把球杆给予台球的力(冲量)移动到球心来计算台球沿球杆方向的速度；同时这种移动还会对台球施加一个力矩使台球产生旋转，因此也需要更新台球的角速度。

Collision Detection

在进行刚体仿真时我们需要考虑不同刚体之间的相互作用，也即所谓的碰撞问题。要求解碰撞问题的第一步是对刚体碰撞进行检测，目前在物理引擎中注意是使用两阶段的检测方法。

Broad Phase

显然场景中大部分的物体是不会同时发生接触的，因此所谓的broad phase就是只利用物体的bounding box来快速筛选出可能发生碰撞的物体。目前物理引擎中常用的碰撞检测包括空间划分(space partitioning)以及sort and sweep两类方法。

BVH Tree

我们在介绍渲染技术时就介绍过空间划分的相关概念，它的思想是把场景中的物体使用一个树状的数据结构进行管理从而加速判断物体是否相交的过程。BVH是空间划分的经典算法，它使用一棵二叉树来管理场景中所有物体的bounding box。BVH的特点是它可以通过动态更新节点来描述场景中物体的变化，因此可以快速地检测场景中的bounding box可能存在的碰撞。

Sort and Sweep

sort and sweep是使用排序来检测碰撞的算法。它的思想非常直观：对于使用AABB进行表示的bounding box，两个bounding box出现碰撞时必然会导致它们的边界产生了重叠，而判断是否出现重叠则可以通过对bounding box的边界进行排序来进行计算。

Narrow Phase

筛选出可能发生碰撞的物体后就需要对它们进行实际的碰撞检测，这个阶段称为narrow phase。除了进一步判断刚体是否相交外，在narrow phase中一般还需要去计算交点、相交深度以及方向等信息。

目前在narrow phase中一般会使用相交测试、Minkowski距离以及分离轴等方法。

Basic Shape Intersection Test

对于一些简单的几何形状可以使用解析的方法来判断它们是否相交并且计算交点的信息。

Minkowski Difference-based Methods

对于凸多边形的情况则可以使用Minkowski差异(Minkowski distance)来判断它们是否相交。在介绍Minkowski距离之前首先要引入Minkowski和(Minkowski sum)的概念：对于两个点集\(A\)和\(B\)，它们的Minkowski和定义为两个集合中任意一对矢量相加后得到的新的点集。

对于凸多边形，它们的Minkowski和也必为一个凸多边形，而且这个新多边形的顶点也是原始多边形顶点的和。

在此基础上我们定义点集\(A\)和\(B\)的Minkowski差异为\(A\)和\(-B\)的Minkowski和，即\(A \ominus B = A \oplus (-B)\)。

可以证明当\(A\)和\(B\)相交时，原点必位于\(A \ominus B\)中。这样判断两个凸多边形是否相交的问题就转化为判断原点是否位于凸多边形\(A \ominus B\)中的问题，这种问题一般可以使用GJK算法来求解。

GJK算法的主要流程如下：

当GJK算法判断出两个凸多边形相交后还可以进一步计算交点以及深度等信息。

Separating Axis Theorem

分离轴定理(separating axis theorem, SAT)同样是一种计算凸多边形相交的算法，它的思想是平面上任意两个互不相交的图形我们必然可以找到一条直线将它们分隔在两端。对于凸多边形还可以进一步证明必然存在以多边形顶点定义的直线来实现这样的分隔，因此判断凸多边形相交就等价于寻找这样的分隔直线。