我正在用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的交叉点的正确方法是什么？
最佳答案
好的，问题在于树的结构本身。我将叶子更改为具有两个元素，并将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
}
然后我遍历叶子以找到三角形的交点。我不知道这是否是最佳方法，但是它可以显着加快渲染过程，所以我认为这已经足够了。
关于go - 如何在二叉树中所有节点的先前父级都符合条件的二叉树中搜索(可能有多个)节点？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/60078951/