Point-Triangle Collision Detection in 3D

Question

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

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.

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.

Answer 1

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).

Answer 2

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.

Answer 3

@Statement: I am indeed already using a "greater than or equal to" comparison in my code, thank you for the suggestion. +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.

Is this a reasonable solution?

Answer 4

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.

Answer 5

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.

• 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.)

• 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.