如何在二叉树中搜索（可能是多个）节点，其中所有节点的先前父节点都符合条件？

Question

我正在用 Golang 编写路径跟踪器，最近我添加了对三角形和 OBJ 文件的支持。我正在使用 Möller–Trumbore 交叉算法来测试交叉点，但是当模型有很多三角形时，渲染会变慢。解决方案是使用 BVH，它们是二叉树。在阅读 BVH 之后，我发现使用 AABB（轴对齐边界框），因为它们易于构建且易于测试交叉点。例如，让我们为具有 10 个三角形的模型构建一个两级 BVH。我没有测试射线与这些三角形中的每一个的相交，而是测试与顶部边界框的相交。如果它不相交，我知道它不会与模型中的任何三角形相交，但如果相交，我想测试较低级别的相交。如果光线与左侧边界框相交，我知道我的三角形在这个框中，现在我可以遍历其中的三角形。

假设我有一个包含 50 个三角形的模型，并且我构建了这样一个 BVH：

                            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

现在有一个问题：光线与两片叶子相交。我尝试像这样递归测试 BVH 交叉点：

// 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
}

，但它仍然不起作用，它不会 return 命中边界框内的所有三角形。这是 BVH 级别 3 的猴头渲染图：

没有任何 BVH 的同一型号：

很难通过射线找到与两个或多个边界框相交的三角形。我查了一下，BVH生成没问题，所以问题出在二叉树搜索上。检查与 BVH 相交的正确方法是什么？

Answer 1

好的，问题出在树的结构本身。我将叶子更改为具有两个元素并将 testBVH 函数更改为如下所示：

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
}

然后我遍历树叶以找到三角形交点。我不知道这是否是最佳方式，但它显着加快了渲染过程，所以我认为它已经足够了。

如何在二叉树中搜索（可能是多个）节点，其中所有节点的先前父节点都符合条件？

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

geometry

binary-tree

raytracing

bounding-box

go