3D碰撞检测：凸包与凸包，需要Position和Normal

jav*_*ver 12 c++ algorithm collision-detection convex game-physics

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

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

第1部分：抢先体验（CPU 1％）

第一步，我使用一种非常便宜的算法- 分离轴定理。
例如，我将15轴用于2个多维数据集。（在实际情况下，形状会更复杂。）
如果至少有1个可以分开的轴，return "no-collide"。
否则，请执行下一部分。

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

检查-的每个顶点A是否在内部B。
检查-的每个顶点B是否在内部A。

第3部分：Edge vs Edge（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资源。
请注意，我不需要准确无误。
有时还会报告错误的正常状态（左：当前，右：希望）：-

^这个问题可能通过增加来解决边缘 VS（的）面对检查（的B），但会使乃至整个碰撞检测更昂贵。

题

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

什么是更准确的算法（第一优先级），也许更便宜？
我的方法在基础级别上可能是错误的。

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

参考文献：

任意大小的凸多边形之间的碰撞检测算法仅检查是否发生碰撞。
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天后）

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

这是我找到法线的方法。

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

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

小智 1

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

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

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

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

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

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

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

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

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

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

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

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

最快的计算是您不执行的计算，因此快速碰撞意味着大量廉价的预测试并避免昂贵的情况。

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

此外，球体-球体测试是一种非常快速的预测试，用于查看两个凸物体的边界球体是否均匀重叠。