Ray casting
Encyclopedia
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 a
scene by providing users a virtual beam as a visual cue extending
from devices such as a baton or glove extending and intersecting
with objects in the environment.
The term was first used in computer graphics in a 1982 paper by Scott Roth to describe a method for rendering CSG
models.
Although "ray casting" and "ray tracing" were often used interchangeably in early computer graphics literature,
more recent usage tries to distinguish the two. The distinction is merely that ray casting never recursively traces secondary rays, whereas ray tracing may.
algorithms used in computer graphics
to render
three dimensional scenes to two dimensional screens by following rays
of light
from the eye
of the observer to a light source. Ray casting does not compute the new direction a ray of light might take after intersecting a surface on its way from the eye to the source of light. This eliminates the possibility of accurately rendering reflections
, refractions, or the natural falloff of shadow
s; however all of these elements can be faked to a degree, by creative use of texture maps or other methods. The high speed of calculation made ray casting a handy rendering method in early real-time 3D video games.
In nature, a light source emits a ray of light that travels, eventually, to a surface that interrupts its progress. One can think of this "ray" as a stream of photon
s travelling along the same path. At this point, any combination of three things might happen with this light ray: absorption
, reflection, and refraction. The 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%. 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. Attempting to simulate this real-world process of tracing light rays using a computer can be considered extremely wasteful, as only a minuscule fraction of the rays in a scene would actually reach the eye.
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 cone
s and sphere
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 modelling 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
.
s and a vertical slice of wall texture
is selected and scaled according to where in the world the ray hits a wall and how far it travels before doing so.
The purpose of the grid based levels is twofold - ray to wall collisions can be found more quickly since the potential hits become more predictable and memory overhead is reduced. However, encoding wide-open areas takes extra space.
Space" engine developed by NovaLogic
for the Comanche games
traces a ray through each column of screen pixels and tests each ray against points in a heightmap
. Then it transforms each element of the heightmap into a column of pixels, determines which are visible (that is, have not been covered up by pixels that have been drawn in front), and draws them with the corresponding color from the texture map.
, the ray casting problem is also known as the ray shooting problem and may be stated as the following query problem. Given a set of objects in d-dimensional space, preprocess them into a data structure
so that for each query ray the first object hit by the ray can be found quickly. The problem has been investigated for various settings: space dimension, types of objects, restrictions on query rays, etc. One technique is to use a sparse voxel octree
.
scene by providing users a virtual beam as a visual cue extending
from devices such as a baton or glove extending and intersecting
with objects in the environment.
The term was first used in computer graphics in a 1982 paper by Scott Roth to describe a method for rendering 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...
models.
Usage
Ray casting can refer to:- the general problem of determining the first object intersected by a ray,
- a technique for hidden surface removal based on finding the first intersection of a ray cast from the eye through each pixel of an image,
- a non-recursive variant of ray tracing that only casts primary rays, or
- a direct volume renderingVolume renderingIn scientific visualization and computer graphics, volume rendering is a set of techniques used to display a 2D projection of a 3D discretely sampled data set.A typical 3D data set is a group of 2D slice images acquired by aCT, MRI, or MicroCT scanner....
method, also called volume ray castingVolume ray castingVolume ray casting, sometimes called volumetric ray casting, volumetric ray tracing, or volume ray marching, is an image-based volume rendering technique. It computes 2D images from 3D volumetric data sets...
.
Although "ray casting" and "ray tracing" were often used interchangeably in early computer graphics literature,
more recent usage tries to distinguish the two. The distinction is merely that ray casting never recursively traces secondary rays, whereas ray tracing may.
Concept
Ray casting is not a synonym for ray tracing, but can be thought of as an abridged, and significantly faster, version of the ray tracing algorithm. Both are image orderImage and object order rendering
In computer graphics, image order algorithms iterate over the pixels in the image to be produced, rather than the elements in the scene to be rendered. Object order algorithms are those that iterate over the elements in the scene to be rendered, rather than the pixels in the image to be produced...
algorithms used in computer graphics
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....
to render
Rendering (computer graphics)
Rendering is the process of generating an image from a model , by means of computer programs. A scene file contains objects in a strictly defined language or data structure; it would contain geometry, viewpoint, texture, lighting, and shading information as a description of the virtual scene...
three dimensional scenes to two dimensional screens by following rays
Ray (optics)
In optics, a ray is an idealized narrow beam of light. Rays are used to model the propagation of light through an optical system, by dividing the real light field up into discrete rays that can be computationally propagated through the system by the techniques of ray tracing. This allows even very...
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...
from the eye
Projective geometry
In mathematics, projective geometry is the study of geometric properties that are invariant under projective transformations. This means that, compared to elementary geometry, projective geometry has a different setting, projective space, and a selective set of basic geometric concepts...
of the observer to a light source. Ray casting does not compute the new direction a ray of light might take after intersecting a surface on its way from the eye to the source of light. This eliminates the possibility of accurately rendering reflections
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...
, refractions, or the natural falloff of 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; however all of these elements can be faked to a degree, by creative use of texture maps or other methods. The high speed of calculation made ray casting a handy rendering method in early real-time 3D video games.
In nature, a light source emits a ray of light that 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 travelling along the same path. At this point, any combination of three 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, and refraction. The 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%. 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. Attempting to simulate this real-world process of tracing light rays using a computer can be considered extremely wasteful, as only a minuscule fraction of the rays in a scene would actually reach the eye.
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
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 cone
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...
s 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 modelling techniques and easily rendered.
Ray casting for producing computer graphics was first used by scientists at Mathematical Applications Group, Inc.
Mathematical Applications Group, Inc.
Mathematical Applications Group, Inc. was an early computer technology company founded in 1966 by Dr. Philip Mittelman, it was located in Elmsford, New York. It was one of four companies hired to create the CGI animation for the film Tron...
, (MAGI) of Elmsford, New York
Elmsford, New York
Elmsford is a village in Westchester County, New York, United States. Roughly one mile square, the village is fully contained within the borders of the town of Greenburgh...
.
Wolfenstein 3-D
The world in Wolfenstein 3-D is built from a square based grid of uniform height walls meeting solid coloured floors and ceilings. In order to draw the world, a single ray is traced for every column of screen pixelPixel
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 and a vertical slice of wall texture
Texture mapping
Texture mapping is a method for adding detail, surface texture , or color to a computer-generated graphic or 3D model. Its application to 3D graphics was pioneered by Dr Edwin Catmull in his Ph.D. thesis of 1974.-Texture mapping:...
is selected and scaled according to where in the world the ray hits a wall and how far it travels before doing so.
The purpose of the grid based levels is twofold - ray to wall collisions can be found more quickly since the potential hits become more predictable and memory overhead is reduced. However, encoding wide-open areas takes extra space.
Comanche series
The so-called "VoxelVoxel
A voxel is a volume element, representing a value on a regular grid in three dimensional space. This is analogous to a pixel, which represents 2D image data in a bitmap...
Space" engine developed by NovaLogic
NovaLogic
NovaLogic is a software developer and publisher established in 1985 and based in Calabasas, California. The company was founded by current CEO John A. Garcia....
for the Comanche games
Comanche series
Comanche is a series of simulation games published by NovaLogic. The goal of each of these games is to fly military missions in a RAH-66 Comanche attack helicopter, which was in development and prototyping at the time of release....
traces a ray through each column of screen pixels and tests each ray against points in a heightmap
Heightmap
In computer graphics, a heightmap or heightfield is a raster image used to store values, such as surface elevation data, for display in 3D computer graphics...
. Then it transforms each element of the heightmap into a column of pixels, determines which are visible (that is, have not been covered up by pixels that have been drawn in front), and draws them with the corresponding color from the texture map.
Computational geometry setting
In computational geometryComputational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, the ray casting problem is also known as the ray shooting problem and may be stated as the following query problem. Given a set of objects in d-dimensional space, preprocess them into a data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
so that for each query ray the first object hit by the ray can be found quickly. The problem has been investigated for various settings: space dimension, types of objects, restrictions on query rays, etc. One technique is to use a sparse voxel octree
Sparse voxel octree
A sparse voxel octree is a 3D computer graphics rendering technique using a raycasting or sometimes a ray tracing approach into an octree data representation....
.