问题标签 [separating-axis-theorem]

我有一个基于分离轴定理（SAT）的凸二维多边形与凸二维多边形碰撞测试。

我的问题是：是否有可能在不以某种形式纠正 MTV 方向的情况下实现这个算法？（通过注意缠绕顺序，朝外的法线或我可能弄错的其他细节）。

SAT 产生一个最小平移向量。我发现很难让 MTV 的方向正确，因为它大约有一半时间指向错误的方向（如果将多边形 A 和 B 传递给碰撞检测功能，则 MTV 应该始终用于 A）。它只有在添加检查两个投影之间重叠方向的代码后才开始正常工作，而不仅仅是两个投影重叠。

但是我感觉我可能错过了一个重要的细节，因为我读过的关于 SAT 的各种文章和评论都提到了面向外的多边形法线，而 MTV 方向的话题却很少受到关注（好像它很简单，而对我来说这是最难的部分）。

我的 SAT 实现的核心是这个函数，它被调用了两次。第二次调用该函数时参数的顺序颠倒了，这会影响 MTV 方向，但我很清楚这一点。

这是我为 Lua 中的 LOVE2D 引擎制作的一个小库，它使用分离轴定理来解决碰撞问题。

当我的 SAT 程序开始运行时，我非常高兴，并开始使用大量多边形对其进行测试。它在大多数情况下都有效，并且也为它们提供了正确的最小平移向量。奇怪的是——如果两个形状都有锐角，那么这些角度会导致程序失败，当形状不接触时返回碰撞，或者更不寻常的是，它会给出一个奇怪的最小平移向量。我检查了返回法线的函数——因为我觉得这是我可能失败的第一点，但它似乎工作正常。

这是处理我的碰撞的主要功能。

我的项目文件在 github https://github.com/ToffeeGoat/ToffeeCollision

我正在尝试使用分离轴定理在 Javascript/p5.js 中实现凹多边形的碰撞检测。我一直在关注如何使用它的以下教程：http ://www.dyn4j.org/2010/01/sat/

但是，无论两个多边形的位置如何，我的检查总是返回 true。这是我的代码：

使用定义的比例、旋转和位置，使用以下函数转换顶点：

SAT 方法总是返回 true。我相信我正在错误地检查重叠，但我无法弄清楚我到底做错了什么。

我制作了一个碰撞检测算法，可以检测旋转的正方形是否发生碰撞。我正在努力理解我应该做些什么来解决这些冲突。我认为第一步是计算可以将两个正方形分开的最小平移向量（MTV）。

我认为做到这一点的方法是通过计算正方形投影在正在测试的轴上的重叠，然后使用最小重叠的长度和该轴的角度来形成 MTV。

问题是我的代码不能通过比较投影来工作，而是使用此代码来检测碰撞：

每个 Box 包含一个由四个 PointF 对象组成的数组，这些对象代表顶点 (Box.vertices)。它们还包含一个由四个 Vector 对象组成的数组，这些对象是归一化（单位）向量，表示每个边的法线（Box.edgeNormals）。

然后我为每个盒子调用这个函数来检查是否有碰撞：

碰撞是一个包含observerBox 和observedBox 的二元数组。

那么如何计算 MTV 呢？

另外我如何将它应用到盒子上？

• 只用 MTV 翻译一个盒子？
• 用一半的 MTV 将每个盒子彼此分开？
• 不知何故，根据盒子的某些属性（质量/速度），将多少 MTV 应用于每个盒子？

我正在用 C++ 编写一些代码来使用分离轴定理测试碰撞，并且在某些方向上它错误地触发了发生碰撞

我正在关注本教程，但是该教程仅是 2D 的，我正在尝试以 3D 实现它，尽管我认为它应该仍然是相同的。

我现在拥有的算法不会错过任何碰撞，但是对于两个框的某些方向，它认为它们实际上没有发生碰撞。可以在这里看到一个例子，根据下面的代码，这两个盒子显然是碰撞的。

代码是用 C++ 编写的

BoxCollider.h

BoxCollider.cpp

算法：

我正在使用分离轴定理来检查两个多边形（玩家和对象）是否相交。我想让玩家从物体上反弹，但要做到这一点，我需要玩家碰撞的一侧（我将计算角度）。

我怎样才能从我的 SAT 函数中得到这个？

