乐趣区

关于javascript:碰撞检测-Separating-Axis-Theorem

jiezi

引子

在 Collision Detection：Transformation 中介绍了动静的碰撞检测，至此 CollisionDetection 我的项目的次要内容差不多都波及了。在查问材料的时候，还接触到一些其它的检测办法，当初来看一下另外一种检测办法：Separating Axis Theorem。

  • Origin
  • My GitHub

相干知识点

矢量和标量

简略的来说：

  • 矢量（vector）也称向量，有大小和方向的量，例如加速度、力。
  • 标量（scalar）只有大小（magnitude）的量，例如工夫、温度。

在几何中，矢量用有向线段示意，示意如下：

矢量 V 计算方法：

  • V = C2 – C1
  • V = (7-3,7-2)
  • V = (4,5)

法向量：向量的垂直向量，替换 x 和 y 重量，而后将坐标 x 重量取反。下面 V 的法向量为 (-5,4)。

点积和投影

点积

两个矢量，能够用 点积（Dot Product）的形式进行相乘，后果是一个标量。示意模式为：A · B。

点积有两种计算形式：

形式一

A · B = Ax * Bx + Ay * By

形式二

A · B = |A| * |B| * cos(θ)
  • |A| 是矢量 A 的量值
  • |B| 是矢量 A 的量值
  • θ 是矢量 A 和 B 之间的角度

还须要理解的一个概念就是 单位向量，单位向量计算方法：向量除以向量本身的量值。

A / |A|

更多信息见这里。

投影

对于 投影（Projection），先看下图：

设想用一个收回平行光线的光源，照射到一个物体上，将在一个面上产生暗影。这个暗影是三维物体的二维投影。

相似的，二维物体的投影就是一维的“暗影”。

点积和投影的关系

利用 点积 能够得出一个矢量在另外一个矢量上的投影。通过简略的推导就能够明确。

如上图所示，将 V 在 W 上的投影标量记为 Pw(V)，能够得悉：

Pw(V) = |V| * cos(θ)

依据点积计算方法得悉:

V · W = |V| * |W| * cos(θ)
V * (W / |W|) = |V| * cos(θ)

因而能够得出：

Pw(V) = |V| * cos(θ) = V * (W / |W|)

多边形

凸多边形

一条直线穿过一个多边形时，如果该线与多边形相交不超过（蕴含）两次，则该多边形为 凸多边形（​Convex Polygon）。

凹多边形

一条直线穿过一个多边形时，如果该线与多边形相交超过两次，则该多边形为 凹多边形（Concave Polygon）。

Separating Axis Theorem

分轴实践（Separating Axis Theorem）由 Hermann Minkowski 提出，可用于解决凸多边形碰撞问题，该实践表明：

如果存在一条轴线，两个凸面物体在该轴上的投影没有重叠，那么这两个凸面物体就没有重叠。

这个轴线称为 分轴。接下来进一步讨论一下。在下文中分轴实践简称 SAT。

没有重叠

在上图中，能够看到投影没有重叠，依据 SAT，这个两个形态没有重叠。

SAT 在检测的时候，可能须要检测很多轴线，但只有检测到有一个轴线上投影没有重叠，就能够进行持续检测。因为这种特点，SAT 对于有很多物体但碰撞很少的利用（游戏、模仿等等）是现实的抉择。

重叠

如果在所有分轴上，形态的投影都重叠，那么咱们能够确定这些形态产生了重叠。示例如下：

算法实现

有了下面的原理，接下来转换成算法须要思考的问题有：

  1. 如何获取到所有潜在的分轴？
  2. 投影重叠判断根据是什么？

问题 1

通过查找材料，第一个问题的答案是：在 2D 中，所有潜在的分轴是形态每条边的法线。

法线简略来说就是没有方向的法向量。在后面的知识点中有介绍。上面是一个大略逻辑实现：

const vertices = [] // 顶点的坐标汇合，假如已有值
const axes = [] // 寄存分轴
const verticesLen = vertices.length;

for (let i = 0; i < verticesLen; i++) {const p1 = vertices[i];
  const p2 = vertices[i + 1 == vertices.length ? 0 : i + 1];
  // 获取每条边的矢量代数示意，subtract 办法性能次要性能是 p2 的坐标与 p1 坐标重量相减
  const edge = subtract(p1,p2);
  // 获取法向量，normalAxes 办法次要性能：(x, y) => (-y, x) or (y, -x)
  const normal = normalAxes(edge);
  axes.push(normal);
}

问题 2

在下面的对于 SAT 的介绍中，在图示中能够比拟显著察看到，在算法实现中，须要遍历形态所有的顶点与分轴执行点积，比拟取得最小值和最大值。而后在一条轴线上大略标注出最小值和最大值，看是否有重叠的区间。

上面是一个大略逻辑实现：

假如有多边形 A 和多边形 B。

const verticesA = []; // A 形态所有顶点坐标汇合
const verticesB = []; // B 形态所有顶点坐标汇合
const axes = [] // 存储获取的所有分轴
const axesLen = axes.length;

for (let i = 0; i < axesLen; i++) {const separateAxes = axes[i];
  // getProject 办法获取投影的最大和最小值
  const projectA = getProject(separateAxes,verticesA);
  const aMin = projectA.min;
  const aMax = projectA.max;
  const projectB = getProject(separateAxes,verticesB);
  const bMin = projectB.min;
  const bMax = projectB.max;
  // 合乎该条件，示意投影重叠了。if ((aMin <= bMax && aMin >= bMin) || (bMin <= aMax && bMin >= aMin) ) {continue;} else {return false;}
}

验证

依据下面的思路，以网页左上角作为坐标原点，程度向左作为 X 轴，垂直向下作为 Y 轴。依据 CSS 的单位形容坐标点。

这个是测试页面，挪动端如下：

在下面测试页面中，以未重叠的投影数据为例，检测的数据投影到一条轴线上：

能够看出没有重叠。

参考资料

  • Separating Axis Theorem
  • SAT (Separating Axis Theorem)
  • Collision Detection and Response
  • Collision Detection Using the Separating Axis Theorem
  • Dot product and vector projections
退出移动版