Triangle Triangle Collision Detection in 3D

Question

How to fix a floating point error in the following physical simulation:

• Starting point (x, y, z),
• The required point (x ', y', z ') after the use of forces.
• Two triangles (A, B, C) and (B, C, D) that separate the edge BC

I use this method to detect collisions:

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 normal). If the intersection point is inside the triangle edges (!) Respond to the collision. End If End If Next Triangle 

The problem I am facing is that sometimes a dot falls into the gray field of floating point mathematics, where it is so close to the BC line that it does not collide with any triangle, although technically it should always collide with one or another because they have an advantage. When this happens, the point passes right between the two triangles of separation of the boundaries. I marked one line of code (!) , Because I think that where I should make changes.

One idea that works in very limited situations is to skip border checking. Effective transformation of triangles in the plane. This only works when my cells are convex hulls, but I plan to create convex shapes.

I specifically use the dot product and triangle normals for all checks in the foreground.

Answer 1

This is an unavoidable problem when shooting a single beam against some geometry with edges and vertices. It's amazing how physical modeling seems to be looking for the smallest of numerical errors!

Some of the explanations and solutions suggested by other respondents will not work. In particular:

• A numerical error can actually lead to the ray "falling through the gap." The problem is that we cross the ray with the plane ABC (getting the point P, say), before testing on the line BC. Then we cross the beam with a flat BCD (getting the point Q, say), before testing on the BC line. P and Q are both represented by the closest floating point approximation; there is no reason to expect that they exactly lie on the planes on which they should lie, and therefore every possibility that you can have like P to the left of BC and Q to the right of BC.

• Using the test less or equal will not help; this is an inaccuracy in the intersection of the beam and the plane, which is the problem.

• Square roots are not a problem; You can perform all the necessary calculations using dot products and floating point.

Here are some genuine solutions:

• For convex meshes, you can simply test all planes and ignore edges and vertices as you say (thus avoiding the problem completely).

• Do not cross the beam with each triangle in turn. Instead, use a scalar three-local product . (This method does the same calculation for the ray and edge BC when examining each triangle, ensuring that any numerical error is at least consistent between the two triangles.)

• For non-convex grids, specify the width of the edges and vertices. That is, place a small sphere at each vertex of the grid and place a thin cylinder along each edge of the grid. Cross the beam with these spheres and cylinders, as well as with triangles. These additional geometric shapes stop the beam passing through the edges and vertices of the grid.

Let me highly recommend the Christer Ericson real-time collision detection book. This exact problem is discussed there 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 looks like you do not enable testing if it is on the edge (you write "Inside the triangles"). Try changing the code to less than or equal to (inside or overlay).

Answer 3

I find it somewhat unlikely that your beam will hit exactly between the triangles so that the floating point precision takes effect. Are you absolutely sure that this is really a problem?

In any case, a possible solution, instead of shooting only one beam, is to shoot three that are very close to each other. If someone falls exactly between them, at least one of the other two is guaranteed to fall on the triangle.

This will let you check if the problem is really a floating point error or something more likely.

Answer 4

@Statement: I really already use more than or equal to comparison in my code, thanks for the suggestion. +1

My current solution is to add a small amount of push to the edge test. Basically, when each triangle is tested, its edges are pushed out by a very small amount to counteract the floating point error. Similar to testing if the result of the floating point calculation is less than 0.01, and not a equality test with zero.

Is this a smart decision?

Answer 5

If you are taking distance measurements, watch out for square roots. They have an unpleasant habit of dropping half of your accuracy. If you stack a few of these calculations up, you can get big problems quickly. Here is the distance function I 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 is not a square root, you no longer lose accuracy.

I found this in a project that I was working on. After studying it and finding out what he did, I tracked down the programmer who I thought was responsible to congratulate him, but he had no idea what I was talking about.