物理引擎

取决于是否单独为斜坡计算速度, 斜坡(假设为45度)的运动速度可以是非斜向运动的1.4倍或非斜向运动的1倍速度, 即正确速度.

需要注意的是, 斜向运动速度较快的物理表现在大部分游戏里是可以接受的, 因此确保斜向速度正确并非必须.

如果要让斜向移动速度正确, 则需要用到勾股定理, 计算出对应的x轴和y轴移动距离.

水平运动很简单, 只要在每物理帧进行基于速度的位移即可.

但是, 如果运动本身不是匀速的, 比如使用了加速度, 则每物理帧移动后再加速的做法会存在计算误差.
因为真实的加速度需要用积分才能计算.
较小的物理帧步长可以在相当程度上掩盖相关误差.

2D游戏项目最常使用的物理引擎, 是很多2D游戏引擎的内置物理引擎.
Box2D库使用MKS单位: 米, 千克, 秒, 角度为弧度.

  • https://2dengine.com/?p=box2d

用Rust编写的2D/3D物理引擎, 提供WebAssembly封装和Bevy引擎的官方插件.

在官方的基准测试中, 它的速度与CPU版本的PhysX一样快, 比Box2D略快.

Rapier支持连续碰撞检测, 具有跨平台的确定性.

Rapier使用国际单位系统(MKS): 米, 千克, 秒.
原点在物体的中心, 并且不能改变.

大部分(非科学计算目的的)物理引擎受制于浮点数的误差和运行速度的现实需求, 都不能完美模拟物理表现.
举例来说, 大部分用于游戏的物理引擎在所有碰撞体的恢复系数都为零的情况下, 仍然会出现弹跳, 这就是因为采用了能够快速得出近似解的算法.
在这种情况下, 引擎依赖开发者通过添加钩子来手动实现"假"的物理行为以满足需要, 但这经常也被视作是在错误的方向上努力(实现假物理引擎比改造引擎容易).

比如, 相当多的物理引擎将矩形的坐标原点设置为矩形的中心, 而不是矩形的左上角.
尽管矩形的坐标原点在中心对于旋转矩形是有帮助的, 但有相当多游戏类型根本不需要会旋转的矩形:
如果坐标在矩形左上角, 将减少很多无谓的换算, 并且更容易让物理世界与渲染世界同步.

通用物理引擎的性能总是低于专用物理引擎, 这是毋庸置疑的, 因为需要考虑的计算量和计算步骤都不同.
大部分游戏物理引擎都是通用物理引擎, 这使得它们的定位变得尴尬.

如果存在重力, 则在碰撞检测时会发现物体与下方物体相交, 就意味着物体在地面上.

检测物体下方一个单位是否存在其他物体, 如果存在, 就意味着物体在地面上.

如果检测的方式类似于一条射线, 则可能存在问题, 因为地面可能有空隙导致射线直接穿过, 导致判断失误.

决定的物体的弹性:

  • 0表示不恢复, 没有弹性, 物体应该与它接触的物体"黏"在一起.
  • 1表示完全弹性碰撞, 具有最大的弹性, 物体会弹回至原本的位置.

v = g * t

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

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

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

https://easings.net/

f(x) = x

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

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

f(x) = x ^ 2

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

function easeIn(progressPercent: number, strength: number): number {
return progressPercent ** (strength * 2)
}

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

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

function easeOut(progressPercent: number, strength: number): number {
return 1 - (1 - progressPercent) ** (strength * 2)
}

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

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

function easeInOut(progressPercent: number): number {
return progressPercent - Math.sin(progressPercent * 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, progressPercent: number): number {
return ((1 - Math.cos(progressPercent * Math.PI * passes)) * (1 - progressPercent)) + progressPercent)
}

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

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

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

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

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

例子:

  • 球形关节

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

旋转角度有限的铰链.

例子:

  • 门的合页

旋转角度无限制的铰链.

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

