GAMES101作业6-BVH完成全过程

痛定思痛。 2023-09-28 08:48 56阅读 0赞

**目录**

作业要求

Render.cpp

TODO:需要的补充内容

Triangle.hpp

框架

Ray.hpp -> struct Ray

Intersection.hpp -> struct Intersection

判断有无交点

TODO:需要的补充内容

Bounds3.hpp

TODO:需要的补充内容

BVH.cpp

框架

BVHAccel::BVHAccel()

recursiveBuild()

框架

分类讨论&递归

TODO:getIntersection()

遇到的问题汇总

报错C4996: 'fopen'不安全

解决方法

报错：Assertion failed

解决方法

结果展示

渲染时间过长的原因及解决方法

--------------------

## 作业要求 ##

![d4daa033d9bd43f0b6bbc2943f07ab91.png][]

一共有四个内容需要我们补充，其中前面的两个过程与作业5类似。

## Render.cpp ##

光线生成，这里跟作业5的基本相同，就不做过多的注释。

### TODO:需要的补充内容 ###

void Renderer::Render(const Scene& scene)
    {
        std::vector<Vector3f> framebuffer(scene.width * scene.height);//设定一个数组储存图片颜色，
    
        float scale = tan(deg2rad(scene.fov * 0.5));
        float imageAspectRatio = scene.width / (float)scene.height;
        Vector3f eye_pos(-1, 5, 10);
        int m = 0;
        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 = normalize(Vector3f(x, y, -1));
                //castRay(const Ray ray, int depth)
                //Ray(ori, dir, _t=0)
                Ray ray(eye_pos, dir);
                framebuffer[m++] = scene.castRay(ray, 0);
                
    
            }
            UpdateProgress(j / (float)scene.height);
        }
        UpdateProgress(1.f);
    
        // save framebuffer to file
        FILE* fp = fopen("binary.ppm", "wb");
        (void)fprintf(fp, "P6\n%d %d\n255\n", scene.width, scene.height);
        for (auto i = 0; i < scene.height * scene.width; ++i) {
            static unsigned char color[3];
            color[0] = (unsigned char)(255 * clamp(0, 1, framebuffer[i].x));
            color[1] = (unsigned char)(255 * clamp(0, 1, framebuffer[i].y));
            color[2] = (unsigned char)(255 * clamp(0, 1, framebuffer[i].z));
            fwrite(color, 1, 3, fp);
        }
        fclose(fp);    
    }

## Triangle.hpp ##

补充光线与三角形求交的getIntersection()函数.

### 框架 ###

inline Intersection Triangle::getIntersection(Ray ray)
    {
        Intersection inter;
        ...
        return inter;
    }

其中包含的两个结构 Ray 和 Intersection：

#### Ray.hpp -> struct Ray ####

struct Ray{
        //Destination = origin + t*direction
        Vector3f origin;
        Vector3f direction, direction_inv;
        double t;//transportation time,
        double t_min, t_max;
    
        Ray(const Vector3f& ori, const Vector3f& dir, const double _t = 0.0): origin(ori), direction(dir),t(_t) {
            direction_inv = Vector3f(1./direction.x, 1./direction.y, 1./direction.z);
            t_min = 0.0;
            t_max = std::numeric_limits<double>::max();
    
        }
    
        Vector3f operator()(double t) const{return origin+direction*t;}
    
        friend std::ostream &operator<<(std::ostream& os, const Ray& r){
            os<<"[origin:="<<r.origin<<", direction="<<r.direction<<", time="<< r.t<<"]\n";
            return os;
        }
    };

#### Intersection.hpp -> struct Intersection ####

struct Intersection
    {
        Intersection(){
            happened=false;
            coords=Vector3f();//交点坐标？maybe
            normal=Vector3f();//面法线
            distance= std::numeric_limits<double>::max();
            obj =nullptr;
            m=nullptr;
        }
        bool happened;
        Vector3f coords;
        Vector3f normal;
        double distance;
        Object* obj;
        Material* m;
    };

