Overview of the Ray-Tracing Rendering Technique

Distributed under the terms of the CC BY-NC-ND 4.0 License.

  1. Overview of the Ray-Tracing Rendering Technique
  2. Light Transport Algorithms and Ray-Tracing: Whitted Ray-Tracing
  3. Source Code (external link GitHub)

Light Transport Algorithms and Ray-Tracing: Whitted Ray-Tracing

Reading time: 21 mins.
Ray-tracing is one of the most elegant techniques in computer graphics. Many phenomena that are difficult or impossible with other techniques are simple with ray tracing, including shadows, reflections, and refracted light". Robert L. Cook Thomas Porter Loren Carpenter. "Distributed Ray-Tracing" (1984).

Light Transport

As mentioned in the first chapter ray tracing is only a technique used to compute the visibility between points. It is simply a technique based on the concept of a ray which can be mathematically (and in a computer program) defined as a point (the origin of the ray in space) and a direction. Then the idea behind ray-tracing is to find mathematical solutions to compute the intersection of this ray with various types of geometry: triangles, quadrics (which we study in one of the following lessons), NURBs, etc. This is all there is to ray-tracing.

Figure 1: direct and indirect illumination.

Finding out the color of objects at any point on their surface is a complex problem. The appearance of objects is essentially the result of light bouncing off of the surface of objects or traveling through these objects if they are transparent. Effects like reflection or refraction are the result of light rays being refracted while traveling through transparent surfaces or being reflected off of the surface of a shiny object for example. When we see an object, what we actually "see" are light rays reflected by this object in the direction of our eyes. Many of the rays reflected off of the surface of that object may travel away from the eyes though some of these rays may be indirectly reflected toward the eye by another object in the scene (figure 1). The way light is reflected by objects is a well know and well-studied phenomenon but this is not a lesson on shading, so we won't get into details at this point. All we want you to know in the context of this lesson is that to compute the color of an object at any given point on the surface of that object, we need to simulate the way light is reflected off of the surface of objects. In compute graphics, this is the task of what we call a light transport algorithm. We will study the concept of light transport in detail in some of the following lessons so don't worry too much if only scratch the surface of the subject at this point.

We could simulate the transport of light in the scene in a brute force manner by just applying the laws of optics and physics which describe the way light interacts with matter; we would probably get an extremely accurate image though, the problem with this approach is that (and to stay short) it would probably take a very very long time to get that perfect result, even with some of the most powerful computers we can get today. This approach is simply not practical.

To truly simulate all effects of light accurately, you would have to program the universe.

What light algorithms do is essentially find ways of simulating all sorts of lighting scenarios in an "acceptable" amount of time while providing the best visual accuracy possible. You can see a light transport algorithm as a strategy for solving that light transport problem (and we all know that some strategies to solve a given problem are better than others and that a strategy that is good in a given scenario might not work well in another scenario - light transport algorithms are the same, which is again why so many of them exist).

Computing the new path of a light ray that strikes the surface of an object is something for which we have well-defined mathematic models. The main problem is that the ray may be reflected into the scene and strike the surface of another object in the scene. Thus, if you want to simulate the trajectory or the paths of a light ray as it bounces off from the surface to the surface, what we need is a solution to compute the intersection of rays with surfaces. As you can guess, this is where ray-tracing comes into play. Ray-tracing is of course ideally suited to compute the first visible surface from any given point in the scene in any given direction. Rasterization, in contrast, is not well suited for this task at all. It works well to compute the first visible surface from the camera point of view, but not from any arbitrary point in the scene. Note that it can be done with rasterization. The process would just be very inefficient (readers interested in this approach can search for a technique called hemisphere or hemicube which is used in the radiosity algorithm) even compared to ray-tracing which has a high computational cost.

In conclusion, if these light transport algorithms involve computing the visibility between surfaces, any technique such as ray-tracing or rasterization can be used to do so, though, as explained before, ray-tracing is simply easier to use in this particular context. For this reason, some of the most popular light-transport algorithms such as path-tracing or bidirectional path-tracing have become inevitably associated with ray-tracing. In the end, this has created a confusing situation in which ray-tracing was understood as a technique for creating photo-realistic images. It is not. A photo-realistic computer-generated image is a mix of a light transport algorithm and a technique to compute visibility between surfaces. Thus when you consider any given rendering program, the two questions you may want to ask yourself to understand the characteristics of this particular program are: what light transport algorithm does it use, and what techniques does it use to compute visibility in general: rasterization, ray-tracing or a mix of the two techniques?

