Radiance Interpolants for Interactive Scene Editing and Ray Tracing

Kavita Bala

Supervised by Profs. Julie Dorsey and Seth Teller

Laboratory for Computer Science, MIT


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 
     I) Interactive Ray Tracing
    II) Interactive Scene Editing and Manipulation


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

Accelerating shading with guaranteed error bounds

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

High-Level Algorithm

  • Collect radiance samples lazily
  • Store samples in data structure
  • For subsequent pixels, reuse stored samples to approximate radiance
  • Use error predicate to adaptively sample radiance. The user specifies an error bound epsilon that is respected.

  • Ray parameterization

  • Ray tracers compute radiance along rays in space.
  • Radiance is a function over the space of all rays.
  • Every ray can be parameterized by 4 intercepts.


    Collecting, storing and reusing samples: 4D linetrees

  • Samples are collected lazily
  • Stored in 4D trees called linetrees
  • Sixteen samples are collected for each linetree cell
  • Per-surface interpolants are built
  • The pixel's radiance value is approximated by quadrilinear interpolation of the sixteen samples

    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

    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.

    Accelerating visibility/pixel assignment
  • Reprojects linetrees from previous frame to new viewpoint.
  • View-dependent clipping of front faces and back faces to determine visible linetree cell.
  • Shaft cull against clipped visible linetrees to guarantee correct pixel assignment.

    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). 

    Additional Results

    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. 

    Interactive Scene Editing

    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:

    Track and update affected region: Incremental rendering

        + 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