物体列表的AABB

上一章中基本讲完了各个类的aabb写法，还剩最后一个，物体列表类的aabb生成，下面给出：

  1. ...
  2. #include "aabb.h"
  3. ...
  5. class hittable_list : public hittable {
  6.     public:
  7.         ...
  8.         virtual bool hit(
  9.             const ray& r, double t_min, double t_max, hit_record& rec) const override;
  11.         //包围盒生成函数
  12.         virtual bool bounding_box(
  13.             double time0, double time1, aabb& output_box) const override;
  14.     ...
  15. };
  17. ...
  18. bool hittable_list::bounding_box(double time0, double time1, aabb& output_box) const {
  19.     //如果物体列表为空，我们无法为空物体生成包围盒，直接返回false。
  20.     if (objects.empty()) return false;
  22.     aabb temp_box;
  23.     //设定一个flag用来初始化一个包围盒。
  24.     bool first_box = true;
  25.     //遍历列表内物体。
  26.     for (const auto& object : objects) {
  27.         //如果遍历刀列表内有物体无法建立包围盒（返回fasle），那对不起，物体列表也无能为力了，直接返回。
  28.         //注意，这个if中的bounding_box函数把这个子物体的包围盒赋给了temp_box。
  29.         if (!object->bounding_box(time0, time1, temp_box)) return false;
  30.         //如果是第一次建立包围盒，那直接使用temp_box。
  31.         //否则要求本循环子物体的aabb和之前包围盒的包围盒，使用surrounding_box函数。
  32.         output_box = first_box ? temp_box : surrounding_box(output_box, temp_box);
  33.         //在首次建立包围盒成功之后，把first_box置false。
  34.         first_box = false;
  35.     }
  37.     return true;
  38. }
  1. 物体列表的aabb的求法就是逐个子物体遍历，求它们这些物体共同的包围盒。其中使用到了上一章中提到的计算两个包围盒的包围盒的函数surrounding_box。<br />自此，我们已有的物体类：球类、移动的球类和物体列表类都接入了生成包围盒的函数。

BVH类

是时候把这一切组织起来了，记得上一章中提到的对象划分已经对象划分下的树状结构吗？我们还没有给它起名字呢：我们将创建一个树状结构，树的每一个节点都是一个包围盒或者一个物体，包围盒一层层的嵌套，物体作为叶子节点被一层一层的包裹着，这种结构叫层次包围盒（Bounding Volume Hierarchies），或称BVH。
BVH既然是一棵树，我们首先得创建它的节点，和其他所有树结构一样，它的节点得储存孩子信息。如果我们把事情再想得简单一点，每个大包围盒内部包着两个子包围盒，那BVH结构就变成了一个二叉树，看代码：

  1. #ifndef BVH_H
  2. #define BVH_H
  4. #include "rtweekend.h"
  6. #include "hittable.h"
  7. #include "hittable_list.h"
  9. //这个节点类是物体类的子类，我们还是得依靠多态的便利性。
  10. class bvh_node : public hittable {
  11.     public:
  12.         bvh_node();
  13.         //这是传入物体列表的构造，直接调用下面的有vector的构造。
  14.         bvh_node(const hittable_list& list, double time0, double time1)
  15.             : bvh_node(list.objects, 0, list.objects.size(), time0, time1)
  16.         {}
  17.         //这个构造函数非常复杂，之后再说。
  18.         bvh_node(
  19.             const std::vector<shared_ptr<hittable>>& src_objects,
  20.             size_t start, size_t end, double time0, double time1);
  22.         //override hit函数。
  23.         virtual bool hit(
  24.             const ray& r, double t_min, double t_max, hit_record& rec) const override;
  26.         //生成包围盒的函数
  27.         virtual bool bounding_box(double time0, double time1, aabb& output_box) const override;
  29.     public:
  30.         //本节点的左右子节点指针，它们都是物体类型的指针。
  31.         shared_ptr<hittable> left;
  32.         shared_ptr<hittable> right;
  33.         //本节点的包围盒，会在构造函数里生成。
  34.         aabb box;
  35. };
  37. //注意，bvh节点类的包围盒我们会在构造函数里生成，这里直接赋值即可。
  38. bool bvh_node::bounding_box(double time0, double time1, aabb& output_box) const {
  39.     output_box = box;
  40.     return true;
  41. }
  43. #endif
  1. 来看一下hit函数，在这里你会看到包围盒是如何减少计算的——你连我的盒子都碰不到，那我们就没有继续看下去的必要了。
  1. bool bvh_node::hit(const ray& r, double t_min, double t_max, hit_record& rec) const {
  2.     //你连我的盒子都碰不到，那我们就没有继续看下去的必要了。
  3.     if (!box.hit(r, t_min, t_max))
  4.         return false;
  6.     //继续遍历左右物体。
  7.     bool hit_left = left->hit(r, t_min, t_max, rec);
  9.     //见下方讲解。
  10.     bool hit_right = right->hit(r, t_min, hit_left ? rec.t : t_max, rec);
  12.     //遍历过程中只要不是所有的子物体都没碰到，就算产生了碰撞。
  13.     return hit_left || hit_right;
  14. }
  1. 注意上面的代码中有一个剪枝操作，在第十行中，遍历右子树节点的时候先检查了左子树返回值是否为true，即光线有无和左子树碰撞，如果有，那么在判断右子树的时候就又有一个参照物了：“右子树上的物体是否是先被光线碰到的？或者它被左子树上的物体遮挡了？改变t的范围，只在右子树物体离光源更近的情况下，才认可这次碰撞，其他的直接剪掉。”<br />我们现在来理一下思路，我们写这样的hit函数会发生什么，假设一个bvh在场景中构造完毕（虽然我们暂时没有给出用来构造bvh的构造函数），即，现在main函数中那个world物体不再是一个物体列表，换做是一个已经构建好的bvh，现在有一根光线自相机或者某处发射过来：<br />既然有光线，我们就得调用场景中所有物体的hit，现在只有一个物体那就是bvh，我们只需要调用它的hit即可。如果这根光线没有碰到最外层的盒子，那上述代码中的第四行`return false`就是整个碰撞检测的最后一句代码，在这之前我们只调用了一个aabb的hit函数，无论场景中有多少物体，也只需要调用这一个函数即可。再想想如果我们没有bvh，而是使用物体列表来管理场景中的物体，那我们会做哪些工作——如果t的范围不考虑进去的话，即便这根光线没有碰到任何一个物体，我们也需要调用每个物体的hit函数，其中就包括一些球，每个球意味着要求一次一元二次方程的求根公式。<br />要知道，场景是无限大的，物体只占了场景中微不足道的某个角落，我们创建的大部分光线实际上都是没有和物体发生碰撞的光线，光考虑这部分光线，bvh就比传统的物体列表要快上几个数量级了。

