Beam tracing

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 also been 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. This initial viewing beam is intersected with each polygon in the environment, typically from nearest to furthest. 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. 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. Classical beam tracing works best in polygonal scenes; reflections and refractions involving curved surfaces are much harder for the basic method and typically require extensions.¹ 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.⁴ The backwards beam tracing technique has also recently 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 radio-wave 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), providing a convenient and compact way to represent visibility.

In underwater acoustics, Gaussian beam tracing (specifically the BELLHOP model) is used to predict sound pressure fields while avoiding singularities like caustics.⁶ In architectural acoustics and auralization, the method uses a 'beam tree' data structure to store sound paths, enabling real-time sound field updates for moving receivers in virtual environments.⁷ Published architectural-acoustics beam-tracing systems have also been used to compute transmission and wedge-diffraction paths, not just specular reflections.⁷⁸

Beam tracing is also used to predict wideband radio-wave propagation in three-dimensional indoor environments.⁹¹⁰

Beam tracing is related in concept to cone tracing.