  Interpolation is a fundamental technique in scientific computing and is at
the heart of many scientific visualization techniques. There is usually a
trade-off between the approximation capabilities of an interpolation scheme and
its evaluation efficiency. For many applications, it is important for a user to
be able to navigate their data in real time. In practice, the evaluation
efficiency (or speed) outweighs any incremental improvements in reconstruction
fidelity. In this two-part work, we first analyze from a general standpoint the
use of compact piece-wise polynomial basis functions to efficiently interpolate
data that is sampled on a lattice. In the sequel, we detail how we generate
efficient implementations via automatic code generation on both CPU and GPU
architectures. Specifically, in this paper, we propose a general framework that
can produce a fast evaluation scheme by analyzing the algebro-geometric
structure of the convolution sum for a given lattice and basis function
combination. We demonstrate the utility and generality of our framework by
providing fast implementations of various box splines on the Body Centered and
Face Centered Cubic lattices, as well as some non-separable box splines on the
Cartesian lattice. We also provide fast implementations for certain Voronoi
splines that have not yet appeared in the literature. Finally, we demonstrate
that this framework may also be used for non-Cartesian lattices in 4D.