构造BVH

到此为止，核心问题还没有解决，如何构造一棵bvh树呢？
先来讲一讲上一课的遗留问题，对象划分的依据是什么？首先，必须要明确一个概念：我们现在不需要任何规律的把bvh里的所有物体粗暴的分成两堆，代码也能很好的工作，即便包围盒内部的包围盒比外面的盒子还要大，也不影响代码的运行，充其量只是慢了一点。我们要找的对象划分的依据，是能让程序运行更快，更发挥bvh优势的一种划分方式，它可以是这样一个划分：
先随便找一个轴，x、y或者z轴，把物体列表里的物体按照这个轴从小到大的顺序进行排序并划分成两堆，对于左右子树，用这两堆分别再次进行递归。

  1. #include <algorithm>
  2. ...
  4. bvh_node::bvh_node(
  5.     const std::vector<shared_ptr<hittable>>& src_objects,
  6.     size_t start, size_t end, double time0, double time1
  7. ) {
  8.     //创建一个指针指向形参中的物体列表，增加代码可读性。
  9.     auto objects = src_objects; 
  10.     //随机一个int值，0，1，2分别代表x，y，z轴，这个函数之后会给出。
  11.     int axis = random_int(0,2);
  12.     //通过选定的是哪个坐标轴选到特定的比较器，注意，这个comparator是一个函数指针
  13.     //之后会给出box_x_compare等三个函数的签名即具体函数体。
  14.     auto comparator = (axis == 0) ? box_x_compare
  15.                     : (axis == 1) ? box_y_compare
  16.                                   : box_z_compare;
  17.     //本列表中有多少物体？
  18.     size_t object_span = end - start;
  19.     //如果发现这个列表中只有一个物体了，那令本节点的左右孩子指针都指向这个物体。
  20.     if (object_span == 1) {
  21.         left = right = objects[start];
  22.     }
  23.     //如果有俩物体，按照给定轴信息，看看谁在左，谁在右。
  24.     else if (object_span == 2) {
  25.         if (comparator(objects[start], objects[start+1])) {
  26.             left = objects[start];
  27.             right = objects[start+1];
  28.         } else {
  29.             left = objects[start+1];
  30.             right = objects[start];
  31.         }
  32.     }
  33.     //如果本段物体列表有超过两个物体，直接对其进行排序，并且二分之后，开启下一轮递归。
  34.     else {
  35.         std::sort(objects.begin() + start, objects.begin() + end, comparator);
  36.         //二分找中值。
  37.         auto mid = start + object_span/2;
  38.         left = make_shared<bvh_node>(objects, start, mid, time0, time1);
  39.         right = make_shared<bvh_node>(objects, mid, end, time0, time1);
  40.     }
  42.     //注意，代码运行到这里，说明本节点的左右孩子递归代码都已经执行完毕。是时候给他们套上包围盒了。
  43.     aabb box_left, box_right;
  44.     //给左右节点分别套盒子，并且利用返回信息来判断盒子是否成功生成。
  45.     if (  !left->bounding_box (time0, time1, box_left)
  46.        || !right->bounding_box(time0, time1, box_right)
  47.     )
  48.         //进入这个if表示左右孩子的某个盒子没有生成成功。
  49.         std::cerr << "No bounding box in bvh_node constructor.\n";
  50.     //注意，这里有一个bug，如果bouding_box返回false,其box一定是没有被赋值的，即为空。
  51.     //空box调用下面的surrounding_box函数是会出错的，因为访问了空物体。
  52.     //我们暂时没有无法生成包围盒的物体，如：无限大的平面。所以这个问题我们先不要管。
  53.     box = surrounding_box(box_left, box_right);
  54. }

