如何计算 BVH 树中的缺失链接？

Question

我正在为多边形模型创建一个基于 OpenGl 的光线追踪器。为了加速我正在使用的应用程序 BVH-trees。因为在 GLSL 中没有递归，我决定找到另一种方法来遍历边界框，将其作为着色器存储缓冲区发送到片段着色器。

我想实现那种方式：

其实我不太明白在构建树的过程中如何计算命中链接和未命中链接。命中和未命中链接帮助程序在遍历过程中导航到下一个节点（边界框），无论是否相交。

到现在我已经创建了构造树的方法，也可以将树放入一个简单的数组中。我有 depth-first 实现将树展平到数组中。

这里是depth-first，树扁平化的方法：

FlatBvhNode nodeConverter2(BvhNode node, int& ind){
    FlatBvhNode result = FlatBvhNode(node.bBox.min, node.bBox.max, ind, node.isLeaf,                            
    node.indices);
    return result;
}

void flattenRecursion(const BvhNode &bvhNode, vector<FlatBvhNode>& nodes, int& ind) {
    ++ind;
    nodes.push_back(nodeConverter2(bvhNode, ind));

    if (!bvhNode.isLeaf) {
        flattenRecursion(*bvhNode.children.at(0), nodes, ind);
        flattenRecursion(*bvhNode.children.at(1), nodes,ind);
    }
}

vector<FlatBvhNode>* flatten(const BvhNode& root) {
    vector<FlatBvhNode>* nodesArray=new vector<FlatBvhNode>;
    nodesArray->reserve(root.countNodes());

    int ind=0;
    flattenRecursion(root, *nodesArray, ind);

    return nodesArray;
}

我必须计算以下 "links" :

图片来自：source。该图显示了不同的链接。因此，例如射线与边界框（命中链接）相交，我们可以移动到数组中的下一个节点。这没关系，因为我有 depth-first 遍历。当我不得不移动到兄弟姐妹甚至 parent 的兄弟姐妹时，问题就来了。我怎样才能实现这些链接/偏移量？我知道我应该创建和索引但是如何使用 depth-first 树构造来做到这一点。

感谢任何帮助。

Answer 1

我没有关于深度优先树的答案，但如果你的树是堆，我已经想出了一个方法来做到这一点。所以这是我使用的 GLSL 中的一些代码

int left(in int index) { // left child
    return 2 * index + 1;
}

int right(in int index) { // right child
    return 2 * index + 2;
}

int parent(in int index) {
    return (index - 1) / 2;
}

int right_sibling(in int index) { // a leaf hit or a miss link
    int result = index;
    while(result % 2 == 0 && result != 0) {
        result = parent(result);
    }
    return result + 1 * int(result != 0);
}

我正在使用它，它的运行速度非常合理。我唯一的问题是那个循环，它会降低性能。我真的很想在那个函数中有一个常量复杂度表达式。

如何计算 BVH 树中的缺失链接？

How to calculate the miss links in a BVH tree?

c++

glsl

binary-tree

aabb

bounding-volume