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

StackOverflow https://stackoverflow.com/questions/99542

  •  01-07-2019
  •  | 
  •  

题

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

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

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

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均由最接近的浮点近似值表示；没有理由期望它们恰好位于它们应该位于的平面上，因此很可能 P 位于 BC 左侧，Q 位于 BC 右侧。

  • 使用小于或等于测试没有帮助；问题在于光线和平面的相交不准确。

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

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

  • 对于凸网格，您可以只测试所有平面并忽略边缘和顶点，正如您所说（从而完全避免问题）。

  • 不要依次使射线与每个三角形相交。相反，使用 标量三重积. 。（此方法在考虑每个三角形时对射线和边 BC 进行完全相同的计算序列，确保两个三角形之间的任何数值误差至少一致。）

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

让我强烈推荐这本书 实时碰撞检测 作者：克里斯特·埃里克森。第 446-448 页讨论了这个确切的问题，第 184-188 页解释了将射线与三角形相交的标量三重积方法。

其他提示

听起来你不包括测试它是否在边缘（你正在写“内部三角形边缘”）。尝试将代码更改为“小于或等于”（内部或重叠）。

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

无论如何，一个可能的解决方案是不只发射一条射线，而是发射三条彼此非常接近的射线。如果其中一个正好落在两者之间，则保证另外两个中至少有一个落在三角形上。

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

@陈述：我确实已经在我的代码中使用了“大于或等于”比较，谢谢您的建议。+1

我当前的解决方案是在边缘测试中添加少量微调。基本上，当测试每个三角形时，其边缘会被推出很小的量，以抵消浮点误差。类似于测试浮点计算的结果是否小于 0.01，而不是测试是否与零相等。

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

如果您正在进行距离测量，请注意平方根。他们有乱扔垃圾的坏习惯 一半 你的精确度。如果你将其中一些计算叠加起来，你很快就会遇到大麻烦。这是我使用过的距离函数。

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) );
}

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

我在我正在进行的一个项目中发现了这一点。在研究它并弄清楚它的作用之后，我找到了我认为有责任祝贺他的程序员，但他不知道我在说什么。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top