“Fast volume rendering using a shear-warp factorization of the viewing transformation” by Lacroute and Levoy

Several existing volume rendering algorithms operate by factoring the viewing transformation into a 3D shear parallel to the data slices, a projection to form an intermediate but distorted image, and a 2D warp to form an undistorted final image. We extend this class of algorithms in three ways. First, we describe a new object-order rendering algorithm based on the factorization that is significantly faster than published algorithms with minimal loss of image quality. Shear-warp factorizations have the property that rows of voxels in the volume are aligned with rows of pixels in the intermediate image. We use this fact to construct a scanline-based algorithm that traverses the volume and the intermediate image in synchrony, taking advantage of the spatial coherence present in both. We use spatial data structures based on run-length encoding for both the volume and the intermediate image. Our implementation running on an SGI Indigo workstation renders a 2563 voxel medical data set in one second. Our second extension is a shear-warp factorization for perspective viewing transformations, and we show how our rendering algorithm can support this extension. Third, we introduce a data structure for encoding spatial coherence in unclassified volumes (i.e. scalar fields with no precomputed opacity). When combined with our shear-warp rendering algorithm this data structure allows us to classify and render a 2563 voxel volume in three seconds. The method extends to support mixed volumes and geometry and is parallelizable.

1. Cameron, G. G. and P. E. Undrill. Rendering volumetric medical image data on a SIMD-architecture computer. In Proceedings of the Third Eurographics Workshop on Ren-dering, 135-145, Bristol, UK, May 1992.
2. Crow, Franklin C. Summed-area tables for texture map-ping. Proceedings of SIGGRAPH ’84. Computer Graphics, 18(3):207-212, July 1984.
3. Danskin, John and Pat Hanrahan. Fast algorithms for volume ray tracing. In 1992 Workshop on Volume Visualization,91- 98, Boston, MA, October 1992.
4. Drebin, Robert A., Loren Carpenter and Pat Hanrahan. Vol-ume rendering. Proceedings of SIGGRAPH ’88. Computer Graphics, 22(4):65-74, August 1988.
5. Glassner, Andrew S. Multidimensional sum tables. In Graphics Gems, 376-381. Academic Press, New York, 1990.
6. Glassner, Andrew S. Normal coding. In Graphics Gems, 257-264. Academic Press, New York, 1990.
7. Hanrahan, Pat. Three-pass affine transforms for volume ren-dering. Computer Graphics, 24(5):71-77, November 1990.
8. Laur, David and Pat Hanrahan. Hierarchical splatting: A progressive refinement algorithm for volume render-ing. Proceedings of SIGGRAPH ’91. Computer Graphics, 25(4):285-288, July 1991.
9. Levoy, Marc. Display of surfaces from volume data. IEEE Computer Graphics & Applications, 8(3):29-37, May 1988.
10. Levoy, Marc. Volume rendering by adaptive refinement. The Visual Computer, 6(1):2-7, February 1990.
11. Levoy, Marc and Ross Whitaker. Gaze-directed volume ren-dering. Computer Graphics, 24(2):217-223, March 1990.
12. Levoy, Marc. Efficient ray tracing of volume data. ACM Transactions on Graphics, 9(3):245-261, July 1990.
13. Meagher, Donald J. Efficient synthetic image generation of arbitrary 3-D objects. In Proceeding of the IEEE Confer-ence on Pattern Recognition and Image Processing, 473- 478, 1982.
14. Novins, Kevin L., Fran~ cois X. Sillion, and Donald P. Green-berg. An efficient method for volume rendering using perspective projection. Computer Graphics, 24(5):95-102, November 1990.
15. Porter, Thomas and Tom Duff. Compositing digital im-ages. Proceedings of SIGGRAPH ’84. Computer Graphics, 18(3):253-259, July 1984.
16. Sakas, Georgios and Matthias Gerth. Sampling and anti-aliasing of discrete 3-D volume density textures. In Proceed-ings of Eurographics ‘91,87-102, Vienna, Austria, Septem-ber 1991.
17. Schr~ oder, Peter and Gordon Stoll. Data parallel volume ren-dering as line drawing. In Proceedings of the 1992 Workshop on Volume Visualization,25-32, Boston, October 1992.
18. Subramanian, K. R. and Donald S. Fussell. Applying space subdivision techniques to volume rendering. In Proceedings of Visualization ’90, 150-159, San Francisco, California, Oc-tober 1990.
19. V~ ezina, Guy, Peter A. Fletcher, and Philip K. Robertson. Volume rendering on the MasPar MP-1. In 1992 Workshop on Volume Visualization,3-8, Boston, October 1992.
20. Westover, Lee. Footprint evaluation for volume render-ing. Proceedings of SIGGRAPH ’90. Computer Graphics, 24(4):367-376, August 1990.
21. Wilhelms, Jane and Allen Van Gelder. Octrees for faster isosurface generation. Computer Graphics, 24(5):57-62, November 1990.
22. Yagel, Roni and Arie Kaufman. Template-based volume viewing. In Eurographics 92, C-153-167, Cambridge, UK, September 1992.
23. Zuiderveld, Karel J., Anton H.J. Koning, and Max A. Viergever. Acceleration of ray-casting using 3D distance transforms. In Proceedings of Visualization in Biomedical Computing 1992, 324-335, Chapel Hill, North Carolina, Oc-tober 1992.