<p>I think any answer to this needs to start with the following immortal quote</p>
<blockquote>
<p><em>Floating point numbers are like piles of sand;<br>
every time you move them around,<br>
you lose a little sand and pick up a little dirt.</em> <br><br>
<a href="https://en.wikipedia.org/wiki/P._J._Plauger" rel="nofollow noreferrer">Kernighan</a> and Plauger</p>
</blockquote>
<p>Basically, floating-point numbers are just approximations to <span class="math-container">$\mathbb{R}$</span> - they aren't infinitely precise. If you do a multiply or divide, C = A op B, then C will have an <em>additional</em> <em>relative</em> error of <em>about</em> 1 part in <span class="math-container">$2^{24}$</span>, AKA 1/2 a <a href="https://en.wikipedia.org/wiki/Unit_in_the_last_place" rel="nofollow noreferrer">ULP</a></p>
<p>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 <a href="https://en.wikipedia.org/wiki/Catastrophic_cancellation" rel="nofollow noreferrer">Catastrophic cancellation</a> )</p>
<p>Now that I've possibly terrified you, it's not that bad.</p>
<p>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 &quot;round down&quot; a little on the &quot;min&quot; bounds intersection (maybe by a one part in a million or so) and the round up on the &quot;max&quot; may help.</p>
<p>Also, when you do your reciprocal, note that the answer is very likely to be too large or too small - you could perhaps use &quot;nextafterf()&quot; to choose the values either side of your result to make the AABB more conservative.</p>

CC BY-SA 4.0
2023-01-27T18:25:58.500Z
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 
andre_ss6
CC BY-SA 4.0
2023-01-27T09:27:11.460Z
2023-01-27T10:18:13.523Z
2023-01-27T10:18:13.523Z
Simon F
<p>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:</p>
<ul>
<li>Rendering without the BVH (naively iterating over all triangles) renders correctly</li>
<li>Replacing AABB test with <code>return true</code> renders correctly</li>
<li>Making bounding volumes ~5 times larger than they need to be renders correctly</li>
<li>Otherwise, rendering with BVH of any depth renders with missing triangles, more missing triangles the deeper the BVH</li>
<li>Replacing below AABB test with an actual geometry test (testing against actual triangle bounding boxes) also render missing triangles</li>
</ul>
<p>This is the AABB test that I'm using: (derived from here: <a href="https://tavianator.com/2011/ray_box.html" rel="nofollow noreferrer">https://tavianator.com/2011/ray_box.html</a>)</p>
<pre class="lang-cs prettyprint-override"><code>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 &gt;= MathF.Max(0f, tmin) &amp;&amp; tmin &lt; float.PositiveInfinity) || tmin == float.NaN || tmax == float.NaN;
}

</code></pre>
<p><code>Ray.Inverse</code> is defined as <code>new Vector3(1f / direction.X, 1f / direction.Y, 1f / direction.Z)</code></p>
<p>What could I be doing wrong?</p>

<raytracing>
Missing triangles when rendering with BVH
andre_ss6
# Missing triangles when rendering with BVH

(Asked by: username_0 on 2023-01-18)

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>)

```cs
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?

**Tags:** raytracing


---

## 1 answers

### Answer by username_1 on 2023-01-27. Score: 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](https://en.wikipedia.org/wiki/P._J._Plauger) 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](https://en.wikipedia.org/wiki/Unit_in_the_last_place)

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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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   

---