As mentioned earlier, don't worry too much about light transport algorithms for now. The point we are trying to make is really that you should not mix ray tracing with the process of actually finding out the color of objects in the scene. We insist on this point as ray tracing is often presented as a technique for producing photo-realistic images of 3D objects. It is not. The job of simulating global illumination effects is that of the light transport algorithm.

For an in-depth introduction to light transport algorithms please read the lesson "Introduction to Shading: The Rendering Equation and Light Transport Algorithms".

Whitted Ray-Tracing

Figure 2: image produced by Turner Whitted with the algorithm he developed in 1980.

Now that the distinction between ray-tracing and light transport algorithms was established, we can finally introduce one of the most classical examples of light transport algorithms based on ray-tracing. The technique was first detailed in 1980 by Turner Whitted in a Siggraph paper titled "An Improved Illumination Model for Shaded Display". The algorithm is for this reason often given the name of Whitted (-style) ray-tracing.

Before Whitted's paper, most programs were already capable of simulating the look of diffuse and specular surfaces. The famous Phong illumination model (which we will talk about in the lesson devoted to Shaders), was already known. Though, simulating complex reflections and refractions was yet to be done. Whitted proposed to use of ray tracing to solve this problem. If object A is a mirror-like surface, and that object B seats on top of it, then we would like to see the reflection of B into A. If A is not a flat surface, there is no easy solution for computing this reflection. Things get even harder if B is also reflective. Mirror surfaces keep reflecting images of themselves causing the "infinity room" effect which is often seen in films.

Figure 3: a light ray emitted by the sphere bounces multiple times off of the surface of the two mirrors before it reaches the eye
Figure 4: objects we see through transparent objects are distorted due to refraction.
Figure 5: different types of rays cast into a scene made of reflective, transparent and diffuse objects

Figure 3 shows an example in which the sphere is reflected a couple of times by the two mirrors before its image finally reaches the eye. What about transparent objects? We should see through transparent surfaces, though materials such as water or glass bend light rays due to the phenomenon of refraction. The optical (and physical) laws governing the phenomena of reflection and refraction are well known. The reflection direction only depends on the surface orientation and the incoming light direction. The refraction direction can be computed using Snell's law and depends on the surface orientation (the surface's normal), the incoming light direction, and the material refractive index (around 1.3 for water and 1.5 for glass). If you know these parameters, computing these directions is just a straight application of the laws of reflection and refractions whose equations are quite simple.

Whitted proposed to use these laws to compute the reflection and refraction direction of rays as they intersect reflective or transparent surfaces, and follow the path of these rays to find out the color of the object they would intersect. Three cases may occur at the intersection point of these reflection and refraction rays (which in CG, we call secondary rays to differentiate them from the primary or camera rays):

Figure 6: how do we find the color reflected off of the surface of a mirror?
Figure 7: how do we find the color of objects seen through a glass ball?

If P1 generates a secondary ray that intersects P2 and another secondary ray is generated at P2 that intersects another object at P3, then the color at P3 becomes the color of P2 which in turn becomes the color of P1 (assuming P1 and P2 belong to a mirror-like surface) as shown in Figure 6. The higher the refractive index of a transparent object is, the stronger these specular reflections are. Additionally, the higher the angle of incidence is, the more light is reflected (this is due to the Fresnel effect). The same method is used for refraction rays. If the ray is refracted a P1 then refracted at P2 and then finally hits a diffuse object at P3, P2 takes on the color of P3 and P1 takes on the color of P2 as shown in Figure 7. The higher the refractive index, the stronger the distortion (figure 3).

The paper was published in 1980, but it took about twenty more years before ray tracing started to get used for anything else than just research projects, due to its high computational cost. It is only in the late 1990s and early 2000s that ray tracing started to be used in production (for films).

Some program uses a hybrid approach. They use rasterization and z-buffering to compute visibility with the first visible surface from the eye, and ray-tracing to simulate effects such as reflection and refraction.

The Whitted algorithm is the classical example of an algorithm that uses ray tracing to produce photo-realistic computer-generated images. Many more advanced light transport algorithms have been developed since the paper was first published. Let's now review some of the algorithm's properties.


Figure 8: Whitted algorithm is recursive.

