译者：刘虹(lewis2012)
审稿人：王悦婷（Yueting）
游戏引擎开发中为什么存在算法？ 就是让游戏角色有真实的化学体验。 游戏引擎需要有多项式来估计运动、碰撞、接触点等，并且有一组基本算法来帮助角色实现这些效果。 例如，龙格-库塔方法使用数值积分来估计运动方程。 Gilbert-Johnson-Keerthi (GJK) 算法使用 Minkowski 差分进行碰撞检测。 Sutherland-Hodgman 算法通过剪切六边形来识别碰撞接触点。
数值积分法
计算运动方程允许角色在空间中自由下落，就好像重力作用在角色上一样。 运动方程使用牛顿第二定律：
和旋转力：
游戏引擎集成运动多项式来获得角色的速度和位移。 引擎使用连续循环来执行此操作，其中包含以下步骤：
1. 识别作用在物体上的所有力和扭矩。
2. 求所有力和扭矩的矢量和。
3. 求解线性加速度和角加速度的运动方程。
4. 对加速度随时间的变化进行积分以获得线速率和角速率。
5. 对随时间变化的速率进行积分以获得线性和角位移。
如果角色有重力和扭力，游戏引擎的连续循环就会产生物体下落和旋转的感觉。
问题是加速度和速度的整合。 计算机只能使用数值积分技术来近似积分值。
游戏引擎开发中使用了三种数值积分方法。 他们是：
1.欧拉法
2.Verlet法
3.龙格-库塔法
欧拉方法估计一个时间间隔内的速率并预测 t + Δ 处的下一个速率。 这种方法实现起来比较简单，但是准确度最差。 下图显示了这些技术的缺点。 您可能会认为 Δt 越小，解就越准确。 然而，一个值得考虑的实际问题是您需要多少时间来执行每个集成步骤。
龙格-库塔方法是一种数字积分技术，可以更好地逼近运动多项式。 与估计一个区间的一个斜率的欧拉方法不同，龙格-库塔方法估计四个不同的斜率，并将这四个斜率用作加权平均值。
这些斜率一般称为k1、k2、k3和k4，引擎需要在每个时间步估计它们的值。
Runga-Kutta 使用该斜率作为加权平均值游戏引擎源码解析，以更好地近似对象的实际斜率和速度。 然后使用这个新的斜率来估计物体的实际位置。
影响检查
检测冲突需要进行某些权衡。 因为简单的碰撞检查系统速度快但不精确。 虽然复杂的碰撞测量系统是准确的，但它们的估计成本也很高。
在碰撞检查期间，引擎使用几何量来约束游戏角色。 这称为边界框。 最常见的如下：
1. 球形边界框（球体）
2. 定向边界框
3.沿坐标轴的边界框（axis-alignedbounding box）
4.凸包（Convex Hull）
碰撞检查系统通过测量边界值是否相交来工作。 使用球体
它的速度与边界检查一样快，但会返回很多错误检查状态。 下图中，两辆车实际上并没有发生碰撞，但检测系统会返回它们已经发生碰撞。
早在 20 世纪 80 年代，我可以有把握地说，使用球形边界框作为检测系统是可以接受的，但今天，玩家可能会对许多错误检查感到不满意。
更精确的测量系统应该采用凸包作为边界检查。
使用 Gilbert-Johnson-Keerthi (GJK) 算法来估计凸包 (Convex Hull) 的交点。 令人惊讶的是，这个算法所包含的物理思想特别简单。 该算法通过估计对象的 Minkowski 差异是否包含原点来确定对象是否相交。 下图显示了两个凸包的交集（左）。 由于 Minkowski 差值（右）包括原点，因此算法会检查对象的交集，并且碰撞检查会返回 true。
尽管 GJK 算法背后的物理思想很简单，但计算量却非常大。
碰撞系统通过使用称为宽阶段测量和窄阶段测量的两阶段检测系统来防止使用 GJK 算法来测量每次碰撞检查。
宽平台测量系统使用球体来检测碰撞。 该阶段速度很快，并报告窄阶段测量到的所有可能的碰撞结果。 窄阶段使用更昂贵且不太准确的 GJK 算法。 此阶段将重新测试并报告碰撞检查结果。
为了进一步减少 GJK 算法的调用次数，游戏引擎解析游戏角色的空间状态并创建称为边界框层次结构 (BVH) 的树结构。
BVH算法解析每个对象的位置并将它们分配给二叉树中的特定节点。 该算法递归地解析每个节点，直到每个节点包含最有可能发生冲突的两个字符。
崩溃响应
碰撞测量系统报告是否发生了碰撞。 不幸的是游戏引擎源码解析，它不报告接触歧管碰撞。 接触流形对于确定碰撞主体的碰撞响应是必要的。 游戏引擎使用 Sutherland-Hodgman 算法来估计两个碰撞角色的接触点。 该算法基于识别两个六边形、一个参考多边形行和一个触发六边形，如下所示。
算法中涉及六边形的部分用作参考平面。
一旦确定了参考六边形，算法就会使用裁剪规则来测试每个参考平面上触发六边形的每个顶点。
当算法终止时，会生成一个新的六边形，其顶点是两个碰撞六边形的接触点。
视觉游戏引擎算法
现在您已经了解了这个游戏引擎算法，您可能想知道如何实现它们。 通常，书籍会直接跳到此类算法的实现，而不提供算法如何工作的直观描述。 我觉得如果你能看到算法的可视化表示，你就可以更容易、更快地实现它们。 因此，我写了几篇文章，为每个算法提供了直观的解释。 希望能够对大家有所帮助（点击阅读原文查看地址如下）：
