algorithm - 在一个方向上与原点相交 minkowski 差异，我如何找到相交的脸？

Question

基本上我在两个多面体的 minkowski 差异的外壳上有一组顶点。我想在任意预定方向上找到从原点到船体的距离。这是一个快速的二维草图:

所以问题是找到光线将与哪个三角形面/平面相交。一旦我有了那架飞机，我就简单地做一个线/平面相交测试。我的问题是找到正确的面/平面。有任何想法吗？我可以做一些点积/叉积/三重积测试来确定它吗？还是比这更复杂？

如果你想知道这对我来说是什么，我使用 GJK 算法来确定两个对象是否相交(我已经开始工作)。如果发生碰撞，我想找到特定方向的穿透深度(这将是物体的运动方向)。

Answer 1

在射线的方向上投影多面体，您的问题将简化为 2D，并找到哪个三角形包围原点。要测试单个三角形，请考虑给定的有向线段 (AB) 相对于原点是顺时针还是逆时针。这很容易通过一个简单的叉积测试来确定:它是逆时针的当且仅当 A x (B-A) > 0。

如果三角形的所有三个边都具有相同的方向(顺时针或逆时针)，则三角形包围原点，这就是您想要的面。

编辑:
由于您的多面体是一个船体，它是凸的，并且由于它是凸的，您可以以有效的方式搜索表面。您可以以一种非常简单的“走上坡/下坡”的方式遍历边缘，以在任一方向上找到沿射线最远的两个顶点。然后在你投影多面体之后，你可以从这两个点开始并向原点进行类似的爬升。这将是 O(sqrt(n))。