我已经在 2D 中实现了 SAT 碰撞检测系统，但我不知道如何获得碰撞影响点。

目前我获得了 mtv 和分离轴，因此我可以解决碰撞但不能对其施加正确的力，因为缺少撞击点。

概括

这个问题是用 JavaScript 写的，但是用任何语言、伪代码或数学来回答都会很棒！

我一直在尝试实现分离轴定理来完成以下任务：

• 检测凸多边形和圆之间的交点。
• 找出可应用于圆的平移以解决相交问题，使圆几乎不接触多边形，但不再在内部。
• 确定碰撞的轴（问题末尾的详细信息）。

我已成功完成第一个要点，您可以在问题末尾看到我的 javascript 代码。我在其他部分有困难。

解决交集

网上有很多关于如何解决圆最小/最短重叠方向上的交点的例子。您可以在最后的代码中看到我已经计算过了。

但是，这不适合我的需要。我必须解决与圆轨迹相反方向的碰撞（假设我已经有了圆的轨迹，并希望将它作为单位向量或角度传递给我的函数，以适合者为准）。

您可以在下图中看到最短分辨率和预期分辨率之间的差异：

如何计算最小平移向量以解决test_CIRCLE_POLY函数内部的交点，但这将应用于特定方向，与圆的轨迹相反？

我的想法/尝试：

• 我的第一个想法是在必须在 SAT 算法中测试的轴上添加一个附加轴，该轴将垂直于圆的轨迹。然后我会在投影到这个轴上时根据重叠来解决。这会有点工作，但在大多数情况下会解决得很远。它不会导致最低翻译。所以这不会令人满意。
• 我的第二个想法是继续使用最短重叠的幅度，但将方向更改为与圆的轨迹相反。这看起来很有希望，但可能有很多我没有考虑到的极端情况。也许这是一个不错的起点。

确定碰撞侧/轴

我想出了一种方法来确定圆与多边形的哪些边相撞。对于多边形的每个测试轴，我会简单地检查重叠。如果有重叠，那一侧就会发生碰撞。

这个解决方案将不再被接受，因为我只想根据圆的轨迹找出一侧。

我的预期解决方案会告诉我，在下面的示例图像中，轴 A 是碰撞轴，而不是轴 B。这是因为一旦解决了交点，轴 A 就是对应于多边形边的轴只是勉强接触到圆圈。

我的想法/尝试：

• 目前我假设碰撞轴垂直于 MTV（最小平移向量）。这目前是不正确的，但是一旦我在问题的前半部分更新了交叉点解析过程，它应该是正确的轴。所以这部分应该首先解决。

• 或者，我考虑从圆的先前位置及其当前位置+半径创建一条线，并检查哪些边与这条线相交。但是，仍然存在歧义，因为有时会有不止一侧与线相交。

到目前为止我的代码

我正在尝试与来自 tria 网格的三角形执行 AABB-三角形相交，而 AABB 是结构化 3D 网格/体素中的单个单元格。有没有什么聪明的方法/算法可以用来过滤和减少我必须执行 SAT 测试的三角形和 AABB 组合的数量？就目前而言，我正在针对网格中的每个单元格检查每个三角形，这是无效的。我还考虑根据三角形网格中的质心距离和最大三角形尺寸过滤掉三角形作为容差。但这又将涉及遍历所有三角形。我也在考虑 K 近邻。

我一直在调整和修改我的代码以针对三角形测试 AABB，但我不确定我做错了什么。我正在使用分离轴定理，因为我相信这是用于检测 AABB 和三角形之间碰撞的最佳且唯一的方法（如果我错了或有更好/更快的方法，请纠正我）。目前，当发生碰撞时，它不会检测到任何东西。

代码比较小，每帧都调用isAABBIntersectingTriangle，希望懂数学或者算法的人能帮帮我。该函数将边界框 min 和 max 作为两个 3D 向量 (glm::vec3) 和三角形顶点 (tri1, tri2, tri3) 中的 3 个作为 glm::vec3s。这些坐标都在世界空间中（AABB 坐标仅通过位置和比例平移，三角形通过位置旋转和比例平移）

这里也是主循环中的代码，它计算三角形的世界位置，然后调用函数，我不相信这里有什么问题，因为它可能被检查得最多：