LycTechStack

Lyc的个人成长技术栈

0%

【RayTracer】（十）实现BVH

发表于 分类于
本文字数： 7.5k 阅读时长 ≈ 7 分钟

这一节我们开始考虑对光线追踪器的性能做一点优化，以应对之后更加复杂的场景。之前在渲染随机场景的时候我们的代码运行的非常慢，根据目前代码的实现过程以及之前学的图形学知识可以分析出，影响速度的一个重要瓶颈是计算光线和物体交点的部分，因为每根光线都要和场景 world 中的所有物体去计算交点，然后判断哪个离我们最近，当物体非常多的时候自然效率会很低。因此这一节我们运用图形学中学过的层次包围盒（BVH）去优化我们的代码。关于 BVH 的理论知识可以查看之前的笔记【计算机图形学】（十一）Whitted 风格光线追踪。

1 轴对齐包围盒（AABB）

构建 BVH 首先需要我们实现一个轴对齐包围盒类，并实现光线和 AABB 的交点计算。在图形学中我们学过计算光线和 AABB 三对平面的交点只需要用一个维度的坐标计算即可，因此我们只需要存储三对平面的坐标，这里的坐标是指一个数字，因为 AABB 是轴对齐的，因此一对平面可以表示为：
$$
x = x_0 ,\ x=x_1
$$
的形式，所以只需要用六个数字就可以表示一个轴对齐包围盒。

于是我们计算出光线和三对平面的交点 tmin 和 tmax ，然后用三对 tmin 和 tmax 判断光线是否和 AABB 有交点。判断方法也在图形学中有学过，这里不再赘述。

需要注意的是在实现中因为我们是用单独一个维度坐标计算的，那就有可能出现分母为 0 的情况，好消息是只要光线的起点不在两对平面之间，即使分母为 0 ，那么得到的 tmin 和 tmax 就会是同样为正无穷或者负无穷，因为计算机中 0 只是一个很小的有符号浮点数。所以我们可以使 tmin 永远为二者中较小的，tmax 永远为二者中较大的，就可以得到正确的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
    轴对齐包围盒类
*/
#pragma once

#ifndef AABB_H
#define AABB_H

#include "utilities.h"

class aabb {
public:
    point3 minslab;
    point3 maxslab;

    aabb() {}
    aabb(const point3& m1, const point3& m2) { minslab = m1; maxslab = m2; }

    point3 min() const { return minslab; }
    point3 max() const { return maxslab; }

    bool hit(const ray& r, double tmin, double tmax) const
    {
        for (int i = 0; i < 3; ++i)
        {
            auto t0 = fmin((minslab[i] - r.origin()[i]) / r.direction()[i],
                          (maxslab[i] - r.origin()[i]) / r.direction()[i]);
            auto t1 = fmax((minslab[i] - r.origin()[i]) / r.direction()[i],
                          (maxslab[i] - r.origin()[i]) / r.direction()[i]);
            tmin = fmax(tmin, t0);
            tmax = fmin(tmax, t1);
            if (tmax <= tmin) return false;
        }
        return true;
    }
};

#endif

