0

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

我想实现这种方式：在着色器中遍历 BVH 树

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

到目前为止，我创建了构造树的方法，并且我还可以将树放入一个简单的数组中。我有深度优先实现将树展平到数组中。

以下是深度优先的树展平方法：

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

我必须计算以下“链接”：

图片来自：来源。该图显示了不同的链接。因此，例如光线与边界框（命中链接）相交，我们可以移动到数组中的下一个节点。这没关系，因为我有深度优先遍历。当我必须搬到兄弟姐妹甚至父母的兄弟姐妹时，问题就来了。如何实现这些链接/偏移？我知道我应该创建和索引，但是如何通过深度优先树构造来做到这一点。

任何帮助表示赞赏。

4

1 回答 1

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);
}

我正在使用它，它以相当合理的速度工作。我唯一的问题是那个循环，它会降低性能。我真的很想在那个函数中有一个恒定的复杂性表达式。

于 2021-01-28T20:14:32.640 回答