Ray tracing - AbsoluteAstronomy.com

Computer graphics

Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

, ray tracing is a technique for generating an image

Digital image

A digital image is a numeric representation of a two-dimensional image. Depending on whether or not the image resolution is fixed, it may be of vector or raster type...

by tracing the path of light

Light

Light or visible light is electromagnetic radiation that is visible to the human eye, and is responsible for the sense of sight. Visible light has wavelength in a range from about 380 nanometres to about 740 nm, with a frequency range of about 405 THz to 790 THz...

through pixel

Pixel

In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....

s in an image plane

Image plane

In 3D computer graphics, the image plane is that plane in the world which is identified with the plane of the monitor. If one makes the analogy of taking a photograph to rendering a 3D image, the surface of the film is the image plane. In this case, the viewing transformation is a projection that...

and simulating the effects of its encounters with virtual objects. The technique is capable of producing a very high degree of visual realism, usually higher than that of typical scanline rendering

Scanline rendering

Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics,that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis...

methods, but at a greater computational cost. This makes ray tracing best suited for applications where the image can be rendered slowly ahead of time, such as in still images and film and television special effects, and more poorly suited for real-time applications like video games where speed is critical. Ray tracing is capable of simulating a wide variety of optical effects, such as reflection

Reflection (physics)

Reflection is the change in direction of a wavefront at an interface between two differentmedia so that the wavefront returns into the medium from which it originated. Common examples include the reflection of light, sound and water waves...

and refraction

Refraction

Refraction is the change in direction of a wave due to a change in its speed. It is essentially a surface phenomenon . The phenomenon is mainly in governance to the law of conservation of energy. The proper explanation would be that due to change of medium, the phase velocity of the wave is changed...

, scattering

Light scattering

Light scattering is a form of scattering in which light is the form of propagating energy which is scattered. Light scattering can be thought of as the deflection of a ray from a straight path, for example by irregularities in the propagation medium, particles, or in the interface between two media...

, and dispersion

Dispersion (optics)

In optics, dispersion is the phenomenon in which the phase velocity of a wave depends on its frequency, or alternatively when the group velocity depends on the frequency.Media having such a property are termed dispersive media...

