by the Codermind team.
This article is the foreword of a serie of article about ray tracing. It's probably a word that you may have heard without really knowing what it represents or without an idea of how to implement one using a programming language. This article and the following will try to fill that for you. Note that this introduction is covering generalities about ray tracing and will not enter into much details of our implementation. If you're interested about actual implementation, formulas and code please skip this and go to part one after this introduction.
What is ray tracing ?
Ray tracing is one of the numerous techniques that exist to render images with computers. The idea behind ray tracing is that physically correct images are composed by light and that light will usually come from a light source and bounce around as light rays (following a broken line path) in a scene before hitting our eyes or a camera. By being able to reproduce in computer simulation the path followed from a light source to our eye we would then be able to determine what our eye sees.
Of course it's not as simple as it sounds. We need some method to follow these rays as the nature has an infinite amount of computation available but we have not. One of the most natural idea of ray tracing is that we only care about the rays that hit our eyes directly or after a few rebounds. The second idea is that our generated images will usually be grids of pixels with a limited resolution. Those two ideas together form the basis of most basic raytracers. We will place our point of view in a 3D scene, and we will shoot rays exclusively from this point of view and towards a representation of our 2D grid in space. We will then try to evaluate the amount of rebounds needed to go from the light source to our eye. This is mostly okay because the actual light simulation does not take into account the actual direction of the ray to be accurate. Of course it is a simplification we'll see later why.
How are raytracers used ?
The ideas behind ray tracing (in its most basic form) are so simple, we would at first like to use it everywhere. But it's not used everywhere.
Ray tracing has been used in production environment for off-line rendering for a few decades now. That is rendering that doesn't need to have finished the whole scene in less than a few milliseconds. Of course we should not generalize and let you know that several implementations of raytracer have been able to hit the "interactive" mark. Right now so called "real-time ray tracing" is a very active field right now, as it's been seen as the next big thing that 3D accelerators need to be accelerating. Raytracer are really liked in areas where the quality of reflections is important. A lot of effects that seem hard to achieve with other techniques are very natural using a raytracer. Reflection, refraction, depth of field, high quality shadows. Of course that doesn't necessarily mean they are fast.
Graphics card on the other hand they generate the majority of images these days but are very limited at ray tracing. Nobody can say if that limitation will be removed in the future but it is a strong one today. The alternative to ray tracing that graphics card use is rasterization. Rasterization has a different view on image generation. Its primitive is not rays, but it is triangles. For each triangle in the scene you would estimate its coverage on the screen and then for each visible pixel that is touched by a triangle you would compute its actual color. Graphics cards are very good at rasterization because they can do a lot of optimization related to this. Each triangle is drawn independently from the precedent in what we call an "immediate mode". This immediate mode knows only what the triangle is made of, and compute its color based on a serie of attributes like shader program, global constants, interpolated attributes, textures. A rasterizer would for example typically draw reflection using an intermediate pass called render to texture, a previous rasterizer pass would feed into itself, but with the same original limitations which then cause all kind of precision issues. This amnesia and several other optimizations are what allow the triangle drawing to be fast. Raytracing on the other hand doesn't forget about the whole geometry of the scene after the ray is launched. In fact it doesn't necessarily know in advance what triangles, or objects it will hit, and because of interreflexion they may not be constrained to a single portion of space. Ray tracing tends to be "global", rasterization tends to be "local". There is no branching besides simple decisions in rasterization, branching is everywhere on ray tracing.
Ray tracing is not used everywhere in off line rendering either. The speed advantage of rasterization and other techniques (scan line rendering, mesh subdivision and fast rendering of micro facets) has often been hold against true "ray tracing solution", especially for primary rays. Primary rays are the one that hit the eye directly, instead of having rebound. Those primary rays are coherent and they can be accelerated with projective math (the attribute interpolation that fast rasterizers rely upon). For secondary ray (after a surface has been reflecting it, or refracting it), all bets are off because those nice properties disappear.
In the interest of full disclosure it should be noted that ray tracing maths can be used to generate data for rasterizer for example. Global illumination simulation may need to shoot ray to determine local properties such as ambiant occlusion or light bleeding. As long as the data is made local in the process that will be able to help a strict "immediate renderer".
Complications, infinity and recursion
Raytracers cannot and will not be a complete solution. No solution exist that can deal with true random infinity. It's often a trade off, trying to concentrate on what makes or break an image and its apparent realism. Even for off line renderer performance is important. It's hard to decide to shoot billions of rays per millions of pixel. Even if that's what the simulation seems to require. What trade offs do we need to do ? We need to decide to not follow every path possible.
Global illumination is a good example. In global illumination techniques such as photon mapping, we try to shorten the path between the light and the surface we're on. In all generality, doing full global illumination would require to cast infinite amount of ray in all the directions and see which percentage hit the light. We can do that but it's going to be very slow, instead, we'll first cast photons (using the exact same algorithm as ray tracing but in reverse from the light point of view) and see what surface they hit. Then we use that information to compute lighting in first approximation at each surface point. We only follow a new ray if we can have a good idea using a couple of rays (perfect reflection needs only one additional ray). Even then it can be expensive, as the tree of rays expands at a geometric rate. We have often to limit ourself to a maximum depth recursion.
Even then, we'll want to go faster. Making intersection tests becomes the bottleneck if we have thousand or millions of intersectable objects in the scene and go for a linear search of intersection for each ray. Instead we definitely need an acceleration structure. Often used are hierarchical representation of a scene. Something like a KD-Tree or octree would come to mind. The structure that we'll use may depend on the type of scene that we intend to render, or the constraints such as "it needs to be updated for dynamic objects", or "we can't address more than that amount of memory", etc. Acceleration structures can also hold photons for the photon mapping, and various other things (collisions for physics).
We can also exploit the coherence of primary rays. Some people will go as far as implementing two solutions, one that use rasterization or similar technique for primary rays and raytracing for anything beyond that. We of course need a good mean of communication between both stages and a hardware that is sufficiently competent at both.
Direction page 1 : "First rays".