| GAMES101 | 您所在的位置：网站首页 › games101作业2不能完全覆盖 › GAMES101 |
GAMES101
|
总览
在之前的编程练习中，我们实现了基础的光线追踪算法，具体而言是光线传输、光线与三角形求交。我们采用了这样的方法寻找光线与场景的交点：遍历场景中的所有物体，判断光线是否与它相交。在场景中的物体数量不大时，该做法可以取得良好的结果，但当物体数量增多、模型变得更加复杂，该做法将会变得非常低效。因此，我们需要加速结构来加速求交过程。在本次练习中，我们重点关注物体划分算法 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& dirIsNeg) in the Bounds3.hpp: 这个函数的作用是判断包围盒 BoundingBox 与光线是否相交，你需要按照课程介绍的算法实现求交过程。 • getIntersection(BVHBuildNode* node, const Ray ray)in BVH.cpp: 建立 BVH 之后，我们可以用它加速求交过程。该过程递归进行，你将在其中调用你实现的 Bounds3::IntersectP. 编译运行基础代码只依赖于 CMake，下载基础代码后，执行下列命令，就可以编译这 个项目： 1$ mkdir build 2$ cd ./build 3$ cmake .. 4$ make在此之后，你就可以通过 ./Raytracing 来执行程序。 代码框架我们修改了代码框架中的如下内容： • Material.hpp: 我们从将材质参数拆分到了一个单独的类中，现在每个物体实例都可以拥有自己的材质。 • Intersection.hpp: 这个数据结构包含了相交相关的信息。 • Ray.hpp: 光线类，包含一条光的源头、方向、传递时间 t 和范围 range. • Bounds3.hpp: 包围盒类，每个包围盒可由 pMin 和 pMax 两点描述（请思考为什么）。Bounds3::Union 函数的作用是将两个包围盒并成更大的包围盒。与材质一样，场景中的每个物体实例都有自己的包围盒。 • BVH.hpp: BVH 加速类。场景 scene 拥有一个 BVHAccel 实例。从根节点开 始，我们可以递归地从物体列表构造场景的 BVH. Render() in Renderer.cpp生成光线，我们需要的是找到这些像素在栅格空间（raster space）中的坐标与在世界空间(world space)中表达的相同像素的坐标之间的关系。具体原理可见，改博主写的非常清楚 // The main render function. This where we iterate over all pixels in the image, // generate primary rays and cast these rays into the scene. The content of the // framebuffer is saved to a file. void Renderer::Render(const Scene& scene) { std::vector 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) * scale * imageAspectRatio ; 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)); // Don't forget to normalize this direction! 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::getIntersection in Triangle.hpp这一部分是判断光线是否与三角形相交，具体用的是Möller–Trumbore 算法。 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; if(t_tmp0),int(y>0),int(z>0)], use this to simplify your logic // TODO test if ray bound intersects float t_min_x = (pMin.x - ray.origin.x)*invDir[0]; float t_min_y = (pMin.y - ray.origin.y)*invDir[1]; float t_min_z = (pMin.z - ray.origin.z)*invDir[2]; float t_max_x = (pMax.x - ray.origin.x)*invDir[0]; float t_max_y = (pMax.y - ray.origin.y)*invDir[1]; float t_max_z = (pMax.z - ray.origin.z)*invDir[2]; if (dirIsNeg[0]){ float t = t_min_x; t_min_x = t_max_x; t_max_x = t; } if (dirIsNeg[1]){ float t = t_min_y; t_min_y = t_max_y; t_max_y = t; } if (dirIsNeg[2]){ float t = t_min_z; t_min_z = t_max_z; t_max_z = t; } float t_enter = std::max(t_min_x,std::max(t_min_y,t_min_z)); float t_exit = std::min(t_max_x,std::min(t_max_y,t_max_z)); if (t_enter < t_exit && t_exit >=0){ return true; } return false; } getIntersection(...) in BVH.cpp Intersection BVHAccel::getIntersection(BVHBuildNode* node, const Ray& ray) const { // TODO Traverse the BVH to find intersection Intersection inter; Vector3f invdir(1 / ray.direction.x , 1 / ray.direction.y , 1 / ray.direction.z); //判断射线的方向正负，如果负，为1；bounds3.hpp中会用到。 std::array dirIsNeg; dirIsNeg[0] = ray.direction.x < 0; dirIsNeg[1] = ray.direction.y < 0; dirIsNeg[2] = ray.direction.z < 0; //没有交点 if (!node->bounds.IntersectP(ray,invdir,dirIsNeg)){ return inter; } //有交点，且该点为叶子节点，去和三角形求交 if (node -> left ==nullptr && node -> right == nullptr){ return node -> object -> getIntersection(ray); } //该点为中间节点，继续判断，并返回最近的包围盒交点 Intersection hit1 = getIntersection(node->left , ray); Intersection hit2 = getIntersection(node->right , ray); return hit1.distance < hit2.distance ? hit1:hit2; } 运行结果
该部分原理可参考SAH， // BVHBuildNode* BVHAccel::recursiveSAH(std::vector objects) { BVHBuildNode* node = new BVHBuildNode(); // Compute bounds of all primitives in BVH node Bounds3 bounds; for (int i = 0; i < objects.size(); ++i) bounds = Union(bounds, objects[i]->getBounds()); if (objects.size() == 1) { // Create leaf _BVHBuildNode_ node->bounds = objects[0]->getBounds(); node->object = objects[0]; node->left = nullptr; node->right = nullptr; return node; } else if (objects.size() == 2) { node->left = recursiveSAH(std::vector{objects[0]}); node->right = recursiveSAH(std::vector{objects[1]}); node->bounds = Union(node->left->bounds, node->right->bounds); return node; } else{ double minCost = std::numeric_limits::max(); int bestDim = 0; int part = 10; Bounds3 centroidBounds; for (int i = 0; i < objects.size(); ++i) centroidBounds = Union(centroidBounds, objects[i]->getBounds().Centroid()); int dim = centroidBounds.maxExtent(); //通过getBounds()的Centroid()方法找到所有物体的中心，并通过Union函数找到它们覆盖的范围， //然后通过maxExtent()方法判断到底是哪个轴覆盖的范围大，返回0，就是x轴范围大，返回1就是y轴大，2就是z轴大 switch (dim) { //判断完后，根据不同的情况，将物体根据中心坐标分别按照z、y、z轴排序 case 0: std::sort(objects.begin(), objects.end(), [](auto f1, auto f2) { return f1->getBounds().Centroid().x < f2->getBounds().Centroid().x; }); break; case 1: std::sort(objects.begin(), objects.end(), [](auto f1, auto f2) { return f1->getBounds().Centroid().y < f2->getBounds().Centroid().y; }); break; case 2: 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 ending = objects.end(); auto middling = objects.begin() + (objects.size()/2); auto size = objects.size(); for (int dim = 0; dim getBounds().Centroid()); } for (int i = 0 ; i < leftShapes.size();++i){ rightBounds = Union(rightBounds , rightShapes[i]->getBounds().Centroid()); } auto leftS = leftBounds.SurfaceArea(); auto rightS = rightBounds.SurfaceArea(); auto S = leftS + rightS; auto cost = leftS / S * leftShapes.size() + rightS / S * rightShapes.size(); if (cost < minCost){ minCost = cost; bestDim = dim; } } middling = objects.begin() + size * bestDim / part ; auto leftShapes = std::vector(beginning,middling); auto rightShapes = std::vector(middling, ending); assert(objects.size() == (leftShapes.size() + rightShapes.size())); node->left = recursiveSAH(leftShapes); node->right = recursiveSAH(rightShapes); node->bounds = Union(node->left->bounds,node->right->bounds); } return node; } |
【本文地址】
公司简介
联系我们