1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I'll try this, thanks. I hadn't thought of that, I guess I was focusing on the complex issues and forgetting about the fundamental stuff 😅. Though since I asked this question I discovered that I have other issues (notably with AABB-triangle intersection during bvh construction), unfortunately :'( How is writing a working octree harder than the pathtracing physics itself 😭 $\endgroup$ Commented Jan 27, 2023 at 18:25

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.