Sparse high‐degree polynomials for wide‐angle lenses

Rendering with accurate camera models greatly increases realism and improves the match of synthetic imagery to real‐life footage. Photographic lenses can be simulated by ray tracing, but the performance depends on the complexity of the lens system, and some operations required for modern algorithms, such as deterministic connections, can be difficult to achieve. We generalise the approach of polynomial optics, i.e. expressing the light field transformation from the sensor to the outer pupil using a polynomial, to work with extreme wide angle (fisheye) lenses and aspherical elements. We also show how sparse polynomials can be constructed from the large space of high‐degree terms (we tested up to degree 15). We achieve this using a variant of orthogonal matching pursuit instead of a Taylor series when computing the polynomials. We show two applications: photorealistic rendering using Monte Carlo methods, where we introduce a new aperture sampling technique that is suitable for light tracing, and an interactive preview method suitable for rendering with deep images.     

Efficient Ray Tracing Through Aspheric Lenses and Imperfect Bokeh Synthesis

We present an efficient ray‐tracing technique to render bokeh effects produced by parametric aspheric lenses. Contrary to conventional spherical lenses, aspheric lenses do generally not permit a simple closed‐form solution of ray‐surface intersections. We propose a numerical root‐finding approach, which uses tight proxy surfaces to ensure a good initialization and convergence behavior. Additionally, we simulate mechanical imperfections resulting from the lens fabrication via a texture‐based approach. Fractional Fourier transform and spectral dispersion add additional realism to the synthesized bokeh effect. Our approach is well‐suited for execution on graphics processing units (GPUs) and we demonstrate complex defocus‐blur and lens‐flare effects.     

Importance Sampling Techniques for Path Tracing in Participating Media

We introduce a set of robust importance sampling techniques which allow efficient calculation of direct and indirect lighting from arbitrary light sources in both homogeneous and heterogeneous media. We show how to distribute samples along a ray proportionally to the incoming radiance for point and area lights. In heterogeneous media, we decouple ray marching from light calculations by computing a representation of the transmittance function that can be quickly evaluated during sampling, at the cost of a small amount of bias. This representation also allows the calculation of another probability density function which can direct samples to regions most likely to scatter light. These techniques are orthogonal and can be combined via multiple importance sampling to further reduce variance. Our method has very modest per‐ray memory requirements and does not require any preprocessing, making it simple to integrate into production ray tracing based renderers.     

Polynomial Optics: A Construction Kit for Efficient Ray‐Tracing of Lens Systems

Simulation of light transport through lens systems plays an important role in graphics. While basic imaging properties can be conveniently derived from linear models (like ABCD matrices), these approximations fail to describe nonlinear effects and aberrations that arise in real optics. Such effects can be computed by proper ray tracing, for which, however, finding suitable sampling and filtering strategies is often not a trivial task. Inspired by aberration theory, which describes the deviation from the linear ray transfer in terms of wavefront distortions, we propose a ray‐space formulation for nonlinear effects. In particular, we approximate the analytical solution to the ray tracing problem by means of a Taylor expansion in the ray parameters. This representation enables a construction‐kit approach to complex optical systems in the spirit of matrix optics. It is also very simple to evaluate, which allows for efficient execution on CPU and GPU alike, including the computation of mixed derivatives of any order. We evaluate fidelity and performance of our polynomial model, and show applications in high‐quality offline rendering and at interactive frame rates.     

Decoupled Space and Time Sampling of Motion and Defocus Blur for Unified Rendering of Transparent and Opaque Objects

We propose a unified rendering approach that jointly handles motion and defocus blur for transparent and opaque objects at interactive frame rates. Our key idea is to create a sampled representation of all parts of the scene geometry that are potentially visible at any point in time for the duration of a frame in an initial rasterization step. We store the resulting temporally‐varying fragments (t‐fragments) in a bounding volume hierarchy which is rebuild every frame using a fast spatial median construction algorithm. This makes our approach suitable for interactive applications with dynamic scenes and animations. Next, we perform spatial sampling to determine all t‐fragments that intersect with a specific viewing ray at any point in time. Viewing rays are sampled according to the lens uv‐sampling for depth‐of‐field effects. In a final temporal sampling step, we evaluate the predetermined viewing ray/t‐fragment intersections for one or multiple points in time. This allows us to incorporate all standard shading effects including transparency. We describe the overall framework, present our GPU implementation, and evaluate our rendering approach with respect to scalability, quality, and performance.     

Practical Real‐Time Lens‐Flare Rendering

