Optimal sampling lattices and trivariate box splines

The Body Centered Cubic (BCC) and Face Centered Cubic (FCC) lattices along with a set of box splines for sampling and reconstruction of trivariate functions are proposed. The BCC lattice is demonstrated to be the optimal choice of a pattern for {\em generic} sampling purposes. While the FCC lattice is the second best choice for this purpose, both FCC and BCC lattices significantly outperform the accuracy of the commonly-used Cartesian 3-D lattice. A set of box splines tailored to the geometry of the BCC and FCC lattices are proposed for approximation of trivariate functions on these lattices. Furthermore, for efficient evaluation, the explicit piecewise polynomial representation of the proposed box splines on the BCC lattice are derived. This derivation can be generalized for other box splines to provide efficient evaluation of box splines at arbitrary points. Despite the common assumption on the superior computational performance of tensor-product reconstruction, it is demonstrated that these non-separable box spline-based reconstructions on the BCC and FCC lattices outperform their tensor-product counterparts on the Cartesian lattice. In particular, the box spline-based reconstruction on the BCC lattice is shown to be twice as efficient as the corresponding tensor-product B-spline solution on the Cartesian lattice. Hence, we establish the fact that not only are these non-Cartesian lattices attractive from the sampling-theory aspects, they also allow for efficient and superior reconstruction algorithms.