phenomena (such as chromatic aberration

Chromatic aberration

In optics, chromatic aberration is a type of distortion in which there is a failure of a lens to focus all colors to the same convergence point. It occurs because lenses have a different refractive index for different wavelengths of light...

Algorithm overview

Optical ray tracing describes a method for producing visual images constructed in 3D computer graphics

3D computer graphics

3D computer graphics are graphics that use a three-dimensional representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering 2D images...

environments, with more photorealism than either ray casting

Ray casting

Ray casting is the use of ray-surface intersection tests to solve a variety of problems in computer graphics. It enables spatial selections of objects in ascene by providing users a virtual beam as a visual cue extending...

or scanline rendering

Scanline rendering

Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics,that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis...

techniques. It works by tracing a path from an imaginary eye through each pixel

Pixel

in a virtual screen, and calculating the color of the object visible through it.

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

Typically, each ray must be tested for intersection with some subset of all the objects in the scene. Once the nearest object has been identified, the algorithm will estimate the incoming light at the point of intersection, examine the material properties of the object, and combine this information to calculate the final color of the pixel. Certain illumination algorithms and reflective or translucent materials may require more rays to be re-cast into the scene.

It may at first seem counterintuitive or "backwards" to send rays away from the camera, rather than into it (as actual light does in reality), but doing so is many orders of magnitude more efficient. Since the overwhelming majority of light rays from a given light source do not make it directly into the viewer's eye, a "forward" simulation could potentially waste a tremendous amount of computation on light paths that are never recorded. A computer simulation that starts by casting rays from the light source is called Photon mapping

Photon mapping

In computer graphics, photon mapping is a two-pass global illumination algorithm developed by Henrik Wann Jensen that solves the rendering equation. Rays from the light source and rays from the camera are traced independently until some termination criterion is met, then they are connected in a...

, 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.

What happens in nature

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 photon

Photon

In physics, a photon is an elementary particle, the quantum of the electromagnetic interaction and the basic unit of light and all other forms of electromagnetic radiation. It is also the force carrier for the electromagnetic force...

s traveling along the same path. In a perfect vacuum this ray will be a straight line (ignoring relativistic effects

General relativity

General relativity or the general theory of relativity is the geometric theory of gravitation published by Albert Einstein in 1916. It is the current description of gravitation in modern physics...

). In reality, any combination of four things might happen with this light ray: absorption

Absorption (electromagnetic radiation)

In physics, absorption of electromagnetic radiation is the way by which the energy of a photon is taken up by matter, typically the electrons of an atom. Thus, the electromagnetic energy is transformed to other forms of energy for example, to heat. The absorption of light during wave propagation is...

, reflection

Reflection (physics)

, refraction

Refraction

and fluorescence

Fluorescence

Fluorescence is the emission of light by a substance that has absorbed light or other electromagnetic radiation of a different wavelength. It is a form of luminescence. In most cases, emitted light has a longer wavelength, and therefore lower energy, than the absorbed radiation...

. A surface may absorb part of the light ray, resulting in a loss of intensity of the reflected and/or refracted light. It might also reflect all or part of the light ray, in one or more directions. 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

Visible spectrum

The visible spectrum is the portion of the electromagnetic spectrum that is visible to the human eye. Electromagnetic radiation in this range of wavelengths is called visible light or simply light. A typical human eye will respond to wavelengths from about 390 to 750 nm. In terms of...

(and possibly altering the color). Less commonly, a surface may absorb some portion of the light and fluorescently re-emit the light at a longer wavelength colour in a random direction, though this is rare enough that it can be discounted from most rendering applications. Between absorption, reflection, refraction and fluorescence, 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%. From here, the reflected and/or refracted rays may strike other surfaces, where their absorptive, refractive, reflective and fluorescent properties again affect the progress of 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.

Ray casting algorithm

The first ray casting

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

Scanline rendering

Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics,that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis...

is its ability to easily deal with non-planar surfaces and solids, such as cones

Cone (geometry)

A cone is an n-dimensional geometric shape that tapers smoothly from a base to a point called the apex or vertex. Formally, it is the solid figure formed by the locus of all straight line segments that join the apex to the base...

and sphere

Sphere

A sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...

s. 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

Solid modeling

Solid modeling is a consistent set of principles for mathematical and computer modeling of three dimensional solids. Solid modeling is distinguished from related areas of Geometric modeling and Computer graphics by its emphasis on physical fidelity...

techniques and easily rendered.

Ray tracing algorithm

The next important research breakthrough came from Turner Whitted in 1979. Previous algorithms cast rays from the eye into the scene until they hit an object, 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.

Advantages over other rendering methods

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 shadow

Shadow

A shadow is an area where direct light from a light source cannot reach due to obstruction by an object. It occupies all of the space behind an opaque object with light in front of it. The cross section of a shadow is a two-dimensional silhouette, or reverse projection of the object blocking the...

s, 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. The computational independence of each ray makes ray tracing amenable to parallelization.

Disadvantages

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

Anti-aliasing

In digital signal processing, spatial anti-aliasing is the technique of minimizing the distortion artifacts known as aliasing when representing a high-resolution image at a lower resolution...

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

Rendering equation

In computer graphics, the rendering equation is an integral equation in which the equilibrium radiance leaving a point is given as the sum of emitted plus reflected radiance under a geometric optics approximation. It was simultaneously introduced into computer graphics by David Immel et al. and...

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

Photon mapping

, are based upon ray tracing for certain parts of the algorithm, yet give far better results.

Reversed direction of traversal of scene by the rays

The process of shooting rays from the eye to the light source to render an image is sometimes called 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 mean shooting rays from the lights and gathering the results. Therefore it is clearer to distinguish eye-based versus light-based ray tracing.

While the direct illumination is generally best sampled using eye-based ray tracing, certain indirect effects can benefit from rays generated from the lights. Caustics are bright patterns caused by the focusing of light off a wide reflective region onto a narrow area of (near-)diffuse surface. An algorithm that casts rays directly from lights onto reflective objects, tracing their paths to the eye, will better sample this phenomenon. This integration of eye-based and light-based rays is often expressed as bidirectional path tracing, in which paths are traced from both the eye and lights, and the paths subsequently joined by a connecting ray after some length.

Photon mapping

Photon mapping

is another method that uses both light-based and eye-based ray tracing; in an initial pass, energetic photons are traced along rays from the light source so as to compute an estimate of radiant flux as a function of 3-dimensional space (the eponymous photon map itself). In a subsequent pass, rays are traced from the eye into the scene to determine the visible surfaces, and the photon map is used to estimate the illumination at the visible surface points. The advantage of photon mapping versus bidirectional path tracing is the ability to achieve significant reuse of photons, reducing computation, at the cost of statistical bias.

An additional problem occurs when light must pass through a very narrow aperture to illuminate the scene (consider a darkened room, with a door slightly ajar leading to a brightly-lit room), or a scene in which most points do not have direct line-of-sight to any light source (such as with ceiling-directed light fixtures or torchieres). In such cases, only a very small subset of paths will transport energy; Metropolis light transport

Metropolis light transport

The Metropolis light transport is a SIGGRAPH 1997 paper by Eric Veach and Leonidas J. Guibas, describing an application of a variant of the Monte Carlo method called the Metropolis-Hastings algorithm to the rendering equation for generating images from detailed physical descriptions of three...

is a method which begins with a random search of the path space, and when energetic paths are found, reuses this information by exploring the nearby space of rays.

To the right 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.

In real time

The first implementation of a "real-time" ray-tracer was credited at the 2005 SIGGRAPH

SIGGRAPH

SIGGRAPH is the name of the annual conference on computer graphics convened by the ACM SIGGRAPH organization. The first SIGGRAPH conference was in 1974. The conference is attended by tens of thousands of computer professionals...

computer graphics conference as the REMRT/RT tools developed in 1986 by Mike Muuss

Mike Muuss

Michael John Muuss was the author of the freeware network tool Ping.A graduate of Johns Hopkins University, Muuss was a senior scientist specializing in geometric solid modeling, ray-tracing, MIMD architectures and digital computer networks at the United States Army Research Laboratory at Aberdeen...

for the BRL-CAD

BRL-CAD

BRL-CAD is a constructive solid geometry solid modeling computer-aided design system. It includes an interactive geometry editor, ray tracing support for graphics rendering and geometric analysis, computer network distributed framebuffer support, scripting, image-processing and signal-processing...

solid modeling system. Initially published in 1987 at USENIX

USENIX

-External links:* *...

, 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. This performance was attained by means of the highly-optimized yet platform independent LIBRT ray-tracing engine in BRL-CAD and by using solid implicit CSG

Constructive solid geometry

Constructive solid geometry is a technique used in solid modeling. Constructive solid geometry allows a modeler to create a complex surface or object by using Boolean operators to combine objects...

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

Open source

The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...

software.

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. These purposes include interactive 3D graphics applications such as demoscene productions

Demo (computer programming)

A demo is a non-interactive multimedia presentation made within the computer subculture known as the demoscene. Demogroups create demos to demonstrate their abilities in programming, music, drawing, and 3D modeling...

, computer and video games, and image rendering. Some real-time software 3D engines based on ray tracing have been developed by hobbyist demo programmers

Demoscene

The demoscene is a computer art subculture that specializes in producing demos, which are non-interactive audio-visual presentations that run in real-time on a computer...

since the late 1990s.

The OpenRT

OpenRT

The goal of the "OpenRT Real Time Ray Tracing Project" was to develop ray tracing to the point where it offers an alternative to the current rasterization based approach for interactive 3D graphics...

project includes a highly-optimized software core for ray tracing along with an OpenGL

OpenGL

OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...

-like API in order to offer an alternative to the current rasterisation

Rasterisation

Rasterisation is the task of taking an image described in a vector graphics format and converting it into a raster image for output on a video display or printer, or for storage in a bitmap file format....

based approach for interactive 3D graphics. Ray tracing hardware

Ray tracing hardware

Ray tracing hardware is special purpose computer hardware designed for accelerating ray tracing calculations.-Introduction: Ray tracing and rasterization:...

, such as the experimental Ray Processing Unit

Ray Processing Unit

The Ray Processing Unit is experimental ray tracing hardware device, developed at the Saarland University. It will be 50-100 times faster than the most advanced graphics processing unit....

developed at the Saarland University

Saarland University

Saarland University is a university located in Saarbrücken, the capital of the German state of Saarland, and Homburg. It was founded in 1948 in Homburg in co-operation with France and is organized in 8 faculties that cover all major fields of science...

, 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.

On June 12, 2008 Intel demonstrated a special version of Enemy Territory: Quake Wars

Enemy Territory: Quake Wars

Enemy Territory: Quake Wars is a first-person shooter video game, and is the follow-up to the 2005 title Quake 4. It is also the first game in the series to be rated T by the ESRB...

, titled Quake Wars: Ray Traced

Quake Wars: Ray Traced

Quake Wars: Ray Traced is a research project from Intel Corporation that applied a ray tracing renderer to the game content of Enemy Territory: Quake Wars...

, using ray tracing for rendering, running in basic HD (720p) resolution. ETQW operated at 14-29 frames per second. The demonstration ran on a 16-core (4 socket, 4 core) Xeon Tigerton system running at 2.93 GHz.

At SIGGRAPH 2009, Nvidia announced OptiX, an API for real-time ray tracing on Nvidia GPUs. The API exposes seven programmable entry points within the ray tracing pipeline, allowing for custom cameras, ray-primitive intersections, shaders, shadowing, etc.

Example

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

Vector notation

This page is an overview of the common notations used when working with vectors, which may be spatial or more abstract members of vector spaces....

, the equation of a sphere with center

and radius

Any point on a ray starting from point

with direction

(here

is a unit vector) can be written as

where

is its distance between

and

. In our problem, we know

(e.g. the position of a light source) and

, and we need to find

. Therefore, we substitute for

Let

for simplicity; then

Knowing that d is a unit vector allows us this minor simplification:

This quadratic equation

Quadratic equation

In mathematics, a quadratic equation is a univariate polynomial equation of the second degree. A general quadratic equation can be written in the formax^2+bx+c=0,\,...

has solutions

The two values of

found by solving this equation are the two ones such that

are the points where the ray intersects the sphere.

Any value which is negative does not lie on the ray, but rather in the opposite half-line

Line (mathematics)

The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...

(i.e. the one starting from

with opposite direction).

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

Let us suppose now that there is at least a positive solution, and let

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

Reflection (physics)

state that the angle of reflection is equal and opposite to the angle of incidence between the incident ray and the normal

Surface normal

A surface normal, or simply normal, to a flat surface is a vector that is perpendicular to that surface. A normal to a non-flat surface at a point P on the surface is a vector perpendicular to the tangent plane to that surface at P. The word "normal" is also used as an adjective: a line normal to a...

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

Reflection (mathematics)

In mathematics, a reflection is a mapping from a Euclidean space to itself that is an isometry with a hyperplane as set of fixed points; this set is called the axis or plane of reflection. The image of a figure by a reflection is its mirror image in the axis or plane of reflection...

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

Field of view

The field of view is the extent of the observable world that is seen at any given moment....

, 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 line–sphere intersection

Line–sphere intersection

In analytic geometry, a line and a sphere can intersect in three ways: no intersection at all, at exactly one point, or in two points. Methods for distinguishing these cases, and determining equations for the points in the latter cases, are useful in a number of circumstances...

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.

External links

Videos

The Compleat Angler (1978)

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Algorithm overview

What happens in nature

Ray casting algorithm

Ray tracing algorithm

Advantages over other rendering methods

Disadvantages

Reversed direction of traversal of scene by the rays

In real time

Example

See also

External links

Videos