Quick Links and Educational Videos

This presentation is a good overview of this research area.

This lecture, in solid state chemistry, is a good introduction to 3-D lattices and how they appear in crystal structures.

Overview

The Cartesian lattice is, quite commonly, the pattern of choice for uniform sampling and approximation of data in many computing applications. However, it turns out that Cartesian lattice is not the best pattern for sampling and discretizing many continuous domain functions. It has been proven that the Body Centered Cubic (BCC) lattice is the best generic pattern for sampling and approximation of tri-variate data. The optimality of the BCC lattice can be explained by its inverse relationship to the densest sphere packing lattice- the Face Centered Cubic (FCC) lattice.

The BCC lattice	FCC sphere packing

As an example, here we have taken roughly the same number of samples from a CT (Computerized Tomography) data set of a Carp fish, left on the commonly used Cartesian lattice and right on the optimal BCC lattice. Not only the BCC lattice provides a more accurate and superior representation of the ribs and tail regions, it is computationally twice more efficient than the Cartesian lattice.

2,744K Cartesian data points, 658 seconds	2,735K BCC data points 335 seconds

Similarly, this CT dataset of a porcelain teapot shows the attractive properties of BCC optimal sampling pattern. The surface reconstructed from the Cartesian data shows an artifact (hole) which is absent in the optimal sampling case:

Cartesian Data	BCC Data
763K Cartesian data points,326 seconds	741K BCC data points, 167 seconds

For a more detailed overview of my work, please see this presentation.

Research Question

Given the data properly sampled at BCC lattice points, how can one interpolate or approximate (reconstruct) a continuous-domain function from the given data points?

I learnt about box splines only when I realized that Rhombic Dodecahedron is a projection of a tesseract (4D hypercube) along its antipodal axis. This incident is not hard to observe in the lower dimensional cases.

• This box spline is represented by

  $$\boldsymbol\Xi$$ = $$\left[\vphantom{\begin{array}{cccc} \boldsymbol{\xi}_1 & \boldsymbol{\xi}_2 & \boldsymbol{\xi}_3 & \boldsymbol{\xi}_4 \end{array}}\right.$$$$\begin{array}{cccc} \boldsymbol{\xi}_1 & \boldsymbol{\xi}_2 & \boldsymbol{\xi}_3 & \boldsymbol{\xi}_4 \end{array}$$$$\left.\vphantom{\begin{array}{cccc} \boldsymbol{\xi}_1 & \boldsymbol{\xi}_2 & \boldsymbol{\xi}_3 & \boldsymbol{\xi}_4 \end{array}}\right]$$ = $$\left[\vphantom{\begin{array}{rrrr} 1 & -1 & -1 & 1 -1 & 1 & -1 & 1 -1 & -1 & 1 & 1 \end{array} }\right.$$$$\begin{array}{rrrr} 1 & -1 & -1 & 1 -1 & 1 & -1 & 1 -1 & -1 & 1 & 1 \end{array}$$$$\left.\vphantom{\begin{array}{rrrr} 1 & -1 & -1 & 1 -1 & 1 & -1 & 1 -1 & -1 & 1 & 1 \end{array} }\right]$$ Figure: The Support of the 4-directional box spline: Rhombic Dodecahedron

  
  
  This box spline and its self convolution helped us achieve really good reconstructions on the BCC lattice. The shape of the ``first ring of neighbours'' on the BCC lattice is a Rhombic Dodecahedron . See our BCC reconstruction paper that was published in IEEE Visualization 2004. In this paper, through some geometric arguments, we showed that the linear box spline can be computed using the remarkably simple explicit formula:

  $$\boldsymbol\Xi \lvert \rvert \lvert \rvert \lvert \rvert \lvert \rvert \lvert \rvert \lvert \rvert$$

  
  

• However computation of the C^2 box spline remained really costly at that time. Recently we managed to flesh out the polynomial pieces constituting this fourth order box spline. Through this explicit piecewise-polynomial representation, we achieved an extremely fast reconstruction using this box spline.

  It turns out that for a C^2 reconstruction using this box spline with a fourth order approximation power we only need a neighborhood of 32 points. Similar smoothness and approximation order is achieved by the tensor product tri-cubic B-spline on the Cartesian lattice by a neighborhood of 4×4×4=64 points. Therefore, reconstruction on the BCC lattice is twice faster than a similar reconstruction on the Cartesian lattice.

• We demonstrated that not only the BCC lattice offers a more accurate 'discrete' representation of many continuous-domain functions, it also has attractive computational efficiency properties, when compared to the usual Cartesian sampling lattice. This paper is going to appear in IEEE TVCG. If you need to look at this work or need the code for such reconstruction, feel free to email me.

• The Face Centered Cubic lattice is the ``dual'' of the BCC lattice. The sincfunction on the BCC lattice is a function whose Fourier domain representation is the indicator function of the Voronoi cell of the dual lattice (i.e. the FCC lattice). Incidentally Rhombic Dodecahedron is the Voronoi cell of the FCC lattice. Rhombic Dodecahedron can be decomposed into four parallelepipeds. This decomposition helped us derive the sincBCCfunction for the ideal interpolation kernel on the BCC for the space of ``bandlimited'' functions. This is explained in Section 5.1 in this PIMS/BIRS publication.

• Also we have used the FCC and BCC lattices to find a 3D multiresolution transform that downsamples by a factor of exactly two in each step. The tensor product way of downsampling can only downsample by eight. I am looking in box splines to find more suitable filters for this downsampling.

• I have also explored using a set of seven directional tri-variate box splines for reconstruction of data sampled on the regular Cartesian lattice. This work shows how a non-separable reconstruction kernel achieves reconstructions that eliminates artifacts amplified by tensor product kernels. The support of this kernel includes a total of 53 points which is 20% less than the 64 points tri-cubic B-spline reconstruction uses. Therefore, while the 7-directional box spline has the same smoothness and approximation power of that of the tri-cubic B-spline, it is 20% more efficient than tri-cubic B-spline. These tri-variate box spline kernels are reminiscent of the well known Zwart-Powell element in 2D. Jörg Peters, has already explored one of these box splines for constructing curvature-continuous surfaces. You can take a look at my VIS2006 slides.

  Figure: The Support of the 7-direction box spline: Truncated Rhombic Dodecahedron

  
• The theoretical expectations is that the BCC sampling captures more information from a given function with the same number of samples as a Cartesian lattice. We have examined this theoretical expectation and found an empirical evidence that a BCC sampled volume with roughly about 70% number of samples of a Cartesian volume produces equivalent visual quality.
•  This paper surveys the appearnce of hexagonal sampling and BCC/FCC lattices in nature and in the computing domain.