From Wikipedia, the free encyclopedia

Ray tracing is a general technique from geometrical optics of modeling the path taken by light by following rays of light as they interact with optical surfaces. It is used in the design of optical systems, such as camera lenses, microscopes, telescopes and binoculars. The term is also applied to mean a specific rendering algorithmic approach in 3D computer graphics, where mathematically-modelled visualisations of programmed scenes are produced using a technique which follows rays from the eyepoint outward, rather than originating at the light sources. It produces results similar to ray casting and scanline rendering, but facilitates more advanced optical effects, such as accurate simulations of reflection and refraction, and is still efficient enough to frequently be of practical use when such high quality output is sought.

Contents 1 Broad description of ray tracing computer algorithm 2 Detailed description of ray tracing computer algorithm and its genesis 2.1 What happens in nature 2.2 Ray casting algorithm 2.3 Ray tracing algorithm 2.4 Advantages of ray tracing 2.5 Disadvantages of ray tracing 2.6 Reversed direction of traversal of scene by the rays 2.7 Algorithm: classical recursive ray tracing 3 Ray tracing in real time 4 In optical design 5 Example 6 See also 6.1 Software 7 References 8 External links

Ray tracing describes a method for producing visual images constructed in 3D computer graphics environments, with more photorealism than either ray casting or scanline rendering techniques. It works by tracing a path from an imaginary eye through each pixel in a virtual screen, accumulating the contribution of each light in the scene to that pixel. As each ray is cast from the eye, it is tested for intersection versus objects within the scene. In the event of a collision, the pixel's values are updated, and the ray is either recast or terminated based on material properties and maximum recursion allowed.

Scenes in raytracing are described mathematically by a programmer or by a visual artist (using intermediary tools). Scenes may also incorporate data from images and models captured by means such as digital photography.

Following rays in reverse is many orders of magnitude more efficient at building up the visual information than would be a genuine simulation of all possible light interactions in the scene, since the overwhelming majority of light rays from a given light source do not wind up providing significant light to the viewer's eye. Instead, they may bounce around until they are absorbed by a material, bounce in a non-intersecting direction, or otherwise do not reach the view frame. A computer simulation that starts by casting rays from the light source is called Photon mapping, and it takes much longer than a comparable ray trace.

Therefore, the shortcut taken in raytracing is to presuppose that a given ray intersects the view frame. After either a maximum number of reflections or a ray traveling a certain distance without intersection, the ray ceases to travel and the pixel's value is updated. The light intensity of this pixel is computed using a number of algorithms, which may include the classic rendering algorithm and may also incorporate techniques such as radiosity.

In nature, a light source emits a ray of light which travels, eventually, to a surface that interrupts its progress. One can think of this "ray" as a stream of photons traveling along the same path. In a perfect vacuum this ray will be a straight line. In reality, any combination of three things might happen with this light ray: absorption, reflection, and refraction. A surface may reflect all or part of the light ray, in one or more directions. It might also absorb part of the light ray, resulting in a loss of intensity of the reflected and/or refracted light. If the surface has any transparent or translucent properties, it refracts a portion of the light beam into itself in a different direction while absorbing some (or all) of the spectrum (and possibly altering the color). Between absorption, reflection, and refraction, all of the incoming light must be accounted for, and no more. A surface cannot, for instance, reflect 66% of an incoming light ray, and refract 50%, since the two would add up to be 116%. An exception here is fluorescence whereby higher non-visible light frequencies such as UV, which are radiated by many light sources to different degrees, can be converted by some materials to visible light. From here, the reflected and/or refracted rays may strike other surfaces, where their absorptive, refractive, and reflective properties are again calculated based on the incoming rays. Some of these rays travel in such a way that they hit our eye, causing us to see the scene and so contribute to the final rendered image.

The first ray casting (versus ray tracing) algorithm used for rendering was presented by Arthur Appel in 1968. The idea behind ray casting is to shoot rays from the eye, one per pixel, and find the closest object blocking the path of that ray – think of an image as a screen-door, with each square in the screen being a pixel. This is then the object the eye normally sees through that pixel. Using the material properties and the effect of the lights in the scene, this algorithm can determine the shading of this object. The simplifying assumption is made that if a surface faces a light, the light will reach that surface and not be blocked or in shadow. The shading of the surface is computed using traditional 3D computer graphics shading models. One important advantage ray casting offered over older scanline algorithms is its ability to easily deal with non-planar surfaces and solids, such as cones and spheres. If a mathematical surface can be intersected by a ray, it can be rendered using ray casting. Elaborate objects can be created by using solid modeling techniques and easily rendered.