Each time a ray intersects a transparent surface, two new rays are generated (a reflection and a refraction ray). If these rays intersect with another transparent object, each ray will generate two more rays. This process can go on forever, as long as secondary rays keep intersecting reflective or transparent objects. In this particular scenario, the number of rays increases exponentially as the recursion depth increases. The primary ray generates 2 secondary rays. This is the first level of recursion (depth 1). After two levels of recursion (depth 2), 4 rays are generated. At depth 3, each ray produces 2 more rays, thus producing a total of 8 rays. At depth 4, we have 16 rays and at depth 5, 32 rays. This practically means that render time also increases exponentially as the depth increases. The simplest solution to the recursive nature of this algorithm and the fact that the number of secondary rays grows exponentially as the depth increases is to put a cap on the maximum number of allowed recursions (or maximum depth). As soon as the maximum depth is reached, then we simply stop generating new rays.

>, Unlike previous ray tracing algorithms, the visibility calculations do not end when the nearest intersection of a ray with objects in the scene is found. Instead, each visible intersection of a ray with a surface produces more rays in the reflection direction, the refraction direction, and in the direction of each light source. The intersection process is repeated for each ray until none of the new rays intersects any object. "An Improved Illumination Model for Shaded Display", Turner Whitted, 1980

Trees of Rays

Figure 9: a tree of rays.

In some papers on ray tracing (especially some of the first papers on the topic), you will often see the term "tree of rays" being used. All the secondary rays spawned by either the primary ray itself or other secondary rays can be represented as a tree as shown in figure 9 (it represents the tree of rays generated by the primary ray in figure 8). Each level in the tree as you go down corresponds to one level of recursion.

To accurately render a two-dimensional image of a three-dimensional scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this information is stored in a tree of "rays" extending from the viewer to the first surface encountered and from there to other surfaces and to the light sources. "An Improved Illumination Model for Shaded Display", Turner Whitted, 1980.

Implementing Whitted Ray-Tracing in C++

This program provided with this lesson will be different than usual, in the sense that we don't intend to explain it. It uses techniques we haven't studied yet such as the generation of primary rays or the intersection of rays with various types of geometry such as spheres or triangles. The laws of reflection and refraction and the Fresnel equation are used to compute reflections and refractions and the Phong illumination model is used to compute the color of diffuse and glossy objects though again we won't explain how these techniques work in this lesson. You will find them explained one by one in the next lessons.

The main goal of this program is for you to understand the concepts that it is based upon on a higher level. For example, note that the program is essentially structured around the following four main components:

You can find the complete source code of this program in the next chapter. If you compile and run the program, you will probably observe that it takes quite a while to render this simple scene. Here is the output of the program:

As you can see, we tried to reproduce the image published by Whitted in his original paper. Note though that a few things could be improved in this image. First, if you look at a closeup of the frame itself, you can see that as with rasterization, it suffers from aliasing. We will learn about anti-aliasing techniques for ray tracing in the next lessons. Note also that the shadow under the glass sphere is opaque. This is a case we don't consider, but it would be easy to address it using what we call in ray-tracing the concept of transmission. More on this topic in the next lessons as well.

Is There Anything Better than the Whitted Light-Transport Algorithm?

The method is already a great improvement compared to whatever could be produced before the publication of the paper. Though, certain effects such as glossy reflection (the reflection of objects by glossy surfaces), soft shadows, or caustics can't be simulated with this algorithm. More advanced light-transport algorithms have been developed since then to address these limitations. The most famous ones which are solely based on ray tracing are the path-tracing, the bidirectional path-tracing and Metropolis light transport algorithms. We will study path tracing in this section. Another very important ray-tracing-based algorithm was developed by Robert L. Cook, Thomas Porter, and Loren Carpenter and published in another seminal paper titled "Distributed Ray-Tracing" (1984). We will also study this algorithm in this section.

What's Next?

We are now ready to learn about the foundations of ray tracing. We will learn how to generate primary rays, and intersect rays with simple geometry shapes as well as triangles. From there we will learn how to ray-tracing triangulated meshes, as well as ray-traced objects which have been transformed by a 4x4 affine transformation matrix. We will then have the tools we need to study shading, light-transport algorithms, and effects such as motion blur, depth-of-field, and textures which are all critical to producing photo-realistic computer-generated images.



An Improved Illumination Model for Shaded Display. Turner Whitted, 1980