点三角形碰撞检测的3D

如何纠正浮点错误以下实物仿真：点三角形碰撞检测的3D

原始点（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线，它不会与任何一个三角形发生碰撞，尽管从技术上讲它应该总是与其中一个碰撞，因为它们共享一个边缘。当发生这种情况时，点在两个边缘共享三角形之间正确通过。我已经用（！）标记了一行代码，因为我相信这是我应该进行更改的地方。

在非常有限的情况下工作的一个想法是跳过边缘测试。有效地将三角形变成飞机。这只适用于我的网格是凸包，但我打算创建凸形。

我特别使用点积和三角法线进行所有前后测试。

来源

2008-09-19 Martin

这是在针对具有边和顶点的几何几何体拍摄单一射线时不可避免的问题。物理模拟似乎寻找最小的数值误差令人惊奇！

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

数值的不准确性可能会导致射线“落入缺口”。问题是，我们在测试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页上将光线与三角形相交的标量三重乘积法的解释。

来源

2009-02-18 22:27:19

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

来源

2008-09-19 04:11:01 Statement

这是一个很好的观点，虽然浮点算术中的“平等”是你永远不能指望的东西。 – shoosh 2008-09-19 04:16:21

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

无论如何，一个可能的解决方案是，而不是只拍摄一条射线来拍摄三个彼此非常接近的射线。如果一个人恰好落在其他两个人中的至少一个之间，则保证落在三角形上。

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

来源

2008-09-19 04:14:36 shoosh

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

我现在的解决方案是在边缘测试中添加一个小的微调量。基本上，每个三角形都经过测试后，它的边缘会被挤出很少量以抵消浮点错误。如果浮点计算的结果小于0.01，而不是测试与零相等，则进行类似的测试。

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

来源

2008-09-19 04:25:30 Martin

是的。这是一种常见的做法，或者我已经接受了导师的教导，以增加精确度容忍度（我不记得他称之为什么）。如果它解决了你的问题，它不会引入新的错误，那就去做吧。 – Statement 2008-09-19 04:34:30

我可以预见的唯一错误是：如果我爬上山顶，当我到达顶部时，我将沿着展开的三角形（或无形地浮动）行走一段非常小的距离（希望用户不可见）我掉到另一个三角形。 – Martin 2008-09-19 04:39:33

如果你正在做距离测量，注意平方根。他们有抛弃你的精确度一半的恶习。如果你将这些计算叠加在一起，你就会很快陷入困境。这是我用过的距离函数。

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-03 19:01:04 user4891

点三角形碰撞检测的3D

回答

相关问题