例子:

  • 活塞
  • 书籍《实时碰撞检测算法技术》
  • https://2dengine.com/?p=intersections
  • http://noonat.github.io/intersect/
  • https://digitalrune.github.io/DigitalRune-Documentation/html/138fc8fe-c536-40e0-af6b-0fb7e8eb9623.htm

大部分物理引擎都内置碰撞检测, 但物理引擎引入的完整物理世界在一些情况下(比如游戏开发)会成为问题.
因为这个原因, 也存在一些独立的碰撞检测库.

  • https://github.com/Prozi/detect-collisions JavaScript, 底层基于npm的rbush和sat库.
  • https://github.com/dimforge/parry Rust

特别实现:

  • https://github.com/mikolalysenko/box-intersect JavaScript, narrow phase, 虽然不再维护, 但其使用的算法性能非常突出.
  • https://github.com/mourner/rbush JavaScript, narrow phase, 性能较高, 适用于动态物体.
  • https://github.com/mourner/kdbush JavaScript, narrow phase, 性能较高, 对静态物体优化, 用于静态物体时比rbush快得多.

事前碰撞检测法是通过估算物体未来的位置来提前判断是否会发生碰撞, 然后再执行位移.

实现非常复杂, 计算量较大, 物理引擎通常只会对少部分物体执行CCD.

CCD通常用于运动速度极快的物体上, 这些物体因为速度太快以至于离散碰撞检测不可用:
在大部分情况下都会发生隧穿以至于检测不到碰撞.

事后碰撞检测法是根据物体当前的位置来判断是否发生了碰撞.

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

在涉及的物理量很多时, 事后碰撞检测法被认为比事前碰撞检测法容易.
由于计算量较小, 离散碰撞检测是最常见的碰撞检测方式.

发生碰撞的时间.

顾名思义, 两个物体相交的深度.

计算MTV的长度可以得到此深度.

碰撞面的表面法线(surface normal), 它是一条垂直于碰撞面的射线.

碰撞处理是物理引擎里最复杂的阶段.

通过碰撞的两个物体的速度和位置, 可以通过将物体的时间倒流来修复物体的位置至首次碰撞点, 即可将碰撞情况解决.
根据物体和碰撞物体的性质, 在解决碰撞后可能还需要对物体进行位移以补充上碰撞之后发生的运动.

尽管通过将物体的位置减去基于 最小碰撞轴 得出的分离向量可以解决碰撞,
但这 在大部分情况下不是解决动态物体碰撞的正确方法:
通过最小碰撞轴得出的分离向量并不反映物体的速度方向, 单纯依赖分离向量解决碰撞, 会在一些碰撞案例上出现异常结果.
举例来说, 一个物体从空中垂直落下, 与右侧的悬崖发生碰撞,
正确的解决方法是向上推物体从而解决碰撞, 让物体立在悬崖上面,
但分离向量可能认应该向左侧移动物体(使其坠落悬崖),
因为这样解决起来距离"最短"(在这种情况下, 由于下落速度受加速度影响, 碰撞时的垂直相交长度大于水平相交长度).
除了错误的解决碰撞外, 基于最小碰撞轴的解决方案也无法为物体补上碰撞后的运动, 因为它在处理碰撞时不知道物体的移动速度.

基于速度的方案通过让物体的运动倒退来找到碰撞点, 通过找到的碰撞点来修复物体位置.

基于速度的方案需要获得撞击时间, 使物体在这个时间可以恰好发生碰撞而不相交.

撞击时间的得出需要依赖反向的CCD方案, 对于不能直接解析出撞击时间的情况, 需要较多的计算量,
但在离散碰撞检测里用CCD寻找撞击时间的计算量仍然要比纯CCD少很多.

解析解只适用于不旋转的简单形状, 例如AABB, 球体等.

对于这些形状, 单纯通过计算就可以得出撞击时间, 从而只用很少的计算量解决问题.

