干货！深度解析游戏引擎开发中的算法

GAD2017-05-03

为什么在做游戏引擎开发中要有算法存在，那是为了让游戏角色能够有真实物理体验，游戏引擎需要有计算运动，碰撞，接触点等相关的方程，有一套基本算法帮助角色实现这种效果。例如，Runge-Kutta方法使用数值积分法计算运动方程。Gilbert-Johnson-Keerthi（GJK）算法使用Minkowski差来进行碰撞检测。 Sutherland-Hodgman算法通过剪切多边形来识别碰撞接触点。

数值积分方法

计算运动方程允许角色在空间中自由落体运动，就好像重力作用在这个角色上。运动方程使用的是牛顿第二定律：

和旋转力：

游戏引擎集成运动方程以获得角色的速度和位移。引擎用连续循环来进行这个操作，这个循环包括以下步骤：

1.识别作用于对象的所有力和力矩。

2.取所有力和力矩的矢量和。

3.求解线性和角加速度的运动方程。

4.在时间上对加速度进行积分以得到线性速度和角速度。

5.在时间上对速度进行积分以得到线性位移和角位移。

如果角色拥有重力和扭矩力，则游戏引擎连续循环将会产生物体下落和旋转的感觉。

问题是加速度和速度的积分。计算机只能通过使用数字积分技术来逼近积分的值。

游戏引擎开发中使用了三种数值积分方法。他们分别是：

1.Euler法

2.Verlet方法

3.Runge-Kutta方法

Euler方法计算在一个时间间隔中的速度，并预测在t +△下一速度。该方法实现起来很简单，但它是最不准确的。下图显示了这种方法的缺点。你可能觉得，使得Δt越无限的小，得到的解就越准确。但是，值得考虑的实际问题是你能有多少时间来进行每步积分。

在Runge-Kutta方法是一个数字集成技术，提供更好的近似运动方程。与欧拉方法（其计算一个间隔的一个斜率）不同，Runge-Kutta计算四个不同的斜率，并将这四个斜率用作加权平均值。

这些斜率通常被称为k1，k2，k3和k4，并且引擎需要在每个时间步长计算它们的值。

Runga-Kutta使用这些斜率作为加权平均值，从而更好地近似出物体的实际斜率和速度。然后使用该新斜率计算出对象的实际位置。

碰撞检测

检测冲突需要进行一定的权衡。因为简单的碰撞检测系统虽然快速但不精确的。而复杂的碰撞检测系统是精确的，但是在计算上各种代价也是昂贵的。

在碰撞检测期间，引擎用几何量来限制游戏角色。这被称为包围盒。最常见的是如下形式：

1. 球形包围盒（spheres）

2. 带方向的包围盒（orientedbounding box）

3. 沿坐标轴的包围盒（axis-alignedbounding boxes）

4. 凸包（Convex Hull）

碰撞检测系统通过检测边界值是否相交来工作。使用球形包围盒（spheres）

作为边界检测时候速度很快，但是会返回的许多错误检测状态。下图中两辆车实际并没有碰撞，但是检测系统会返回已经碰撞。

早在上世纪80年代，我能确信的说使用球形包围盒作为检测系统是可以接受的，但是现在，玩家可能会对许多错误检测感到不满意。

更精确的检测系统应该采用凸包作为边界检测。

使用Gilbert-Johnson-Keerthi（GJK）算法计算凸包（Convex Hull）的交点。令人惊讶的是，这种算法包含的数学思想非常的简单。算法通过计算它们的Minkowski差是否包含了原点来确定物体是否相交。下图显示了两个凸包（Convex Hull）相交（左）。由于Minkowski差（右）包括原点，算法检测为物体相交，碰撞检测返回真。

虽然GJK算法背后的数学思想是简单的，它是它非常计算代价却是昂贵的。

碰撞系统通过使用被称为宽阶段检测和窄阶段检测的这种两个阶段检测系统来避免每次碰撞检测都使用GJK算法来进行检测。

宽阶段检测系统使用球形包围盒（spheres）检测碰撞。这个阶段是快速的，并把检测到的所有可能的碰撞结果报告给窄阶段。窄阶段使用代价更昂贵和但是结果精确的GJK算法，这个阶段将再次测试并报告碰撞检测结果。

为了进一步减少GJK算法的调用，游戏引擎解析了游戏角色的空间状态，并创建称为一个树状结构的层次包围盒（BVH）。

BVH算法解析每个对象的位置，并将它们分配给二叉树中的特定节点。该算法递归地分析每个节点，直到每个节点包含最可能碰撞的两个角色。

碰撞响应

碰撞检测系统报告碰撞是否发生。不幸的是，它不报告Contact-Manifold（接触点）的碰撞。contact-manifold对于确定碰撞角色的碰撞响应是必要的。游戏引擎采用Sutherland-Hodgman算法来计算的两个碰撞人物接触点。该算法基于识别两个多边形，一个参考多边行，一个触发多边形，如下图。