总览
在之前的编程练习中，我们实现了基础的光线追踪算法，具体而言是光线传输、光线与三角形求交。我们采用了这样的方法寻找光线与场景的交点：遍历场景中的所有物体，判断光线是否与它相交。在场景中的物体数量不大时，该做法可以取得良好的结果，但当物体数量增多、模型变得更加复杂，该做法将会变得非常低效。因此，我们需要加速结构来加速求交过程。在本次练习中，我们重点关注物体划分算法Bounding Volume Hierarchy (BVH)。本练习要求你实现Ray-BoundingVolume 求交与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.

上一次的两个函数需要改一改：

1. Render() in Renderer.cpp:
   for循环里面的内容，主要是这次加了Ray类，更新了函数参数形式，改一下就好了

// 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));
            framebuffer[m++] = scene.castRay(Ray(eye_pos, dir), 0);

2. Triangle::getIntersection in Triangle.hpp：
   和作业5一样的，不过要更新自己设定的Intersection

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

    if (dotProduct(ray.direction, normal) > 0)
        return inter;
    double u, v, t_tmp = 0;
    Vector3f pvec = crossProduct(ray.direction, e2);
    double det = dotProduct(e1, pvec);
    if (fabs(det) < EPSILON)
        return inter;

    double det_inv = 1. / det;
    Vector3f tvec = ray.origin - v0;
    u = dotProduct(tvec, pvec) * det_inv;
    if (u < 0 || u > 1)
        return inter;
    Vector3f qvec = crossProduct(tvec, e1);
    v = dotProduct(ray.direction, qvec) * det_inv;
    if (v < 0 || u + v > 1)
        return inter;
    t_tmp = dotProduct(e2, qvec) * det_inv;

    // TODO find ray triangle intersection
    inter.happened = true;
    inter.coords = ray.origin + t_tmp * ray.direction;
    inter.normal = this->normal;
    inter.distance = t_tmp;
    inter.obj = this;
    inter.m = this->m;

    return inter;
}

3. IntersectP(const Ray& ray, const Vector3f& invDir,const std::array<int, 3>& dirIsNeg) in the Bounds3.hpp
   

需要理解一下Bounds3然后用AABB的方式判断有没有交，把第三个参数去掉了，没有用到

inline bool Bounds3::IntersectP(const Ray& ray, const Vector3f& invDir) 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 = (this->pMin - ray.origin) * invDir;
    Vector3f tmax = (this->pMax - ray.origin) * invDir;
    if (ray.direction.x < 0) std::swap(tmin.x, tmax.x);
    if (ray.direction.y < 0) std::swap(tmin.y, tmax.y);
    if (ray.direction.z < 0) std::swap(tmin.z, tmax.z);
    float tenter = fmax(tmin.x, fmax(tmin.y, tmin.z));
    float texit = fmin(tmax.x, fmin(tmax.y, tmax.z));
    if (tenter < texit && texit > 0)return true;
    return false;
}

4. getIntersection(BVHBuildNode* node, const Ray ray)in BVH.cpp
   也是递归，没有交就跳出返回空的Intersection,有交但没有左右子节点就返回和本身的交，否则就对左右子节点分别进行判断，取交的距离最近的一个（因为另一个收到的光线会被遮挡）

Intersection BVHAccel::getIntersection(BVHBuildNode* node, const Ray& ray) const
{
    // TODO Traverse the BVH to find intersection
    Intersection intersect;
    if (!node->bounds.IntersectP(ray, ray.direction_inv)) return intersect;
    if (node->left == nullptr && node->right == nullptr) {
        intersect = node->object->getIntersection(ray);
        return intersect;
    }
    Intersection intersectL = getIntersection(node->left, ray);
    Intersection intersectR = getIntersection(node->right, ray);
    return intersectL.distance < intersectR.distance ? intersectL : intersectR;

}

5. 附加分SAH(Surface Area Heuristic)
   参考：GAMES101作业6解析及SVH加速实现
   文章写得很详细，但是我自己电脑这反而跑得比BVH要慢，而且慢很多，BVH十几秒，SAH四分多钟，十分离谱……可能是计算cost引起的？
6. 结果