### 判断有无交点 ###

与作业5相同，这里用到了以下与面求交的公式以及表示方法：

![6af73453b3f676790c244e0fb0705898.png][]

![a740f5e13ad1a864531d5e5764cb0595.png][]

...
        if (dotProduct(ray.direction, normal) > 0)//光线从里面打的
            return inter;//无交点
        double u, v, t_tmp = 0;
        Vector3f pvec = crossProduct(ray.direction, e2);//S1
        double det = dotProduct(e1, pvec);//E1·S1
        if (fabs(det) < EPSILON)//det趋近于0，光线与面平行
            return inter;
    
        double det_inv = 1. / det;
        Vector3f tvec = ray.origin - v0;
        u = dotProduct(tvec, pvec) * det_inv;
        if (u < 0 || u > 1)//u∈[0,1]
            return inter;
        Vector3f qvec = crossProduct(tvec, e1);
        v = dotProduct(ray.direction, qvec) * det_inv;
        if (v < 0 || u + v > 1)//v∈[0,1] v+u∈[0,1]
            return inter;
        t_tmp = dotProduct(e2, qvec) * det_inv;
    
        if (t_tmp < 0)//t>0 ray是射线
            return inter;
    ...

### TODO:需要的补充内容 ###

这里要明确一点，返回的是一个Intersection类的返回值，因此在储存交点参数的时候，我们要给inter中的一些变量赋值。

...
        // TODO find ray triangle intersection
        //给inter所有参数赋予值
        inter.happened = true;//有交点
        inter.coords = ray(t_tmp);//vector3f operator()(double t){return origin+dir*t};
        inter.normal = normal;//法向量
        inter.distance = t_tmp;//double distance
        inter.obj = this;//this是所有成员函数的隐藏函数，一个const指针，指向当前对象（正在使用的对象）
        inter.m = m;//class 材质 m
        return inter;
    ...

## Bounds3.hpp ##

这里需要补充的IntersectP()函数，用以判断光线是否与包围盒相交。

### TODO:需要的补充内容 ###

函数类型是bool，返回true/false，其中，Bounds3是一个Bounds3.hpp中定义的一个class类。

inline bool Bounds3::IntersectP(const Ray& ray, const Vector3f& invDir,
                                    const std::array<int, 3>& dirIsNeg) const
    {
        //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
        //判断包围盒Bounding Box与光线是否相交
        //tenter = max{tmin} texit = min{tmax}
        //先给个无穷初值
        double tenter = -std::numeric_limits<double>::infinity();
        double texit = std::numeric_limits<double>::infinity();
        for (int i = 0; i < 3; i++) {
            //求三个轴的tmin,tmax
            // invDir: ray direction(x,y,z), invDir=(1.0/x,1.0/y,1.0/z),
            double tmin = (pMin[i] - ray.origin[i]) * invDir[i];
            double tmax = (pMax[i] - ray.origin[i]) * invDir[i];
            //用dirIsNeg判断光线方向
            if (!dirIsNeg[i])//如果i<0,则在i轴光线方向为负，则从pmax进入，pmin离开，swap tmin和tmaxx
                std::swap(tmin, tmax);
            tenter = std::max(tenter,tmin);
            texit = std::min(texit, tmax);
        }
        return tenter < texit&& texit >= 0;
    }

## BVH.cpp ##

#### 框架 ####

Intersection BVHAccel::getIntersection(BVHBuildNode* node, const Ray& ray) const
    {
        // TODO Traverse the BVH to find intersection
        ...
    }

在填充之前，有必要理解BVH是怎样运行的，下面我们来简单的注释以下BVH.cpp每一部分代码的含义。

**（1）给了一些初步的定义值，主要是定义了开始时间和结束时间。**

### BVHAccel::BVHAccel() ###