We present a practical real‐time approach for rendering lens‐flare effects. While previous work employed costly ray tracing or complex polynomial expressions, we present a coarser, but also significantly faster solution. Our method is based on a first‐order approximation of the ray transfer in an optical system, which allows us to derive a matrix that maps lens flare‐producing light rays directly to the sensor. The resulting approach is easy to implement and produces physically‐plausible images at high framerates on standard off‐the‐shelf graphics hardware.     

SAH guided spatial split partitioning for fast BVH construction

We present a new SAH guided approach to subdividing triangles as the scene is coarsely partitioned into smaller sets of spatially coherent triangles. Our triangle split approach is integrated into the partitioning stage of a fast BVH construction algorithm, but may as well be used as a stand alone pre‐split pass. Our algorithm significantly reduces the number of split triangles compared to previous methods, while at the same time improving ray tracing performance compared to competing fast BVH construction techniques. We compare performance on Intel's Embree ray tracer and show that BVH construction with our splitting algorithm is always faster than Embree's pre‐split construction algorithm. We also show that our algorithm builds significantly improved quality trees that deliver higher ray tracing performance. Our algorithm is implemented into Embree's open source ray tracing framework, and the source code will be released late 2015.     

The photon pipeline revisited

With the development of real-time ray tracing in recent years, it is now very interesting to ask if real-time performance can be achieved for high-quality rendering algorithms based on ray tracing. In this paper, we propose a pipelined architecture to implement reverse photon mapping. Our architecture can use real-time ray tracing to generate photon points and camera points, so the main challenge is how to implement the gathering phase that computes the final image. Traditionally, the gathering phase of photon mapping has only allowed coarse-grain parallelism, and this situation has been a source of inefficiency, cache thrashing, and limited throughput. To avail fine-grain pipelining and data parallelism, we arrange computations so that photons can be processed independently, similar to the way that triangles are efficiently processed in traditional real-time graphics hardware. We employ several techniques to improve cache behavior and to reduce communication overhead. Simulations show that the bandwidth requirements of this architecture are within the capacity of current and future hardware, and this suggests that photon mapping may be a good choice for real-time performance in the future.     

Parallel BVH Construction using Progressive Hierarchical Refinement

We propose a novel algorithm for construction of bounding volume hierarchies (BVHs) for multi‐core CPU architectures. The algorithm constructs the BVH by a divisive top‐down approach using a progressively refined cut of an existing auxiliary BVH. We propose a new strategy for refining the cut that significantly reduces the workload of individual steps of BVH construction. Additionally, we propose a new method for integrating spatial splits into the BVH construction algorithm. The auxiliary BVH is constructed using a very fast method such as LBVH based on Morton codes. We show that the method provides a very good trade‐off between the build time and ray tracing performance. We evaluated the method within the Embree ray tracing framework and show that it compares favorably with the Embree BVH builders regarding build time while maintaining comparable ray tracing speed.     

Time‐Continuous Quasi‐Monte Carlo Ray Tracing

Domain‐continuous visibility determination algorithms have proved to be very efficient at reducing noise otherwise prevalent in stochastic sampling. Even though they come with an increased overhead in terms of geometrical tests and visibility information management, their analytical nature provides such a rich integral that the pay‐off is often worth it. This paper presents a time‐continuous, primary visibility algorithm for motion blur aimed at ray tracing. Two novel intersection tests are derived and implemented. The first is for ray versus moving triangle and the second for ray versus moving AABB intersection. A novel take on shading is presented as well, where the time continuum of visible geometry is adaptively point‐sampled. Static geometry is handled using supplemental stochastic rays in order to reduce spatial aliasing. Finally, a prototype ray tracer with a full time‐continuous traversal kernel is presented in detail. The results are based on a variety of test scenarios and show that even though our time‐continuous algorithm has limitations, it outperforms multi‐jittered quasi‐Monte Carlo ray tracing in terms of image quality at equal rendering time, within wide sampling rate ranges.     

Using Wavefront Tracing for the Visualization and Optimization of Progressive Lenses

Progressive addition lenses are a relatively new approach to compensate for defects of the human visual system. While traditional spectacles use rotationally symmetric lenses, progressive lenses require the specification of free-form surfaces. This poses difficult problems for the optimal design and its visual evaluation.
This paper presents two new techniques for the visualization of optical systems and the optimization of progressive lenses. Both are based on the same wavefront tracing approach to accurately evaluate the refraction properties of complex optical systems.
We use the results of wavefront tracing for continuously re-focusing the eye during rendering. Together with distribution ray tracing, this yields high-quality images that accurately simulate the visual quality of an optical system. The design of progressive lenses is difficult due to the trade-off between the desired properties of the lens and unavoidable optical errors, such as astigmatism and distortions. We use wavefront tracing to derive an accurate error functional describing the desired properties and the optical error across a lens. Minimizing this error yields optimal free-form lens surfaces.
While the basic approach is much more general, in this paper, we describe its application to the particular problem of designing and evaluating progressive lenses and demonstrate the benefits of the new approach with several example images.     

