math - 3D 中的点三角形碰撞检测

Question

如何纠正以下物理模拟中的浮点错误:

原点 (x, y, z),

施加力后所需的点 (x', y', z')。

共享边 BC 的两个三角形 (A, B, C) 和 (B, C, D)

我正在使用这种方法进行碰撞检测:

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

我遇到的问题是，有时该点落入浮点数学的灰色区域，在那里它非常接近 BC 线，以至于它无法与任何一个三角形碰撞，尽管从技术上讲它应该始终与一个或另一个碰撞他们共享一个优势。当这种情况发生时，该点正好在两个边共享三角形之间通过。我用 (!) 标记了一行代码，因为我相信这是我应该进行更改的地方。

在非常有限的情况下工作的一种想法是跳过边缘测试。有效地将三角形变成平面。这仅在我的网格是凸包时有效，但我计划创建凸形。

我专门使用点积和三角形法线进行我所有的前后测试。

Answer 1

当对某些具有边缘和顶点的几何体拍摄单条光线时，这是一个不可避免的问题。物理模拟似乎能找出最小的数值误差，这真是太神奇了!

其他受访者提出的一些解释和解决方案是行不通的。特别是:

数值不准确确实会导致光线“穿过间隙”。问题是我们在对线 BC 进行测试之前将射线与平面 ABC(例如得到点 P)相交。然后，在对线 BC 进行测试之前，我们将射线与平面 BCD 相交(比如得到点 Q)。 P 和 Q 都用最接近的浮点近似表示；没有理由期望它们恰好位于它们应该位于的平面上，因此您可以将 P 放在 BC 的左侧，将 Q 放在 BC 的右侧。

使用小于或等于测试无济于事；问题在于光线和平面的交点不准确。

平方根不是问题；您可以使用点积和浮点除法进行所有必要的计算。

以下是一些真正的解决方案:

对于凸面网格，您可以只针对所有平面进行测试并忽略边缘和顶点，如您所说(从而完全避免该问题)。

不要让光线依次与每个三角形相交。相反，使用 scalar triple product 。 (当考虑每个三角形时，此方法对射线和边 BC 进行完全相同的计算序列，确保任何数值误差至少在两个三角形之间是一致的。)

对于非凸面网格，给边缘和顶点一些宽度。也就是说，在网格的每个顶点放置一个小球体，并沿网格的每个边缘放置一个细圆柱体。将射线与这些球体和圆柱体以及三角形相交。这些额外的几何图形阻止光线穿过网格的边缘和顶点。

让我强烈推荐 Christer Ericson 的书 Real-Time Collision Detection。第 446–448 页讨论了这个确切的问题，第 184–188 页解释了使射线与三角形相交的标量三重积方法。