//BVH.hpp定义的一个类
    //class::class():prop1(..),prop2(..){}
    BVHAccel::BVHAccel(std::vector<Object*> p, int maxPrimsInNode,
                       SplitMethod splitMethod)
        : maxPrimsInNode(std::min(255, maxPrimsInNode)), splitMethod(splitMethod),
          primitives(std::move(p))//定初值
    {
        time_t start, stop;//开始&停止时间
        time(&start);//定初值
        if (primitives.empty())
            return;
    
        root = recursiveBuild(primitives);
    
        time(&stop);
        double diff = difftime(stop, start);
        int hrs = (int)diff / 3600;
        int mins = ((int)diff / 60) - (hrs * 60);
        int secs = (int)diff - (hrs * 3600) - (mins * 60);
    
        printf(
            "\rBVH Generation complete: \nTime Taken: %i hrs, %i mins, %i secs\n\n",
            hrs, mins, secs);
    }

**（2）定义了递归求包围盒的函数.**

### recursiveBuild() ###

#### 框架 ####

BVHBuildNode* BVHAccel::recursiveBuild(std::vector<Object*> objects)
    {
        //创建了一个节点
        BVHBuildNode* node = new BVHBuildNode();
        //遍历
        // Compute bounds of all primitives in BVH node
        Bounds3 bounds;
        for (int i = 0; i < objects.size(); ++i)
            //遍历每个物体的AABB，然后整合起来得到一个大的AABB
            //Union(b1,b2) 给出b1b2整合起来的AABB
            bounds = Union(bounds, objects[i]->getBounds());
        
        ...
    
        return node;
    }

出现了新的函数：

**（1）BVHVuildNode**

是BVH.hpp中定义的一个struct：定义的一个表示节点的strcut，用于储存叶节点的左右子节点，用于之后的递归。

struct BVHBuildNode {
        Bounds3 bounds;
        BVHBuildNode *left;
        BVHBuildNode *right;
        Object* object;
    
    public:
        int splitAxis=0, firstPrimOffset=0, nPrimitives=0;
        // BVHBuildNode Public Methods
        BVHBuildNode(){
            bounds = Bounds3();
            left = nullptr;right = nullptr;
            object = nullptr;
        }
    };

**（2）Union()**

求两个box的一个大的边界AABB

inline Bounds3 Union(const Bounds3& b, const Vector3f& p)
    {
        Bounds3 ret;
        ret.pMin = Vector3f::Min(b.pMin, p);
        ret.pMax = Vector3f::Max(b.pMax, p);
        return ret;
    }

#### 分类讨论&递归 ####

场景中的物体个数分为三种情况：

①只有一个物体

...
    //如果只有一个物体，创建叶节点赋予值，然后这个叶节点的左右子节点为空
        if (objects.size() == 1) {
            node->bounds = objects[0]->getBounds();
            node->object = objects[0];
            node->left = nullptr;
            node->right = nullptr;
            return node;
        }
        //如果只有两个物体，则把两个物体分别作为左右子节点进行遍历，下一个recur这两个物体就可以分别作为size==1的叶节点了
        else if (objects.size() == 2) {
            node->left = recursiveBuild(std::vector{objects[0]});
            node->right = recursiveBuild(std::vector{objects[1]});
            node->bounds = Union(node->left->bounds, node->right->bounds);
            return node;
        }
    ...

②只有两个物体：

...
    //如果只有两个物体，则把两个物体分别作为左右子节点进行遍历，下一个recur这两个物体就可以分别作为size==1的叶节点了
        else if (objects.size() == 2) {
            node->left = recursiveBuild(std::vector{objects[0]});
            node->right = recursiveBuild(std::vector{objects[1]});
            node->bounds = Union(node->left->bounds, node->right->bounds);
            return node;
        }
    ...

③物体>2个：

