

Dieses Dokument ist leider nur in Englisch verfügbar.
Abstract 
Pictures 
MPeg movies 
Sparse Grids 
Visualization 
Results 
Papers
Scientific Visualization on Sparse Grids
Abstract
Huge threedimensional 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 trilinear 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
socalled combination technique. It uses trilinear 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.
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 
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 
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 
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 CPUtimes 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 RungeKutta 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 
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 
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
 C. Teitzel, R. Grosso, T. Ertl,
Particle Tracing on Sparse Grids,
in D. Bartz (ed.), Visualization in Scientific Computing '98, SpringerVerlag, 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 ErlangenNuernberg
 C. Teitzel, M. Hopf, R. Grosso, T. Ertl,
Volume Visualization on Sparse Grids,
Technical Report 8/1998, University ErlangenNuernberg
 C. Teitzel, M. Hopf, T. Ertl,
Scientific Visualization on Sparse Grids,
Technical Report 10/1998, University ErlangenNuernberg
 C. Teitzel, T. Ertl,
New Approaches for Particle Tracing on Sparse Grids,
Technical Report 12/1998, University ErlangenNuernberg
Matthias Hopf
<hopf@immd9.informatik.unierlangen.de>
Christian Teitzel
<teitzel@immd9.informatik.unierlangen.de>