一个更稳定的 hit 函数的实现方式是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline bool hit(const ray& r, double tmin, double tmax) const
{
    for (int i = 0; i < 3; ++i) {
        auto invD = 1.0f / r.direction()[i];
        auto t0 = (min()[i] - r.origin()[i]) * invD;
        auto t1 = (max()[i] - r.origin()[i]) * 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;
}

在之前的图形学中推导光线和 AABB 有交点的时候，得出的条件是 tmax > tmin 且 tmax >= 0，但是在上面的代码中我们并没有考虑是否满足 tmax >= 0，这是因为这里的 hit 函数的 tmin 和 tmax 是作为参数给定的，我们在传入参数的时候就会保证得到的交点的 t 值一定是大于 0 的。

2 计算 BoundingBox

现在需要为物体类 hittable 添加一个计算物体 BoundingBox 的方法，并在不同的物体中有不同的实现，该函数返回 bool 类型，因为不是所有物体都能有 BoundingBox ，比如一个无限大的平面。此外对于移动的物体，需要 BoundingBox 能够覆盖所有时刻物体所在的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
    抽象类hittable，所有物体都继承该类
*/
#pragma once
#ifndef HITTABLE_H
#define HITTABLE_H

#include "utilities.h"
#include "material.h"
#include "aabb.h"

class hittable {
public:
    virtual bool hit(ray& r, double t_min, double t_max, hit_record& rec) const = 0;
    // 计算物体的包围盒
    virtual bool bounding_box(double time0, double time1, aabb& output_box) const = 0;
};

#endif

然后实现球体的 bounding_box 函数：

1
2
3
4
5
6
7
8
9
10
11
bool sphere::bounding_box(double _time0, double _time1, aabb& output_box) const
{
    aabb box0(
        center(_time0) - vec3(radius, radius, radius),
        center(_time0) + vec3(radius, radius, radius));
    aabb box1(
        center(_time1) - vec3(radius, radius, radius),
        center(_time1) + vec3(radius, radius, radius));
    output_box = surrounding_box(box0, box1);
    return true;
}

surrounding_box 函数在 aabb.h 中定义：

1
2
3
4
5
6
7
8
9
10
11
12
// 合并两个包围盒形成一个大的包围盒
aabb surrounding_box(aabb box0, aabb box1) {
    point3 small(fmin(box0.min().x(), box1.min().x()),
        fmin(box0.min().y(), box1.min().y()),
        fmin(box0.min().z(), box1.min().z()));

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

然后实现物体列表 hittable_list 的包围盒计算，思路是计算每个物体的包围盒，然后利用 surrounding_box 函数合并这些包围盒形成整个场景的包围盒：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool hittable_list::bounding_box(double time0, double time1, aabb& output_box) const
{
    if (objects.empty()) return false;

    aabb temp_box;
    bool first_box = true;

    for (const auto& object : objects) {
        if (!object->bounding_box(time0, time1, temp_box)) return false;
        output_box = first_box ? temp_box : surrounding_box(output_box, temp_box);
        first_box = false;
    }

    return true;
}

3 实现 BVH 树

在图形学中我们学过，BVH 树的中间节点只存储包围盒，叶子节点存储物体，因此我们可以实现一个 BVH 节点类，每个 BVH 节点的孩子节点可以是另外的 BVH 节点或者是场景中的物体，同时每个 BVH 节点也需要计算和光线的交点，因此我们可以让 BVH 节点类也继承于 hittable 基类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
    BVH类
*/
#pragma once
#ifndef BVH_H
#define BVH_H

#include "hittable.h"
#include "hittable_list.h"

class bvh_node : public hittable {
public:
    bvh_node();
    // 可以通过hittable_list来构建BVH
    bvh_node(const hittable_list& list, double time0, double time1)
        : bvh_node(list.objects, 0, list.objects.size(), time0, time1)
    {}
    // 构造BVH树
    bvh_node(
        const std::vector<shared_ptr<hittable>>& src_objects,
        size_t start, size_t end, double time0, double time1);

    virtual bool hit(
        ray& r, double t_min, double t_max, hit_record& rec) const override;

    virtual bool bounding_box(double time0, double time1, aabb& output_box) const override;

public:
    // 孩子节点可以是其他的BVH节点也可以是物体
    shared_ptr<hittable> left;
    shared_ptr<hittable> right;
    aabb box;
};

bool bvh_node::hit(ray& r, double t_min, double t_max, hit_record& rec) const {
    if (!box.hit(r, t_min, t_max))
        return false;

    bool hit_left = left->hit(r, t_min, t_max, rec);
    // 如果和左子树中有交点，要更新t_max，使得最终的交点是最近的交点
    bool hit_right = right->hit(r, t_min, hit_left ? rec.t : t_max, rec);

    return hit_left || hit_right;
}

bool bvh_node::bounding_box(double time0, double time1, aabb& output_box) const {
    output_box = box;
    return true;
}

#endif

比较复杂的是构建 BVH 树，我们在构造函数中构造整个 BVH 树，对于给定的物体列表，我们将其按照某一方向（x，y，z随机选择）排序，然后一分为二，一部分放到左子树，一部分放到右子树，因此这是一个类似于二分的递归过程。当物体列表中只有两个物体的时候，左右子树各放一个物体，当只有一个物体的时候，我们把这个物体复制一份，同时放到左右子树中，这样可以保证整个 BVH 树是一个完全二叉树，并且所有非叶子节点都一定有两个孩子节点，可以方便我们之后的处理，不需要判断孩子节点是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
bvh_node::bvh_node(
    const std::vector<shared_ptr<hittable>>& src_objects,
    size_t start, size_t end, double time0, double time1
) {
    // 不要修改原来的物体列表
    auto objects = src_objects;
    // 随机选择一个划分方向，并传递相应的比较函数指针
    int axis = random_int(0, 2);
    auto comparator = (axis == 0) ? box_x_compare
                    : (axis == 1) ? box_y_compare
                    : box_z_compare;
    // 区间内的物体数量
    size_t object_span = end - start;
    // 只有一个物体，同时放到两个孩子节点
    if (object_span == 1) {
        left = right = objects[start];
    }
    // 有两个物体，左右孩子结点各一个
    else if (object_span == 2) {
        if (comparator(objects[start], objects[start + 1])) {
            left = objects[start];
            right = objects[start + 1];
        }
        else {
            left = objects[start + 1];
            right = objects[start];
        }
    }
    // 多个物体递归的进行划分
    else {
        // 先按照指定的维度进行排序
        std::sort(objects.begin() + start, objects.begin() + end, comparator);
        // 二分
        auto mid = start + object_span / 2;
        left = make_shared<bvh_node>(objects, start, mid, time0, time1);
        right = make_shared<bvh_node>(objects, mid, end, time0, time1);
    }

    // 当前节点的box由左右两个子树的box的合并而来
    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_int 函数，在 utilities.h 中增加：

1
2
3
4
// 生成[min,max]之间的随机整数
inline int random_int(int min, int max) {
    return static_cast<int>(random_double(min, max + 1));
}

以及自定义的比较函数，我们根据不同的方向，按照物体或者 BVH 节点的包围盒位置从小到大排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
}
---- 本文结束 知识又增加了亿点点！----

文章版权声明 1、博客名称：LycTechStack
2、博客网址：https://lz328.github.io/LycTechStack.github.io/
3、本博客的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系博主进行删除处理。
4、本博客所有文章版权归博主所有，如需转载请标明出处。
相关文章