Bounding volume hierarchy,一种管理3D场景物体的方法,用于加速光线追踪。
BVH采用二叉树的结构,每个分支节点储存包围两个AABB的BVH子节点,叶节点储存包含真正的物体的AABB(对,都是AABB)
光线从上而下进入二叉树,对每个分支节点的AABB进行相交判断,如果打中了就往子节点继续求交。
那BVH究竟如何加快求交速度呢?待我用图解来说明
假设有这样一个BVH结构
其中包含了四个物体(其实是包含了物体的AABB),那么存在两个分支节点,A和B
其树状结构如图
假设有这样一根光线,穿过了A和B,但是很可惜,一个物体也没击中。
那么,该如何使用BVH判断光线是否击中物体呢?
首先,先从BVH的根节点开始,调用根节点的hit(),根节点的hit()调用其AABB的hit(),击中了,下降到子节点,调用子节点的hit(),子节点的hit()调用其AABB的hit(),击中了,那么继续下降到叶节点,调用叶节点的hit()函数。此处一个物体都没打中,叶节点的hit()的返回值为false,分支节点hit函数的返回值为子节点返回值的或关系,那么此处所有分支节点的hit()的返回值都为false
再一步步的返回根节点,那么根节点的hit()函数返回值也应该是false。
可以发现这就是个递归调用,和二叉树的遍历非常相似。
第一种情况并没有体现出AABB的优势
先别急,这只是练手的,再来看第二种情况
一根光线打中了物体a
再来一遍流程,首先调用根节点的hit,再调用子节点的hit.
但是在这里,光线并没有击中子节点B的AABB,那么此处的hit返回false,隶属于B的叶节点也就不用计算了,只需要计算A的子节点就行了!
BVH相当于帮我们完成了剪枝的动作
是不是有点理解BVH怎么工作的了?
别急,还有第三个case
光线同时打中了a和c
那么,只需要取最小的那个t值就行了,所以应该返回击中a的t值。
现在应该完全理解BVH了吧。
BVH是树状结构,其建立也是个递归过程,父节点有两个子节点,子节点又有两个子节点....直到叶节点,也就是物体为止。
BVH节点类 code:
class bvh_node : public hitable {
public:
bvh_node() {}
bvh_node(hitable_list &list) : bvh_node(list.obj_list) {}
bvh_node(std::vector<shared_ptr<object>> &aabb_list)
: bvh_node(aabb_list, 0, aabb_list.size()) {}
bvh_node(std::vector<shared_ptr<object>> &aabb_list, size_t start,
size_t end);
bool bounding_box(AABB &box_out) const override;
bool hit(const ray &r, double t_min, double t_max,
record &rec) const override;
shared_ptr<hitable> left;
shared_ptr<hitable> right;
AABB box;
};
用于std::sort的比较函数
我挺讨厌这种全局函数的污染的,所以上了个namespace
namespace BVH_CMP {
inline bool comparator(const shared_ptr<hitable> &a,
const shared_ptr<hitable> &b, int axis) {
AABB box_a;
AABB box_b;
if (!a->bounding_box(box_a) || !b->bounding_box(box_b))
std::cerr << "Error : No bounding box in bvh node.\n";
return box_a.min()[axis] < box_b.min()[axis];
}
inline bool x_compare(const shared_ptr<hitable> &a,
const shared_ptr<hitable> &b) {
return comparator(a, b, 0);
}
inline bool y_compare(const shared_ptr<hitable> &a,
const shared_ptr<hitable> &b) {
return comparator(a, b, 1);
}
inline bool z_compare(const shared_ptr<hitable> &a,
const shared_ptr<hitable> &b) {
return comparator(a, b, 2);
}
}; // namespace BVH_CMP
然后是BVH的递归建立
每次产生一个随机数,来决定通过哪条坐标轴来对物体列表进行排序
递归的结束条件是物体的区间大小为2,或者区间为1,也就是下降到了叶节点的时候。
这时候再次进行比较,把AABB放入叶节点即可。
对于只有一个物体的情况,因为不想做空指针判断(?),所以整了两个相同的节点。
最后,该节点的AABB大小,也就是两个子节点AABB相加起来。
我知道你可能会疑惑,“诶为什么在每次创建时复制一遍aabb_list”
好吧我也不知道,书中作者给了注释,我把它贴在下面
// Create a modifiable array of the source scene objects
inline bvh_node::bvh_node(std::vector<shared_ptr<object>> &aabb_list,
size_t start, size_t end) {
auto objs = aabb_list;
int axis = rand_i(0, 2);
using namespace BVH_CMP;
auto comparator = axis == 0 ? x_compare : axis == 1 ? y_compare : z_compare;
size_t mInterval = end - start;
//set up AABB recursively
if (mInterval == 1) {
left = objs[start];
right = objs[start];
} else if (mInterval == 2) {
if (comparator(objs[start], objs[start + 1])) {
left = objs[start];
right = objs[start + 1];
} else {
left = objs[start + 1];
right = objs[start];
}
} else {
std::sort(objs.begin() + start, objs.begin() + end, comparator);
int mid = start + mInterval / 2;
left = std::make_shared<bvh_node>(bvh_node(objs, start, mid));
right = std::make_shared<bvh_node>(bvh_node(objs, mid, end));
}
AABB box_left, box_right;
if (!left->bounding_box(box_left) || !right->bounding_box(box_right)) {
std::cerr << "Error : No bounding box in bvh node.\n";
}
box = AABB::surrounding_box(box_left, box_right);
}
AABB::surrounding_box的定义再AABB的类中,用这个函数求出两个AABB相加的大小。
class AABB(){
public:
.....
static AABB surrounding_box(AABB &box_1, AABB &box_2);
};
inline AABB AABB::surrounding_box(AABB &box_1, AABB &box_2) {
vec3 small(fmin(box_1.min().x(), box_2.min().x()),
fmin(box_1.min().y(), box_2.min().y()),
fmin(box_1.min().z(), box_2.min().z()));
vec3 big(fmax(box_1.max().x(), box_2.max().x()),
fmax(box_1.max().y(), box_2.max().y()),
fmax(box_1.max().z(), box_2.max().z()));
return AABB(small,big);
}
击中判断和剩下的函数
inline bool bvh_node::hit(const ray &r, double t_min, double t_max,
record &rec) const {
if (!box.hit(r, t_min, t_max, rec))
return false;
bool hit_left = left->hit(r, t_min, t_max, rec);
// if hit left then changing t_max to t to get the closest t.
bool hit_right = right->hit(r, t_min, hit_left ? rec.t : t_max, rec);
return hit_left || hit_right;
}
inline bool bvh_node::bounding_box(AABB &box_out) const {
box_out = box;
return true;
};