Ray tracers are usually regarded as off-line rendering algorithms that are too slow for interactive use. My thesis introduces techniques to accelerate ray tracing and to support interactive editing of ray-traced scenes. These techniques should be useful in many applications, such as architectural walk-throughs, modeling, and games, and will enhance both interactive and batch rendering.

The thesis introduces radiance interpolants: radiance samples that can be used to rapidly approximate radiance with bounded approximation error. Radiance interpolants capture object-space, ray-space, image-space and temporal coherence in the radiance function. New algorithms are presented that efficiently, accurately and conservatively bound approximation error.

The interpolant ray tracer is a novel renderer that uses radiance interpolants to accelerate both primary operations of a ray tracer: shading and visibility determination. Shading is accelerated by quadrilinearly interpolating the radiance samples associated with a radiance interpolant. Determination of the visible object at each pixel is accelerated by reprojecting interpolants as the user's viewpoint changes. A fast scan-line algorithm then achieves high performance without sacrificing image quality. For a smoothly varying viewpoint, the combination of lazily sampled interpolants and reprojection substantially accelerates the ray tracer. Additionally, an efficient cache management algorithm keeps the memory footprint of the system small with negligible overhead.

The interpolant ray tracer is the first accelerated ray tracer that reconstructs radiance from sparse samples while bounding error conservatively. The system controls error by adaptively sampling at discontinuities and radiance non-linearities. Because the error introduced by interpolation does not exceed a user-specified bound, the user can trade performance for quality.

The interpolant ray tracer also supports interactive scene editing with incremental rendering; it is the first incremental ray tracer to support both object manipulation and changes to the viewpoint. A new hierarchical data structure, called the ray segment tree tracks the dependencies of radiance interpolants on regions of world space. When the scene is edited, affected interpolants are rapidly identified and updated by traversing these ray segment trees.

For details: thesis, and shorter version published in TOG

Motivation: Ray tracing produces high quality images, but is slow.

+ High quality imagery  Arbitrary implicit primitives Global illumination effects

- Slow expensive computation
Ray tracing is traditionally regarded as an offline computation
For each pixel of an image the ray tracer determines:
Visibility (pixel assignment)
Shading

Insights:

+ Large amount of coherence (spatial and temporal) to be exploited.

+ Visibility and shading can be separated out and independently accelerated.

+ User would like to trade performance for quality.

How to accelerate ray tracing
   Accelerate Shading with guaranteed error bounds
  Accelerate Visibility computation

Ray tracers compute radiance; treat ray tracing as a sampling problem.

High-Level Algorithm

Ray parameterization

Collecting, storing and reusing samples: 4D linetrees

Magenta rectangles are on the front face of linetree. Blue rectangles are on back face of linetree.	Green rays are the 16 sample rays associated with the linetree cell.

Guaranteed error bound

+ User-specified error bound epsilon is used to trade performance for quality.

+ Error predicate guides sampling where necessary. Predicate detects both:
Discontinuities (shadows, blockers, silhouettes)
Non-linear radiance (generalized interval arithmetic to compute error bounds)

The left column shows rendered images, the middle column shows the associated linetrees and the right column shows the maximum error as a height-field. The top row does not have error tests enabled, the middle row has epsilon=2.5, the bottom row has epsilon=0.625. 

Note the Error-driven subdivision.

+ Exploits temporal coherence for smooth movements of view point

Reproject linetree cells from previous frame.	Detect occlusion using shaft culling.

The top row shows the reprojection buffer and a color-coded image. Purple shaded pixels are span-filled (fast path), blue-gray pixels are interpolated (ip path) and the green and yellow pixels are not accelerated (slow path). On the second row, the left image shows all the span-filled pixels and the right image shows the span-filled and interpolated pixels.

	->		->
76% of the pixels can be reprojected from the previous frame (Fast Path).		16% of the pixels are interpolated (Accelerated Path).		8% of the pixels are shaded by the standard ray tracer (Slow Path).

The first row shows rendered images, while the second row shows color-coded images. Interpolation succeeds in gray-blue regions. Yellow and green correspond to failure due to discontinuities. Magenta corresponds to failure due to non-linearity. Red corresponds to failure due to potential occlusion. 

When an object is edited (moved, attribute changed) the entire scene need not be re-rendered from scratch.
Part of the scene that is affected is:

• Direct: Edited object
• Indirect: Reflections/refractions that depend on object, shadows cast by object

Insight:
    + The interpolants affected by an edit can be rapidly identified using an auxilliary data structure - ray segment trees.
    When a radiance interpolant is updated, all rays covered by the interpolant are updated.
 

Light rays, occluders, reflections.

For each case, we would like to track the regions of space that affect an interpolant

Problem with 4D rays is that it is too conservative.

Therefore use an extra parameter t, which is the distance along the ray.
Identify a new space called Ray segment space.
Important property: A box in ray segment space is a shaft in world space.
Can build trees, called ray segment trees, over ray segment space, that stores all the interpolants dependencies.

When an object is edited
    Affected interpolants are typically identified in 0.1 seconds by walking down the ray segment trees.
    Affected interpolants are typically updated in 1 second.
 

The left column shows the rendered scene for two edits: 
a) delete top of sculpture b) delete bottom of sculpture. 
The right column shows a color-coded image of the scene. 
The red pixels are the regions that are affected by the edit. 
The rest of the scene is rendered using interpolants from before the edit. 

Page maintained by: Kavita Bala (kb@graphics.cornell.edu)
Last updated: September 22 1999