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