我正在使用 vulkan 计算着色器开发路径跟踪器。我实现了一棵树代表包围体层次结构。 BVH 的想法是最大限度地减少需要执行光线相交测试的对象数量。
#1 简单的实施
我的第一个实现非常快，它遍历树到singleBVH 树的叶子。然而，射线可能相交multiple树叶。然后，此代码会导致一些三角形未渲染（尽管它们应该渲染）。
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 多叶实施
我的第二个实现考虑了多个叶子可能相交的事实。然而，这个实现是36x比实现 #1 慢
经过一番挖掘，我找到了解决方案。需要理解的重要一点是，BVH 树并不排除需要评估的可能性all leaves.
下面的实现 #3 使用命中和未命中链接。需要对这些框进行排序，以便在最坏的情况下以正确的顺序查询所有框（因此单个循环就足够了）。然而，链接用于跳过不需要评估的节点。当当前节点是叶子节点时，进行实际的三角形相交。
图片取自here。相关论文和源代码也在 Toshiya Hachisuka 教授的文章中page。相同的概念也描述于幻灯片中引用的本文.
#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教授针对此类情况提出了进一步优化在他的幻灯片中（第 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 and miss_node查找链接的索引并存储它们。