Dr. Kavita Bala (original) (raw)
Radiance Interpolants for Interactive Scene Editing and Ray Tracing
Kavita Bala
Supervised by Profs. Julie Dorsey and Seth Teller
Laboratory for Computer Science, MIT
Abstract
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.
- 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
Goals:
I) Interactive Ray Tracing
II) Interactive Scene Editing and Manipulation
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 Shadingwith guaranteed error bounds
Accelerate Visibilitycomputation
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 approximateradiance
- 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
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.
Accelerating visibility/pixel assignment
+ Exploits temporal coherence for smooth movements of view point Algorithm
- 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.
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.
 |
 |
|---|---|
 |
 |
Results
|
-> | |
-> |  |
|---|---|---|---|---|
| 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:
- Direct: Edited object
- Indirect: Reflections/refractions that depend on object, shadows cast by object Track and update affected region: Incrementalrendering
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.
Results
When an object is edited
Affected interpolants are typicallyidentifiedin 0.1 seconds by walking down the ray segment trees.
Affected interpolants are typicallyupdatedin 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