关于数学:3D中的点三角形碰撞检测

关于数学:3D中的点三角形碰撞检测

Point-Triangle Collision Detection in 3D

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

  • 原点(x,y,z),
  • 施加力后的期望点(x',y',z')。
  • 共享边BC的两个三角形(A,B,C)和(B,C,D)

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

1
2
3
4
5
6
7
8
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线非常接近,以致于无法与任何一个三角形发生碰撞,即使从技术上讲它应始终与另一个发生碰撞,因为他们有优势。当发生这种情况时,该点就在两个边缘共享三角形之间通过。我用(!)标记了代码的一行,因为我认为那是我应该进行更改的地方。

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

我在所有前后测试中都特别使用了点积和三角形法线。


当对具有边缘和顶点的某些几何形状拍摄单个光线时,这是一个不可避免的问题。令人惊讶的是,物理模拟似乎能找出最小的数值误差!

其他答复者提出的某些解释和解决方案将不起作用。尤其是:

  • 数值上的错误确实会导致射线"穿过间隙"掉落。问题在于,在针对BC线进行测试之前,我们将射线与平面ABC相交(得到点P,例如)。然后,在与BC线进行测试之前,将光线与BCD平面相交(得到点Q,例如)。 P和Q都由最接近的浮点近似表示;没有理由期望它们正好位于它们应该位于的平面上,因此,您有可能使BC左侧的P和BC右侧的Q都存在。

  • 使用小于或等于测试将无济于事;问题是射线与平面的交点不准确。

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

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

  • 对于凸网格,您可以像测试中所说的那样对所有平面进行测试,而忽略边和顶点(从而完全避免出现此问题)。

  • 不要将光线与每个三角形依次相交。而是使用标量三乘积。 (当考虑每个三角形时,此方法对射线和边缘BC进行完全相同的计算序列,以确保两个三角形之间的任何数值误差至少是一致的。)

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

让我强烈推荐Christer Ericson所著的《实时碰撞检测》。在第446–448页上讨论了此确切问题,并在第184–188页上说明了将光线与三角形相交的标量三乘积方法。


听起来您不包括测试它是否在边缘上(您正在编写"内部三角形边缘")。尝试将代码更改为"小于或等于"(内部或重叠)。


我发现您的射线不太可能完全以浮点精度生效的方式落在三角形之间。您绝对肯定这确实是问题吗?

无论如何,一种可能的解决方案是代替仅拍摄一束光线来拍摄三束非常接近的光线。如果一个恰好落在该至少一个之间,则其他两个中的至少一个可以保证落在三角形上。

这将至少允许您测试问题是否确实是浮点错误或更可能的问题。


如果要进行距离测量,请注意平方根。他们有一个讨厌的习惯,就是丢掉一半的精度。如果将这些计算中的一些叠加起来,就会很快遇到大麻烦。这是我使用的距离函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

由于最后一个运算不是平方根,因此您不会再失去精度。

我在我正在从事的项目中发现了这一点。在研究了它并弄清楚它是做什么之后,我找到了我认为应该向他表示祝贺的程序员,但是他不知道我在说什么。


@声明:我的代码中确实已经使用了"大于或等于"的比较,谢谢您的建议。 +1

我当前的解决方案是在边缘测试中添加少量微调。基本上,在测试每个三角形时,都会将其边缘推出一小部分以抵消浮点误差。有点像测试浮点计算的结果是否小于0.01,而不是测试是否等于零。

这是一个合理的解决方案吗?


推荐阅读