Ray casting for producing computer graphics was first used by scientists at Mathematical Applications Group, Inc., (MAGI) of Elmsford, New York, New York. In 1966, the company was created to perform radiation exposure calculations for the Department of Defense. MAGI's software calculated not only how the gamma rays bounced off of surfaces (ray casting for radiation had been done since the 1940s), but also how they penetrated and refracted within. These studies helped the government to determine certain military applications; constructing military vehicles that would protect troops from radiation, designing re-entry vehicles for space exploration. Under the direction of Dr. Philip Mittelman, the scientists developed a method of generating images using the same basic software. In 1972, MAGI became a commercial animation studio. This studio used ray casting to generate 3-D computer animation for television commercials, educational films, and eventually feature films – they created much of the animation in the film Tron using ray casting exclusively. MAGI went out of business in 1985.

The next important research breakthrough came from Turner Whitted in 1979. Previous algorithms cast rays from the eye into the scene, but the rays were traced no further. Whitted continued the process. When a ray hits a surface, it could generate up to three new types of rays: reflection, refraction, and shadow. A reflected ray continues on in the mirror-reflection direction from a shiny surface. It is then intersected with objects in the scene; the closest object it intersects is what will be seen in the reflection. Refraction rays traveling through transparent material work similarly, with the addition that a refractive ray could be entering or exiting a material. To further avoid tracing all rays in a scene, a shadow ray is used to test if a surface is visible to a light. A ray hits a surface at some point. If the surface at this point faces a light, a ray (to the computer, a line segment) is traced between this intersection point and the light. If any opaque object is found in between the surface and the light, the surface is in shadow and so the light does not contribute to its shade. This new layer of ray calculation added more realism to ray traced images.

Ray tracing's popularity stems from its basis in a realistic simulation of lighting over other rendering methods (such as scanline rendering or ray casting). Effects such as reflections and shadows, which are difficult to simulate using other algorithms, are a natural result of the ray tracing algorithm. Relatively simple to implement yet yielding impressive visual results, ray tracing often represents a first foray into graphics programming.

A serious disadvantage of ray tracing is performance. Scanline algorithms and other algorithms use data coherence to share computations between pixels, while ray tracing normally starts the process anew, treating each eye ray separately. However, this separation offers other advantages, such as the ability to shoot more rays as needed to perform anti-aliasing and improve image quality where needed. Although it does handle interreflection and optical effects such as refraction accurately, traditional ray tracing is also not necessarily photorealistic. True photorealism occurs when the rendering equation is closely approximated or fully implemented. Implementing the rendering equation gives true photorealism, as the equation describes every physical effect of light flow. However, this is usually infeasible given the computing resources required. The realism of all rendering methods, then, must be evaluated as an approximation to the equation, and in the case of ray tracing, it is not necessarily the most realistic. Other methods, including photon mapping, are based upon ray tracing for certain parts of the algorithm, yet give far better results.

The process of shooting rays from the eye to the light source to render an image is sometimes referred to as backwards ray tracing, since it is the opposite direction photons actually travel. However, there is confusion with this terminology. Early ray tracing was always done from the eye, and early researchers such as James Arvo used the term backwards ray tracing to refer to shooting rays from the lights and gathering the results. As such, it is clearer to distinguish eye-based versus light-based ray tracing. Research over the past decades has explored combinations of computations done using both of these directions, as well as schemes to generate more or fewer rays in different directions from an intersected surface. For example, radiosity algorithms typically work by computing how photons emitted from lights affect surfaces and storing these results. This data can then be used by a standard recursive ray tracer to create a more realistic and physically correct image of a scene. In the context of global illumination algorithms, such as photon mapping and Metropolis light transport, ray tracing is simply one of the tools used to compute light transfer between surfaces.