//>2个物体
        else {
            Bounds3 centroidBounds;
            for (int i = 0; i < objects.size(); ++i)
                //得到所有box的中心覆盖的范围AABB
                centroidBounds =
                    Union(centroidBounds, objects[i]->getBounds().Centroid());//centroid()得到box的中心
            //得到覆盖范围最大的轴（x->0 y->1 z->2）
            int dim = centroidBounds.maxExtent();
            //在该轴进行排序，升序排列
            switch (dim) {
            case 0://x
                std::sort(objects.begin(), objects.end(), [](auto f1, auto f2) {
                    return f1->getBounds().Centroid().x <
                           f2->getBounds().Centroid().x;
                });
                break;
            case 1://y
                std::sort(objects.begin(), objects.end(), [](auto f1, auto f2) {
                    return f1->getBounds().Centroid().y <
                           f2->getBounds().Centroid().y;
                });
                break;
            case 2://z
                std::sort(objects.begin(), objects.end(), [](auto f1, auto f2) {
                    return f1->getBounds().Centroid().z <
                           f2->getBounds().Centroid().z;
                });
                break;
            }
            //对半分
            auto beginning = objects.begin();
            auto middling = objects.begin() + (objects.size() / 2);
            auto ending = objects.end();
            //分成左右两份，分别进行
            auto leftshapes = std::vector<Object*>(beginning, middling);
            auto rightshapes = std::vector<Object*>(middling, ending);
    
            assert(objects.size() == (leftshapes.size() + rightshapes.size()));
            //开始递归了，把叶节点不断分成左右两个子节点，直到到了最后只剩一个物体
            node->left = recursiveBuild(leftshapes);
            node->right = recursiveBuild(rightshapes);
    
            node->bounds = Union(node->left->bounds, node->right->bounds);
        }

### TODO:getIntersection() ###

这里主要是要有个分类的思路，我在代码注释里展示出来了，具体看代码就好：

Intersection BVHAccel::getIntersection(BVHBuildNode* node, const Ray& ray) const
    {
        // TODO Traverse the BVH to find intersection
        //递归调用Bounds3::intersectP
        Intersection res;
        // 首先判断这个ray与当前box是否有交点：
        // 1.如果没有交点 -> 那就不用继续了，因为再进行细分也没有意义，直接返回当前的intersection
        std::array<int, 3> dirIsNeg = { int(ray.direction.x>0),int(ray.direction.y > 0),int(ray.direction.z > 0) };
        if (!node->bounds.IntersectP(ray, ray.direction_inv, dirIsNeg)) {
            return res;
        }
        // 2.如果有交点 -> 2.1若该点无子节点，则返回该交点，该节点是没有子节点，可以进行BVN判断是否相交
        if (node->left == nullptr && node->right == nullptr) {
            res = node->object->getIntersection(ray);
            return res;
        }
        //2.1该点有子节点，则左右子节点分别判断，继续递归
        Intersection resleft, resright;
        resleft = getIntersection(node->left, ray);
        resright = getIntersection(node->right, ray);
        return resleft.distance < resright.distance ? resleft : resright;
    }

## 遇到的问题汇总 ##

### 报错C4996: 'fopen'不安全 ###

![bd31129b28a14441a1ffaf62b0223383.png][]

#### 解决方法 ####

属性 -> C/C++ -> 预处理器 -> 定义 ->加上以下定义即可：

_CRT_SECURE_NO_WARNINGS

![7d3b74a7738c44d3b94c3efef354ee38.png][]

![c5c27ef9139843b5b0a6cc67d33ab6f9.png][]

### 报错：Assertion failed ###

![ea20913a4ef141db86e58b8dbde97399.png][]

#### 解决方法 ####

检查main.cpp里obj模型的路径，如果是两个点，需要将model文件夹放在VS项目文件夹下面才行。

![54305360e67840b2a580c60936f11b68.png][]

![f155c5dd87634ed2a86c132f5b4e1f22.png][]

## 结果展示 ##

注意，跟作业5一样，输出的是ppm文件，可以用PS等软件打开再保存成png等图片格式即可。

![265413df9a534104a865f8e06d68471d.png][]

吐槽：用时80min我真的会谢。。。电脑太拉了TAT，迟早给他换掉！！

