【光线追踪系列十】光追加速结构(BVH树)
本文主要参照 Ray Tracing: The Next Week,其中只是主要精炼光追相关理论,具体实现可参照原文。
经过之前几部分的光追实现,我们大致可以实现了光追的效果,但其中有一个致命的bug就是:慢!!!本部分我们就来解决这个问题。
首先我们分析下:射线和物体的相交检测,是光线追踪器的主要时间瓶颈,目前时间复杂度是线性的。有两种方法可以将时间复杂度降低到对数级别:一是空间划分,二是物体划分。本节将用BVH实现物体划分,对当前的项目进行加速。
下边贴出未使用加速结构和使用BVH后的光追对比图(对单个像素单点采样):
未使用加速结构:
使用BVH加速结构:
一、层次包围体 BVH
Bounding volume hierarchy (BVH)即层次包围体,在BVH中,所有的几何物体都会被包在bounding volume的叶子节点里面,bounding volume外面继续包着一个更大的bounding volume,递归地包裹下去,最终形成的根节点会包裹着整个场景。常用于碰撞检测和光线追踪的加速,能够将时间复杂度降低到关于物体数量的对数级别。
举例:找个volume包围10个物体,如果射线没击中这个volume,那么射线肯定没击中这10个物体。
我们来看一下划分流程:
步骤一:
步骤二:
步骤三:
注意:把物体分成子集,可能会bounding volums重叠的情况。
例如上图中用方框来包围物体,一堆物体最终被分成ABCD四组,这四组物体又被其之上根节点更大的方框包围。
最常见的bounding volume就是AABB。
二、轴对齐包围盒 AABB
轴对齐包围盒:axis-aligned bounding box, 缩写为 AABB
可用slab方法检测射线于AABB相交。
下边我们来看一下公式求解:
其中:
则x轴方向上的t区间为:
射线和AABB是否相交,可以转化为不同轴方向上的t区间是否重叠。如上图中的tmin与tmax之间的区间。
2D情况写成伪代码:
compute (tx0, tx1)
compute (ty0, ty1)
return overlap?( (tx0, tx1), (ty0, ty1))
3D情况写成伪代码:
compute (tx0, tx1)
compute (ty0, ty1)
compute (tz0, tz1)
return overlap?( (tx0, tx1), (ty0, ty1), (tz0, tz1))
注意2个问题:
问题1:
1.射线沿着x轴的反方向发射,区间会反过来,例如(7,3)
2.分母可能为0
Bx为0的情况,tx0和 tx1都会是正无穷或者负无穷,tx0和 tx1可以分别取两者之间的较小者和较大者。
问题2:
Bx=0的同时,x0−Ax=0或 x1−Ax=0,这个问题稍后再处理。
假设没有反转区间,只需处理两对t区间是否重叠,伪代码如下:
bool overlap(d, D, e, E){
f = max(d, e) //f为两者起点的最大值
F = min(D, E) //F为两者终点的最小值
return (f < F) //区间相交条件:f<F
}
f为两者起点的最大值,F为两者终点的最小值,区间相交条件:f<F ( 即光线射入时只有最后一个方向进入才算进入,射出时只要有方向出去即为出区域 )。
可参考下图理解:
3D的情况,则需要多判断一次,写成代码如下:
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:
vec3 _min; //左下角顶点
vec3 _max; //右上角顶点
aabb() {}
aabb(const vec3& min, const vec3& max) { _min = min; _max = max;}
vec3 min() const {return _min; }
vec3 max() const {return _max; }
//判断射线是否在t区间
bool hit(const ray &r, float tmin, float tmax) const
{
//xyz三个方向分别判断
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;
if (invD < 0.0f)
std::swap(t0, t1);
tmax = t1 < tmax ? t1 : tmax; //F为两者终点的最小值
tmin = t0 > tmin ? t0 : tmin; //f为两者起点的最大值
if (tmax <= tmin) //F <= f
return false;
}
return true;
}
};
此外我们还需要计算2个box的包围盒:
/计算2个box的包围盒
aabb surrounding_box(aabb box0, aabb box1)
{
vec3 small(ffmin(box0.min().x(), box1.min().x()),
ffmin(box0.min().y(), box1.min().y()),
ffmin(box0.min().z(), box1.min().z()));
vec3 big(ffmax(box0.max().x(), box1.max().x()),
ffmax(box0.max().y(), box1.max().y()),
ffmax(box0.max().z(), box1.max().z()));
return aabb(small, big);
}
用bounding_box来设置物体的包围盒,目前场景中的物体只有sphere,但后续会新增其他物体(例如无边界的平面),这些物体不一定都会有包围盒,所以该函数返回bool值。对于动态模糊球体moving_sphere则需要时间间隔参数来模拟相机快门曝光,所以参数里面带上t0和t1。
在基类hittable中定义虚函数bounding_box(),并在子类中分别实现:
class hittable {
public:
...
virtual bool bounding_box(float t0, float t1, aabb& box) const = 0;
};
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;
}
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;
}
bool hittable_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;
}
二、BVH树的实现
下面开始实现BVH树,定义BVH树的节点为bvh_node类,继承自hittable。目前hittable子类的继承关系如下:
每个bvh_node都有一个AABB和左右孩子指针,左右孩子同样指向hittable的指针,可能指向bvh_node,也可能指向sphere或其他hittable子类。
hit()函数非常简单粗暴:检查当前节点的box是否命中,若是,则检查该节点的左右孩子(可能是bvh_node或sphere)是否命中。
对于所有的加速结构(包括BVH),最复杂的部分就是创建。使用自顶向下创建BVH树的方式如下:
- 随机选择x,y,z轴中的一个;
- 对该轴正方向的顺序对物体排序,并分成前后两半;
- 前一半物体放左子树,后一半物体放右子树,继续对左右子树递归创建。如果左右子树的物体数量等于2,直接左右节点分别指向物体。如果等于1,则左右节点均指向该物体。最后将当前节点的aabb设置为包含左右子树的box。
class bvh_node : public hittable
{
public:
bvh_node() {}
hittable *left;
hittable *right;
aabb box;
//t0, t1为moving_sphere中使用
bool bounding_box(float t0, float t1, aabb &b) const
{
b = box;
return true;
}
bool 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_node(hittable **l, int n, float time0, float time1)
{
int axis = int(3 * random_double());
if (axis == 0)
qsort(l, n, sizeof(hittable *), box_x_compare);
else if (axis == 1)
qsort(l, n, sizeof(hittable *), box_y_compare);
else
qsort(l, n, sizeof(hittable *), 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轴、y轴和z轴上的qsort()比较函数如下:
int box_x_compare(const void * a, const void * b) {
aabb box_left, box_right;
hittable *ah = *(hittable**)a;
hittable *bh = *(hittable**)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;
}
int box_y_compare(const void * a, const void * b) {
aabb box_left, box_right;
hittable *ah = *(hittable**)a;
hittable *bh = *(hittable**)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().y() - box_right.min().y() < 0.0)
return -1;
else
return 1;
}
int box_z_compare(const void * a, const void * b) {
aabb box_left, box_right;
hittable *ah = *(hittable**)a;
hittable *bh = *(hittable**)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().z() - box_right.min().z() < 0.0)
return -1;
else
return 1;
}
修改random_scene的返回值:
hittable *random_scene() {
...
// return new hittable_list(list,i);
return new bvh_node(list, i, 0.0, 1.0);
}
对比显示,使用BVH后,生成速度提升一倍左右。