v4vendeta's homepage

home | project | blog| other

Ray Tracing in One Weekend Summary X - Bounding Volume Hierarchies

层次包围盒


本章我们重构hittable类,可以使得代码运行的更快,在之前的光线追踪器中,计算光线-物体相交是最费时的步骤,运算的时间和物体的数量是线性相关的,而且,我们用二分搜索的思想

首先把模型分为两类:1)划分空间 2)划分对象

然后,每条光线的相交就是一个次线性搜索

对多个物体,用bounding volume的关键就是,找到一个包围了所有物体的包围盒,如果光线和包围盒没有交点,那光线和这些物体都不相交,判断碰撞的伪代码如下

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

如上图,每一个物体都有一个bounding volume,多个物体的bounding volume相互叠加,就形成了一个有层级关系的bounding volume,

对此层级检测碰撞的伪代码为

if(hit purple) //紫色
    hit0 = hits blue enclosed objects
    hit1 = hits red enclosed objects
    if(hit0 or hit1)
        return true and info of closer hit //返回hit的信息
else
    return false

在实际操作中,我们采用与坐标轴平行的长方体(axis-aligned bounding rectangular parallelepiped)作为包围盒,或叫做aabbs,我们只用检测光线是否与包围盒相交,而不用得知交点的具体信息

以2D平面为例

p(t)= a+t*b

x轴上

x0=ax0+t0∗bx0

x1=ax1+t1∗bx1

解得:

t0=(x0-ax0)/bx0

t1=(x1-ax1)/bx1

同理,在y轴上

t0=(y0-ay0)/by0

t1=(y1-ay1)/by1

x,y是分开计算的,接下来,判断x,y轴的(t0,t1)有没有相交的部分即可

判断的方法如下:

两个区间的左端点最大值小于右端点的最小值
  有交点
反之
  无交点

注意:

1)直接计算出来的t0,t1大小不确定,需要先判断,调整大小使t0 < t1

2)如果除数Bx=0,或者分子是0,求出来的解也许无意义,需要提前检测

aabb.h

#ifndef AABB
#define AABB 

#include "hittable.h"
#include "ray.h"

//faster than fmin and fmax because it doesn’t worry about NaNs and other exceptions
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; }
        virtual bool hit(const ray& r, float tmin, float tmax) const;

        vec3 _min;
        vec3 _max;
};

inline bool aabb::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;
        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;
}
#endif

接下来我们在hittable.h中添加bounding_box纯虚函数,这样,在每个物体在计算时都会有一个包围盒了

class hittable {
    public:
        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的包围盒:球心加半径

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的包围盒:对t0时刻的box和t1时刻的box,取一个更大的boundingbox

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

hittable_list的包围盒:对list的每个物体计算surrounding_box,并叠加,最终返回一个包含所有物体的包围盒

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;
}
//两个包围盒叠加生成的包围盒
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);
}

bvh.h

class bvh_node : public hittable {
    public:
        bvh_node() {}
        bvh_node(hittable **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;

        hittable *left;
        hittable *right;
        aabb box;
};

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

hit函数中,如果光线击中了节点的包围盒,对于左右子树进行递归操作,直到射到叶子节点,击中重叠的部分,击中的数据用引用rec传出去。

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_node分为两个子列表,如果划分得很好,代码的运行速度就会快很多,最佳是满二叉树的情况,步骤如下:

随机选择一个轴
使用qsort对物体进行排序
在每个子树中放一半物体
bvh_node::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);
}

compare函数

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