Cutting it Too Close

I recently ran into a pretty heart-sinking problem:

Indeed, that's NOT the kind of thing one wants to see 5 weeks before the competition.  Especially when I've been working super hard on this tracer for over a month.  Surprisingly, I had not seen anything like this from my KD trees before, as they always seemed to work nicely.  But this is obviously an acceleration structure problem; there's simply no other explanation for those results.

Thankfully, it only took me about 4 hours to solve this one (it could have been way worse...).  It comes down to a pretty tricky case:  if a cell contains triangles that are perfectly-aligned with one of the cardinal planes (in this case, the sides of the ship are axis-aligned), then the KD tree may try to split space "too" finely.  If you think about a triangle that's planar with the xy, xz, or yz plane, it makes sense that, in theory, such a triangle could be contained in an AABB of zero volume.  This would no doubt cause precision problems with the ray-AABB intersection test.  Well, I was limiting my KD tree to a depth of 30, and allowing it 50 splitting plane choices with 3 recursive refinements (each of which also considered 50 splitting planes).  In short, this means that my KD tree builder is absurdly precise...to the point that it actually will cut space "too" closely for floating-point precision to handle.  If we start cutting space to the point of having bounding boxes with side lengths of 1e-5, floats start to cry in agony, and everything breaks down.

It took a good amount of thought to understand that - but now it makes sense.  Bottom line: don't cut it too close!  When considering a split, make sure that you don't slice a bounding box along a side that is already dangerously short.  I've set this "dangerously short" threshold to 5e-5, which seems to be about as small of a side as I can split before precision becomes a problem.  In theory, I probably should have checked the lengths of the resultant split sides rather than the length of the side before splitting...maybe I'll change it to that later.

Whew, that was a close call :)