Beam tracing is an
algorithm to simulate
wave propagation.
It was developed in the context of
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great deal ...
to
render 3D scenes,
but it has been also used in other similar areas such as
acoustics and
electromagnetism simulations.
Beam tracing is a derivative of the
ray tracing algorithm that replaces rays, which have no thickness, with beams. Beams are shaped like unbounded pyramids, with (possibly
complex)
polygonal cross sections. Beam tracing was first proposed by
Paul Heckbert and
Pat Hanrahan.
In beam tracing, a pyramidal beam is initially cast through the entire
viewing frustum
In 3D computer graphics, the view frustum (also called viewing frustum) is the region of space in the modeled world that may appear on the screen; it is the field of view of a perspective virtual camera system.
The view frustum is typically ...
. This initial viewing beam is intersected with each polygon in the environment, typically from nearest to farthest. Each polygon that intersects with the beam must be visible, and is removed from the shape of the beam and added to a render queue. When a beam intersects with a reflective or refractive polygon, a new beam is created in a similar fashion to ray-tracing.
A variant of beam tracing casts a pyramidal beam through each
pixel
In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a raster image, or the smallest point in an all points addressable display device.
In most digital display devices, pixels are the s ...
of the
image plane
In 3D computer graphics, the image plane is that plane in the world which is identified with the plane of the display monitor used to view the image that is being rendered. It is also referred to as screen space. If one makes the analogy of taking ...
. This is then split up into sub-beams based on its intersection with scene geometry.
Reflection and transmission (
refraction) rays are also replaced by beams. This sort of implementation is rarely used, as the geometric processes involved are much more complex and therefore expensive than simply casting more rays through the pixel.
Cone tracing is a similar technique using a cone instead of a complex pyramid.
Beam tracing solves certain problems related to
sampling and
aliasing, which can plague conventional ray tracing approaches. Since beam tracing effectively calculates the path of every possible ray within each beam (which can be viewed as a dense bundle of adjacent rays), it is not as prone to under-sampling (missing rays) or over-sampling (wasted computational resources). The computational complexity associated with beams has made them unpopular for many visualization applications. In recent years,
Monte Carlo algorithms like
distributed ray tracing (and
Metropolis light transport?) have become more popular for rendering calculations.
A 'backwards' variant of beam tracing casts beams from the light source into the environment. Similar to
photon mapping, backwards beam tracing may be used to efficiently model lighting effects such as
caustics. Recently the backwards beam tracing technique has also been extended to handle glossy to diffuse material interactions (glossy backward beam tracing) such as from polished metal surfaces.
Beam tracing has been successfully applied to the fields of acoustic modelling and electromagnetic propagation modelling.
[Steven Fortune,]
A Beam-Tracing Algorithm for Prediction of Indoor Radio Propagation
, in WACG 1996: 157-166 In both of these applications, beams are used as an efficient way to track deep reflections from a source to a receiver (or vice versa). Beams can provide a convenient and compact way to represent visibility. Once a beam tree has been calculated, one can use it to readily account for moving transmitters or receivers.
Beam tracing is related in concept to
cone tracing.
See also
*
Pat Hanrahan
*
Ray tracing (graphics)
References
{{DEFAULTSORT:Beam Tracing
Global illumination algorithms