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

我正在使用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慢36倍(好吧，我错过了＃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树查询的标准方法？

最佳答案

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

下面的实现＃3使用点击和未命中链接。需要对框进行排序，以便在最坏的情况下以正确的顺序查询所有框(因此，一个循环就足够了)。但是，链接用于跳过不需要评估的节点。当当前节点是叶节点时，将执行实际的三角形相交。

命中链接〜命中时跳至哪个节点(下面的绿色)

错过链接〜发生错过时跳至哪个节点(以下红色)

图片来自here。相关的论文和源代码也在Hoshisuka教授的page上。 this paper referenced in the slides中也描述了相同的概念。

＃3具有命中和小姐链接的BVH树

我必须扩展通过链接推送到着色器的数据。另外，还需要一些离线摆弄才能正确存储树。最初，我尝试使用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树后，查找链接非常简单(以下一些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查找链接的索引并进行存储。