in Proceedings of of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX 2003), R. E. Ladner, Editor, SIAM, 2003, pp. 56-68.
We present a data structure, called a ray interpolant tree, or RI-tree, which stores a discrete set of directed lines in 3-space, each represented as a point in 4-space. Each directed line is associated with some small number of continuous geometric attributes. We show how this data structure can be used for answering interpolation queries, in which we are given an arbitrary ray in 3-space and wish to interpolate the attributes of neighboring rays in the data structure. We illustrate the practical value of the RI-tree in two applications from computer graphics: ray tracing and volume visualization. In particular, given objects defined by smooth curved surfaces, the RI-tree can produce high-quality renderings significantly faster than standard methods. We also investigate a number of tradeoffs between the space and time used by the data structure and the accuracy of the interpolation results.
| Viewpoint animation (360 Frames) |
|
|
Click for full animation (12Meg, MPEG-2). |
| Figure 11(a): Ray-traced image |
 |
Click for full resolution. |
| Figure 11(c): Interpolated image (distance threshold: 0.05, angular threshold:10) |
 |
Click for full resolution. |
| Figure 11(b): Interpolated image (distance threshold: 0.25, angular threshold:30) |
 |
Click for full resolution. |
| Figure 10: Radiance vs. Ray Interpolation |
10(a): Normal Interpolation, Max_Depth = 28, Number of nodes = 7.4K
10(b): Normal Interpolation, Max_Depth = 32, Number of nodes = 13K
10(c): Radiance Interpolation, Max_Depth = 32, Number of nodes = 25K
10(d): Depth Color Scale
To Dave Mount's home page.
To Betul Atalay's home page.
Last updated November 15, 2003.