首页 C++ RayTracing

[toc]

# RayTracing 射线检测伪代码

1
2
3
4
if (ray hits bounding object)
    return whether ray hits bounded objects
else
    return false

如上所示，最简单的例子中，每轮都需要遍历所有的对象。而且需要对每个对象进行射线检测

# 使用 BVH (或加速结构) 优化后的伪代码

1
2
3
4
5
6
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

如上所示，我们会使用加速结构，将物体拆分到不同的空间块中，然后检索物体时就可以使用 LgN 的时间找到最接近的块， 然后只需要对最接近的块进行射线碰撞检测

# AABB 碰撞代码

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
#pragma once

#include "rtweekend.h"

class aabb {
public:
    aabb(){}
    aabb(const point3& a, const point3& b) { minimum = a; maximum = b; }

    point3 min() const { return minimum; }
    point3 max() const { return maximum; }

    bool hit(const ray& r, double t_min, double t_max) const {
        for (int a = 0; a < 3; ++a) {
            auto t0 = fmin((minimum[a] - r.origin()[a]) / r.direction()[a],
                           (maximum[a] - r.origin()[a]) / r.direction()[a]);

            auto t1 = fmax((minimum[a] - r.origin()[a]) / r.direction()[a],
                           (maximum[a] - r.origin()[a]) / r.direction()[a]);

            t_min = fmax(t0, t_min);
            t_max = fmin(t1, t_max);
            //有一个不满足 就碰撞失败
            if (t_max <= t_min)
                return false;
        }
        return true;
    }

public:
    point3 minimum;
    point3 maximum;
};

对 XYZ 三个轴进行相交判断，一个不满足就无法碰撞

# AABB 碰撞代码优化

  1. 减少除法
  2. 减少分支判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool hit(const ray& r, double t_min, double t_max) const {
    for (int a = 0; a < 3; a++) {
        auto invD = 1.0f / r.direction()[a];
        auto t0 = (min()[a] - r.origin()[a]) * invD;
        auto t1 = (max()[a] - r.origin()[a]) * invD;
        if (invD < 0.0f)
            std::swap(t0, t1);
        t_min = t0 > t_min ? t0 : t_min;
        t_max = t1 < t_max ? t1 : t_max;
        if (t_max <= t_min)
            return false;
    }
    return true;
}

# bvh 最简算法

    1. 递归建树
    1. 每次随机选择一个坐标轴 (axis) 对 hittable 对象进行分割
    • 2.1 找一个位置。保证按 axis 分割后两边的数量比 尽量为1:1
    • 2.2 如果 hittable 只有一个，则为叶子节点，两边子树都包含
    • 2.3 如果 hittable 有两个，为两个叶子节点，根据大小关系放到 left/right 子树上
    • 2.4 hittable 对象大于两个，先对 hittable 对象进行排序，然后选择中点，递归建树
    • 2.5 经过 2.4 最终一定会递归到 1/2 数量的节点上，类似于归并，向上归并 AABB

# 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#pragma once

#include "rtweekend.h"

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

#include <algorithm>


class bvh_node : public hittable {
public:
    bvh_node();

    bvh_node(const hittable_list& list,double time0,double time1)
        : bvh_node(list.objects, 0, list.objects.size(), time0, time1)
    {}

    bvh_node(
        const std::vector<shared_ptr<hittable>>& src_objects,
        size_t start, size_t end, double time0, double time1);

    virtual bool hit(
        const 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:
    shared_ptr<hittable> left;
    shared_ptr<hittable> right;
    aabb box;
};

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

bool bvh_node::hit(const 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);
    bool hit_right = right->hit(r, t_min, hit_left ? rec.t : t_max, rec);


    return hit_left  hit_right;
}

bvh_node::bvh_node(const std::vector<shared_ptr<hittable>>& src_objects,
        size_t start,size_t end,double time0,double time1
    ) {
    //Create a modifiable array of the source scene objects
    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);
    }

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


#pragma region compare Fucntion

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

#pragma endregion

# 为什么说这个是最简算法？

pbrt 书中有一个比较完善的写法，其中需要考虑的还有很多优化，如
- 每次选择轴不能使用随机的，尽量找一个可以二分的轴进行切分
- 稠密化 bvh 节点 - 动态插入删除节点 (插入监测是否触发平衡变更 / 删除暂时置为 dirty)
- SAH 启发式 (用来尽量避免运行时射线的检测次数过多)