Ray-Tracing a Polygon Mesh

News (August, 31): We are working on Scratchapixel 3.0 at the moment (current version of 2). The idea is to make the project open source by storing the content of the website on GitHub as Markdown files. In practice, that means you and the rest of the community will be able to edit the content of the pages if you want to contribute (typos and bug fixes, rewording sentences). You will also be able to contribute by translating pages to different languages if you want to. Then when we publish the site we will translate the Markdown files to HTML. That means new design as well.

That's what we are busy with right now and why there won't be a lot of updates in the weeks to come. More news about SaP 3.0 soon.

We are looking for native Engxish (yes we know there's a typo here) speakers that will be willing to readproof a few lessons. If you are interested please get in touch on Discord, in the #scratchapixel3-0 channel. Also looking for at least one experienced full dev stack dev that would be willing to give us a hand with the next design.

Feel free to send us your requests, suggestions, etc. (on Discord) to help us improve the website.

And you can also donate). Donations go directly back into the development of the project. The more donation we get the more content you will get and the quicker we will be able to deliver it to you.

10 mns read.

Ray-Tracing a Polygon Mesh

As we suggested before, ray-tracing a polygon mesh which has been triangulated is really simple. We already have a routine to compute the intersection of rays and triangles. Therefore, to test if a ray intersects a polygon mesh, all we need to do is loop over all the triangles in the mesh and test each individual triangle against the ray. However a ray may intersect more than one triangle from the mesh therefore we also need to keep track of the nearest intersection distance as we iterate over the triangles. This problem is similar to the one described in the lesson A Minimal Ray-Tracer where we had to keep track of the nearest intersected object. We will use the same technique here. In pseudo code the intersection routine looks like this (check the last chapter for the C++ implementation):

// Test if the ray interesests this triangle mesh bool intersect(const Vec3f &orig, const Vec3f &dir, float &tNear, uint32_t &triIndex, Vec2f &uv) const { uint32_t j = 0; bool isect = false; for (uint32_t i = 0; i < numTris; ++i) { const Vec3f &v0 = P[trisIndex[j]]; const Vec3f &v1 = P[trisIndex[j + 1]]; const Vec3f &v2 = P[trisIndex[j + 2]]; float t = kInfinity, u, v; if (rayTriangleIntersect(orig, dir, v0, v1, v2, t, u, v) && t < tNear) { tNear = t; uv.x = u; uv.y = v; triIndex = i; isect |= true; } j += 3; } return isect; }

We need the three vertices making up each triangle in the mesh (lines 7-9). We then pass these three points to the ray-triangle intersection routine which returns true if the ray intersects the triangle and false otherwise (we will use the Möller-Trumbore ray-triangle algorithm studied in the previous lesson). In case on an intersection, the variable \(tNear\) is set with the intersection distance (the distance from the ray origin to the intersection point on the triangle) and the barycentric coordinates of the hit point (u & v). We also keep track of the triangle index that the ray intersected as well as the barycentric coordinates of the intersected point on the triangle (lines 13-15). This will be needed later on to compute the normal and the texture coordinates at the hit point.

Creating a Poly Sphere

We need a polygon mesh to test our code. One solution is to use an existing model but this solution requires to chose a file format and write code to read and parse models exported to this format. Another solution consists of creating some simple geometry on the fly, procedurally. In this chapter, we will use this option. In the next chapter, we will render a polygon mesh defined in an external file. Building a polygon object procedurally is also an opportunity to put in practice what we learned in the previous chapter. We will generate a sphere as a 3D polygon mesh using the following code:

