物理引擎

小型游戏项目最常使用的物理引擎, 是很多游戏引擎的内置物理引擎.
Box2D库的单位是"米".

  • https://github.com/shakiba/planck.js (推荐)
  • https://github.com/kripken/box2d.js/
  • 受约束的刚体模拟
  • 重力
  • 摩擦力
  • 恢复力
  • 连续碰撞检测

v = g * t

g: 重力加速度
t: 时间
v: 垂直方向的速度

angle = angle0 * cos(sqrt(g/l) * t)

angle: 钟摆当前的角度
angle0: 钟摆的初始角度
g: 重力加速度
l: 钟摆摆杠长度

f(x) = x

x: 整个运动完成的百分比进度, [0,1].
f(x): 扭曲后的百分比进度, [0,1].

function linear() {
return function (percentComplete: number) {
return percentComplete
}
}

f(x) = x ^ 2

strength: 缓入的强度
x: 整个运动完成的百分比进度, [0,1].
f(x): 扭曲后的百分比进度.

function easeIn(strength: number) {
return function (percentComplete: number) {
return Math.pow(percentComplete, strength * 2)
}
}

f(x) = 1 - ((1 - x) ^ 2)

strength: 缓出的强度
x: 整个运动完成的百分比进度.
f(x): 扭曲后的百分比进度.

function easeOut(strength: number) {
return function (percentComplete: number) {
return 1 - Math.pow(1 - percentComplete, strength * 2)
}
}

f(x) = x - sin(x * 2 * pi) / (2 * pi)

x: 整个运动完成的百分比进度.
f(x): 扭曲后的百分比进度.

function easeInOut() {
return function (percentComplete: number) {
return percentComplete - Math.sin(percentComplete * 2 * Math.PI) / (2 * Math.PI)
}
}

f(x) = (1 - cos(x * Npasses * pi) * (1 - x)) + x

x: 整个运动完成的百分比进度.
Npasses: 运动物体穿过中轴的次数.
f(x): 扭曲后的百分比进度(注意, 弹簧运动过程的起点是0, 终点在1, 但 最大值可以到2, 即"穿过中轴").

function elastic(passes: number) {
return function (percentComplete: number) {
return ((1 - Math.cos(percentComplete * Math.PI * passes)) * (1 - percentComplete)) + percentComplete)
}
}

由弹簧运动衍生而来, 在"穿过中轴"时取 2 - f(x), 从而避免了运动过程中最大值到2的问题.

bounces: 弹跳次数, 即弹簧运动的Npasses.
x: 整个运动完成的百分比进度.
f(x): 扭曲后的百分比进度, 起点是0, 终点是1, 最大值是1.

function bounce(bounces: number) {
const fn = elastic(bounces)
return function (percentComplete: number) {
const result = fn(percentComplete)
return result <= 1
? result
: 2 - result
}
}

描述物体与物体之间的连接性.

基于点的相连, 物体之间只需要保持这个点相连, 因此可以绕着这个点任意旋转.

例子:

  • 球形关节

有一定距离的点对点约束, 就好像中间有一根隐形的杆将两个物体连接起来.

旋转角度有限的铰链.

例子:

  • 门的合页

旋转角度无限制的铰链.

物体只能朝一个方向平移.

例子:

  • 活塞

事前碰撞检测法是通过估算物体未来的位置来提前判断是否会发生碰撞,
在判断会发生碰撞的情况下将其设置为刚好不发生碰撞的状态.

事后碰撞检测法是根据物体当前的位置来判断是否发生了碰撞.
这种方法需要在碰撞发生以后, 在渲染发生以前"修复"碰撞物体的位置, 使其处于刚好不发生碰撞的状态.

事后碰撞检测法可能出现隧穿.
在涉及的物理量很多时, 事后碰撞检测法被认为比事前碰撞检测法容易.

可以移动的物体, 具有刚性, 不会变形, 会与其他物体发生碰撞.

Havok使用的术语, 描述一个参与碰撞检测的单独刚体物体.

凸性是一个形状的性质, 在碰撞检测中很重要,
具有凸性的形状更容易处理, 运算量更少.

形状内发射的光线不会穿越形状表面两次或以上.

例子:

  • 圆形
  • 矩形
  • 三角形

例子:

  • 吃豆人

用来管理所有可碰撞体的容器, 它的命名是将游戏世界分类后的结果:

  • 游戏性世界: 与游戏规则相关的部分
  • 视觉世界: 用户可以看到的程序的视觉部分
  • 物理世界: 游戏的动力学系统, 有时候它和碰撞世界是一体的
  • 碰撞世界: 所有可碰撞体发生碰撞的不可见部分, 有时候它和物理世界是一体的

碰撞表达形式是一个对象与碰撞相关的属性, 用来描述它在碰撞世界的位置和定向.

单独分出碰撞表达形式符合游戏开发中使用的组件模式, 也便于进一步实现ECS.

包围盒是一个表示碰撞模型的矩形/立方体.

只需要判断矩形的四个边是否与其他物体相交.

AABB是与坐标轴保持平行的矩形.
如果物体旋转, 碰撞模型可能改变大小, 但边的角度不会发生改变,
于是它的包围盒相当于对被旋转的物体重新描了个框, 有时这会产生与视觉世界相差甚远的结果.
因此AABB只适用于逼近长方形的物体(最好不会旋转).

AABB表示起来很容易, 只需要两个坐标: 矩形左上角的坐标, 矩形右下角的坐标.