SATO: Surface Area Traversal Order for Shadow Ray Tracing

We present the surface area traversal order (SATO) metric to accelerate shadow ray traversal. Our formulation uses the surface area of each child node to compute the TO. In this metric, we give a traversal priority to the child node with the larger surface area to quickly find occluders. Our algorithm reduces the pre‐processing overhead significantly, and is much faster than other metrics. Overall, the SATO is useful for ray tracing large and complex dynamic scenes (e.g. a few million triangles) with shadows.     

The Use of Precomputed Triangle Clusters for Accelerated Ray Tracing in Dynamic Scenes

In this paper we present a hybrid algorithm for building the bounding volume hierarchy (BVH) that is used in accelerating ray tracing of animated models. This algorithm precomputes densely packed clusters of triangles on surfaces. Folowing that, a set of clusters is used to rebuild the BVH in every frame. Our approach utilizes the assumption that groups of connected triangles remain connected throughout the course of the animation. We introduce a novel heuristic to create triangle clusters that are designed for high performance ray tracing. This heuristic combines the density of connectivity, geometric size and the shape of the cluster.
Our approach accelerates the BVH builder by an order of magnitude rebuilding only the set of clusters that is much smaller than the original set of triangles. The speed-up is achieved against a 'brute-force' BVH builder that repartitions all triangles in every frame of animation without using any pre-clustering. The rendering performance is not affected when a cluster contains a few dozen triangles. We demonstrate the real-time/interactive ray tracing performance for highly-dynamic complex models.     

Interactive Simulation of the Human Eye Depth of Field and Its Correction by Spectacle Lenses

This paper describes a fast rendering algorithm for verification of spectacle lens design. Our method simulates refraction corrections of astigmatism as well as myopia or presbyopia. Refraction and defocus are the main issues in the simulation. For refraction, our proposed method uses per-vertex basis ray tracing which warps the environment map and produces a real-time refracted image which is subjectively as good as ray tracing. Conventional defocus simulation was previously done by distribution ray tracing and a real-time solution was impossible. We introduce the concept of a blur field, which we use to displace every vertex according to its position. The blurring information is precomputed as a set of field values distributed to voxels which are formed by evenly subdividing the perspective projected space. The field values can be determined by tracing a wavefront from each voxel through the lens and the eye, and by evaluating the spread of light at the retina considering the best human accommodation effort. The blur field is stored as texture data and referred to by the vertex shader that displaces each vertex. With an interactive frame rate, blending the multiple rendering results produces a blurred image comparable to distribution ray tracing output.     

Stackless Multi‐BVH Traversal for CPU,MIC and GPU Ray Tracing

Stackless traversal algorithms for ray tracing acceleration structures require significantly less storage per ray than ordinary stack‐based ones. This advantage is important for massively parallel rendering methods, where there are many rays in flight. On SIMD architectures, a commonly used acceleration structure is the MBVH, which has multiple bounding boxes per node for improved parallelism. It scales to branching factors higher than two, for which, however, only stack‐based traversal methods have been proposed so far. In this paper, we introduce a novel stackless traversal algorithm for MBVHs with up to four‐way branching. Our approach replaces the stack with a small bitmask, supports dynamic ordered traversal, and has a low computation overhead. We also present efficient implementation techniques for recent CPU, MIC (Intel Xeon Phi) and GPU (NVIDIA Kepler) architectures.     

Visibility Silhouettes for Semi‐Analytic Spherical Integration

At each shade point, the spherical visibility function encodes occlusion from surrounding geometry, in all directions. Computing this function is difficult and point‐sampling approaches, such as ray‐tracing or hardware shadow mapping, are traditionally used to efficiently approximate it. We propose a semi‐analytic solution to the problem where the spherical silhouette of the visibility is computed using a search over a 4D dual mesh of the scene. Once computed, we are able to semi‐analytically integrate visibility‐masked spherical functions along the visibility silhouette, instead of over the entire hemisphere. In this way, we avoid the artefacts that arise from using point‐sampling strategies to integrate visibility, a function with unbounded frequency content. We demonstrate our approach on several applications, including direct illumination from realistic lighting and computation of pre‐computed radiance transfer data. Additionally, we present a new frequency‐space method for exactly computing all‐frequency shadows on diffuse surfaces. Our results match ground truth computed using importance‐sampled stratified Monte Carlo ray‐tracing, with comparable performance on scenes with low‐to‐moderate geometric complexity.     

