in Proceedings of of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX 2003), R. E. Ladner, Editor, SIAM, 2003, pp. 5668.
We present a data structure, called a ray interpolant tree, or RItree, which stores a discrete set of directed lines in 3space, each represented as a point in 4space. 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 3space and wish to interpolate the attributes of neighboring rays in the data structure. We illustrate the practical value of the RItree in two applications from computer graphics: ray tracing and volume visualization. In particular, given objects defined by smooth curved surfaces, the RItree can produce highquality 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, MPEG2). 
Figure 11(a): Raytraced 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.