c++ - 3D碰撞检测：凸包与凸包，需要位置和法线

问题描述

我想知道两个 3D 凸包（ vs ）之间碰撞部位的近似 3D 位置和3D 法线。AB

括号中的 CPU 显示了我完成的程序所需的相对 CPU 时间。

第 1 部分：提前退出（CPU 1%）

第一步，我使用了一个非常便宜的算法——分离轴定理。
例如，我对 2 个立方体使用15 轴。（在实际情况下，形状更复杂。）
如果至少有 1 个轴可以分开，return "no-collide".
否则，做下一部分。

第 2 部分：顶点与体积（CPU 10%）

检查A- 的每个顶点是否在里面B。
检查B- 的每个顶点是否在里面A。

第 3 部分：边缘与边缘（CPU >20%）

有一个奇怪的案例，例如https://gamedev.stackexchange.com/questions/75437/collision-detection-3d-rectangles-using-sat。我从那里偷了图像：-

因此，我也需要edge vs edge。

对于每对 A 和 B 边（12 * 12 = 144 对），在的边中找到一个A与的边最近的点B。检查顶点是否在内部B。
（反之亦然）对于每对 B & A 边，检查这样的顶点是否在里面A。

哇，这是很多计算。
然而，事情还没有结束。

问题

报告的碰撞位置不太准确（左：当前，右：希望）：-

为了解决这个问题，我考虑过生成一个新的凸形 = A intersect B。
那里有一些 C++ 免费库（例如OpenMesh），但我认为它的 CPU 成本太高。
请注意，我不需要它完全正确。
它有时也会报告错误的正常情况（左：当前，右：希望）：-

^ 这个问题可以通过添加边缘（A）与面（B）检查来解决，但这会使整个碰撞检测更加昂贵。

问题

看起来互联网上的常见算法（我从中复制）只识别微特征。恕我直言，顶点体积/边缘边缘算法专注于拓扑，而不是两种形状都是实体体积
的事实。

什么算法更准确（第一优先级）并且可能更便宜？
我的方法在基础层面可能是错误的。

为了加快速度，我已经做了一些修剪，例如只选择靠近的一对边 A 和 B。

参考：-

任意大小的凸多边形之间的碰撞检测算法仅检查是否发生碰撞。
https://pybullet.org/Bullet/BulletFull/btBoxBoxDetector_8cpp_source.html ：启发子弹物理库中盒子与盒子碰撞检测的完整代码 - 很难理解。
https://math.stackexchange.com/questions/397413/determine-direction-of-minimum-overlap-of-convex-polygons 与此非常相似的未回答的数学问题。

编辑（10天后）

现在，我可以找到所有相交的凸点（凸点被描绘为粉红色的三角形/矩形）：-

这是我如何找到正常的。

对于每个分离轴（全部=15 轴），我将粉色凸面投影到轴上。
产生最短投影距离的轴（粉红色箭头）应该是法线方向。

我的上述假设通常是正确的（例如左），但有时是错误的（例如右）。
如何以 CPU 便宜的方式改进它？

标签： c++algorithmcollision-detectiongame-physicsconvex

解决方案

游戏引擎通常模拟时间一系列离散的步骤。因此，由于相互渗透（您的情况）或当事物快速移动时，碰撞系统可能会遇到困难（计算成本高）的情况 - 在步骤 N 处 A 在 B 的一侧并且完全在 B 的另一侧的情况下在步骤 N+1。如果您需要处理多体接触或连续接触或非凸面或关节或柔软物体，则更加困难。哎呀！我们正在模拟整个世界。

你想做“游戏物理”并使用近似值来买回帧率......最后，你可以用一堆烟雾或光弹来掩盖很多错误。:-)

有一类算法明确考虑模拟时间以帮助碰撞系统。有很多方法可以实现“连续碰撞检测”系统。您可以从这里开始，但您应该先广泛阅读，然后再提交代码。幸运的是，有很多关于碰撞的文献。这是一个开始的好地方 https://docs.unity3d.com/Manual/ContinuousCollisionDetection.html https://pybullet.org/Bullet/phpBB3/viewtopic.php?t=20

这是一个建议的启发式方法，它可能适用于您现有的系统……这种启发式技术可能适用于像 astroids 3d 这样的游戏，其中物体在空间中自由浮动。这可能足以满足您的需要。

图像每个对象都存储其当前状态向量（位置、方向、速度、加速度、旋转...）及其上一个时间步长的状态向量。

假设您在 time=current 检测到对象 A 和 B 之间的潜在碰撞。

对于 time=previous，假设 A 和 B 没有接触。

使用 A 和 B 的先前状态向量（closestA，closestB）分别在 time=prev 计算 A 和 B 表面上的最近点。

线段 (closestA,closestB) 在 time=previous 时将具有非零长度。您可以将最接近的 B 用于您的位置和法线，但它会产生一些与线段长度成正比的误差..

因此，通过查找 A 任意接近 B 的时间，及时进行二进制搜索，并最大限度地减少错误。在您的每次搜索过程中，将搜索时间步长减半。0.5, 0.25, 0.125 .. 直到 (closestA,mostB) 的长度低于错误阈值或您放弃。

对于简单的情况，这应该为您提供可接受的近似解决方案...

另外，您说您正在使用分离轴定理作为“第一次检查”。如果这真的是“第一次检查”，那对我来说实际上听起来很昂贵..

最快的计算是你不做的，所以快速碰撞意味着大量廉价的预测试并避免昂贵的情况。

您可以考虑使用空间技术，例如粗略的空间网格，并且只检查您已经知道彼此靠近的对象。

此外，球-球测试是一种非常快速的预测试，可以查看两个凸物体的边界球是否甚至重叠。