4

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

  • 原点（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 线，以至于它无法与任何一个三角形发生碰撞，即使从技术上讲它应该总是与一个或另一个发生碰撞，因为他们有共同的优势。当这种情况发生时，该点正好穿过两个共享边三角形之间。我已经用(!)标记了代码的一行，因为我相信那是我应该做出改变的地方。

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

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

4

5 回答 5

10

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

其他受访者提出的一些解释和解决方案将不起作用。尤其：

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

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

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

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

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

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

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

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

于 2009-02-18T22:27:19.350 回答
2

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

于 2008-09-19T04:11:01.453 回答
1

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

无论如何，一个可能的解决方案不是只发射一条射线，而是发射三条彼此非常接近的射线。如果一个恰好落在其他两个之间，那么至少一个肯定会落在一个三角形上。

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

于 2008-09-19T04:14:36.827 回答
0

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

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

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

于 2008-09-19T04:25:30.000 回答
0

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

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

由于最后一个操作不是平方根，因此您不会再丢失精度。

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

于 2008-10-03T19:01:04.063 回答