Beam tracing
Encyclopedia
Beam tracing is an algorithm
to simulate wave propagation
.
It was developed in the context of computer graphics
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
) polygon
al 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
. 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
of the image plane
. 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.
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
have become more popular for rendering calculations.
A 'backwards' variant of beam tracing casts beams from the light source into the environment. Similar to backwards raytracing and 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 . 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
.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
to simulate wave propagation
Wave propagation
Wave propagation is any of the ways in which waves travel.With respect to the direction of the oscillation relative to the propagation direction, we can distinguish between longitudinal wave and transverse waves....
.
It was developed in the context of 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...
3D
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...
scenes,
but it has been also used in other similar areas such as acoustics
Acoustics
Acoustics is the interdisciplinary science that deals with the study of all mechanical waves in gases, liquids, and solids including vibration, sound, ultrasound and infrasound. A scientist who works in the field of acoustics is an acoustician while someone working in the field of acoustics...
and
electromagnetism
Electromagnetism
Electromagnetism is one of the four fundamental interactions in nature. The other three are the strong interaction, the weak interaction and gravitation...
simulations.
Beam tracing is a derivative of the ray tracing algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that replaces rays, which have no thickness, with beams. Beams are shaped like unbounded pyramids, with (possibly complex
Complex polygon
The term complex polygon can mean two different things:*In computer graphics, as a polygon which is neither convex nor concave.*In geometry, as a polygon in the unitary plane, which has two complex dimensions.-Computer graphics:...
) polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
al cross sections. Beam tracing was first proposed by Paul Heckbert and Pat Hanrahan
Pat Hanrahan
Pat Hanrahan is a computer graphics researcher, the Canon USA Professor of Computer Science and Electrical Engineering in the Computer Graphics Laboratory at Stanford University....
.
In beam tracing, a pyramidal beam is initially cast through the entire viewing frustum
Viewing frustum
In 3D computer graphics, the viewing frustum or view frustum is the region of space in the modeled world that may appear on the screen; it is the field of view of the notional camera. The exact shape of this region varies depending on what kind of camera lens is being simulated, but typically it is...
. 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
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....
of the 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...
. This is then split up into sub-beams based on its intersection with scene geometry. 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 transmission (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...
) 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.
Beam tracing solves certain problems related to sampling and aliasing
Aliasing
In signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable when sampled...
, 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
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
algorithms like distributed ray tracing
Distributed ray tracing
Distributed ray tracing, also called distribution ray tracing and stochastic ray tracing, is a refinement of ray tracing that allows for the rendering of "soft" phenomena....
have become more popular for rendering calculations.
A 'backwards' variant of beam tracing casts beams from the light source into the environment. Similar to backwards raytracing and 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...
, backwards beam tracing may be used to efficiently model lighting effects such as caustics
Caustic (optics)
In optics, a caustic or caustic network is the envelope of light rays reflected or refracted by a curved surface or object, or the projection of that envelope of rays on another surface. The caustic is a curve or surface to which each of the light rays is tangent, defining a boundary of an...
. 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 . 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
Cone tracing
Cone tracing is a derivative of the ray tracing algorithm that replaces rays, which have no thickness, with cones. Cone tracing is related to beam tracing, but uses circular rather than polygonal cross sections....
.