HP Labs Technical Reports

Fast Volume Rendering Using an Efficient, Scalable Parallel Formulation of the Shear-Warp Algorithm

Minesh B. Amin ; Ananth Grama ; Vineet Singh

HPL-95-132
November, 1995

Keyword(s): volume rendering, raytracing, algorithms, shear-warp algorithms, performance modeling and analysis, scalability, adaptive load-balancing

Abstract: This paper presents a fast and scalable parallel algorithm for volume rendering and its implementation on distributed-memory parallel computers. This parallel algorithm is based on the shear-warp algorithm of Lacroute and Levoy. Coupled with optimizations that exploit coherence in the volume and image space, the shear-warp algorithm is currently acknowledged to be the fastes sequential volume rendering algorithm. We have designed a memory efficient parallel formulation of this algotithm that (1) drastically reduces communincation by using a novel data partitioning scheme and, (2) improves multi-frame performance with an adaptive load-balancing technique. All the optimizations of the Lacroute-Levoy algorithm are preserved in the parallel formulation. The paper also provides an analytical model of performance for the parallel formulation that shows it is possible to sustain excellent performance across a wide range of practical problem sizes and number of processors. Our implementation, running on a 128 processor TMC CM-5 distributed-memory parallel computer, renders a 256 ³ voxel medical data set at 12 frames/sec.

Back to Index