Fast volume rendering using a shear-warp factorization of the viewing transformation

ABSTRACT

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.

REFERENCES

• 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: Franklin C. Crow, Summed-area tables for texture mapping, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.207-212, January 1984
• 3: John Danskin , Pat Hanrahan, Fast algorithms for volume ray tracing, Proceedings of the 1992 workshop on Volume visualization, p.91-98, October 19-20, 1992, Boston, Massachusetts, United States [doi>10.1145/147130.147155]
• 4: Robert A. Drebin , Loren Carpenter , Pat Hanrahan, Volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.65-74, Aug. 1988
• 5: Andrew S. Glassner, Multidimensional sum tables, Graphics gems, Academic Press Professional, Inc., San Diego, CA, 1990
• 6: Andrew S. Glassner, Normal coding, Graphics gems, Academic Press Professional, Inc., San Diego, CA, 1990
• 7: Pat Hanrahan, Three-pass affine transforms for volume rendering, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.71-78, Nov. 1990
• 8: David Laur , Pat Hanrahan, Hierarchical splatting: a progressive refinement algorithm for volume rendering, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.285-288, July 1991
• 9: Marc Levoy, Display of Surfaces from Volume Data, IEEE Computer Graphics and Applications, v.8 n.3, p.29-37, May 1988 [doi>10.1109/38.511]
• 10: Marc Levoy, Volume rendering by adaptive refinement, The Visual Computer: International Journal of Computer Graphics, v.6 n.1, p.2-7, 1990 [doi>10.1007/BF01902624]
• 11: Marc Levoy , Ross Whitaker, Gaze-directed volume rendering, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.217-223, Mar. 1990
• 12: Marc Levoy, Efficient ray tracing of volume data, ACM Transactions on Graphics (TOG), v.9 n.3, p.245-261, July 1990 [doi>10.1145/78964.78965]
• 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: Kevin L. Novins , Francois X. Sillion , Donald P. Greenberg, An efficient method for volume rendering using perspective projection, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.95-102, Nov. 1990
• 15: Thomas Porter , Tom Duff, Compositing digital images, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.253-259, January 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: Peter Schröder , Gordon Stoll, Data parallel volume rendering as line drawing, Proceedings of the 1992 workshop on Volume visualization, p.25-32, October 19-20, 1992, Boston, Massachusetts, United States [doi>10.1145/147130.147142]
• 18: K. R. Subramanian , Donald S. Fussell, Applying space subdivision techniques to volume rendering, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
• 19: Guy Vézina , Peter A. Fletcher , Philip K. Robertson, Volume rendering on the MasPar MP-1, Proceedings of the 1992 workshop on Volume visualization, p.3-8, October 19-20, 1992, Boston, Massachusetts, United States [doi>10.1145/147130.147138]
• 20: Lee Westover, Footprint evaluation for volume rendering, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.367-376, Aug. 1990
• 21: Jane Wilhelms , Allen Van Gelder, Octrees for faster isosurface generation, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.57-62, Nov. 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
coherence, medical imaging, scientific visualization, volume rendering