3

我正在尝试使用 JavaScript 中的分离轴定理来检测两个正方形碰撞（一个旋转，一个不旋转）。尽我所能，我无法弄清楚这在 JavaScript 中会是什么样子，也找不到任何 JavaScript 示例。请帮忙，用纯数字或 JavaScript 代码解释将是最有用的。

更新：在研究了大量几何和数学理论后，我决定在 GitHub 存储库中推出一个简化的 SAT 实现。您可以在此处找到 JavaScript 中的 SAT 工作副本：https ://github.com/ashblue/canvas-sat

4

1 回答 1

4

变换多边形

首先，您必须通过应用angle.

为了将来对缩放、平移等的支持。我建议通过矩阵变换来做到这一点。您必须编写自己的Matrix类或找到一些已经具有此功能的库（我相信有很多选择）。

然后，您将徒劳地使用代码：

var transform = new Matrix();
transform.appendRotation(alpha);
points = transform.transformPoints(points);

对象points数组在哪里。Point

碰撞算法概述

所以这就是在你遇到任何碰撞之前的全部内容。关于碰撞算法，标准做法是尝试使用以下步骤分离 2 个凸多边形（在您的情况下为正方形）：

  • 对于每个多边形边（多边形 0 和多边形 1 的边）：
    • 将两个 polgyons 分类为“在前面”、“跨越”或“在”边缘。
    • 如果两个多边形在不同的边上（1 个“前面”和 1 个“后面”），则没有碰撞，您可以停止算法（提前退出）。
  • 如果你到了这里，没有边缘能够分离多边形：多边形相交/碰撞。

请注意，从概念上讲，“分离轴”是垂直于我们对多边形进行分类的边缘的轴。

关于边的多边形分类

为了做到这一点，我们将根据边缘对多边形的点/顶点进行分类。如果所有点都在一侧，则多边形在该侧。否则，多边形跨越边缘（部分在一侧，部分在另一侧）。

要对点进行分类，我们首先需要获取边缘的法线：

// this code assumes p0 and p1 are instances of some Vector3D class

var p0 = edge[0]; // first point of edge
var p1 = edge[1]; // second point of edge
var v = p1.subtract(p0);
var normal = new Vector3D(0, 0, 1).crossProduct(v);
normal.normalize();

上面的代码使用边缘方向和 z 向量的叉积来获得法线。当然，您应该为每条边预先计算这个值。

注意：法线代表与 SAT 的分离轴。

接下来，我们可以通过首先使其相对于边缘（减去边缘点）并使用法线的点积来对任意点进行分类：

// point is the point to classify as "in front" or "behind" the edge
var point = point.subtract(p0);
var distance = point.dotProduct(normal);
var inFront = distance >= 0;

现在，inFront是true该点是在前面还是在边缘，false否则。

请注意，当您遍历多边形的点以对多边形进行分类时，如果前面至少有 1 个点，后面至少有 1 个点，您也可以提前退出，因为那时已经确定多边形跨越边缘（而不是前面或后面）。

如您所见，您仍然需要编写大量代码。Matrix找到一些带有和类的js库，Vector3D并使用它来实现上述内容。将您的碰撞形状（多边形）表示为序列Point和Edge实例。

希望这能让你开始。

于 2012-05-01T17:34:51.763 回答