How do I correct for floating point error in the following physical simulation:
如何在以下物理模拟中更正浮点错误:
- Original point (x, y, z),
- Desired point (x', y', z') after forces are applied.
- Two triangles (A, B, C) and (B, C, D), who share edge BC
原点(x,y,z),
施加力后所需的点(x',y',z')。
共享边缘BC的两个三角形(A,B,C)和(B,C,D)
I am using this method for collision detection:
我正在使用这种方法进行碰撞检测:
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
The problem I am having is that sometimes the point falls into the grey area of floating point math where it is so close to the line BC that it fails to collide with either triangle, even though technically it should always collide with one or the other since they share an edge. When this happens the point passes right between the two edge sharing triangles. I have marked one line of the code with (!) because I believe that's where I should be making a change.
我遇到的问题是,有时候这个点落入浮点数学的灰色区域,它靠近BC线,以至于它不能与任何一个三角形碰撞,即使从技术上来说它应该总是与其中一个碰撞。他们有共同的优势。当发生这种情况时,该点在两个边共享三角形之间正好通过。我用(!)标记了一行代码,因为我相信这是我应该做出改变的地方。
One idea that works in very limited situations is to skip the edge testing. Effectively turning the triangles into planes. This only works when my meshes are convex hulls, but I plan to create convex shapes.
在非常有限的情况下工作的一个想法是跳过边缘测试。有效地将三角形转换为平面。这仅在我的网格是凸包时才有效,但我计划创建凸形。
I am specifically using the dot product and triangle normals for all of my front-back testing.
我专门使用点积和三角法线进行所有前后测试。
5 个解决方案
#1
9
This is an inevitable problem when shooting a single ray against some geometry with edges and vertices. It's amazing how physical simulations seem to seek out the smallest of numerical inaccuracies!
当使用边和顶点针对某些几何体拍摄单个光线时,这是一个不可避免的问题。令人惊讶的是,物理模拟似乎在寻找最小的数值误差!
Some of the explanations and solutions proposed by other respondents will not work. In particular:
其他受访者提出的一些解释和解决方案将无效。特别是:
-
Numerical inaccuracy really can cause a ray to "fall through the gap". The problem is that we intersect the ray with the plane ABC (getting the point P, say) before testing against line BC. Then we intersect the ray with plane BCD (getting the point Q, say) before testing against line BC. P and Q are both represented by the closest floating-point approximation; there's no reason to expect that these exactly lie on the planes that they are supposed to lie on, and so every possibility that you can have both P to the left of BC and Q to the right of BC.
数值不准确确实会导致射线“穿过间隙”。问题是我们在测试线BC之前将光线与平面ABC(比如说得到点P)相交。然后我们在测试线BC之前将光线与平面BCD(得到点Q)相交。 P和Q都用最接近的浮点近似表示;没有理由期望这些完全躺在它们应该躺在的平面上,所以你可以将BC放在BC的左边和Q放在BC的右边。
-
Using less-than-or-equal test won't help; it's inaccuracy in the intersection of the ray and the plane that's the trouble.
使用低于或等于的测试无济于事;这是射线和飞机交叉点的不准确之处。
-
Square roots are not the issue; you can do all of the necessary computations using dot products and floating-point division.
平方根不是问题;你可以使用点积和浮点除法进行所有必要的计算。
Here are some genuine solutions:
这是一些真正的解决方案:
-
For convex meshes, you can just test against all the planes and ignore the edges and vertices, as you say (thus avoiding the issue entirely).
对于凸网格,您可以测试所有平面并忽略边和顶点,如您所说(从而完全避免问题)。
-
Don't intersect the ray with each triangle in turn. Instead, use the scalar triple product. (This method makes the exact same sequence of computations for the ray and the edge BC when considering each triangle, ensuring that any numerical inaccuracy is at least consistent between the two triangles.)
不要依次将光线与每个三角形相交。相反,使用标量三重产品。 (当考虑每个三角形时,此方法对光线和边缘BC进行完全相同的计算序列,确保两个三角形之间的任何数值不准确性至少一致。)
-
For non-convex meshes, give the edges and vertices some width. That is, place a small sphere at each vertex in the mesh, and place a thin cylinder along each edge of the mesh. Intersect the ray with these spheres and cylinders as well as with the triangles. These additional geometric figures stop the ray passing through edges and vertices of the mesh.
对于非凸网格,请为边和顶点指定一些宽度。也就是说,在网格中的每个顶点放置一个小球体,并沿网格的每个边缘放置一个细圆柱体。将光线与这些球体和圆柱体以及三角形相交。这些额外的几何图形阻止光线穿过网格的边缘和顶点。
Let me strongly recommend the book Real-Time Collision Detection by Christer Ericson. There's a discussion of this exact problem on pages 446–448, and an explanation of the scalar triple product approach to intersecting a ray with a triangle on pages 184–188.
让我强烈推荐Christer Ericson的实时碰撞检测书。第446-448页讨论了这个确切的问题,并对第184-188页上的光线与三角形相交的标量三重积方法进行了解释。
#2
2
It sounds like you ain't including testing if it's ON the edge (you're writing "Inside triangle edges"). Try changing code to "less than or equal" (inside, or overlapping).
听起来你不是在测试它是否在边缘(你正在写“内部三角形边缘”)。尝试将代码更改为“小于或等于”(内部或重叠)。
#3
1
I find it somewhat unlikely that your ray would fall exactly between the triangles in a way that the floating point precision would take effect. Are you absolutely positive that this is indeed the problem?
我发现你的光线不太可能以浮点精度生效的方式落在三角形之间。你是绝对肯定的,这确实是问题吗?
At any rate, a possible solution is instead of shooting just one ray to shoot three that are very close to each other. If one falls exactly in between that atleast one of the other two is guaranteed to fall on a triangle.
无论如何,一个可能的解决方案是不只拍摄一张光线来拍摄三张非常接近的光线。如果一个完全落在两者之间,那么其中两个中的至少一个保证落在三角形上。
This will atleast allow you to test if the problem is really the floating point error or something more likely.
这将至少允许您测试问题是否真的是浮点错误或更可能的问题。
#4
0
@Statement: I am indeed already using a "greater than or equal to" comparison in my code, thank you for the suggestion. +1
@Statement:我的代码中确实已经使用了“大于或等于”的比较,谢谢你的建议。 +1
My current solution is to add a small nudge amount to the edge test. Basically when each triangle is tested, its edges are pushed out by a very small amount to counteract the error in floating point. Sort of like testing if the result of a floating point calculation is less than 0.01 rather than testing for equality with zero.
我目前的解决方案是在边缘测试中添加一个小的轻推量。基本上,当测试每个三角形时,其边缘被推出非常小的量以抵消浮点中的误差。如果浮点计算的结果小于0.01而不是测试等于零,则类似于测试。
Is this a reasonable solution?
这是合理的解决方案吗?
#5
0
If you are doing distance measurements, watch out for square roots. They have a nasty habit of throwing away half of your precision. If you stack a few of these calculations up, you can get in big trouble fast. Here is a distance function I have used.
如果您正在进行距离测量,请注意平方根。他们有一种令人讨厌的习惯,就是扔掉一半的精确度。如果你将这些计算中的一些叠加起来,你可能会很快遇到大麻烦。这是我用过的距离函数。
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) );
}
Since the last operation isn't a square root, you don't lose the precision any more.
由于上一次操作不是平方根,因此不再失去精度。
I discovered this in a project I was working on. After studying it and figuring out what it did I tracked down the programmer who I thought was responsible to congratulate him, but he had no idea what I was talking about.
我在一个正在研究的项目中发现了这一点。在研究它并弄清楚它做了什么后,我追踪了我认为有责任祝贺他的程序员,但他不知道我在说什么。
#1
9
This is an inevitable problem when shooting a single ray against some geometry with edges and vertices. It's amazing how physical simulations seem to seek out the smallest of numerical inaccuracies!
当使用边和顶点针对某些几何体拍摄单个光线时,这是一个不可避免的问题。令人惊讶的是,物理模拟似乎在寻找最小的数值误差!
Some of the explanations and solutions proposed by other respondents will not work. In particular:
其他受访者提出的一些解释和解决方案将无效。特别是:
-
Numerical inaccuracy really can cause a ray to "fall through the gap". The problem is that we intersect the ray with the plane ABC (getting the point P, say) before testing against line BC. Then we intersect the ray with plane BCD (getting the point Q, say) before testing against line BC. P and Q are both represented by the closest floating-point approximation; there's no reason to expect that these exactly lie on the planes that they are supposed to lie on, and so every possibility that you can have both P to the left of BC and Q to the right of BC.
数值不准确确实会导致射线“穿过间隙”。问题是我们在测试线BC之前将光线与平面ABC(比如说得到点P)相交。然后我们在测试线BC之前将光线与平面BCD(得到点Q)相交。 P和Q都用最接近的浮点近似表示;没有理由期望这些完全躺在它们应该躺在的平面上,所以你可以将BC放在BC的左边和Q放在BC的右边。
-
Using less-than-or-equal test won't help; it's inaccuracy in the intersection of the ray and the plane that's the trouble.
使用低于或等于的测试无济于事;这是射线和飞机交叉点的不准确之处。
-
Square roots are not the issue; you can do all of the necessary computations using dot products and floating-point division.
平方根不是问题;你可以使用点积和浮点除法进行所有必要的计算。
Here are some genuine solutions:
这是一些真正的解决方案:
-
For convex meshes, you can just test against all the planes and ignore the edges and vertices, as you say (thus avoiding the issue entirely).
对于凸网格,您可以测试所有平面并忽略边和顶点,如您所说(从而完全避免问题)。
-
Don't intersect the ray with each triangle in turn. Instead, use the scalar triple product. (This method makes the exact same sequence of computations for the ray and the edge BC when considering each triangle, ensuring that any numerical inaccuracy is at least consistent between the two triangles.)
不要依次将光线与每个三角形相交。相反,使用标量三重产品。 (当考虑每个三角形时,此方法对光线和边缘BC进行完全相同的计算序列,确保两个三角形之间的任何数值不准确性至少一致。)
-
For non-convex meshes, give the edges and vertices some width. That is, place a small sphere at each vertex in the mesh, and place a thin cylinder along each edge of the mesh. Intersect the ray with these spheres and cylinders as well as with the triangles. These additional geometric figures stop the ray passing through edges and vertices of the mesh.
对于非凸网格,请为边和顶点指定一些宽度。也就是说,在网格中的每个顶点放置一个小球体,并沿网格的每个边缘放置一个细圆柱体。将光线与这些球体和圆柱体以及三角形相交。这些额外的几何图形阻止光线穿过网格的边缘和顶点。
Let me strongly recommend the book Real-Time Collision Detection by Christer Ericson. There's a discussion of this exact problem on pages 446–448, and an explanation of the scalar triple product approach to intersecting a ray with a triangle on pages 184–188.
让我强烈推荐Christer Ericson的实时碰撞检测书。第446-448页讨论了这个确切的问题,并对第184-188页上的光线与三角形相交的标量三重积方法进行了解释。
#2
2
It sounds like you ain't including testing if it's ON the edge (you're writing "Inside triangle edges"). Try changing code to "less than or equal" (inside, or overlapping).
听起来你不是在测试它是否在边缘(你正在写“内部三角形边缘”)。尝试将代码更改为“小于或等于”(内部或重叠)。
#3
1
I find it somewhat unlikely that your ray would fall exactly between the triangles in a way that the floating point precision would take effect. Are you absolutely positive that this is indeed the problem?
我发现你的光线不太可能以浮点精度生效的方式落在三角形之间。你是绝对肯定的,这确实是问题吗?
At any rate, a possible solution is instead of shooting just one ray to shoot three that are very close to each other. If one falls exactly in between that atleast one of the other two is guaranteed to fall on a triangle.
无论如何,一个可能的解决方案是不只拍摄一张光线来拍摄三张非常接近的光线。如果一个完全落在两者之间,那么其中两个中的至少一个保证落在三角形上。
This will atleast allow you to test if the problem is really the floating point error or something more likely.
这将至少允许您测试问题是否真的是浮点错误或更可能的问题。
#4
0
@Statement: I am indeed already using a "greater than or equal to" comparison in my code, thank you for the suggestion. +1
@Statement:我的代码中确实已经使用了“大于或等于”的比较,谢谢你的建议。 +1
My current solution is to add a small nudge amount to the edge test. Basically when each triangle is tested, its edges are pushed out by a very small amount to counteract the error in floating point. Sort of like testing if the result of a floating point calculation is less than 0.01 rather than testing for equality with zero.
我目前的解决方案是在边缘测试中添加一个小的轻推量。基本上,当测试每个三角形时,其边缘被推出非常小的量以抵消浮点中的误差。如果浮点计算的结果小于0.01而不是测试等于零,则类似于测试。
Is this a reasonable solution?
这是合理的解决方案吗?
#5
0
If you are doing distance measurements, watch out for square roots. They have a nasty habit of throwing away half of your precision. If you stack a few of these calculations up, you can get in big trouble fast. Here is a distance function I have used.
如果您正在进行距离测量,请注意平方根。他们有一种令人讨厌的习惯,就是扔掉一半的精确度。如果你将这些计算中的一些叠加起来,你可能会很快遇到大麻烦。这是我用过的距离函数。
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) );
}
Since the last operation isn't a square root, you don't lose the precision any more.
由于上一次操作不是平方根,因此不再失去精度。
I discovered this in a project I was working on. After studying it and figuring out what it did I tracked down the programmer who I thought was responsible to congratulate him, but he had no idea what I was talking about.
我在一个正在研究的项目中发现了这一点。在研究它并弄清楚它做了什么后,我追踪了我认为有责任祝贺他的程序员,但他不知道我在说什么。