向前倒退固定时间, 每倒退一次检查一次是否发生碰撞, 直到不发生碰撞.

视步进的长短和物体的速度, 得出的撞击时间近似解与真正的撞击时间可能有一些误差.

使用二分法寻找物体的撞击时间.
二分法将不断逼近真正的撞击时间, 最终找到真正的撞击时间或非常接近的近似解.

解决碰撞后, 视情况可能需要修改碰撞之后的物体速度方向, 甚至模拟物体的运动, 例如将撞墙的物体反弹出去等.

如果不补上碰撞后的运动, 则会表现为物体碰撞后的运动被吞掉, 这与碰撞物体具有无限的摩擦力时的表现一致.

出自Ian Millington的《游戏物理引擎开发》, 该书主要采用了这种方案.

当解决物体A与B的碰撞时, 物体A与C碰撞.
当解决物体A与C的碰撞时, 物体A与B碰撞.
这就是典型的多物体碰撞问题, 涉及碰撞的物体超过2个.

这种方案认为不需要真正解决碰撞, 因为碰撞物体之间的碰撞可能是无法解决的.
因此, 只需要在每次碰撞解决完毕后再次检测碰撞情况,
就这样循环直到碰撞解决或达到设定好的最大循环次数, 将最后一次处理结果视作此帧的结果.

缺点:

  • 由于期间需要多次检测和解决碰撞, 这种方案是耗费CPU时间的.
    尤其是在无法解决的碰撞中, 它总是会到达最大碰撞解决次数.
    在物理系统的时间步长较小的情况下, 计算量会很大.
  • 与解决碰撞的顺序有关, 因此可能会需要排序.

同步碰撞处理同时处理一组碰撞而不是一个碰撞.

从而在效率上高于对每一种组合执行碰撞检测.

然后再进行精确碰撞检测.
broad phase会通过算法对空间内的物体数量进行修剪或划分来实现粗略碰撞检测, 从而将需要进行碰撞检测的数量减少.
由于AABB比较起来较为简单, 大部分的游戏broad phase检测会将物体视作AABB来处理.

粗略比较多个对象的碰撞情况, 找到所有潜在的碰撞对.

精确比较两个对象的碰撞情况.

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

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

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

将被检测的物体数量减少以降低计算压力的优化方式.

建立一条垂直于某个轴的线, 从轴的起点开始向终点遍历扫描, 只检测位于这条轴上的物体之间的碰撞.

这种方法在大部分对象分离在轴的不同位置的情况下效果很好, 反之效果不佳.

将物体放在一个名为包围体层次结构的二叉树里, 树中的父节点是大包围体, 子节点是父节点大包围体内的小包围体.

进行碰撞检测时, 从根节点开始递归, 判断节点是否与某个祖先节点相交, 如果是, 则继续向下寻找相交的节点.

https://en.wikipedia.org/wiki/Bin_(computational_geometry)

将空间划分为边长均匀的单元格组成的网格, 然后获得每个物体覆盖的单元格.

在进行碰撞检测时, 只检测那些单元格存在交集的物体.

这种方法非常适合物体到处分布的情况, 是最流行的方法.

创建一个二叉空间划分树, 将父节点的空间一分为二为子节点.

用于二维环境的空间划分树.

用于三维环境的空间划分树.

游戏开发中, 角色与斜坡具有与AABB不同的碰撞方式.

角色与斜坡碰撞时, 不使用矩形碰撞盒, 而是使用角色脚下的一个点.
当点与斜坡接触时, 点就依附在斜坡的斜线轨道上, 直到离开斜坡.

在大部分需求里, 斜坡碰撞都需要单独处理水平和垂直方向的碰撞效果.

可以移动的物体, 具有刚性, 不会变形.

引擎中的刚体往往只是一个具有特定属性的点, 因此它不一定表示该物体会参与碰撞.

rigid body经常与body互换使用.