MCFTLE: Monte Carlo Rendering of Finite‐Time Lyapunov Exponent Fields

Traditionally, Lagrangian fields such as finite‐time Lyapunov exponents (FTLE) are precomputed on a discrete grid and are ray casted afterwards. This, however, introduces both grid discretization errors and sampling errors during ray marching. In this work, we apply a progressive, view‐dependent Monte Carlo‐based approach for the visualization of such Lagrangian fields in time‐dependent flows. Our approach avoids grid discretization and ray marching errors completely, is consistent, and has a low memory consumption. The system provides noisy previews that converge over time to an accurate high‐quality visualization. Compared to traditional approaches, the proposed system avoids explicitly predefined fieldline seeding structures, and uses a Monte Carlo sampling strategy named Woodcock tracking to distribute samples along the view ray. An acceleration of this sampling strategy requires local upper bounds for the FTLE values, which we progressively acquire during the rendering. Our approach is tailored for high‐quality visualizations of complex FTLE fields and is guaranteed to faithfully represent detailed ridge surface structures as indicators for Lagrangian coherent structures (LCS). We demonstrate the effectiveness of our approach by using a set of analytic test cases and real‐world numerical simulations.     

A Vectorial Framework for Ray Traced Diffusion Curves

Diffusion curves allow creating complex, smoothly shaded images by diffusing colours defined at curves. These methods typically require the solution of a global optimization problem (over either the pixel grid or an intermediate tessellated representation) to produce the final image, making fully parallel implementation challenging. An alternative approach, inspired by global illumination, uses 2D ray tracing to independently compute each pixel value. This formulation allows trivial parallelism, but it densely computes values even in smooth regions and sacrifices support for instancing and layering. We describe a sparse, ray traced, multi‐layer framework that incorporates many complementary benefits of these existing approaches. Our solution avoids the need for a global solve and trivially allows parallel GPU implementation. We leverage an intermediate triangular representation with cubic patches to synthesize smooth images faithful to the per‐pixel solution. The triangle mesh provides a resolution–independent, vectorial representation and naturally maps diffusion curve images to a form natively supported by standard vector graphics and triangle rasterization pipelines. Our approach supports many features which were previously difficult to incorporate into a single system, including instancing, layering, alpha blending, texturing, local blurring, continuity control and parallel computation. We also show how global diffusion curves can be combined with local painted strokes in one coherent system.     

Memory Considerations for Low Energy Ray Tracing

We propose two hardware mechanisms to decrease energy consumption on massively parallel graphics processors for ray tracing. First, we use a streaming data model and configure part of the L2 cache into a ray stream memory to enable efficient data processing through ray reordering. This increases L1 hit rates and reduces off‐chip memory energy substantially through better management of off‐chip memory access patterns. To evaluate this model, we augment our architectural simulator with a detailed memory system simulation that includes accurate control, timing and power models for memory controllers and off‐chip dynamic random‐access memory . These details change the results significantly over previous simulations that used a simpler model of off‐chip memory, indicating that this type of memory system simulation is important for realistic simulations that involve external memory. Secondly, we employ reconfigurable special‐purpose pipelines that are constructed dynamically under program control. These pipelines use shared execution units that can be configured to support the common compute kernels that are the foundation of the ray tracing algorithm. This reduces the overhead incurred by on‐chip memory and register accesses. These two synergistic features yield a ray tracing architecture that reduces energy by optimizing both on‐chip and off‐chip memory activity when compared to a more traditional approach.     

Shallow Bounding Volume Hierarchies for Fast SIMD Ray Tracing of Incoherent Rays

Photorealistic image synthesis is a computationally demanding task that relies on ray tracing for the evaluation of integrals. Rendering time is dominated by tracing long paths that are very incoherent by construction. We therefore investigate the use of SIMD instructions to accelerate incoherent rays. SIMD is used in the hierarchy construction, the tree traversal and the leaf intersection. This is achieved by increasing the arity of acceleration structures, which also reduces memory requirements. We show that the resulting hierarchies can be built quickly and are smaller than acceleration structures known so far while at the same time outperforming them for incoherent rays. Our new acceleration structure speeds up ray tracing by a factor of 1.6 to 2.0 compared to a highly optimized bounding interval hierarchy implementation, and 1.3 to 1.6 compared to an efficient kd‐tree. At the same time, the memory requirements are reduced by 10–50%. Additionally we show how a caching mechanism in conjunction with this memory efficient hierarchy can be used to speed up shadow rays in a global illumination algorithm without increasing the memory footprint. This optimization decreased the number of traversal steps up to 50%.