Interpolation is fundamental in many applications that are based on multidimensional
scalar or vector fields. In such applications, it is possible to sample points from the
field, for example, through the numerical solution of some mathematical model. Because
point sampling may be computationally intensive, it is desirable to store samples in a data
structure and estimate the values of the field at intermediate points through interpolation.
We present methods based on building dynamic spatial data structures in which the samples
are computed on-demand, and adaptive strategies are used to avoid oversampling.
We first show how to apply this approach to accelerate realistic rendering through
ray-tracing. Ray-tracing can be formulated as a sampling and reconstruction problem,
where rays in 3-space are modeled as points in a 4-dimensional parameter space. Sample
rays are associated with various geometric attributes, which are then used in rendering.
We collect and store a relatively sparse set of sampled rays, and use inexpensive interpolation
methods to approximate the attribute values for other rays. We present two data
structures: (1) the ray interpolant tree (RI-tree), which is based on a kd-tree-like subdivision
of space, and (2) the simplex decomposition tree (SD-tree), which is based on
a hierarchical regular simplicial mesh, and improves the functionality of the RI-tree by
guaranteeing continuity.
For compact storage as well as efficient neighbor computation in the mesh, we
present a pointerless representation of the SD-tree. An essential element of this approach
is the development of a location code that enables efficient access and navigation of the
data structure. For this purpose we introduce a location code, called an LPT code, that
uniquely encodes the geometry of each simplex of the hierarchy. We present rules to compute
the neighbors of a given simplex efficiently through the use of this code. We show
how to traverse the associated tree and how to answer point location and interpolation
queries. Our algorithms work in arbitrary dimensions. We also demonstrate the use of the
SD-tree for rendering atmospheric effects. We present empirical evidence that our methods
can produce renderings of good quality significantly faster than simple ray-tracing. |