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

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.

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