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):
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
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.
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.
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.
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.
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.