TIME AND SPACE OPTIMAL DATA-PARALLEL VOLUME RENDERING USING PERMUTATION WARPING

In this paper we present a data parallel volume rendering algorithm th at possesses numerous advantages over prior published solutions, Volum e rendering is a three-dimensional graphics rendering algorithm that c omputes views of sampled medical and simulation data, but has beers mu ch slower than other graphics algorithms because of the data sat sizes and the computational complexity. Our algorithm uses permutation warp ing to achieve linear speedup (run time is O(S/P) for P processors whe n P = O(S/log S) for S = n(3) samples), linear storage (O(S) for large data sets, arbitrary view directions, and high-quality filters. We de rived a new processor permutation assignment of five passes tour prior known solution was eight passes), and a new parallel compositing tech nique that is essential for scaling linearly on machines that have mor e processors than view rays to process (P > n(2)). We show a speedup o f 15.7 for a 16k processor over a 1k processor MasPar MP-1 (16 is line ar) and two frames/second with a 128(3) volume and trilinear view reco nstruction. In addition, we demonstrate volume sizes of 256(3) constan t run time over angles 5 to 75 degrees, filter quality comparisons, an d communication congestion of just 19 to 29%. (C) 1997 Academic Press.