在二叉树中查找满足特定条件的节点，并验证其所有先前节点是否满足条件

在Golang实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《在二叉树中查找满足特定条件的节点，并验证其所有先前节点是否满足条件》，聊聊，希望可以帮助到正在努力赚钱的你。

我正在用 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
}

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

没有任何 bvh 的同一型号：

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

解决方案

好吧，问题出在树的结构本身。我将 leaves 更改为具有两个元素，并将 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
}

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

今天带大家了解了的相关知识，希望对你有所帮助；关于Golang的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~