The HAVS algorithm

Harvesting the power of modern graphics hardware to solve the complex problem of real-time rendering of large unstructured meshes is a major research goal in the volume visualization community. While for regular grids, texture-based techniques are well suited for current GPUs, the steps necessary for rendering unstructured meshes are not so easily mapped to current hardware.

The HAVS algorithm is a novel volume rendering technique that simplifies the CPU-based processing and shifts much of the sorting burden to the GPU, where it can be performed more efficiently. Our visibility sorting algorithm is a hybrid technique that operates in both object-space and image-space. In object-space, the algorithm performs a partial sort of the 3D primitives in preparation for rasterization. The goal of the partial sort is to create a list of primitives that generate fragments in nearly sorted order. In image-space, the fragment stream is incrementally sorted using a fixed-depth sorting network. In our algorithm, the object-space work is performed by the CPU and the fragment-level sorting is done completely on the GPU. Our implementation of the algorithm achieves rendering rates of about three million tetrahedral cells per second on a commodity PC with an NVidia 7800 GTX.

Because the HAVS algorithm requires no neighbor information in the mesh, it naturally handles dynamic data. We exploit this property by using a sample-based simplification of the mesh for dynamic level-of-detail (LOD) rendering. Our LOD approach is simple and efficient because instead of keeping a hierarchy of simplified meshes, we sample the existing geometry on each frame to keep the rendering interactive. By ordering the triangles by importance in a preprocess, our dynamic LOD algorithm can decide the number of triangles to render per frame based on the rendering time of the previous frame. An important benefit of this algorithm is that it allows interactive rendering during user interaction and a return to full quality rendering when the user stops interaction. Our dyanamic LOD allows datasets with millions of tetrahedra to be rendered at interactive rates while still maintaining high quality visualizations.

The HAVS code has also been integrated into VTK and ParaView. See vtkHAVSVolumeMapper and vtkOpenGLHAVSVolumeMapper.

Publications and Presentations

Please cite the relevant papers when using our system in your research. BibTeX

Hardware-Assisted Visibility Sorting for Unstructured Volume Rendering
S. P. Callahan, M. Ikits, J. L. D. Comba, C. T. Silva
IEEE Transactions on Visualization and Computer Graphics; May/Jun 2005

Interactive Rendering of Large Unstructured Grids Using Dynamic Level-of-Detail
S. P. Callahan, J. L. D. Comba, P. Shirley, C. T. Silva
Proceedings of IEEE Visualization '05; October 2005 (presentation)

Other Related Publications

The K-Buffer and Its Applications to Volume Rendering
S. P. Callahan
M. S. Thesis in Computational Engineering and Science from the University of Utah; May 2005 (presentation)

A Survey of GPU-Based Volume Rendering of Unstructured Grids
C. T. Silva, J. L. D. Comba, S. P. Callahan, F. F. Bernardon
Revista de Informatica Teorica e Aplicada (RITA); Vol 12, Num 2, October 2005
Supplement for tutorial at XVII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2005)

Hardware-Accelerated Simulated Radiography
D. Laney, S. P. Callahan, N. Max, C. T. Silva, S. Langer, R. Frank
Proceedings of IEEE Visualization '05; June 2005

Interactive Volume Rendering of Unstructured Grids with Time-Varying Scalar Fields
F. F. Bernardon, S. P. Callahan, J. L. D. Comba, C. T. Silva
Proceedings of Eurographics Symposium on Parallel Graphics and Visualization; May 2006

Progressive Volume Rendering of Large Unstructured Grids
S. P. Callahan, L. Bavoil, V. Pascucci, C. T. Silva
IEEE Transactions on Visualization and Computer Graphics (Proceedings of Visualization 2006), to appear.


This software was produced by members of the Visualization and Geometric Computing (VGC) group at the University of Utah. Main contributors to the algorithm include:

Other contributors:


This work was partially supported by the Department of Energy, the National Science Foundation, IBM, and a University of Utah Seed Grant.