RTTNW-ch2：Bounding Volume Hierarchies

这部分是迄今为止我们正在研究的光线追踪器中最困难的部分。 我们的光线与物体相交点是光线追踪器的主要时间瓶颈，时间是与物体的数量呈线性关系。但它是对同一个模型的重复搜索，所以我们可以使用二分搜索进行对数查找。 两个最常见的排序方法是划分空间和划分对象。后者通常是编码起来更容易，而且大多数模型的运行速度都很快。 关键在于在找到一个边界体积包围所有物体。

if (ray hits bounding object)
return whether ray hits bounded objects
else
return false

我们要把物体分离到不同的边界框中去，任何一个物体都在一个边界盒中，边界盒有可能重叠。如果我们使用矩形分成红色和蓝色两组，得到如下： [

](http://www.wjgbaby.com/wp-content/uploads/2018/06/18062901.png)

红色框和蓝色框都被包围在紫色盒子中，但是它们可能会重叠，而且它们不是有序的 ，它们都在里面。 所以树上显示的树没有左孩子和右孩子的概念。

if (hits purple)
hit0 = hits blue enclosed objects
hit1 = hits red enclosed objects
if (hit0 or hit1)
return true and info of closer hit
return false

一个好的射线与层次包围相交需要快速，并且边界需要紧凑，轴对齐是个不错的方案。 从现在开始，我们将调用轴对齐的边界矩形平行六面体（真的，也就是说，他们需要如何调用）轴对齐边界框或AABB。 任何你想用来与AABB相交的方法很好。 所有我们需要知道的是否我们击中了它; 我们不需要相交点或法线或任何东西需要我们显示的对象。 大多数人使用“slab”方法。 这是基于n维的观察AABB只是n轴对齐的区间的交集，通常称为“平板”。 间隔只是两个端点之间的点，例如，x使得3 <x <5，或者更简洁地x in(3,5)。 在2D中，两个重叠的区间构成一个2D AABB（一个矩形）：[

在3D中，这些边界是平面。平面的方程为x

/Bx[/latex] 在一维空间中判定一次命中的关键是在t时间间隔内要有重叠。在二维空间中，如果有命中，绿色和蓝色会有一个重叠，如下面的那条射线。 用代码描述“在slab的t间隔是否重叠”：

compute (tx0, tx1)
compute (ty0, ty1)
return overlap?( (tx0, tx1), (ty0, ty1))

在3D中，slab方法依然可以工作，这也是人们喜欢它的原因。

compute (tx0, tx1)
compute (ty0, ty1)
compute (tz0, tz1)
return overlap?( (tx0, tx1), (ty0, ty1), (tz0, tz1))

有一些注意事项我们要知道，首先，假设射线在负x方向上行进。间隔（tx0，tx1）如上所述计算可能会逆转，例如（7,3）。第二，那里的鸿沟可能会给我们带无限可能。如果射线源位于一个slab边界上，我们可以得到一个NaN。那里 这些问题在许多光线追踪器的AABB中处理的方式有很多。 （也有像SIMD这样的矢量化问题，我们不在这里讨论。) 目的，只要我们使速度合理快速，这不太可能成为主要瓶颈，所以让我们走最简单的，无论如何，这往往是最快的！首先让我们看看计算间隔： [latex]tx_{0}=(x_{0}-Ax)/Bx[/latex]， [latex]tx_{1}=(x_{1}-Ax)/Bx[/latex] 一个麻烦事是如果Bx=0，造成分离为0.这样的射线有的是在平板内的，有些不在，而且这个0会带正负号。在IEEE浮点标准下，在Bx=0时，t0和t1会都是 正无穷或者负无穷，反正不是x0和x1之间的数字，所以我们可以使用最大值和最小值来解决问题 [latex]tx_{0}=min((x_{0}-Ax)/Bx,(x_{1}-Ax)/Bx)[/latex]， [latex]tx_{1}=min((x_{0}-Ax)/Bx,(x_{1}-Ax)/Bx)[/latex] 如果我们这样做，剩下的麻烦情况是如果Bx = 0并且x0-Ax = 0或者x1-Ax= 0，所以我们得到一个NaN。在这种情况下，我们可以返回不命中作为结果。 现在，我们来看看这个重叠函数。假设我们可以假设间隔不是反转（所以第一个值小于间隔中的第二个值），我们想要在那种情况下返回true。布尔重叠也计算重叠区间（f，F）（d，D）和（e，E）的间隔为：

bool overlap(d, D, e, E, f, F)
f = max(d, e)
F = min(D, E)
return (f < F)

如果有任何NaN在那里运行，比较将返回false，所以我们需要确保我们的边界盒有一些填充。

创建AABB包围盒的类：

inline float ffmin(float a, float b) { return a < b ? a : b; }
inline float ffmax(float a, float b) { return a > b ? a : b; }

class aabb {
public:
aabb() {}
aabb(const vec3& a, const vec3& b) { _min = a; _max = b;}

vec3 min() const {return \_min; }
vec3 max() const {return \_max; }

bool hit(const ray& r, float tmin, float tmax) const {
    for (int a = 0; a < 3; a++) {
        float t0 = ffmin((\_min\[a\] - r.origin()\[a\]) / r.direction()\[a\],  
                        (\_max\[a\] - r.origin()\[a\]) / r.direction()\[a\]);
        float t1 = ffmax((\_min\[a\] - r.origin()\[a\]) / r.direction()\[a\],  
                        (\_max\[a\] - r.origin()\[a\]) / r.direction()\[a\]);
        tmin = ffmax(t0, tmin);
        tmax = ffmin(t1, tmax);
        if (tmax <= tmin)
            return false;
    }
    return true;
}

vec3 \_min;
vec3 \_max;

};

我们现在需要添加一个函数来计算所有需求的边界框，并生成它们，这是个重载函数：

class hitable {
public:
//hit()虚函数
virtual bool hit(const ray& r, float t_min, float t_max, hit_record& rec) const = 0;
virtual bool bounding_box(float t0, float t1, aabb& box) const = 0;
};

sphere的bounding_box函数：

bool sphere ::bounding_box(float t0, float t1, aabb& box) const {
box = aabb(center - vec3(radius, radius, radius), center + vec3(radius, radius, radius));
return true;
}

moving_sphere的bounding_box函数：

bool moving_sphere::bounding_box(float t0, float t1, aabb& box) const {
aabb box0(center(t0) - vec3(radius, radius, radius), center(t0) + vec3(radius, radius, radius));
aabb box1(center(t1) - vec3(radius, radius, radius), center(t1) + vec3(radius, radius, radius));
box = surrounding_box(box0, box1);
return true;
}

hitable_list的bounding_box函数：

bool hitable_list::bounding_box(float t0, float t1, aabb& box) const {
if (list_size < 1) return false;
aabb temp_box;
bool first_true = list[0]->bounding_box(t0, t1, temp_box);
if (!first_true)
return false;
else
box = temp_box;
for (int i = 1; i < list_size; i++) {
if(list[0]->bounding_box(t0, t1, temp_box)) {
box = surrounding_box(box, temp_box);
}
else
return false;
}
return true;
}

对于移动球体，我们可以在t0处取球体的方框，在t1处取球体的方框，将t0时的盒子和t1时的盒子放进一个大盒子里：

aabb surrounding_box(aabb box0, aabb box1) {
vec3 small( fmin(box0.min().x(), box1.min().x()),
fmin(box0.min().y(), box1.min().y()),
fmin(box0.min().z(), box1.min().z()));
vec3 big ( fmax(box0.max().x(), box1.max().x()),
fmax(box0.max().y(), box1.max().y()),
fmax(box0.max().z(), box1.max().z()));
return aabb(small,big);
}

一个BVH也将是一个可以击中的 ，就像击中列表一样。 这真的是一个容器，但是 它可以回应询问“这光线击中了你？”。 一个设计问题是我们是否有两个类，一个用于树，另一个用于树中的节点; 或者我们只有一个类，并且根只是我们指向的一个节点。这里我们使用一个类：

class bvh_node : public hitable {
public:
bvh_node() {}
bvh_node(hitable **l, int n, float time0, float time1);
virtual bool hit(const ray& r, float tmin, float tmax, hit_record& rec) const;
virtual bool bounding_box(float t0, float t1, aabb& box) const;
hitable *left;
hitable *right;
aabb box;
};

bool bvh_node::bounding_box(float t0, float t1, aabb& b) const {
b = box;
return true;
}

这里的左右节点都是基类Hitable类型，这样BVH的子节点也有可能是另一个BVH节点或者是一个物体，如果是BVH的话就继续检测其子节点：

bool bvh_node::hit(const ray& r, float t_min, float t_max, hit_record& rec) const {
if (box.hit(r, t_min, t_max)) {
hit_record left_rec, right_rec;
bool hit_left = left->hit(r, t_min, t_max, left_rec);
bool hit_right = right->hit(r, t_min, t_max, right_rec);
if (hit_left && hit_right) {
if (left_rec.t < right_rec.t)
rec = left_rec;
else
rec = right_rec;
return true;
}
else if (hit_left) {
rec = left_rec;
return true;
}
else if (hit_right) {
rec = right_rec;
return true;
}
else
return false;
}
else return false;
}

任何效率结构中最复杂的部分就是构建这个结构。关于BVH的一个很酷的事情是，只要BVH节点中的对象列表被分成两个子列表，命中检测就可以工作。如果合适分隔，这将最高效，为了生成一个尽量小的，包含所有对象的盒子，我们让每个节点沿一个轴分割列表： 1. 随机选择一个轴 2. 将节点内的对象进行排序 3. 左右子树各放一半

当列表进入是两个元素时，我在每个子树中放一个并结束递归。遍历算法应该是平滑的，不必检查空指针，所以如果我只需要在每个子树中复制一个元素。 明确检查三个元素只是在一次递归之后可能会有所帮助，但我认为整体方法稍后会得到优化。 这产生：

bvh_node::bvh_node(hitable **l, int n, float time0, float time1) {
int axis = int(3*((rand() % (100) / (float)(100))));
if (axis == 0)
qsort(l, n, sizeof(hitable *), box_x_compare);
else if (axis == 1)
qsort(l, n, sizeof(hitable *), box_y_compare);
else
qsort(l, n, sizeof(hitable *), box_z_compare);
if (n == 1) {
left = right = l[0];
}
else if (n == 2) {
left = l[0];
right = l[1];
}
else {
left = new bvh_node(l, n/2, time0, time1);
right = new bvh_node(l + n/2, n - n/2, time0, time1);
}
aabb box_left, box_right;
if(!left->bounding_box(time0,time1, box_left) || !right->bounding_box(time0,time1, box_right))
std::cerr << “no bounding box in bvh_node constructor\n”;
box = surrounding_box(box_left, box_right);
}

检查是否有边界框是为了防止你发送像一个无限平面一样的东西，它们没有边界框. x轴compare函数：

int box_x_compare (const void * a, const void * b) {
aabb box_left, box_right;
hitable *ah = *(hitable**)a;
hitable *bh = *(hitable**)b;
if(!ah->bounding_box(0,0, box_left) || !bh->bounding_box(0,0, box_right))
std::cerr << “no bounding box in bvh_node constructor\n”;
if ( box_left.min().x() - box_right.min().x() < 0.0 )
return -1;
else
return 1;
}

参考书籍：《Ray Tracing The Next Week》 RTTNW系列项目地址：GitHub