--------------------

## 渲染时间过长的原因及解决方法 ##

这里是做完作业7后的我，又回来复盘了！

作业6渲染时长竟然有快80min，后来我发现大家大部分都是用了几秒就完成了，开始回来找问题，后来看到了这个问题：

[作业6渲染时间过长是为什么 – 计算机图形学与混合现实在线平台 (games-cn.org)][6_ _ _ _games-cn.org]

其中，有两个人给了问题的解决方法：

![19a4b058e4b9400d89199f13a3701cd0.png][]

我再回去看了一眼自己IntersectP函数：

**竟然用了一个循环!!!**

先甩一下把循环消除后的解决办法，**用时11s**

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
        Vector3f tmin = (pMin - ray.origin) * invDir;
        Vector3f tmax = (pMax - ray.origin) * invDir;
        Vector3f dir = ray.direction;
        if (dir.x < 0)
            std::swap(tmin.x, tmax.x);
        if (dir.y < 0)
            std::swap(tmin.y, tmax.y);
        if (dir.z < 0)
            std::swap(tmin.z, tmax.z);
        float texit = std::min(tmax.x, std::min(tmax.y, tmax.z));
        float tenter = std::max(tmin.x, std::max(tmin.y, tmin.z));
        return tenter < texit&& tenter > 0;
    }

![bde6d01adf5f4dd3825f7aa236b719c3.png][]

11s VS 80min 很多了！那么为什么会这样呢？道理其实很简单，递归如果有循环相当于指数增长了，用时也会爆炸增长，因此以后如果遇到这种需要取值的可以选择其他的方法，尽量避免循环的使用~【X】

【2023.6.13补充】其实时间差别不是循环的影响，我后来发现，循环用不用只是20s和10s的差别，真正原因是在tenter和texit那里max和min用错了导致的问题！

[d4daa033d9bd43f0b6bbc2943f07ab91.png]: https://img-blog.csdnimg.cn/d4daa033d9bd43f0b6bbc2943f07ab91.png
[6af73453b3f676790c244e0fb0705898.png]: https://img-blog.csdnimg.cn/img_convert/6af73453b3f676790c244e0fb0705898.png
[a740f5e13ad1a864531d5e5764cb0595.png]: https://img-blog.csdnimg.cn/img_convert/a740f5e13ad1a864531d5e5764cb0595.png
[bd31129b28a14441a1ffaf62b0223383.png]: https://img-blog.csdnimg.cn/bd31129b28a14441a1ffaf62b0223383.png
[7d3b74a7738c44d3b94c3efef354ee38.png]: https://img-blog.csdnimg.cn/7d3b74a7738c44d3b94c3efef354ee38.png
[c5c27ef9139843b5b0a6cc67d33ab6f9.png]: https://img-blog.csdnimg.cn/c5c27ef9139843b5b0a6cc67d33ab6f9.png
[ea20913a4ef141db86e58b8dbde97399.png]: https://img-blog.csdnimg.cn/ea20913a4ef141db86e58b8dbde97399.png
[54305360e67840b2a580c60936f11b68.png]: https://img-blog.csdnimg.cn/54305360e67840b2a580c60936f11b68.png
[f155c5dd87634ed2a86c132f5b4e1f22.png]: https://img-blog.csdnimg.cn/f155c5dd87634ed2a86c132f5b4e1f22.png
[265413df9a534104a865f8e06d68471d.png]: https://img-blog.csdnimg.cn/265413df9a534104a865f8e06d68471d.png
[6_ _ _ _games-cn.org]: https://games-cn.org/forums/topic/zuoye6xuanranshijianguochangshiweishenme/
[19a4b058e4b9400d89199f13a3701cd0.png]: https://img-blog.csdnimg.cn/19a4b058e4b9400d89199f13a3701cd0.png
[bde6d01adf5f4dd3825f7aa236b719c3.png]: https://img-blog.csdnimg.cn/bde6d01adf5f4dd3825f7aa236b719c3.png