三维点三角碰撞检测

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都用最接近的浮点近似表示; 没有理由期望这些完全躺在它们应该躺在的平面上,所以你可以将BC放在BC的左边和Q放在BC的右边.

• 使用低于或等于的测试将无济于事; 这是射线和飞机交叉点的不准确之处.

• 平方根不是问题; 你可以使用点积和浮点除法进行所有必要的计算.

这是一些真正的解决方案:

• 对于凸网格,您可以测试所有平面并忽略边和顶点,正如您所说(从而完全避免了问题).

• 不要依次将光线与每个三角形相交.相反,使用标量三重产品.(当考虑每个三角形时,此方法对光线和边缘BC进行完全相同的计算序列,确保两个三角形之间的任何数值不准确性至少一致.)

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

让我强烈推荐Christer Ericson 的" 实时碰撞检测 "一书.第446-448页讨论了这个确切的问题,并对第184-188页上的光线与三角形相交的标量三重积方法进行了解释.