Interpolation over Light Fields with Applications in Computer Graphics

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 interpo-lation 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 vi-sualization. In particular, given objects defined by smooth curved surfaces, the RI-tree can produce high-quality renderings signifi-cantly 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.