作业6-加速结构
1 总览
在之前的编程练习中，我们实现了基础的光线追踪算法，具体而言是光线传输、光线与三角形求交。我们采用了这样的方法寻找光线与场景的交点：遍历场景中的所有物体，判断光线是否与它相交。在场景中的物体数量不大时，该做法可以取得良好的结果，但当物体数量增多、模型变得更加复杂，该做法将会变得非常低效。因此，我们需要加速结构来加速求交过程。在本次练习中，我们重点关注物体划分算法 Bounding Volume Hierarchy (BVH)。本练习要求你实现 Ray-Bounding Volume 求交与 BVH 查找。
首先，你需要从上一次编程练习中引用以下函数：
- Render() in Renderer.cpp: 将你的光线生成过程粘贴到此处，并且按照新框架更新相应调用的格式。
- Triangle::getIntersection in Triangle.hpp: 将你的光线-三角形相交函数粘贴到此处，并且按照新框架更新相应相交信息的格式。
在本次编程练习中，你需要实现以下函数：
IntersectP(const Ray& ray, const Vector3f& invDir,const std::array<int, 3>& dirIsNeg)in the Bounds3.hpp: 这个函数的作用是判断包围盒 BoundingBox 与光线是否相交，你需要按照课程介绍的算法实现求交过程。getIntersection(BVHBuildNode* node, const Ray ray)in BVH.cpp: 建立 BVH 之后，我们可以用它加速求交过程。该过程递归进行，你将在其中调用你实现的 Bounds3::IntersectP.
总的来说，本实验只需要实现实现 Ray-Bounding Volume 求交与 BVH 查找，而不需要实现BVH的建立过程。
2 代码框架
我们修改了代码框架中的如下内容：
- Material.hpp：我们从将材质参数拆分到了一个单独的类中，现在每个物体实例都可以拥有自己的材质。
- Intersection.hpp: 这个数据结构包含了相交相关的信息。
- Ray.hpp: 光线类，包含一条光的源头、方向、传递时间 t 和范围 range.
- Bounds3.hpp: 包围盒类，每个包围盒可由 pMin 和 pMax 两点描述（请思考为什么）。Bounds3::Union 函数的作用是将两个包围盒并成更大的包围盒。与材质一样，场景中的每个物体实例都有自己的包围盒。
- BVH.hpp: BVH 加速类。场景 scene 拥有一个 BVHAccel 实例。从根节点开始，我们可以递归地从物体列表构造场景的 BVH.
注意
需要注意的是，原本在Renderer.cpp中实现的trace()和castRay()被搬到了Scene.cpp中
3 知识回顾
3.1 BVH（Bounding Volume Hierarchy）树
BVH树对物体进行划分，如图所示，直至划分至子结点中有足够少的三角形；
BVH树解决了 KD-Tree 的两大问题；
Oct-Tree和KD-Tree
八叉树（Oct-Tree）对空间进行轴向划分，将每个节点进行八分割存储在子结点中，划分至子结点中有足够少的物体；
KD-Tree不同于八叉树，每次只对节点进行一次轴向划分，不对于父子节点进行相同轴向的划分（三维上沿 x ，y ，z 方向上循环），同样直至子结点中有足够少的物体；
在判断时，先判断与根节点是否存在交点，如果有交点则判断与两子节点是否存在交点；直至叶子节点，如果仍有交点则判断其与节点内部模型是否有交点；
KD-Tree 的主要问题是难以判断格点与哪些模型相交；此外，如果一个物体与多个叶子节点相交，其会被存储多份；
BVH树存在的问题是节点包围盒可能相交，但这个问题的影响有限，因为实际上会保证重叠部分尽量少；
BVH树是怎么划分节点的呢？
- 类似 KD-Tree ，可以循环使用不同的轴向；也可以选择包围盒最长的一条轴进行划分；
- 对于如何划分两半，可以将三角形的重心按分割轴向排序，取中位三角形进行分隔，使得两部分三角形数量均匀，降低资源消耗；
寻找中位数不需要排序，可以转化为top-k大数问题，通过快速选择算法在线性复杂度内解决；
在场景变化时，需要重新计算BVH树；
与 KD-Tree 类似，在中间节点只存储包围盒和子节点指针，只在叶子节点存储分割后的模型；
光线求交过程也与 KD-Tree 类似，有伪代码
Intersect (Ray ray, BVH node) {
if (ray misses node.bbox) return;
if (node is a leaf node)
{
test intersection with all objs;
return closest intersection;
}
hit1 = Intersect(ray, node.child1);
hit2 = Intersect(ray, node.child2);
return the closer of hit1, hit2;
}
3.2 判断光线与包围盒相交
考虑光线和包围盒求交过程；当光线与三组对面中的任何一个面均有交点时，认为光线进入包围盒，当光线穿过任何的两个平面时，认为光线离开包围盒；
对于每一组对面（对应每个维度），分别计算 \(t_{min},t_{max}\)（无论正负），光线关于包围盒的进入点有 \(t_{enter}=\max\{t_{min}\}\) ，离开点有 \(t_{exit}=\min\{t_{max}\}\) ；
- 如果 \(t_{exit}<0\) ，我们认为包围盒在光线后，与光线没有交点；
- 如果 \(t_{exit}\geqslant0,t_{enter}<0\) ，我们认为光源在包围盒中；
总地来说，如果 \(t_{enter}<t_{exit}，t_{exit}\geqslant0\) ，我们认为光线与包围盒有交点；
4 我的实现
4.1 迁移光线生成的代码
需要修改Render() in Renderer.cpp: 将你的光线生成过程粘贴到此处，并且按照新框架更新相应调用的格式。
for (uint32_t j = 0; j < scene.height; ++j) {
for (uint32_t i = 0; i < scene.width; ++i) {
// generate primary ray direction
float x = (2 * (i + 0.5) / (float)scene.width - 1) *
imageAspectRatio * scale;
float y = (1 - 2 * (j + 0.5) / (float)scene.height) * scale;
// TODO: Find the x and y positions of the current pixel to get the
// direction
// vector that passes through it.
// Also, don't forget to multiply both of them with the variable
// *scale*, and x (horizontal) variable with the *imageAspectRatio*
// Don't forget to normalize this direction!
Vector3f dir = Vector3f(x, y, -1);
dir = normalize(dir);
Ray ray= Ray(eye_pos, dir);
// 参数(摄像机位置，光线方向，场景，递归深度)
framebuffer[m++] = scene.castRay(ray, 0);
}
UpdateProgress(j / (float)scene.height);
}
重点在于产生光线ray，并通过scene.castRay函数，根据ray来计算framebuffer中当前的像素点。
上述代码有一个可以优化的地方
// 参数(摄像机位置，光线方向，场景，递归深度)
framebuffer[m++] = scene.castRay(std::move(ray), 0);
那就是在这里使用
std::move来传递参数std::move 是C++ 移动语义，将 ray 的资源（而非拷贝资源）转移给 castRay 函数，避免拷贝大型对象的性能开销
4.2 迁移三角形面求交的代码
需要修改Triangle::getIntersection()in Triangle.hpp。重点在于适配新的架构，将原本返回是否相交的布尔值改成Intersection结构体。
inter.happened = true;
inter.distance = t_tmp;
inter.obj = this;
inter.m = this->m;
inter.coords = ray.origin + ray.direction * t_tmp;
inter.normal = this->normal;
上述代码中的
this-> 可加可不加
4.3 IntersectP判断包围盒与光线相交
inline bool Bounds3::IntersectP(const Ray& ray, const Vector3f& invDir,const std::array<int, 3>& dirIsNeg) const;
这个属于
Bounds类的方法负责判断光线ray是否与包围盒相交，它可以使用Bounds类的属性pMin和pMax，另外根据参数ray来判断是否相交。Ray类含有下述属性//Destination = origin + t*direction
Vector3f origin;
Vector3f direction, direction_inv;
double t;//transportation time,
double t_min, t_max;
另外传入的还有两个参数,它们分别反映了光线方向向量坐标的倒数和符号，由函数调用者在外部设置后传入
invDir=(1.0/x,1.0/y,1.0/z)dirIsNeg=[int(x>0),int(y>0),int(z>0)]
inline bool Bounds3::IntersectP(const Ray& ray, const Vector3f& invDir,
const std::array<int, 3>& dirIsNeg) const
{
// invDir: ray direction(x,y,z), invDir=(1.0/x,1.0/y,1.0/z), use this because Multiply is faster that Division
// dirIsNeg: ray direction(x,y,z), dirIsNeg=[int(x>0),int(y>0),int(z>0)], use this to simplify your logic
// TODO test if ray bound intersects
float t_enter = -std::numeric_limits<float>::max();
float t_exit = std::numeric_limits<float>::max();
Vector3f t_min, t_max;
for (int i = 0; i < 3; i++) {
if(dirIsNeg[i]) {
t_min[i] = (pMax[i] - ray.origin[i]) * invDir[i];
t_max[i] = (pMin[i] - ray.origin[i]) * invDir[i];
} else {
t_min[i] = (pMin[i] - ray.origin[i]) * invDir[i];
t_max[i] = (pMax[i] - ray.origin[i]) * invDir[i];
}
}
for (int i = 0; i < 3; i++) {
t_enter = fmax(t_min[i], t_enter);
t_exit = fmin(t_max[i], t_exit);
}
return t_enter < t_exit && t_exit >= 0;
}
4.4 getIntersection遍历BVH求交
这个函数位于文件BVH.cpp
Intersection BVHAccel::getIntersection(BVHBuildNode* node, const Ray& ray) const
这个函数接受BVH树的节点
node和一个光线类ray，功能是从node往下递归，找到光线射中的最前面的物体(object),返回的Intersection信息包括射中的物体，碰撞点的坐标，法线，碰撞的距离。注意找到的物体一定是最前面的，最多只有一个。返回值的类型为结构体
Intersection，它含有以下属性struct Intersection
{
Intersection(){
happened=false;
coords=Vector3f();
normal=Vector3f();
distance= std::numeric_limits<double>::max();
obj =nullptr;
m=nullptr;
}
bool happened;
Vector3f coords;
Vector3f normal;
double distance;
Object* obj;
Material* m;
};
结构体
BVHBuildNode的定义如下：struct BVHBuildNode {
Bounds3 bounds;
BVHBuildNode *left;
BVHBuildNode *right;
Object* object;
public:
int splitAxis=0, firstPrimOffset=0, nPrimitives=0;
// splitAxis 表示当前节点的分割轴012分别对应xyz
// firstPrimOffset 表示首个元素偏移量，表明要处理的第一个元素在数组中的位置
// nPrimitives 表示元素总数
// BVHBuildNode Public Methods
BVHBuildNode(){
bounds = Bounds3();
left = nullptr;right = nullptr;
object = nullptr;
}
};
由于函数
IntersectP()要用到invDir和dirIsNeg，并且这两个参数是和ray完全绑定的，所以我修改了函数 getIntersection() 的定义，加入了参数invDir和dirIsNeg。最终getIntersection() 的实现代码如下：Intersection BVHAccel::getIntersection(BVHBuildNode* node, const Ray& ray, const Vector3f& invDir,
const std::array<int, 3>& dirIsNeg) const
{
Intersection isect;
// TODO Traverse the BVH to find intersection
//ray和node包围盒没有交点，返回默认isect
if(! node->bounds.IntersectP(ray, invDir, dirIsNeg)) {
return isect;
}
//ray和node的包围盒有交点
//node为叶节点
if(node->left==nullptr && node->right==nullptr) {
//调用object类(可能是Triangle或者MeshTriangle)的getIntersection方法,返回相交点的信息
return node->object->getIntersection(ray);
} else if (node->left==nullptr) {
return getIntersection(node->right, ray, invDir, dirIsNeg);
} else if (node->right==nullptr) {
return getIntersection(node->left, ray, invDir, dirIsNeg);
}
//node不是叶节点
//分别计算两个孩子节点的相交信息,取最先相交的孩子节点递归下去
float t_left;
float t_right;
float t_second;
t_left = node->left->bounds.IntersectT(ray, invDir, dirIsNeg);
t_right = node->right->bounds.IntersectT(ray, invDir, dirIsNeg);
BVHBuildNode *first_node;
BVHBuildNode *second_node;
if(t_left <= t_right) {
first_node = node->left;
second_node = node->right;
t_second = t_right;
} else {
first_node = node->right;
second_node = node->left;
t_second = t_left;
}
Intersection first_isect = getIntersection(first_node, ray, invDir, dirIsNeg);
if( first_isect.happened && first_isect.distance < t_second) {
return first_isect;
}
Intersection second_isect = getIntersection(second_node, ray, invDir, dirIsNeg);
if( !first_isect.happened) {
return second_isect;
} else if( !second_isect.happened) {
return first_isect;
} else {
return first_isect.distance < second_isect.distance ? first_isect : second_isect;
}
}
代码这样设计的核心在于优化了满足条件
first_isect.happened && first_isect.distance < t_second
时的情况，在这种条件下，程序只需计算一个孩子节点的
getIntersection()，不需要两个孩子节点都计算。由于
getIntersection()的参数列表改变了，所以在函数Intersect()中调用它之前要先得到invDir, dirIsNeg，实现代码如下Intersection BVHAccel::Intersect(const Ray& ray) const
{
Intersection isect;
Vector3f invDir = ray.direction_inv;
std::array<int,3> dirIsNeg;
for (int i = 0; i < 3; i++) {
dirIsNeg[i] = (int)(ray.direction[i] < 0);
}
if (!root)
return isect;
isect = BVHAccel::getIntersection(root, ray, invDir, dirIsNeg);
return isect;
}
5 问题与解决方法
5.1 文件读取问题
原本读取模型的语句为
MeshTriangle bunny("../models/bunny/bunny.obj");
如果在Assignment6目录下执行下述指令
./build/RayTracing.exe
会导致读取失败，会有下面的报错
Assertion failed: loader.LoadedMeshes.size() == 1, file E:\games101\Homework6\Assignment6\Triangle.hpp, line 84
这是因为这样的话相对路径会以程序运行时的工作路径为基准，而不是以程序可执行文件所在的路径为基准。
正确方法是先
cd ./build
再执行
./RayTracing.exe
5.2 渲染物体没有显示
我发现渲染的结果中没有显示物体，全屏都是背景颜色。这很有可能是因为光线碰撞检测出了问题。在一开始我检查了IntersectP() 和 getIntersection()，发现它们都没有问题。最终才发现问题出在
Intersection BVHAccel::Intersect(const Ray& ray) const
这个函数。在计算
dirIsNeg时，我原本写的是(int)(ray.direction[i] > 0),由于把小于号写成了大于号，导致所有的检测都出错了。
启示
在出错时一定要先根据错误类型进行垂直检查。
比如错误为渲染结果中一个三角面都没有显示。先分析错误的特点。这种错误是0(不显示)和1(显示)之间的判断错误，而不是1和2之间这种计算错误。所以检查的重点要放在光线相交的判断逻辑上，围绕这个重点垂直向下进行检查。要检查与光线相交检测有关的判断逻辑。检查的过程不能只停留在表面几个函数，尽量层层向下。
6 最终结果
7 Cpp特性
7.1 emplace_back()
std::vector<Triangle> triangles;
triangles.emplace_back(face_vertices[0], face_vertices[1],
face_vertices[2], new_mat);
emplace_back(...)是容器的 “原地构造” 成员函数 —— 直接在容器的内存空间中构造新对象，而非先创建临时对象再拷贝 / 移动到容器中，效率更高；逻辑上与下述语句等价
// 先创建临时三角形对象，再拷贝到 triangles（效率更低）
triangles.push_back( 三角形类型(face_vertices[0], face_vertices[1], face_vertices[2], new_mat) );
7.2 std::sort()
std::sort(objects.begin(), objects.end(), [](auto f1, auto f2) {
return f1->getBounds().Centroid().x <
f2->getBounds().Centroid().x;
});
7.3 std::vector<>(beginning, ending)
auto leftshapes = std::vector<Object*>(beginning, middling);
采用
vector 的 范围构造函数：vector(InputIt first, InputIt last)，作用是将 [first, last) 区间内的元素复制到新创建的 vector 中。
7.4 用于计时的标准库<chrono>
auto start = std::chrono::system_clock::now();
r.Render(scene);
auto stop = std::chrono::system_clock::now();
std::cout << "Render complete: \n";
std::cout << "Time taken: " << std::chrono::duration_cast<std::chrono::hours>(stop - start).count() << " hours\n";
std::cout << " : " << std::chrono::duration_cast<std::chrono::minutes>(stop - start).count() << " minutes\n";
std::cout << " : " << std::chrono::duration_cast<std::chrono::seconds>(stop - start).count() << " seconds\n";
7.5 关键字inline
inline 是 C/C++ 中的关键字，核心作用是建议编译器将函数调用 “内联展开”（而非常规的函数调用跳转），本质是一种编译优化手段。主要有以下几个特点
- 建议而非强制：
inline是编译器的 “优化建议”，不是命令。如果函数体过大（如数百行代码）、有循环 / 递归，或被复杂指针指向，编译器可能忽略inline，按普通函数处理。 - 必须在调用前定义：不同于普通函数（声明和定义可分离），
inline函数的定义需放在头文件中（或调用代码之前），否则编译器无法在调用处展开（链接时可能报错 “未定义引用”）。 - 避免代码膨胀：若
inline函数被频繁调用且函数体较大，展开后会导致目标文件体积增大（代码冗余），可能反而降低性能（缓存命中率下降），因此仅适合短小、高频调用的函数（如工具类小函数、getter/setter）。
7.6 数学库cmath
fmax(a, b), fmin(a, b)
这两个函数可以用来求浮点数的最大值和最小值
7.7 浮点数范围
#include<limits>
std::numeric_limits<float>::max(); //float可以表示的最大正数
std::numeric_limits<float>::min(); //float可以表示的最小正数
评论
如果你已登录 GitHub，就可以直接在这里评论。