float point rounding error problems

[billconan]

hello guys,

in my program, i need to check if an arbitrary 3D line segment intersects with any edge of a 3D triangle (but they are actually in the same plane).

my approach is to solve the equations that are consisted of the line function of the line segment and the line functions of the triangle edges.

once i have a result, i then check if the intersection point is actually on the line segment and one of the triangle edges.


however, i got float point rounding error problems, because the equation solving part involves some subtractions, especially when the triangle and the line segment are very small.

the actual problem happens at where i need to check if a denominator is 0. sometimes, the denominator should be 0, but because of the rounding error, it is not but a very small value.



i thought about using barycentric coordinates method, instead of directly solving the equations, but in my program, i need not only checking if they intersect with each other but also finding out the intersection point. with barycentric coordinates, it is easy to tell if a line segment intersects a triangle edge by checking if one of it's endpoint is outside the triangle, but i don't know how to get the intersection point.




i have two ideas to solve this problem, either transforming the line segment and the triangle into a 2D coordinate system, as there are a lot of intersection solutions in 2D. but why don't those 2D intersection methods have the float point rounding error problem?

or maybe i can use a small value instead of 0 in my equation solving function to check the denominator. is this reasonable? because i did see someone's code doing this trick.

thank you.





or is there any better way to solve linear equations? say using matrix?

[Yves M]

for floating point, you can never check whether a value is equal to 0.0 in order to check if it's zero. You have to fix an epsilon which is a small value and if your value is under that, consider it zero.

const double epsilon = 0.00000001; // arbitrary, depends on the range of values you work with
bool is_zero(double d)
{
  return (fabs(d) < epsilon);
}

You might also want to read this excellent FAQ

[TheCPUWizard]

for floating point, you can never check whether a value is equal to 0.0 in order to check if it's zero. You have to fix an epsilon which is a small value and if your value is under that, consider it zero.

100% correct (although I do not use a fixed constant for epsilon, but that is a different story.

There are also two different geometric issues (that transcent programming).

The first is intersect (cross) and abut (touch). Note that this distinction only applies if one of the shapes is not a straight line.

In the real world there is always measurement error. You may look with the naked eye and say that two objects are touching. Magnification may proves this to be false. At the atomic level, the whole concept gets "wierd" with electrons, clouds, etc....

Intersection is much easier to detect, and find an approximation of the intersection point. One mental technique is to imagine the line, to be a two dimensional object (ie one that has a width, and any non-theoretical line must have. The intersection then does not become a point but rather is a polygon (having area).

When dealing with floating point numbers, the limited precision effectively becomes the width.

[mop65715]

for floating point, you can never check whether a value is equal to 0.0 in order to check if it's zero. You have to fix an epsilon which is a small value and if your value is under that, consider it zero.

const double epsilon = 0.00000001; // arbitrary, depends on the range of values you work with
bool is_zero(double d)
{
  return (fabs(d) < epsilon);
}

You might also want to read this excellent FAQ

I have follow up question on this. Let suppose I'd like to check if 20 milliseconds has elapsed. So now the pseduo source:

  double const duration = .020;
  while ( 1 ) {
     if ( time_expired ( start_time, duration )  ) {
       break ; 
     }
   }

Now given, the issue surrounding comparing floating point values for equality, if you were to write the code for the method time_expired what would that look like?

[MikeAThon]

Calculate in units of milliseconds, and then you can use simple integer arithmetic.

More fundamentally, however, your program is polling for an event (i.e., expiration of 20 msec), which is a terrible waste of CPU resources. Rewrite the code so that your program receives a notification of the event, and simpley waits (without use of CPU) for the event to arrive. In windows, and with your desired behavior of waiting for expriation of 20 msecs, you can use waitable timers, a simple sleep (maybe), inter-thread signalling, etc