go - 如何在二叉树中所有节点的先前父级都符合条件的二叉树中搜索(可能有多个)节点？

Question

我正在用Golang写一个路径跟踪器，最近我增加了对三角形和OBJ文件的支持。我正在使用Möller-Trumbore相交算法来测试相交，但是当模型中有很多三角形时，渲染会变慢。解决方案是使用BVH，它们是二叉树。在阅读了有关BVH的内容之后，我遇到了使用AABB(轴对齐的边界框)的问题，因为它们易于构造且易于测试相交。例如，让我们为具有10个三角形的模型构建两级BVH。与其测试ray是否与这些三角形中的每个三角形相交，不如测试带有顶部边界框的instersection。如果不相交，我知道它不会与模型中的任何三角形相交，但是如果确实相交，我想在较低级别测试相交。假设射线与左边界框相交，我知道我的三角形在此框内，现在我可以遍历其中的三角形。

假设我有一个包含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
}

，但仍然无法使用，它不会返回点击边界框内的所有三角形。这是3级BVH的猴子头的渲染:



而没有任何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
}

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