有没有一种方法可以修改 Gilbert-Johnson-Keerthi 算法，使其能够找到两个物体碰撞点而不是 true/false 结果？据我所知，接收到的距离值可以用于找到这些点。我在网上搜索了一下，但没有找到任何线索。
GJK中的碰撞点
7
- Viuo
2
一个外行的想法：如果你从原点到一个物体进行GJK，你不仅可以得到从原点到物体的距离，还可以得到最靠近原点的物体上的实际点。然而，对于两个物体，你要测量的是Minkowski和A-B。如果物体发生碰撞，你将得到0作为结果，但你需要找到所有差值恰好为0的点对(a在A中，b在B中)来获取碰撞点集。因此，我认为GJK的结果并不能导致简单的通用解决方案。请尝试查看http://www.pfirth.co.uk/minkowski.html以获取直觉。 - Owen S.
你知道其他简单的方法来找到两个物体之间的撞击点吗？我已经阅读了Gino Van Den Bergen的《针对一般凸物体的光线投射及其在连续碰撞检测中的应用》，但它真的很复杂，似乎并没有真正帮助我（我正在尝试制作一个物理模拟器，对于我来说，在碰撞后正确旋转是至关重要的）。从我所了解的情况来看，如果一个物体旋转，用这种方式找到撞击点并不容易。也许还有其他算法我可以实现吗？如果需要，我可以每帧进行检查。 - Viuo
2个回答
4
您提出的问题不够明确。如果它们发生碰撞，那么交点是未定义的，因为交点实际上是重叠区域，因此可能是任意数量的可能点。相反，您应该将“交点”视为时空坐标(dx,dy,dz,t)，表示冲击时间，以及两个物体之间的平移向量，给出它们的相对配置。
修改GJK以计算时空交点的一种方法是在扫描体积上进行二分搜索，找到碰撞前的时间点。使用这些数据，您可以计算分离轴和对应的极端点，从而得到接触点的近似值。如果您重用先前迭代的搜索中的简单形状来加速后续测试，则此方法也可以快速执行。Christer Ercisson在这里有一些关于这种技术的笔记: http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf
修改GJK以计算时空交点的一种方法是在扫描体积上进行二分搜索，找到碰撞前的时间点。使用这些数据，您可以计算分离轴和对应的极端点，从而得到接触点的近似值。如果您重用先前迭代的搜索中的简单形状来加速后续测试，则此方法也可以快速执行。Christer Ercisson在这里有一些关于这种技术的笔记: http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf
- Mikola
1
这篇论文应该能回答你的问题，并且是最新的。我没有任何代码，也不会重新解释它，但是作者在YouTube上也有一个演示。现在正在编写代码，并且很少有例子。但这就是你想要的。你可以使用论文中提到的“效果较差”的方式，因为它对你的工作完全有效，除非你的目标是极高的性能。
“改进GJK算法以实现更快、更可靠的凸体之间距离查询”
作者：MATTIA MONTANARI和NIK PETRINIC，牛津大学
ETTORE BARBIERI，伦敦玛丽女王大学
“改进GJK算法以实现更快、更可靠的凸体之间距离查询”
作者：MATTIA MONTANARI和NIK PETRINIC，牛津大学
ETTORE BARBIERI，伦敦玛丽女王大学
- Zepalz
1
这是一个关于编程的视频，讲解时长为18分钟。以下是该视频的Youtube链接：
https://www.youtube.com/watch?v=NcivnQ02rGw - Zepalz
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接