运用分离轴定理, 判断AABB与AABB相交非常简单, 只需要检查x轴和y轴上的投影就行了.

function collided(a, b)
return a.x < b.x + b.width
and a.x + a.width > b.x
and a.y < b.y + b.height
and a.y + a.height > b.y
end

如果物体旋转, 碰撞模型也跟着旋转.

相比AABB要复杂, 表示起来也需要更多信息.

一种用于逼近物体形状的凸胞形.

多边形汤用来表示任意形状.

这是最费时的碰撞检测目标, 通常只用于不参与动力学的物体, 比如地形, 建筑.

包围球是一个表示碰撞模型的圆形/球体.

圆形和球体的碰撞检测较为简单.

只需要判断点是否在 圆心与点的距离 是否小于 圆的半径.

点与点的距离通过勾股定理就可以计算.

只需要 圆心与圆心的距离 是否小于 两个圆形的半径之和.

只在3D碰撞检测时存在.

一个长得像胶囊的碰撞模型, 2D时是两个半圆形和一个矩形组合而成, 3D时是两个半球与一个立方体组合而成.

一种非常高效的任意凸多胞形碰撞检测算法, 基于minkowski difference运算, 该运算理解起来很简单, 但证明很困难.

该定理指出, 如果能找到一个轴, 两个凸形状于该轴的投影不重叠, 就能确定两个形状不相交.

对于二维空间来说, 该定理很容易理解:
在笛卡尔座标系上放两个凸形状, 然后将它们投影向x轴, 会产生两个投影.
两个投影(线段)的长度即是形状面向此坐标轴的最左端和最右端的坐标.
现在把x轴取消掉, 换成任意的轴, 如果能找到这样一个轴(称作"分离轴"), 让投影不重叠, 则说明两个形状没有相交.

实际使用SAT时, 会通过延长多边形的一条边(称作"边向量"), 然后将与其垂直的线作为投影轴(称作"边的法向量").
需要检查的轴的数量等于两个多边形的边数之和.

当其中一个形状是圆形时, 取"圆心到多边形最近的顶点"的线段作为投影轴.

大多数碰撞检测系统都会大量使用分离轴定理.

最小平移向量是SAT的副产物, 指的是恰好将两个碰撞物体分离至不碰撞状态所需移动的最小距离.

一种实施方法是在寻找分离轴的过程中, 记录下投影重叠长度最小的轴, 该轴的投影重叠长度就是MTV.

向量 (x, y) 的法向量为 (-y, x)(y, -x).

根据平行四边形法则, 向量线段a和b相加, 会得到两条向量夹角构成的平行四边形的中线.

向量a减去向量b, 得到向量b的终点至向量a的终点的一条向量线段.

向量a在向量b上的标量投影 = 向量a的长度 * cos(两个向量的夹角)

两个向量相乘会得到点积(dot product, 也称数量积), 其结果是一个标量.

向量a * 向量b = 向量a的长度 * 向量b的长度 * cos(两个向量的夹角)

即"向量b在向量a方向上的投影长度"与"向量a长度"的乘积.

碰撞查询的目的是得出假想的碰撞问题的答案, 比如子弹射出后的路径上会不会碰到障碍物.

选择一个点, 向外射出一条线, 计算射线路径与物体的交点坐标.

常见用途:

  • 实现动态的视野范围.
  • 鼠标对3D场景中的物件的拾取(mouse picking).

形状投射和光线投射类似, 但起点是一个凸形状而不是一个点.

碰撞检测的性能消耗会随着空间内需要检测的物体数量而发生 O(n^2) 的增长.

物理引擎会将检测分为多个阶段, 先从计算量小的算法(AABB)开始排除不可能发生碰撞的物体, 从而减少计算量.

通过将先前多帧的结果缓存, 来避免在每一帧间进行重新计算.

一种将空间里需要被检测的物体数量减少以降低计算压力的做法.

需要用到划分空间的算法或数据结构, 有很多种方案.

数学碰撞检测不考虑物体的物理因素, 只判断物体是否相交.

因为考虑的因素更少, 数学碰撞检测的性能比物理好得多.

物理碰撞检测是考虑物体因素(基于动力学的, 例如速度, 加速度)的碰撞检测.

离散碰撞检测的动作是离散的, 这意味着一个速度很快的物体可以穿过比较薄的物体,
因为在两个连续的帧之间物体根本没有可以发生"碰撞"的时间点,
这被称为隧穿(tunneling)效应/子弹穿纸(bullet through paper)问题.

检测到碰撞时两个物体已经相交(interpenetrate)了, 因此在检测到碰撞之后还要编写将两个已碰撞的物体分开的代码.

由于性能影响小, 这是最常见的碰撞检测方式.

一种避免隧穿的方法, 它会创建一个形状, 该形状是被检测的形状的各个顶点在时间变化前后的坐标相连形成的.
例如一个直线运动的圆形的扫掠形状会是一个胶囊的形状.

创建扫掠形状后, 用该扫掠形状替代原有形状进行碰撞检测.

这种方法并不完美, 因为生成凹形状会增加碰撞测试的复杂度:

  • 曲线运动的物体很可能会形成凹扫掠形状.
  • 正在旋转的直线运动物体也可能形成凹扫掠形状.

连续碰撞检测考虑到了物体之间的运动状态.

实现非常复杂, 性能影响较大, 引擎通常只会对少部分物体使用CDC.