How to search for (possibly multiple) nodes in a binary tree where all node's previous parents match criteria?

Question

I'm writing a path tracer in Golang and recently I added support for triangles and OBJ files. I'm using Möller–Trumbore intersection algorithm to test for intersections, but when model has lots of triangles, rendering gets slower. The solution for this is to use BVHs, which are binary trees. After reading about BVHs, I came across using AABBs (axis-aligned bounding boxes), because these are easy to construct and easy to test for intersections. For example, let's build a two-level BVH for a model with 10 triangles. Instead of testing ray for intersection with every one of these triangles, I'm just testing for instersection with top bounding box. If it doesn't intersect, I know that it won't intersect with any triangle in the model, but if it does, I want to test for intersection on lower level. If the ray intersects with, let's say, the left bounding box, I know that my triangle is in this box and now I can iterate through triangles inside of it.

Let's say I have a model with 50 triangles and I built a BVH like this:

                            50 tris  <--- the ray intersects with this bounding box
                            |
                            |
                           / \
                          /   \
                         /     \
                        /       \
                       /         \
                 25 tris         25 tris   <--- the ray intersects with both bounding boxes
                   |                 |
                   |                 |
                  / \               / \
                 /   \             /   \
                /     \           /     \
           12 tris  13 tris   12 tris  13 tris  <--- leaves
           ^                               ^
           |                               |
the ray intersects with this bb       and this bb

Now there's a problem: ray intersected with two leaves. I tried to recursively test for BVH intersections like this:

// here's my BVH struct:

type BVH struct {
    left, right *BVH
    leaves      []Triangle
    bounds      AABB
    last        bool
}

func testBVH(tree *BVH, level int, r Ray, tMin, tMax float64) []Triangle {
    temp := []Triangle{}
    if tree == nil {
        return nil
    }
    if tree.last {
        return tree.leaves
    } else if level > 1 {
        if tree.left.bounds.hit(r, tMin, tMax) {
            temp = testBVH(tree.left, level-1, r, tMin, tMax)
        }
        if tree.right.bounds.hit(r, tMin, tMax) {
            tr := testBVH(tree.right, level-1, r, tMin, tMax)
            for i := 0; i < len(tr); i++ {
                temp = append(temp, tr[i])
            }
        }
    }
    return temp
}

, but it still doesn't work, it doesn't return all triangles inside hit bounding boxes. Here's a render of a monkey head with level 3 of BVH:

And the same model without any BVHs:

It struggles to find triangles where there's an intersection with two or more bounding boxes by the ray. I checked and BVH generation is alright, so the problem lies in binary tree search. What's the proper way of checking for intersections with BVHs?

Answer 1

Okay, so the problem was with the tree's structure itself. I changed leaves to have two elements and changed testBVH function to look like this:

func testBVH(tree *BVH, level int, r Ray, tMin, tMax float64) [][2]Leaf {
    temp := [][2]Leaf{}
    if tree == nil {
        return nil
    }
    if tree.last {
        if tree.bounds.hit(r, tMin, tMax) {
            return append(temp, tree.leaves)
        }
        return temp
    } else if level > 0 {
        if tree.left.bounds.hit(r, tMin, tMax) {
            temp = testBVH(tree.left, level-1, r, tMin, tMax)
        }
        if tree.right.bounds.hit(r, tMin, tMax) {
            tr := testBVH(tree.right, level-1, r, tMin, tMax)
            temp = append(temp, tr...)
        }
    }
    return temp
}

And then I'm iterating through leaves to find triangle intersections. I don't know if it's the most optimal way, but it speeds up the rendering process significally, so I think it's good enough.