VIS- und Uni-Logo
Blindenversion home uni uni suche suche sitemap sitemap kontakt kontakt
unilogo Universität Stuttgart
Institut für Visualisierung und Interaktive Systeme

Scientific Visualization on Sparse Grids

englische VersionDruckversionBlindenversion

Dieses Dokument ist leider nur in Englisch verfügbar.

Abstract   |   Pictures   |   MPeg movies   |   Sparse Grids   |   Visualization   |   Results   |   Papers

Scientific Visualization on Sparse Grids


Huge three-dimensional data sets have to be compressed for visualization if they do not fit into the main memory of todays work stations. A possible approach is to use sparse grids featuring very simple basis functions for interpolation. Sparse grids are also of increasing interest in numerical simulations.

The visualization algorithms that are available so far could not cope with sparse grids. Now we present some approaches that directly work on sparse grids. For getting interactive rates at visualizing sparse grid volumes, we introduce an interpolation algorithm that harnesses silicon graphics hardware for acceleration purposes.


stream balls in the blunt fin data set  stream tetrahedra in a vortex flow  IRIS Explorer map  modules for Explorer 
stream balls in an ananlytic flow  stream balls in an ananlytic flow  convergence comparison  convergence comparison 
different geometries  convergence comparison  analytic, level 1  analytic, level 3 
smoothness comparison  sgrid main window  cavity pressure, XRay, combi  cavity pressure, XRay, hardware
cavity temperature, MIP, combi  orbital, iso surface analytic, iso surface test, iso surface
Figure 1: Several examples

MPeg movies

Rotating view of the pressure of a simulated cavity flow, visualized with the combination technique.

Download size: 1.21 MB

The same view, this time visualized with the hardware accelerated combination technique.

Download size: 1.26 MB

Sparse Grids

For interpolation on sparse grids, a hierarchy of basis functions is used, where some functions are defined on the entire grid. For interpolation all basis functions that are accessed during the hierarchy traversal have to be evaluated. On the contrary, the tri-linear interpolation on full grids only needs 8 basis functions, independend from the grid size. Thus, interpolation is much more expensive on sparse grids than on full grids.

The actual sparse grid is created by removing the points that do not contribute to the the sparse grid interpolation functions from the associated full grid (Figure 2). By increasing the hierarchy depth by one the resolution of the associated full grid is doubled within each axis.

2D, Level 2 2D, Level 5 2D, Level 8
3D, Level 2 3D, Level 5 3D, Level 8
Figure 2: The structure of sparse grids

Faster than the standard sparse grid interpolation approach is the so-called combination technique. It uses tri-linear interpolation on several smaller full grids. This technique needs somewhat more memory than the standard method, but still much less than the associated full grid. Additionally, the graphics hardware of modern Silicon Graphics work stations can be used for acceleration purposes.

Visualization Techniques

We have created several visualization algorithms that work directly on sparse grids. For flow visualization particle tracing is a standard approach that is now available on sparse grids as well.

Another standard visualization technique is direct volume visualization using ray casting. This method needs a lot of values to be interpolated in the data volume. Therefore, to be able to use this visualization technique efficiently, a new interpolation method was introduced that harnesses graphics hardware in oder to accelerate the combination method.


Sparse grids need only a negligible amount of memory compared with their associated full grids as shown in Table 1.

Level 567 891011
Points of full grid 33³65³129³ 257³513³1025³2049³
Full grid 128 kB1 MB8 MB 64 MB 512 MB4 GB32 GB
Standard technique 6 kB15 kB35 kB 83 kB200 kB450 kB1 MB
Combination technique 22 kB59 kB152 kB 377 kB914 kB2.1 MB5 MB
Hardware acceleration 43 kB 124 kB 338 kB 884 kB2.2 MB 5.4 MB 13.1 MB
Table 1: Memory consumption of the different interpolation techniques

On the other hand, interpolation on sparse grids is much slower than on full grids and depends on the visualized level. In contrast, interpolation on full grids is almost level independent. Table 2 shows typical computation times for different volume sizes, using volume ray casting as visualization method.

Level 567 891011
Full grid 5.3 s5.3 s5.4 s5.7 s6.9 s --
Standard technique 755 s 1040 s 1380 s 1935 s 2750 s 3910 s 5400 s
Combination technique 83 s124 s173 s 233 s309 s454 s726 s
Hardware acceleration 3.6 s4.5 s5.5 s 6.8 s8.5 s10.3 s12.5 s
Table 2: Typical ray casting times of the different interpolation techniques

By using the hardware accelerated combination technique computation times can be reduced for huge grid sizes by a factor of about 430. However, due to the limited frame buffer depth some artifacts can occur in the computed images. Take a look at the movies or the cavity pictures for some examples about these artifacts and for comparing hardware acceleration with the software method.

In the next table the CPU-times of sparse and full grid particle tracing are listed. All tests were performed on a Silicon Graphics computer with a 250 MHz R10000 processor. For testing, at each time nine streak ribbons were computed consisting of about 500 particles (see pictures). The used integration method was an adaptive Runge-Kutta scheme RK3(2). See Efficient and Reliable Integration Methods for Particle Tracing in Unsteady Flows on Discrete Meshes for a discussion of different integration algorithms for particle tracing.

Level 345 678
Uniform full grid 0.67 s1.18 s1.89 s 2.28 s2.66 s-
Uniform sparse grid 0.24 s0.33 s0.68 s 0.93 s4.51 s5.91 s
Uniform combination technique 0.07 s0.12 s0.20 s 0.30 s1.15 s1.61 s
Curvilinear full grid 0.70 s1.30 s2.58 s 5.28 s10.6 s-
Curvilinear sparse grid 1.56 s3.28 s6.82 s 9.31 s22.7 s31.2 s
Curvilinear combination technique 0.64 s1.19 s2.02 s 3.02 s6.05 s8.49 s
Table 3: Typical times for particle tracing

The measured times show that interactive particle tracing is possible even on sparse grids of level 8 by using the combination technique.

Papers and Technical Reports

Matthias Hopf <>
Christian Teitzel <>