2

The problem I am trying to solve is to generate an AABB for the intersection of a triangle and a cube. In 2D, the required volume is the green square shown here: enter image description here

The input points and output bounds are IEEE float.

My current method using floating point is to clip the triangle to each face of the voxel, and bound the resulting poly. However, using floating point means that the intersection points are not exact, and so it could be the case that the resulting AABB does not fully bound the intersection area. I need a conservative bound.

I looked into using interval arithmetic for the clipping, but there are two potential issues:

  • Intervals will likely become large for the chain of operations
  • Branching where the condition depends on an interval is a mess, the result may be uncertain which means both possibilities need computing. Eg. If (line crosses plane)

Is there a neater way to do this? Maybe some way to compute a required epsilon to offset the final result? Temping just to compute in double and offset the final float result by 1ULP, in hopes that the double math doesn't accumulate >28 bits of error. It would be nice if I could prove that though.

Rational arithmetic may be another option, but I can't see how I can guarantee having enough bits when the inputs can span the whole floating point range.

Any suggestions? Thanks in advance.

Greg
  • 123
  • 6
  • The voxel size should be a significant reference for the required accuracy. Why don't you add a constant fraction of that size (say a thousandth) on all sides ? This shouldn't cause a significant performance degradation when exploiting the AABB. –  Jan 07 '16 at 15:08
  • The size of the voxel doesn't affect the accuracy of the intersection results though, I think that depends on the exponent of the operands. I see what you are getting at, but the error might be more than 1/1000 for a small voxel, I need guaranteed bounds on the error. As an example, a voxel might only be 10 floating point values wide, One could easily imagine a series of operations accumulating 1ULP of error, which is 1/10 of the voxel size – Greg Jan 07 '16 at 17:15

0 Answers0