Introduction

Different grid structures have been studied extensively in various fields like chemistry [18], solid state physics [1], condensed matter physics [10], or crystallography [7]. Researchers in these fields have studied the structure of atoms and molecules, which are often placed in a regular grid structure. This structure is optimized for energy states ³ and results in covering space as closely as possible.

Results in multi-dimensional signal processing show that a Cartesian sampling structure is not the most efficient one [16]. Efficiency here is measured in terms of sampling points per unit hyper-volume. Under the assumption that the sampled function is isotropic and band-limited the resulting frequency support would be a hyper-sphere. Hence the most efficient sampling scheme would arrange the replicated (hyper-spherical) frequency response as densely as possible in frequency domain.

The problem of how to place as many (hyper-)spheres as possible in a fixed (hyper-)volume is known as the sphere packing problem [14]. This has been studied by many mathematicians in up to quite staggering dimensions (Conway and Sloane [3] give examples of dimensions up to 1048584). The problem of packing spheres optimally was stated in 1900 by Hilbert as his now famous Problem 18 [6]. It is still not solved completely. However, several regular grid structures are known which are optimal. Among these is the body-centered cubic (bcc) grid, which turns out to be particularly easy to use.

In the image processing community it is well known that sampling an image on a Cartesian grid is not optimal. By using a hexagonal sampling scheme one can save 13.4% of the samples [12]. Research has been directed to adapt algorithms like straight line generation [9], distance transformations [2], or oversampling [8] to hexagonal grids. However, the Cartesian structure of display devices limits the use of hexagonal grids for image processing so that 2D hexagonal grids are rarely used.

In volume visualization, or generally when dealing with 3D functions we are not bound to Cartesian grids. The representation of the function we want to visualize can be chosen arbitrarily since typically only two-dimensional projections of the data set are examined. Since a bcc grid can represent isotropic, band-limited data as accurately as Cartesian grids using 29.3% fewer samples [4]⁴, the advantages of using a bcc grid are significant.

In this paper we show how to take advantage of hexagonal sampling in volume rendering. We outline and propose solutions for the inherent issues of re-sampling of rectangular grids as well as interpolation and gradient estimation.

The remainder of this paper is organized as follows. We summarize the results of hexagonal sampling in 2D and derive an optimal sampling scheme in 3D in Section 2. In Section 3 we show how the splatting algorithm can be adopted for bcc grids, including storing of the data and gradient estimation. In Section 4 we examine acquisition techniques for data sampled on bcc grids. In Section 5 we present the results of our experiments. Some ideas for future work are presented in Section 6, and we derive conclusions of our studies in Section 7.

Footnotes

3
This is, of course, a serious oversimplification. However, for almost all the elements the lowest energy state is crystalline [10].
4	In Table 1.1 on page 47 Dudgeon and Mersereau give a sampling density ratio of 0.705, i.e., 29.5% fewer samples. This is simply due to a rounding error, compare the results of Petersen and Middleton [16].