Ray casting

From Wikipedia, the free encyclopedia

Ray casting is a computer image generation method used to produce a three-dimensional perspective of a scene, using mathematics.

1 Concept
2 Wolfenstein 3d
3 Comanche series
4 Build engine
5 Doom
6 'Mode 7'
7 References and External links

[edit] 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 order 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 tangents 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 fall off of shadows -- 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 method for the rendering in early real-time 3D video games.

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

[edit] Wolfenstein 3d

The world in Wolfenstein 3d 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 pixels 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.

[edit] Comanche series

The so-called "Voxel 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.^[1]

[edit] Build engine

The Build engine uses a unique form of raycasting, as described by its creator-

This is how Build works: It starts by looking at the front-facing walls in the current sector. It then renders walls 1 at a time, starting with the first unoccluded wall it finds on the list. (There is always at least 1 unoccluded wall). I do hidden surface removal by remembering the highest and lowest points that have been drawn so far to each column. Ceilings and floors fill the gaps between these old high and low points and the tops and bottoms of the new wall. If a wall is a portal, I add the walls of the sector behind it to the list of walls left to consider. Rendering ends when either the wall list is empty, or all columns are filled.

[edit] Doom

Doom's use of ray casting is very limited. The Doom engine's primary drawing algorithm is based on a binary space partitioning tree system that determines which walls and floors are visible from any particular position. Ray casting is used to determine texture position and scaling on walls but only after the walls that the rays will hit are already known. This has the advantage of replacing thousands of expensive divide operations with trigonometric multiplies.

[edit] 'Mode 7'

'Mode 7' is a popular name for the display of textured horizontal surfaces, named after the display mode that allows their pixel plotting to be done in hardware on the Super Nintendo. These require knowledge of texture offset and scale per pixel row and are often implemented using the same trigonometric means as the other algorithms described here.