Scientific Visualization on Sparse Grids

Abstract

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.

Pictures

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.

Figure 2: The structure of sparse grids

2D, Level 2	2D, Level 5	2D, Level 8

3D, Level 2	3D, Level 5	3D, Level 8

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.

Results

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

Table 1: Memory consumption of the different interpolation techniques
Level	5	6	7	8	9	10	11
Points of full grid	33³	65³	129³	257³	513³	1025³	2049³
Full grid	128 kB	1 MB	8 MB	64 MB	512 MB	4 GB	32 GB
Standard technique	6 kB	15 kB	35 kB	83 kB	200 kB	450 kB	1 MB
Combination technique	22 kB	59 kB	152 kB	377 kB	914 kB	2.1 MB	5 MB
Hardware acceleration	43 kB	124 kB	338 kB	884 kB	2.2 MB	5.4 MB	13.1 MB

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.

Table 2: Typical ray casting times of the different interpolation techniques
Level	5	6	7	8	9	10	11
Full grid	5.3 s	5.3 s	5.4 s	5.7 s	6.9 s	-	-
Standard technique	755 s	1040 s	1380 s	1935 s	2750 s	3910 s	5400 s
Combination technique	83 s	124 s	173 s	233 s	309 s	454 s	726 s
Hardware acceleration	3.6 s	4.5 s	5.5 s	6.8 s	8.5 s	10.3 s	12.5 s

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.

Table 3: Typical times for particle tracing
Level	3	4	5	6	7	8
Uniform full grid	0.67 s	1.18 s	1.89 s	2.28 s	2.66 s	-
Uniform sparse grid	0.24 s	0.33 s	0.68 s	0.93 s	4.51 s	5.91 s
Uniform combination technique	0.07 s	0.12 s	0.20 s	0.30 s	1.15 s	1.61 s
Curvilinear full grid	0.70 s	1.30 s	2.58 s	5.28 s	10.6 s	-
Curvilinear sparse grid	1.56 s	3.28 s	6.82 s	9.31 s	22.7 s	31.2 s
Curvilinear combination technique	0.64 s	1.19 s	2.02 s	3.02 s	6.05 s	8.49 s

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

C. Teitzel, R. Grosso, T. Ertl, Particle Tracing on Sparse Grids,
in D. Bartz (ed.), Visualization in Scientific Computing '98, Springer-Verlag, 1998
Proceedings of the Eurographics Workshop in Blaubeuren, Germany
C. Teitzel, M. Hopf, R. Grosso, T. Ertl, Volume Ray Casting on Sparse Grids,
Technical Report 5/1998, University Erlangen-Nuernberg
C. Teitzel, M. Hopf, R. Grosso, T. Ertl, Volume Visualization on Sparse Grids,
Technical Report 8/1998, University Erlangen-Nuernberg
C. Teitzel, M. Hopf, T. Ertl, Scientific Visualization on Sparse Grids,
Technical Report 10/1998, University Erlangen-Nuernberg
C. Teitzel, T. Ertl, New Approaches for Particle Tracing on Sparse Grids,
Technical Report 12/1998, University Erlangen-Nuernberg

Matthias Hopf <hopf@immd9.informatik.uni-erlangen.de>
Christian Teitzel <teitzel@immd9.informatik.uni-erlangen.de>

back to VIS Homepage
Deutsch


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

	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