Progressive Data Access for Regular Grids 165
is called coefficient prioritization. With either method, a number of practical
implementation issues arise.
8.4.7.1 Blocking
The multidimensional DWT, discussed in 8.4.6, can be applied directly to
a d-dimensional grid. However, for high-resolution grids, there are a number of
reasons for considering decomposing the grid into a collection of smaller blocks
and applying the DWT to each individual block. Computational efficiency is
one consideration. Significantly improved performance may be achieved on
cache-based microprocessors by operating on a collection of smaller blocks
that better accommodate the memory hierarchy rather than one large, single
volume. The second reason, and perhaps the more compelling one, is efficient
region extraction. For many visualization workflows—such as drawing a cut-
ting plane through a 3D volume or zooming in and volume rendering a small
subregion of a larger volume—only a subset of the data is required. By de-
composing the volume into blocks, it is possible to access (from storage) only
those blocks that intersect the region of interest. The merits of data blocking
with regard to I/O are discussed in Hierarchical and Geometrical Methods in
Scientific Visualization [9].
The best choice of block size is somewhat application dependent. Given
the dyadic nature of the wavelet, and the complexities of boundary handling
discussed in 8.4.5, power-of-two dimensions are sensible. As each pass of the
DWT reduces the number of approximation coefficients by half along each
dimension, larger block sizes permit more passes of the DWT resulting in a
deeper multiresolution hierarchy. A deeper hierarchy offers more refinement
levels for a progressive access scheme based on frequency truncation. Simi-
larly, if coefficient prioritization is employed, more coefficients present greater
degrees of freedom for compression. However, if the block size is too large, the
goal of performing efficient region extraction and computational performance
may be defeated. As a reasonable compromise for 3D grids, the suggested
block sizes are 64
3
or 128
3
.
For data that is not block-aligned, padding of the boundary blocks is re-
quired. Care should be taken to use an extension strategy that does not in-
troduce sharp discontinuities. Constant, linear extrapolation, or symmetric
extension, generally produces reasonable results.
8.4.7.2 Wavelet Choice
The advantages of symmetric, biorthogonal wavelets have been discussed;
and filter coefficients for two wavelets commonly used have been provided in
image compression applications in 8.4.5. Other biorthogonal wavelets possess-
ing more vanishing moments and, therefore, greater information compaction
capability also exist at the cost of additional filter taps. It is worth noting that
while filters with better energy compaction capabilities may yield sparser rep-
resentations, the additional filter coefficients incur additional computational
166 High Performance Visualization
cost. Also, the wider the filter the greater the number of input coefficients
required, which may limit the possible number of cascades of the DWT. For
example, with a block of dimension 64
3
after three stages of the DWT, there
are 8
3
approximation coefficients—too few for another pass with the nine-
tap CDF9/7 filter, but sufficient for one more stage of the narrower, five-tap
CDF5/3 filter.
8.4.7.3 Coefficient Addressing
An important attribute of regular grids is the implicit addressing of grid
vertices. For example, each vertex in the grid can be addressed by an integer
index, (i, j, k) in 3D, whose offsets can be implicitly determined by the serial-
ized storage order. Therefore, only the sampled field value for each grid point
needs to actually be stored. The implicit addressing of expansion coefficients is
easily preserved during storage with frequency truncation. The coefficients are
simply written in the order that they are output from each stage of the filter
bank. With coefficient prioritization, however, the coefficients must be ordered
by their information content. Their addresses are no longer implicit by their
position in the output stream, and must be explicitly preserved. The number
of bits required to uniquely address each of the N expansion coefficients is
log
2
(N), which introduces a sizeable storage overhead.
Consider, however, binning the N expansion coefficients output by the
DWT (which will generically refer to as c[k]) into a collection of P sets,
S
p
= {c
π(i)
|C(p −1) ≤ i<C(p), 0 ≤ i<N− 1}, (8.27)
where C(0) = 0, C(p ≥ 1) =
p
1
|S
p
|, and, as before, π(i) is a permutation
of 0 ...N − 1 such that |c
π(0)
|≥... ≥|c
π(N−1)
|. Then, if within each set
S
p
, the expansion coefficients are stored in their relative order of output from
the filter bank, the addresses of the coefficients need only be stored for sets
S
1
...S
P −1
. The addresses of the elements of S
P
can be inferred from the
addresses of S
1
...S
P −1
. By keeping track of the ordered set of addresses not
found in S
1
...S
P −1
, the lowest address not found in S
1
...S
P −1
is the address
of the first coefficient found in S
P
and so on. If |S
P
| is sufficiently large, the
storage savings can be considerable.
8.4.8 A Hybrid Approach
Frequency truncation and coefficient prioritization each have their
strengths and weaknesses. Frequency truncation preserves the implicit order-
ing of grid vertices, thereby imposing minimum storage overhead, but it offers
only a very coarse grain control over the the level of detail available; incre-
menting or decrementing the j scaling parameter by one changes the number
of grid points by a factor 2
d
. Furthermore, unlike coefficient prioritization,
all coefficients are treated equally regardless of their contribution to the sig-
nal. On the other hand, though, coefficient prioritization allows for arbitrary
Progressive Data Access for Regular Grids 167
control over level of detail, and generally offers better approximations for a
given bit budget, but prioritization requires additional storage to keep track
of coefficient addresses. Perhaps, a less obvious difference between the two
schemes is that, by virtue of possessing fewer grid points, multiresolution ap-
proximations (frequency truncation) benefit all the resources of the visualiza-
tion pipeline including: physical memory, floating point calculations, and I/O.
Frequency truncation, on the other hand, only benefits the transmission of
the data (e.g., access to secondary storage). Once a signal is reconstructed—
albeit even if from fewer expansion coefficients than samples in the original
signal—the number of samples in the reconstructed signal is the same as for
the original signal. After the reconstruction is finished, there is no further
realized benefit of the wavelet expansion.
The merits of both methods may readily be combined with little or no
additional effort. By allowing control over both the j parameter in Equa-
tion 8.26, which controls the resolution, and (if the coefficients are binned by
their information content) the p parameter, then, Equation 8.27 controls the
expansion coefficients used in reconstruction.
8.4.9 Volume Rendering Example
Figure 8.7 shows at varying approximations a direct volume rendering
of an enstrophy field derived from a subregion of a 1024
3
isotropic and ho-
mogeneous Taylor–Green (TG) incompressible turbulence simulation [7]. The
original data is shown in Figure 8.7a. Approximations based on coefficient
prioritization, using reduction factors of
1
500
,
1
100
,and
1
10
, are shown in Fig-
ures 8.7b–d, respectively. The data was decomposed into 128
3
blocks, and
transformed with the CDF9/7 wavelet.
8.5 Further Reading
The presentation on Z-order curves and their application in progressive
data access is based almost entirely on the work of Pascucci and Frank. We
refer the reader to their papers for further details on the method, suggested
implementation strategies, and a discussion of their results with real data sets
and applications [10, 9].
Wavelets are a relatively new field in mathematics with a wealth of applica-
tions related to data analysis that go far beyond progressive data access. Here
we have only scratched the surface on their theory and their capabilities. For
the interested reader, an excellent introduction on wavelets and wavelet trans-
forms may be found in the books by Burrus et al. [2] and Stollnitz et al. [11].
For a deeper understanding we recommend the authoritative books by Mal-
lat [6], and Strang and Nguyen [12], and the seminal work by Daubechies [4].
168 High Performance Visualization
(a) (b)
(c) (d)
FIGURE 8.7: Direct volume rendering of an enstrophy field: original data (a),
and shown in (b)–(d), respectively, are results after reduction of the number
of expansion coefficients used in reconstruction by factors of
1
500
,
1
100
,and
1
10
.
Progressive Data Access for Regular Grids 169
References
[1] Christopher M. Brislawn. Classification of Nonexpansive Symmetric Ex-
tension Transforms for Multirate Filter Banks. Applied and Computa-
tional Harmonic Analysis, 3(4):337 – 357, 1996.
[2] Sidney C. Burrus, Ramesh A. Gopinath, and Haitao Guo. Introduction
to Wavelets and Wavelet Transforms: A Primer. Prentice Hall, August
1997.
[3] A. R. Calderbank, Ingrid Daubechies, Wim Sweldens, and Boon-Lock
Yeo. Wavelet Transforms that Map Integers to Integers. Applied and
Computational Harmonic Analysis, 5(3):332–369, 1998.
[4] Ingrid Daubechies. Ten Lectures on Wavelets. Society for Industrial and
Applied Mathematics, June 1992.
[5] D. L. Donoho. Unconditional Bases are Optimal Bases for Data Compres-
sion and for Statistical Estimation. Applied and Computational Harmonic
Analysis, 1(1):100–115, 1993.
[6] Stephane Mallat. A Wavelet Tour of Signal Processing, Third Edition:
The Sparse Way. Academic Press, December 2008.
[7] P. D. Mininni, A. Alexakis, and A. Pouquet. Large-Scale Flow Effects,
Energy Transfer, and Self-Similarity on Turbulence. Physical Review E,
74:016303, Jul 2006.
[8] G. M. Morton. A Computer Oriented Geodetic Data Base and a New
Technique in File Sequencing. Technical report, IBM Ltd., Ottawa, On-
tario, Canada, 1966.
[9] V. Pascucci and R. J. Frank. Hierarchical Indexing for Out-of-Core Access
to Multi-Resolution Data. In G.Farin, B. Hamann, and H. Hagen, editors,
Hierarchial and Geometrical Methods in Scentific Visualization, pages
225–241. Springer-Verlag, Berlin, 2002. UCRL-JC-140581.
[10] Valerio Pascucci. Global Static Indexing for Real-time Exploration of
Very Large Regular Grids. In Proceedings of Supercomputing (SC01),
2001.
[11] Eric J. Stollnitz, Anthony D. Derose, and David H. Salesin. Wavelets for
Computer Graphics (The Morgan Kaufmann Series in Computer Graph-
ics). Morgan Kaufmann, January 1996.
[12] Gilbert Strang and T. Nguyen. Wavelets and Filter Banks. Wellesley-
Cambridge Press, 1997.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.