Efficient ray tracing of volume data

ABSTRACT

Volume rendering is a technique for visualizing sampled scalar or vector fields of three spatial dimensions without fitting geometric primitives to the data. A subset of these techniques generates images by computing 2-D projections of a colored semitransparent volume, where the color and opacity at each point are derived from the data using local operators. Since all voxels participate in the generation of each image, rendering time grows linearly with the size of the dataset. This paper presents a front-to-back image-order volume-rendering algorithm and discusses two techniques for improving its performance. The first technique employs a pyramid of binary volumes to encode spatial coherence present in the data, and the second technique uses an opacity threshold to adaptively terminate ray tracing. Although the actual time saved depends on the data, speedups of an order of magnitude have been observed for datasets of useful size and complexity. Examples from two applications are given: medical imaging and molecular graphics.

REFERENCES

• 1: John Amanatides, Ray tracing with cones, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.129-135, July 1984
• 2: AMANTIDES, J., AND Woo, A. A fast voxel traversal algorithm for ray tracing. In Proceedings of Eurographics '87, G. Marechal, Ed. Elsevier North-Holland, New York, 1987, 3-10.
• 3: James Arvo , David Kirk, Fast ray tracing by ray classification, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.55-64, July 1987
• 4: ARVO, J., AND KIRK, D. A survey of ray tracing acceleration techniques. In SIGGRAPH 88 Course Notes, vol. 7 (Atlanta, Ga., Aug.). ACM, New York, 1988.
• 5: BADT, S., JR. Two algorithms for taking advantage of temporal coherence in ray tracing. Visual Comput. 4 (1988), 123-132.
• 6: CLEARY, J. G., AND WYVILL, G. Analysis of an algorithm for fast ray tracing using uniform space subdivision. Visual Comput. 4 (1988), 65-83.
• 7: Robert L. Cook, Stochastic sampling in computer graphics, ACM Transactions on Graphics (TOG), v.5 n.1, p.51-72, Jan. 1986 [doi>10.1145/7529.8927]
• 8: Mark Dippé , John Swensen, An adaptive subdivision algorithm and parallel architecture for realistic image synthesis, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.149-158, July 1984
• 9: Robert A. Drebin , Loren Carpenter , Pat Hanrahan, Volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.65-74, Aug. 1988
• 10: H. Fuchs , Z. M. Kedem , S. P. Uselton, Optimal surface reconstruction from planar contours, Communications of the ACM, v.20 n.10, p.693-702, Oct. 1977 [doi>10.1145/359842.359846]
• 11: Akira Fujimoto , Takayuki Tanaka , Kansei Iwata, ARTSccelerated ray-tracing system, IEEE Computer Graphics and Applications, v.6 n.4, p.16-26, April 1986 [doi>10.1109/MCG.1986.276715]
• 12: GAROANTINI, I. Linear octtrees for fast processing of three-dimensional objects. Comput. Graph. Image Process. 20 (1982), 365-374.
• 13: GARGANT!N!, !~, WAT.,~w4, To R. S~, AND WU, O~ L, r)i~p!aying a voxe!-based object via linear octtrees. Proc. SPIE 626 (1986), 460-466.
• 14: GLASSNER, A.S. Space subdivision for fast ray tracing. IEEE Comput. Graph. Appl. 4, 10 (Oct. 1984), 15-22.
• 15: GOLDWASSER, S. Rapid techniques for the display and manipulation of 3-D biomedical data. In NCGA "86 Tutorial (Anaheim, Calif., May 1986).
• 16: HAINES, E. A., AND GREENBERG, D.P. The light buffer: A shadow-testing accelerator. IEEE Comput. Graph. Appl. 6, 9 (Sept. 1986), 6-16.
• 17: Paul S. Heckbert , Pat Hanrahan, Beam tracing polygonal objects, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.119-127, July 1984
• 18: HERMAN, G. T., AND LIU, H.K. Three-dimensional display of human organs from computer tomograms. Comput. Graph. Image Process. 9 (1979), 1-21.
• 19: James T. Kajiya, New techniques for ray tracing procedurally defined objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.91-102, July 1983
• 20: Timothy L. Kay , James T. Kajiya, Ray tracing complex scenes, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.269-278, Aug. 1986
• 21: 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]
• 22: M. S. Levoy, Display of surfaces from volume data, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1990
• 23: 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]
• 24: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 25: MEAGHER, D. Geometric modeling using octree encoding. Comput. Graph. Image Process. 19 (1982), 129-147.
• 26: M. Ohta , M. Maekawa, Ray coherence theorem and constant time ray tracing algorithm, CG International '87 on Computer graphics 1987, p.303-314, June 1987, Karuizawa, Japan
• 27: Thomas Porter , Tom Duff, Compositing digital images, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.253-259, July 1984
• 28: Steven M. Rubin , Turner Whitted, A 3-dimensional representation for fast rendering of complex scenes, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.110-116, July 1980
• 29: Paolo Sabella, A rendering algorithm for visualizing 3D scalar fields, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.51-58, Aug. 1988
• 30: SCHLUSSELBERG, D. S., AND SMITH, W. K. Three-dimensional display of medical image volumes. In Proceedings of NCGA '86, vol. III (Anaheim, Calif., May). 1986, 114-123.
• 31: Mikio Shinya , T. Takahashi , Seiichiro Naito, Principles and applications of pencil tracing, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.45-54, July 1987
• 32: TROUSSET, Y., AND SCHMITT, F. Active-ray tracing for 3D medical imaging. In Proceedings of Eurographics '87, G. Marechal, Ed. Elsevier North-Holland, New York, 1987, 139-149.
• 33: Craig Upson , Michael Keeler, V-buffer: visible volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.59-64, Aug. 1988
• 34: Turner Whitted, An improved illumination model for shaded display, Communications of the ACM, v.23 n.6, p.343-349, June 1980 [doi>10.1145/358876.358882]
• 35: Mann-May Yau , Sargur N. Srihari, A hierarchical data structure for multidimensional digital images, Communications of the ACM, v.26 n.7, p.504-515, July 1983 [doi>10.1145/358150.358158]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

General Terms:
Algorithms, Design, Performance