描述一个参与碰撞检测的刚体.

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

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

例子:

  • 圆形
  • 矩形
  • 三角形

例子:

  • 吃豆人

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

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

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

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

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

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

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

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

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

function isColliding(a: AABB, b: AABB): boolean {
return a.x < (b.x + b.width)
&& (a.x + a.width) > b.x
&& a.y < (b.y + b.height)
&& (a.y + a.height) > b.y
}
// or
function isColliding(a: AABB, b: AABB): boolean {
if (a.min.x > b.max.x) return false
if (a.max.x < b.min.x) return false
if (a.min.y > b.max.y) return false
if (a.max.y < b.min.y) return false
return true
}
function isCollided(aabb: AABB, point: Point): boolean {
return point.x >= aabb.x
&& point.x <= (aabb.x + aabb.width)
&& point.y >= aabb.y
&& point.y <= (aabb.y - aabb.height)
}

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

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

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

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

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

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

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

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

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

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

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

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

该定理指出, 如果能找到一个轴, 两个凸形状于该轴的投影不重叠, 就能确定两个形状不相交.
一种更通俗的说法是, 如果能在中间画一条线来分离两个凸多边形, 则两者不相交.

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

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

分离轴定理被物理引擎广泛使用.

参考:

  • https://www.sevenson.com.au/programming/sat/
  • https://jcharry.com/blog/physengine10

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

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

该问题本质上是求多边形各个顶点的平均值.
只需要将多边形各顶点的向量相加, 再除以顶点的数量.

以AABB为例:
center = (leftTop + rightTop + rightBottom + leftBottom) / 4

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

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

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

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

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

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

和GJK算法接近的一种算法, 可以直接得出碰撞点.

流行的, 非常高效的任意凸多胞形碰撞检测算法, 可以替代SAT.
GJK是基于minkowski difference(Minkowski差, 或称Minkowski addition)实现的.
理解起来很简单, 但在数学上证明其成立很困难.

计算两个AABB的闵可夫斯基差, 结果也是一个AABB.

function minkowskiDifference(a: AABB, b: AABB): AABB {
const minkowskiDifferenceLeft = a.left - b.right
const minkowskiDifferenceTop = a.top - b.bottom
const minkowskiDifferenceWidth = a.width + b.width
const minkowskiDifferenceHeight = a.height + b.height
return new AABB(
minkowskiDifferenceLeft
, minkowskiDifferenceTop
, minkowskiDifferenceWidth
, minkowskiDifferenceHeight
)
}

参考: https://blog.hamaluik.ca/posts/simple-aabb-collision-using-minkowski-difference/

若结果AABB覆盖了原点 (0, 0), 则意味着两个AABB碰撞.

function isCollided(minkowskiDifference: AABB): boolean {
return minkowskiDifference.left <= 0
&& minkowskiDifference.right >= 0
&& minkowskiDifference.top <= 0
&& minkowskiDifference.bottom >= 0
}

相交向量是原点到结果AABB四条边的最小距离.

const penetrationVector = closestPointOnBoundsToPoint(minkowskiDifference, new Vector(0, 0))
function closestPointOnBoundsToPoint(aabb: AABB, point: Vector): Vector {
let minDistance = Math.abs(point.x - aabb.left)
let boundsPoint = new Vector(aabb.left, point.y)
if (Math.abs(aabb.right - point.x) < minDistance) {
minDistance = Math.abs(aabb.right - point.x)
boundsPoint = new Vector(aabb.right, point.y)
}
if (Math.abs(aabb.bottom - point.y) < minDistance) {
minDistance = Math.abs(aabb.bottom - point.y)
boundsPoint = new Vector(point.x, aabb.bottom)
}
if (Math.abs(aabb.top - point.y) < minDistance) {
minDistance = Math.abs(aabb.top - point.y)
boundsPoint = new Vector(point.x, aabb.top)
}
return boundsPoint
}

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

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

常见用途:

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

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