TriangleMesh* generatePolyShphere(float rad, uint32_t divs) { // generate points uint32_t numVertices = (divs - 1) * divs + 2; std::unique_ptr P(new Vec3f[numVertices]); std::unique_ptr N(new Vec3f[numVertices]); std::unique_ptr st(new Vec2f[numVertices]); float u = -M_PI_2; float v = -M_PI; float du = M_PI / divs; float dv = 2 * M_PI / divs; P[0] = N[0] = Vec3f(0, -rad, 0); uint32_t k = 1; for (uint32_t i = 0; i < divs - 1; i++) { u += du; v = -M_PI; for (uint32_t j = 0; j < divs; j++) { float x = rad * cos(u) * cos(v); float y = rad * sin(u); float z = rad * cos(u) * sin(v) ; P[k] = N[k] = Vec3f(x, y, z); st[k].x = u / M_PI + 0.5; st[k].y = v * 0.5 / M_PI + 0.5; v += dv, k++; } } P[k] = N[k] = Vec3f(0, rad, 0); uint32_t npolys = divs * divs; std::unique_ptr faceIndex(new uint32_t[npolys]); std::unique_ptr vertsIndex(new uint32_t[(6 + (divs - 1) * 4) * divs]); // create the connectivity lists uint32_t vid = 1, numV = 0, l = 0; k = 0; for (uint32_t i = 0; i < divs; i++) { for (uint32_t j = 0; j < divs; j++) { if (i == 0) { faceIndex[k++] = 3; vertsIndex[l] = 0; vertsIndex[l + 1] = j + vid; vertsIndex[l + 2] = (j == (divs - 1)) ? vid : j + vid + 1; l += 3; } else if (i == (divs - 1)) { faceIndex[k++] = 3; vertsIndex[l] = j + vid + 1 - divs; vertsIndex[l + 1] = vid + 1; vertsIndex[l + 2] = (j == (divs - 1)) ? vid + 1 - divs : j + vid + 2 - divs; l += 3; } else { faceIndex[k++] = 4; vertsIndex[l] = j + vid + 1 - divs; vertsIndex[l + 1] = j + vid + 1; vertsIndex[l + 2] = (j == (divs - 1)) ? vid + 1 : j + vid + 2; vertsIndex[l + 3] = (j == (divs - 1)) ? vid + 1 - divs : j + vid + 2 - divs; l += 4; } numV++; } vid = numV; } return new TriangleMesh(npolys, faceIndex, vertsIndex, P, N, st); }

Figure 1: a sphere with 5 divisions. Left: a face is created by connecting vertices. Right: the top and bottom row of the sphere are triangle fans (all the triangles share one vertex at the center). The other faces are quads.

The number of divisions represents the number of stacks and slices along and around the y axis. For example the sphere in figure 1 uses five divisions. We start by creating all the vertices. The total number of points in this example is 22 (2 for the top and bottom of the spheres plus 5 times 4 rings of points). We create the position for these vertices using trigonometric functions (line 20-22). To complete the mesh description, we need to provide some information about the faces connectivity. The faces at the top and bottom of the spheres are triangles (the top and bottom cap make what we call a triangle fan: all the triangles share one central vertex). They are defined by three vertices (lines 42-44 and 49-51). The others are quads (line xx). Finally, the faces are created by connecting vertices in a precise order. In figure 1 we are showing the vertex indexes for the sixth face in the sphere (lines 56-59). Note that in the code we also generate vertex normals and texture coordinates. Normals are simple to compute. Since the sphere is centered around the world origin the normal at the vertex is simply the normalized vertex position. For the texture coordinates all we need to need to do is normalise the parameters u (the horizontal angle \(\phi\)) and v (the vertical angle \(\theta\)) which lie in the range \([-\pi,\pi]\) and \([-\pi/2,\pi/2]\) respectively (lines 24-25). The intersect() method implements the Möller-Trumbore algorithm for the ray-triangle intersection test. Images in figure 2 were obtained by increasing the number of divisions for the polygon sphere.

The complete source code for ray-tracing apply sphere can be found in the Source Code chapter of this lesson.


Figure 2: render time (vertical axis, in seconds) increases linearly with the number of triangles in the scene (horizontal axis). This is the nature.

Figure 3: increasing the number of subdivisions.

If we regularly increase the number of faces making the sphere and measure the time it takes to render a frame, we can see in figure 3 that the render time increases linearly with the number of triangles in the scene (there is a linear dependence between the render time and the number of triangles in the scene). We can already realize from the numbers we get for a simple scene, that ray-tracing is "slow" (and processors today are incredibly faster than in the early days of ray-tracing). A scene containing approximately 200 polygons takes around 2.5 seconds to render on a computer equipped with a 2.5 GHz processor.

Figure 4: if a ray doesn't intersect the mesh bounding box, we don't need to test if the ray intersects any of the mesh triangles.

Can this problem be solved? In fact, ray-tracing will always be slower than rasterization, but things can be improved quite significantly with the help of acceleration structures. The problem with ray-tracing is that each ray needs to be tested against every single triangle in the scene. No matter how small the object are in the scene (see the next chapter), the time it will take to produce a frame is constant. It only depends on how many triangles the scene contains. The time it takes to render a pixel is constant, whether this pixel is the top-left corner of the frame or right in the middle of it. The idea behind acceleration structure is simple. For example, we could first test if a ray intersects the object's bounding box. If it doesn't, then we know for sure that the ray can't hit the object. Though if it does, then we can still test if the ray intersects any of the mesh triangles (figure 4). This very simple test can already save a lot of time. For example, all the pixels in the corners of the frame are unlikely to intersect the mesh's bounding box. Acceleration structures are more complex than bounding boxes but are based on the same idea. They can be used to divide the space that the objects fill in into simple volumes which are fast to ray-trace. If rays intersect these sub-volumes then we can go deeper into the structure and test the ray against smaller sub-volumes until we eventually hit a sub-volume that contains the mesh original triangle. At this point of the process, we test the ray against the triangles contained in the sub-volume. Lessons on acceleration structures can be found in the Advanced Ray-Tracing section.

int main(int argc, char **argv) { // setting up options Options options; options.cameraToWorld[3][2] = 4; for (uint32_t i = 0; i < 10; ++i) { int divs = 5 + i; // creating the scene (adding objects and lights) std::vector<std::unique_ptr<Object>> objects; TriangleMesh *mesh = generatePolyShphere(2, divs); objects.push_back(std::unique_ptr<Object>(mesh)); // finally, render auto timeStart = std::chrono::high_resolution_clock::now(); render(options, objects); auto timeEnd = std::chrono::high_resolution_clock::now(); auto passedTime = std::chrono::duration<double, std::milli>(timeEnd - timeStart).count(); std::cerr << mesh->numTris << " " << passedTime << std::endl; } return 0; }


In this lesson we have given some information about the polygon geometry representation and showed how this geometry could be rendered with a ray tracer. The polygons (if they are convex) can be converted to triangles and an efficient algorithm (the Möller-Trumbore method for instance) can then be used to compute the intersection of rays with these triangles. Converting all the different geometry representations into triangles is easier than supporting a fast and robust ray-geometry intersection method for each one of these representations. It require to only support a ray-triangle intersection routine which can be highly optimized. Finally in this chapter, we showed one of the most important properties of the ray-tracing algorithm: the computational time is linearly dependent on the number of objects or triangles in the scene. Despite the progress made with processors, using a naive implementation of the ray tracing to render reasonably complex scenes becomes quickly unpractical. Hopefully the cost of testing each object in the scene with each ray can be greatly reduced if we use some acceleration techniques.

What's Next?

In the next chapter, we will render the image we produced in the lesson on rasterization but using ray-tracing. We will load the object geometry from disk, pass the data to the TriangleMesh constructor, generate a triangle mesh, loop over all the pixels in the image, generate primary rays and test each one of the rays against each triangle in the mesh.