随机范围内的int值的函数如下所示，工具函数都写到rtweekend.h里：

inline int random_int(int min, int max) {
    // 返回[min,max]范围内int值。
    return static_cast<int>(random_double(min, max+1));
}

最后，我们给出比较器的函数代码，注意把它写在上述构造函数的前面，让编译器可以成功的找到他们：

//比较两个物体的盒子“大小”的主要函数，第三个参数axis表示比较的是哪个轴。
inline bool box_compare(const shared_ptr<hittable> a, const shared_ptr<hittable> b, int axis) {
    aabb box_a;
    aabb box_b;
    //先求两个物体的盒子。
    if (!a->bounding_box(0,0, box_a) || !b->bounding_box(0,0, box_b))
        std::cerr << "No bounding box in bvh_node constructor.\n";
    //比较两个盒子的较小的边，谁的给定轴分量越大，谁就越大。
    return box_a.min().e[axis] < box_b.min().e[axis];
}

//下面是三个轴比较函数，都是调用上面的比较函数。这三个函数存在的意义是方便构造函数中的函数指针。

bool box_x_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
    return box_compare(a, b, 0);
}

bool box_y_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
    return box_compare(a, b, 1);
}

bool box_z_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
    return box_compare(a, b, 2);
}

测试包围盒*

现在回到动态模糊那一章的最后一个场景，我们分别使用物体列表和BVH来装载场景物体，并运行光追器，来对比一下两者的耗时，首先，给main函数打个时间戳：

#if !MULTITHREAD

...
//需要引用此头文件
#include <windows.h>

...
int main() {
    //这个函数可以获取当前时间，并转换成某种基于毫秒的整数。
    auto start = GetTickCount64();

    //main中的全部代码都要被包进来。
    ...

    std::cerr << "\nDone.\n";
    //再次获得当前时间，并且减去main函数开头时记录的时间，便得到了毫秒差。
    int time = GetTickCount64() - start;
    time = time / 1000;
    auto minute = time / 60;
    auto second = time % 60;
    //简单转换一下，并输出出去。
    std::cerr << "took " << minute << "m " << second <<"s  to complete. \n";
}

}

紧接着，用bvh提到程序中的物体列表，在main函数中调用random_scene的地方，直接把物体列表传到bvh_node类的构造函数里，创建一个bvh即可：

//调用函数生成一个有着许多随机小球的场景！！！
//auto world = random_scene();
auto world = bvh_node(random_scene(),0,1);

传入构造函数的两个时刻值0和1是和相机的快门打开时间和关闭时间保持一致的。这决定了我们程序中所有的移动的球对象的包围盒都是通过这两个时间值来计算的。对于直线运动的球来说，在两个极端情况下的包围盒的包围盒，即是最终的包围盒。
运行程序，可见命令行中的运行时间（release-x86）：
image.png
对比前者——物体列表作为容器下的运行时间，后者bvh容器下的运行时间快了好几倍。

课后实践

  1. 在脑海中构建一个少量物体的bvh，按顺序阅读bvh的构造函数，体会物体被二分和生成包围盒的过程。接下来思考hit函数中包围盒是如何和光线求交的，这有助于理解整体架构。
    2*. 将bvh应用于多线程模式，并生成一个视频，比较使用包围盒前后的序列帧生成时间。

    参考文献

    https://raytracing.github.io/books/RayTracingTheNextWeek.html
    参考自《Ray Tracing: The Next Week》第3.8节到第3.10节。