There are two approaches to the computer graphics problem:

1. For each object in a scene, project it onto the screen, then color in all the pixels that it covers.
2. For each pixel on the screen figure out which object in the scene it points at, then color the pixel the color of that object.

The first approach is the one used by mainstream, real-time graphics toolkits like OpenGL and DirectX. The second approach is ray tracing. This may seem like a fine distinction, but this choice determines what sort of things end up being hard or easy later.

Camera Models

Inquisitive Reader: So how does that #2 thing you said make a picture?

Jess: I’ll tell you how.

IR: So you keep saying.

J: Ahem. Well. To begin, you must have a model of a camera. By model, I mean a geometrical way of describing how an image is actually formed. In real life, this is somewhat complicated. But since we’re not in real life, we can assume very simple model: the pinhole camera.

IR: That’s a nice picture, and accurate I’m sure, however, I couldn’t help but notice that the tree inside the box is upside down.

J: Quite observant of you! The place where the image of the tree is formed is called the image plane. We’ll cleverly do away with this problem by placing the image plane in front of the pinhole by the same distance that it is behind in the illustration. This way, the light rays will not have crossed paths at the pinhole yet, and the image will not be upside down.

IR: Wait, that doesn’t seem quite right… I’m sure there’s a problem here but I can’t put my finger on it.

J: The reason we can get away with this is because, as I mentioned before, we aren’t in real life. In real life the light-sensitive imaging surface must be contained in a dark box, so that light coming from other directions, doesn’t affect the image. Since we are simulating the light ourselves, we can choose to only simulate the light in front of the image plane.

IR: Simulating light… maybe we’re finally getting to the good part.

J: That we are. We call the point where the rays come together in the illustration, the focal point. To generate an image we create rays that begin at the focal point and go through each point on the image plane. We then trace them back out into the scene and see what they hit. This isn’t really simulating light, as I said earlier, but working backwards from the camera and saying, “Now if light were to hit the image plane here, where must it have come from?” Where the light came from determines what color it is, ergo what color we will make a given spot on the image.

J: To make an image out of all of this, we map our image onto the image plane. Since an image is essentially a grid of pixels, we imagine that grid superimposed on the image plane. Then we cast rays from the focal point through each grid cell, moving over the entire image plane, each ray determining the color of one pixel.

IR: It still seems as if there are a few things missing here. How do you figure out what the ray hits in the scene? How do you know what color light the ray should be anyway? How do lights and shadows work? I’m not at all satisfied by your hand waving.

J: That’s it. I’m tired of your carping. I’ll answer your questions, but I’ll do so in non-dialog form.

IR: No! Wait! I.. [zop!]

With a spray of orange sparks and a puff of acrid smoke, he was gone, and I was left to my narrative, uninterrupted.

Intersecting the Scene

Once you have a ray, travelling from the focal point, through the image plane, out into the scene, the next thing you need to know is what object the ray hits. The simplest way to determine this is to check each object in the scene and see if the ray intersects it.

Every type of object that exists in the scene must have a function to test whether a ray intersects it and to find where the intersection occurs. ZeroRay supports a number of primitive shapes, planes, spheres, rectangular prisms and billboards to be precise. Furthermore, it supports any mesh made up of triangles. This is pretty much the same set of objects supported by a non-ray-tracing graphics engine. Most of the objects you see in computer graphics are meshes of triangles (sometimes quadrilaterals are allowed, they are easily broken into 2 triangles along the diagonal). Some advanced rendering engines support more exotic primitives, but we’re not going to talk about them.

We are only interested in the intersection nearest to the camera. Any intersections that are further away will be blocked from the camera’s view by the closer object. The object of nearest intersection is the object that determines the color of the point in the image (so far. There are other considerations that are left for later).

Lights and Materials

Now that we know which object controls the color of a pixel, how do we figure out what the color is? Every object also has a property called the surface material, so named because it represents what type of material the object is made of. The surface material and lighting are the basic contributors to the color that we will ascribe to the ray. A surface material itself has a number of properties, the simples of which is diffuse color. Diffuse color is the color that light takes on when it is scattered diffusely (in all directions) after hitting the object. Another color property is specular color. For more details on diffuse vs specular lighting see my article Dynamic Skies and Normal Mapping (scroll down to the sections entitled Some Background on Lighting in 3D Graphics).

The surface material tells us the basic color of the object. To produce more realistic renderings we need to take lighting into account. A light is a very simple construct. It has simply a position and a color (and maybe a few attenuation properties, i.e. how strong its light is some distance away). The way the light is used is a bit more complex. Once we’ve determined the point of our camera ray intersection, we move on to lighting calculations. For each light in the scene, we cast a ray from the light to the camera ray intersection point. We find the nearest intersection in the scene for the light rays. If the nearest intersected object isn’t the same object as the camera ray intersection object, then that point is shadowed from that light by some other object. If the point is shadowed by another object, that light has no contribution to that point’s color. If the object is the same, then we know that there is nothing blocking that light and we perform the calculation described in the Dynamic Skies and Normal Mapping article to determine how much light that point receives.

Reflection, Refraction: Recursion

The beauty of the ray tracing approach to graphics is that we can perform this whole process again to calculate reflections and refractions. We can use the angle of the surface the ray hit and the angle of incidence to determine which direction the ray would reflect off the surface. Since we’re tracing the light backwards, what we’re actually doing is figuring out the direction that light must have come from, if it were to have hit that point from somewhere else and reflected into the camera. So we send our algorithm off in that direction as if this ray were the original ray from the camera. Once we get a color back from that calculation, we add it to the color at the original point subject to a reflectivity parameter. More reflective objects show the reflected light brighter while less reflective objects show the reflected light more mutely.

This process of setting up a calculation that then performs the same calculation within itself is called recursion, and it is a very powerful method of computation. If we allowed infinite levels of reflection our ray tracer would never finish calculating the color of any point, so we usually set some hard limit on the number of recursive reflection calculations (like 3 or so).

Another way we can exploit this same trick is if we have objects that transmit light through themselves, like glass. We can use the ray angles to calculate the ray that the light would travel after passing through the object and recursively calculate the contribution of light passing through the object to the color of the point.

Tags: 3D Graphics, Camera Model, Computer Graphics, Lighting, Pinhole Camera, Ray Tracer, Ray Tracing, Recursion, Reflection, Refraction, ZeroRay

This entry was posted on Tuesday, December 21st, 2010 at 12:55 am and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.