构造BVH加速结构

构造BVH加速结构

BVH概念

Bounding volume hierarchy,一种管理3D场景物体的方法,用于加速光线追踪。
BVH采用二叉树的结构,每个分支节点储存包围两个AABB的BVH子节点,叶节点储存包含真正的物体的AABB(对,都是AABB)
光线从上而下进入二叉树,对每个分支节点的AABB进行相交判断,如果打中了就往子节点继续求交。

那BVH究竟如何加快求交速度呢?待我用图解来说明
假设有这样一个BVH结构

其中包含了四个物体(其实是包含了物体的AABB),那么存在两个分支节点,A和B
其树状结构如图

case1:

假设有这样一根光线,穿过了A和B,但是很可惜,一个物体也没击中。

那么,该如何使用BVH判断光线是否击中物体呢?
首先,先从BVH的根节点开始,调用根节点的hit(),根节点的hit()调用其AABB的hit(),击中了,下降到子节点,调用子节点的hit(),子节点的hit()调用其AABB的hit(),击中了,那么继续下降到叶节点,调用叶节点的hit()函数。此处一个物体都没打中,叶节点的hit()的返回值为false,分支节点hit函数的返回值为子节点返回值的或关系,那么此处所有分支节点的hit()的返回值都为false
再一步步的返回根节点,那么根节点的hit()函数返回值也应该是false。
可以发现这就是个递归调用,和二叉树的遍历非常相似。


第一种情况并没有体现出AABB的优势
先别急,这只是练手的,再来看第二种情况

case2:

一根光线打中了物体a


再来一遍流程,首先调用根节点的hit,再调用子节点的hit.
但是在这里,光线并没有击中子节点B的AABB,那么此处的hit返回false,隶属于B的叶节点也就不用计算了,只需要计算A的子节点就行了!

BVH相当于帮我们完成了剪枝的动作


是不是有点理解BVH怎么工作的了?
别急,还有第三个case

case3:

光线同时打中了a和c

那么,只需要取最小的那个t值就行了,所以应该返回击中a的t值。

现在应该完全理解BVH了吧。

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

留言