Bounding Volume Hierarchies 加速结构

背景

光线与物体求交是光线追踪的主要 时间瓶颈 。

如果不进行优化，则对每条光线，我们都需要遍历场景中的全部物体并求交。而现在想建模一个小物体的表面，往往要几千甚至几万个三角形，一个商业级产品，屏幕内甚至可能同时存在几亿个三角形。

想要提升效率，我们需要 加速结构 的帮助。

类似于二分查找的思想，我们先判断光线是否与较大的集合相交，如果不相交，则该集合内的所有物体都无需求交，减少了原有的计算量。

加速结构一般有 两种 ：

一种是 划分空间 ：如K-D Tree

一种是 划分物体 ：如BVH

下面我们将主要介绍BVH。

BVH（Bounding Volume Hierarchies）

Bounding Volume

由于和不规则物体求交，计算量较大，我们通常给每个物体创建一个Bounding Volume，先与Bounding Volume求交，通过了Bounding Volume的测试，才与物体求交，这样减少了平均的时间开销。

那么bounding volume具体是什么样的结构呢，可以肯定的是，与该结构求交的速度一定需要非常快。通常我们会选用axis-aligned bounding boxes（AABB）作为具体的求交结构，顾名思义，即棱边分别平行于坐标轴的盒子。在实际使用中，它被证明，比大多数的结构更快。

Hierachy

hierachy体现在，整个BVH结构是 一棵树 ，树的每个节点，都是一个bounding box，其中的object的box都为叶子节点，中间节点为构造出的BVH Node用于更高层级的求交。只有和树高层的bounding box相交，才能进入树的更深层。

实现思路

首先，每个物体都需要有各自的aabb用于求交，因此我们需要先 创建一个aabb类 ，其中包括求交的函数。

再在每个object中加入 求其aabb的具体方法 。这样我们就有了物体的bounding box，并有了与它们求交的方法。

其次，我们需要构建BVH层级，建立层级不仅需要上述的叶子节点，也需要为了实现层级加速的 中间结点 ，我们会创建中间节点的类，并在其中具体实现层级求交。

创建aabb类

创建一个box很简单，关键是如何判断是否与box相交呢？

将直线和box的六个平面相交，会有6个交点，即便box与ray相交，这些交点也并非全部落在box的xyz范围之内，如何根据这些交点，判断ray和box的相交情况呢？

这里的技巧是：ray与box的x，y，z方向的平面，都分别会有两个交点，记录他们的t值，如x方向的平面 tx0 , tx1 。y,z方向同理。

则，若 [tx0,tx1] ， [ty0,ty1] ， [tz0,tz1] 三个区间有交集，则ray和box相交。

.

关于这个技巧，https://www.cnblogs.com/lv-anchoret/p/10284085.html 已经有了非常详细的说明，本文便不再赘述。

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 invD = 1.0f / r.direction()[a];

			float t0 = (min()[a] - r.origin()[a])*invD;

			float t1 = (max()[a] - r.origin()[a])*invD;

                        //确保t0<t1，在射线朝某轴负方向射出时t0>t1

			if (invD < 0.0f)

				std::swap(t0, t1);

			tmin = t0 > tmin ? t0 : tmin;

			tmax = t1 < tmax ? t1 : tmax;

			if (tmax <= tmin)

				return false;

		}

		return true;

	}

	vec3 _min;

	vec3 _max;

};

求具体类型object的bounding box

球 ：aabb的中心为球心，边长为球直径。

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;

}

运动的球 ：其开始位置的box1，结束位置的box2，对box1，box2组合后求得的box3即为结果。

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;

}

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);

}

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[i]->bounding_box(t0, t1, temp_box)) {

			box = surrounding_box(box, temp_box);

		}

		else

			return false;

	}

	return true;

}

建立bounding box的 hierarchy

这里仅采用最简单的 按物体数均匀划分 的方式，先建立最高层级的node，再对两个子树进行递归调用。

在三个分量上对物体排序，以便就近划分。

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;

};

//需要输入全部object，才能建立加速结构

bvh_node::bvh_node(hitable **l, int n, float time0, float time1) {

	int axis = int(3 * random_double());

	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创建本bvh_node的aabb

	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);

}

在random_scene()中有：

return new bvh_node(list, i, 0.0, 1.0);

在main()中有：

hitable *world = random_scene();

ray r = cam.get_ray(u, v);

col += color(r, world,0);

求交流程

先判断是否与自己的box相交，若相交，则分别与子节点测试，递归调用hit

bool bvh_node::hit(const ray& r, float t_min, float t_max, hit_record& rec) const {

	//如果和自己的box交，则测试子节点的box

	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加速结构啦。