For each pixel in image {
  Create ray from eyepoint passing through this pixel
  Initialize NearestT to INFINITY and NearestObject to NULL

  For every object in scene {
     If ray intersects this object {
        If t of intersection is less than NearestT {
           Set NearestT to t of the intersection
           Set NearestObject to this object
        }
     }
  }

  If NearestObject is NULL {
     Fill this pixel with background color
  } Else {
     Shoot a ray to each light source to check if in shadow
     If surface is reflective, generate reflection ray: recurse
     If surface is transparent, generate refraction ray: recurse
     Use NearestObject and NearestT to compute shading function
     Fill this pixel with color result of shading function
  }
}

Below is an image showing a simple example of a path of rays recursively generated from the camera (or eye) to the light source using the above algorithm. A diffuse surface reflects light in all directions.

First, a ray is created at an eyepoint and traced through a pixel and into the scene, where it hits a diffuse surface. From that surface the algorithm recursively generates a reflection ray, which is traced through the scene, where it hits another diffuse surface. Finally, another reflection ray is generated and traced through the scene, where it hits the light source and is absorbed. The color of the pixel now depends on the colors of the first and second diffuse surface and the color of the light emitted from the light source. For example if the light source emitted white light and the two diffuse surfaces were blue, then the resulting color of the pixel is blue.

The first implementation of a "real-time" ray-tracer was credited at the 2005 SIGGRAPH computer graphics conference as the REMRT/RT tools developed by Mike Muuss for the BRL-CAD solid modeling system. Initially implemented in 1986 and later published in 1987 at USENIX, the BRL-CAD ray-tracer is the first known implementation of a parallel network distributed ray-tracing system that achieved several frames per second in rendering performance.^[1] This performance was attained by leveraging the highly-optimized yet platform agnostic LIBRT ray-tracing engine in BRL-CAD and by using solid implicit CSG geometry on several shared memory parallel machines over a commodity network. BRL-CAD's ray-tracer, including REMRT/RT tools, continue to be available and developed today as Open Source software.^[2]

Since then, there have been considerable efforts and research towards implementing ray tracing in real time speeds for a variety of purposes on stand-alone desktop configurations. This purposes include interactive 3D graphics applications such as demoscene productions, computer and video games, and image rendering. Some real-time software 3D engines based on ray tracing have been developed by hobbyist demo programmers since the late 1990s.^[3]

The OpenRT project includes a highly-optimized software core for ray tracing along with an OpenGL-like API in order to offer an alternative to the current rasterization based approach for interactive 3D graphics. Ray tracing hardware, such as the experimental Ray Processing Unit developed at the Saarland University, has been designed to accelerate some of the computationally intensive operations of ray tracing. On March 16, 2007, the University of Saarland revealed an implementation of a high-performance ray tracing engine that allowed computer games to be rendered via ray tracing without intensive resource usage.^[4]

Ray tracing in computer graphics derives its name and principles from a much older technique used for lens design since the 1900s. Geometric ray tracing is used to describe the propagation of light rays through a lens system or optical instrument, allowing the image-forming properties of the system to be modeled. The following effects can be integrated into a ray tracer in a straight forward fashion, but are usually omitted in computer graphics:

• Dispersion leads to chromatic aberration (partly integrated into Povray)
• Gradient index optics
• Polarization
  • Crystal optics
  • Fresnel equations
• Laser
• Thin film interference (optical coating, soap bubble) can be used to calculate the reflectivity of a surface.

For the application of lens design two special cases of interference is important. In a focus rays from a point light source meet again. In a closeup of the focal region all rays are replaced by plane waves. They inherit their direction from the rays. The optical path length from the light source is used for the phase. The derivative of the position of the ray in the focal region on the source position is used to get the width of the ray and from that the amplitude of the plane wave. The result is the point spread function, its Fourier transform is the optical transfer function, and from the former the Strehl ratio can be calculated also. The other case is wavefront calculation of a plane wavefront. Of course when the rays come to close together or even cross the wavefront approximation breaks down. Interference of spherical waves is usually not combined with ray tracing thus diffraction at an aperture cannot be calculated.

This is used to optimize the design of the instrument by minimizing aberrations, for photography, and for longer wavelength applications such as designing microwave or even radio systems, and for shorter wavelengths, such as ultraviolet and X-ray optics.

