遍历着色器中的边界体积层次结构

Question

我正在使用 vulkan 计算着色器开发路径跟踪器。我实现了一棵代表 bounding volume hierachy 的树。 BVH 的想法是尽量减少需要执行光线相交测试的对象数量。

#1 天真的实现

我的第一个实现非常快，它将树向下遍历到 BVH 树的单个叶子。但是，射线可能会与多个叶相交。然后这段代码导致一些三角形没有被渲染（尽管它们应该被渲染）。

int box_index = -1;

for (int i = 0; i < boxes_count; i++) {
    // the first box has no parent, boxes[0].parent is set to -1
    if (boxes[i].parent == box_index) {
        if (intersect_box(boxes[i], ray)) {
            box_index = i;
        }
    }
}

if (box_index > -1) {
    uint a = boxes[box_index].ids_offset;
    uint b = a + boxes[box_index].ids_count;

    for (uint j = a; j < b; j++) {
        uint triangle_id = triangle_references[j];
        // triangle intersection code ...
    }
}

#2 多叶实现

我的第二个实现说明了多个叶子可能相交的事实。然而，这个实现比实现#1慢36x（好吧，我错过了#1 中的一些交叉测试，但仍然......）。

bool[boxes.length()] hits; hits[0] = intersect_box(boxes[0], ray); for (int i = 1; i < boxes_count; i++) { if (hits[boxes[i].parent]) { hits[i] = intersect_box(boxes[i], ray); } else { hits[i] = false; } } for (int i = 0; i < boxes_count; i++) { if (!hits[i]) { continue; } // only leaves have ids_offset and ids_count defined (not set to -1) if (boxes[i].ids_offset < 0) { continue; } uint a = boxes[i].ids_offset; uint b = a + boxes[i].ids_count; for (uint j = a; j < b; j++) { uint triangle_id = triangle_references[j]; // triangle intersection code ... } }

这种性能差异让我抓狂。似乎只有像 if(dynamically_modified_array[some_index]) 这样的单个语句会对性能产生巨大影响。我怀疑 SPIR-V 或 GPU 编译器不再能够发挥其优化魔力？所以这是我的问题：

这真的是优化问题吗？

如果是，我可以将实现 #2 转换为更好的可优化性吗？我可以以某种方式提供优化提示吗？

是否有在着色器中实现 BVH 树查询的标准方法？

Answer 1

经过一番挖掘，我找到了解决方案。重要的是要理解 BVH 树不排除需要评估 all 叶子的可能性。

下面的实施 #3，使用命中和未命中 links。这些盒子需要以一种方式排序，在最坏的情况下，所有盒子都以正确的顺序被查询（所以一个循环就足够了）。但是，links 用于跳过不需要评估的节点。当当前节点为叶子节点时，进行实际的三角形求交

命中link~命中时跳转到哪个节点（下图绿色）
miss link ~ miss 时跳转到哪个节点（下图红色）

图片取自here. The associated paper and source code is also on Prof. Toshiya Hachisuka's page. The same concept is also described in this paper referenced in the slides。

#3 具有命中和未命中链接的 BVH 树

我不得不扩展使用 link 推送到着色器的数据。还需要一些离线操作才能正确存储树。起初我尝试使用 while 循环（循环直到 box_index_next 为 -1），这再次导致了疯狂的减速。无论如何，以下工作相当快：

int box_index_next = 0;

for (int box_index = 0; box_index < boxes_count; box_index++) {
    if (box_index != box_index_next) {
        continue;
    }

    bool hit = intersect_box(boxes[box_index], ray);
    bool leaf = boxes[box_index].ids_count > 0;

    if (hit) {
        box_index_next = boxes[box_index].links.x; // hit link
    } else {
        box_index_next = boxes[box_index].links.y; // miss link
    }

    if (hit && leaf) {
        uint a = boxes[box_index].ids_offset;
        uint b = a + boxes[box_index].ids_count;

        for (uint j = a; j < b; j++) {
            uint triangle_id = triangle_references[j];
            // triangle intersection code ...
        }
    }
}

此代码比快速但有缺陷的实施 #1 慢大约 3 倍。这有点意料之中，现在速度取决于实际的树，而不是 gpu 优化。例如，考虑三角形沿轴对齐的退化情况：同一方向的射线可能与所有三角形相交，然后需要评估所有树叶。

教授。 Toshiya Hachisuka 提出了针对此类情况的进一步优化 in his sildes（第 36 页及以后）：一个存储 BVH 树的多个版本，沿 x、-x、y、-y、z 和 -z 在空间上排序。对于遍历，需要根据射线选择正确的版本。然后，一旦叶子的三角形相交，就可以停止遍历，因为要访问的所有剩余节点将在空间上位于该节点后面（从射线的角度来看）。

一旦构建了 BVH 树，找到 links 就非常简单了（下面的一些 python 代码）：

class NodeAABB(object):

    def __init__(self, obj_bounds, obj_ids):
        self.children = [None, None]
        self.obj_bounds = obj_bounds
        self.obj_ids = obj_ids

    def split(self):
        # split recursively and create children here
        raise NotImplementedError()

    def is_leaf(self):
        return set(self.children) == {None}

    def build_links(self, next_right_node=None):
        if not self.is_leaf():
            child1, child2 = self.children

            self.hit_node = child1
            self.miss_node = next_right_node

            child1.build_links(next_right_node=child2)
            child2.build_links(next_right_node=next_right_node)

        else:
            self.hit_node = next_right_node
            self.miss_node = self.hit_node

    def collect(self):
        # retrieve in depth first fashion for correct order
        yield self
        if not self.is_leaf():
            child1, child2 = self.children
            yield from child1.collect()
            yield from child2.collect()

将所有 AABB 存储在一个数组中（将发送到 GPU）后，您可以使用 hit_node 和 miss_node 来查找 link 和也存储它们。

遍历着色器中的边界体积层次结构

Traversal of Bounding Volume Hierachy in Shaders

glsl

compiler-optimization

vulkan

raytracing

bounding-box