c++ - 3D碰撞检测: convex hull vs convex hull ,需要位置和法线

Question

我想知道两个 3D 凸包(A vs B)之间碰撞位置的近似 3D 位置和 3D 法线。

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

第 1 部分:提前退出(CPU 1%)

在第一步中，我使用了一个非常便宜的算法——separation axis theorem .
例如，我使用 15 axis 2 个立方体。 (在实际情况下，形状更复杂。)
如果至少有 1 个轴可以分离，返回“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 与 edge。

• 对于每对 A 和 B 边(12 * 12 = 144 对)，在 A 的边中找到与 B 边最近的点。检查顶点是否在B内。
• (反之亦然)对于每对 B 和 A 边，检查这样的顶点是否在 A 内。

哇，计算量太大了。
然而，事情还没有结束。

问题

1. 报告的碰撞位置不太准确(左:当前，右:希望):-

   

   为了解决这个问题，我想到了生成一个新的凸形 = A intersect B。
   有一些 C++ 免费库(例如 OpenMesh )，但我认为它的 CPU 开销太大。
   请注意，我不需要它完全正确。

2. 有时也会报错正常(左:当前，右:愿望):-

   

   ^ 这个问题可以通过添加 edge (of A) vs face (of B) 检查来解决，但这会使整个碰撞检测更加昂贵。

问题

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

哪种算法更准确(第一优先级)并且可能更便宜？
我的方法在基础层面可能是错误的。

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

引用资料:-

• Algorithms for Collision Detection between Arbitrarily sized Convex Polygons仅检查是否发生碰撞。

• https://pybullet.org/Bullet/BulletFull/btBoxBoxDetector_8cpp_source.html : 启发 Bullet Physics 库中盒子与盒子碰撞检测的完整代码 - 很难理解。

• https://math.stackexchange.com/questions/397413/determine-direction-of-minimum-overlap-of-convex-polygons与此非常相似的未回答的数学问题。

编辑(10 天后)

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

这是我找到正常的方法。

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

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

Answer 1

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

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

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

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

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

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

对于 time=previous，假设 A 和 B 没有联系。

使用 A 和 B 的先前状态 vector 分别在 time=prev 计算 A 和 B 表面上的最近点。(最近的A，最近的B)。

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

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

对于简单的情况，这应该会给你一个可接受的近似解决方案......

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

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

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

另外，sphere-sphere 测试是一种非常快速的预测试，用于查看两个凸对象的边界球是否甚至重叠。