Before the advent of the computer, ray tracing calculations were performed by hand using trigonometry and logarithmic tables. The optical formulas of many classic photographic lenses were optimized by rooms full of people, each of whom handled a small part of the large calculation. Now they are worked out in optical design software such as OSLO or TracePro from Lambda Research, Code-V or Zemax. A simple version of ray tracing known as ray transfer matrix analysis is often used in the design of optical resonators used in lasers. The basic principles of the mostly used algorithm could be found in Spencer and Murty's fundamental paper: "General Ray-Tracing Procedure".^[5]

As a demonstration of the principles involved in raytracing, let us consider how one would find the intersection between a ray and a sphere. In vector notation, the equation of a sphere with center and radius r is

.

Any point on a ray starting from point with direction (here is a unit vector) can be written as

where t is its distance between and . In our problem, we know , r, (e.g. the position of a light source) and , and we need to find . Therefore, we substitute for :

Let for simplicity; then

This quadratic equation has solutions

The two values of t found by solving this equation are the two ones such that are the points where the ray intersects the sphere.

If one (or both) of them are negative, then the intersections do not lie on the ray but in the opposite half-line (i.e. the one starting from with opposite direction).

If the quantity under the square root is negative, then the ray does not intersect the sphere.

Let us suppose now that there is at least a positive solution, and let t be the minimal one. In addition, let us suppose that the sphere is the nearest object on our scene intersecting our ray, and that it is made of a reflective material. We need to find in which direction the light ray is reflected. The laws of reflection state that the angle of reflection is equal and opposite to the angle of incidence between the incident ray and the normal to the sphere.

The normal to the sphere is simply

,

where is the intersection point found before. The reflection direction can be found by a reflection of with respect to , that is

.

Thus the reflected ray has equation

.

Now we only need to compute the intersection of the latter ray with our field of view, to get the pixel which our reflected light ray will hit. Lastly, this pixel is set to an appropriate color, taking into account how the color of the original light source and the one of the sphere are combined by the reflection.

This is merely the math behind the ray-sphere intersection and the subsequent determination of the colour of the pixel being calculated. There is, of course, far more to the general process of raytracing, but this demonstrates an example of the algorithms used.

• Ray casting
• Scanline rendering
• Beam tracing
• Cone tracing
• Global illumination
• Radiosity
• Photon mapping
• Distributed ray tracing
• Ray tracing hardware
• Line-sphere intersection
• Specular reflection and Mirrors

• ASAP
• Blender
• BRL-CAD
• Indigo Renderer
• POV-Ray
• Radiance
• Sunflow
• TurboSilver
• YafRay
• Bryce

1. ^ See Proceedings of 4th Computer Graphics Workshop, Cambridge, MA, USA, October 1987. Usenix Association, 1987. pp 86–98.
2. ^ BRL-CAD Overview. Retrieved on 2007-09-17.
3. ^ Piero Foscari. The Realtime Raytracing Realm. ACM Transactions on Graphics. Retrieved on 2007-09-17.
4. ^ Mark Ward. "Rays light up life-like graphics", BBC News, March 16, 2007. Retrieved on 2007-09-17. 
5. ^ G. H. Spencer and M. V. R.K. Murty (1962). "General Ray-Tracing Procedure" (PDF). J. Opt. Soc. Am. 52 (6): 672–678. 

• Glassner, Andrew (Ed.) (1989). An Introduction to Ray Tracing. Academic Press. ISBN 0-12-286160-4.
• Shirley, Peter and Morley Keith, R. (2001) Realistic Ray Tracing,2nd edition. A.K. Peters. ISBN 1-56881-198-5.
• Henrik Wann Jensen. (2001) Realistic image synthesis using photon mapping. A.K. Peters. ISBN 1-56881-147-0.
• Pharr, Matt and Humphreys, Greg (2004). Physically Based Rendering : From Theory to Implementation. Morgan Kaufmann. ISBN 0-12-553180-X.

• The Ray Tracing News – short research articles and new links to resources
• Interactive Ray Tracing: The replacement of rasterization? – thesis about real time ray tracing and its state in December 2006
• Games using realtime raytracing
• A series of tutorials on implementing a raytracer using C++
• The Internet Ray Tracing Competition – still and animated categories
• Quake 4 Raytraced by Daniel Pohl – good information on potential for real-time raytraced games
• The Amusement Machine – videos of real-time raytracing on graphics hardware