Missing triangles when rendering with BVH

Question

I'm writing a software ray-tracer. I implemented a BVH structure (octree, actually) and traverse algorithm, but when I use it I get missing triangles. These are the facts that I have:

• Rendering without the BVH (naively iterating over all triangles) renders correctly
• Replacing AABB test with return true renders correctly
• Making bounding volumes ~5 times larger than they need to be renders correctly
• Otherwise, rendering with BVH of any depth renders with missing triangles, more missing triangles the deeper the BVH
• Replacing below AABB test with an actual geometry test (testing against actual triangle bounding boxes) also render missing triangles

This is the AABB test that I'm using: (derived from here: https://tavianator.com/2011/ray_box.html)

private static bool RayBoxIntersects(in Ray ray, in BoundingVolume bvh)
{

    // return true // if I uncomment this, renders correctly
    float tx1 = (bvh.MinimumCoordinates.X - ray.Origin.X) * ray.Inverse.X;
    float tx2 = (bvh.MaximumCoordinates.X - ray.Origin.X) * ray.Inverse.X;

    float tmin = MathF.Min(tx1, tx2);
    float tmax = MathF.Max(tx1, tx2);

    float ty1 = (bvh.MinimumCoordinates.Y - ray.Origin.Y) * ray.Inverse.Y;
    float ty2 = (bvh.MaximumCoordinates.Y - ray.Origin.Y) * ray.Inverse.Y;

    tmin = MathF.Max(tmin, MathF.Min(ty1, ty2));
    tmax = MathF.Min(tmax, MathF.Max(ty1, ty2));

    float tz1 = (bvh.MinimumCoordinates.Z - ray.Origin.Z) * ray.Inverse.Z;
    float tz2 = (bvh.MaximumCoordinates.Z - ray.Origin.Z) * ray.Inverse.Z;

    tmin = MathF.Max(tmin, MathF.Min(tz1, tz2));
    tmax = MathF.Min(tmax, MathF.Max(tz1, tz2));

    return (tmax >= MathF.Max(0f, tmin) && tmin < float.PositiveInfinity) || tmin == float.NaN || tmax == float.NaN;
}

Ray.Inverse is defined as new Vector3(1f / direction.X, 1f / direction.Y, 1f / direction.Z)

What could I be doing wrong?

Answer 1

I think any answer to this needs to start with the following immortal quote

Floating point numbers are like piles of sand;
every time you move them around,
you lose a little sand and pick up a little dirt.

Kernighan and Plauger

Basically, floating-point numbers are just approximations to $\mathbb{R}$ - they aren't infinitely precise. If you do a multiply or divide, C = A op B, then C will have an additional relative error of about 1 part in $2^{24}$, AKA 1/2 a ULP

If you do addition or subtraction, then although the amount of additional absolute error can be bounded, the amount of additional relative error than can be enormous (see Catastrophic cancellation )

Now that I've possibly terrified you, it's not that bad.

What you need to do is allow for the small amount of error that will occur in your RAY-AABB and RAY-triangle testing by making your AABB tests a bit more conservative. You mention making them 5x larger - but that's complete overkill. Having you code "round down" a little on the "min" bounds intersection (maybe by a one part in a million or so) and the round up on the "max" may help.

Also, when you do your reciprocal, note that the answer is very likely to be too large or too small - you could perhaps use "nextafterf()" to choose the values either side of your result to make the AABB more conservative.