Octrees for faster isosurface generation

ABSTRACT

The large size of many volume data sets often prevents visualization algorithms from providing interactive rendering. The use of hierarchical data structures can ameliorate this problem by storing summary information to prevent useless exploration of regions of little or no current interest within the volume. This paper discusses research into the use of the octree hierarchical data structure when the regions of current interest can vary during the application, and are not known a priori. Octrees are well suited to the six-sided cell structure of many volumes. A new space-efficient design is introduced for octree representations of volumes whose resolutions are not conveniently a power of two; octrees following this design are called branch-on-need octrees (BONOs). Also, a caching method is described that essentially passes information between octree neighbors whose visitation times may be quite different, then discards it when its useful life is over. Using the application of octrees to isosurface generation as a focus, space and time comparisons for octree-based versus more traditional “marching” methods are presented.

REFERENCES

• 1: ARTZY, E., FRIEDER, G., AND HERMAN, G. The theory, design, implementation, and evaluation of a three-dimensional surface detection algorithm. Comput. Graph. Image Process. 15, 1 (Jan. 1981), 1-24.
• 2: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 3: J. Bloomenthal, Polygonization of implicit surfaces, Computer Aided Geometric Design, v.5 n.4, p.341-355, Nov. 1988 [doi>10.1016/0167-8396(88)90013-1 ]
• 4: DOCTOR, L. J., AND TORBORG, J. G. Display techniques for octree-encoded objects. IEEE Comput. Graph. Appl. 1, 3 (July 1981), 29-38.
• 5: R. S. Gallagher , J. C. Nagtegaal, An efficient 3-D visualization technique for finite element models and other coarse volumes, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.185-194, July 1989
• 6: GARGANTINI, I. Linear octrees for fast processing of three-dimensional objects. Comput. Graph. Image Process. 20, 4 (Dec. 1982), 365-374.
• 7: I Gargantini , T R Walsh , O L Wu, Viewing transformations of voxel-based objects via linear octrees, IEEE Computer Graphics and Applications, v.6 n.10, p.12-21, Oct. 1986 [doi>10.1109/MCG.1986.276564]
• 8: GLASSNER, A.S. Space subdivision for fast ray tracing. IEEE Comput. Graph. Appl. 4, 10 (Oct. 1984), 15-22.
• 9: GLOBUS, A. Octree optimization. In Symposium on Electronic Imaging Science and Technology (San Jose, Calif., Feb. 1991), SPIE/SPSE.
• 10: JACKINS, C. L., AND TANIMOTO, S. Oct-trees and their use in representing 3D objects. omput. Graph. Image Process. 14, 3 (Nov. 1980), 249-270.
• 11: KLINGER, A., AND DYER, C.R. Experiments on picture representation using regular decomposition. Comput. Graph. Image Process. 5, 1 (Mar. 1976), 68-105.
• 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: 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
• 14: MA(), X., KUNII, T., Fumsmm), 1., AND N()MOA, T. Hierarchical representations of 2D/3D gray-scale images and their 2D/3D two-way conversion. IEEE Comput. Graph. Appl. 7, 12 (Dec. 1987), 37 44.
• 15: MEAt;It~:R, D.J. Octree encoding: A new technique for the representation, manipulation, and display of arbitrary, three-dimensional objects by computer. Tech. Rep. IPL-TR-80-111. Image Processing Laboratory, Rensselaer Polytechnic institute, Troy, N.Y., Oct. 1980.
• 16: MEA(;ItER, D.J. Geometric modeling using octree encoding. Comput. Graph. Image Process. 19, 2(June 1982), 129 147.
• 17: MEAl;HER, D.J. Interactive solids processing for medical analysis and planning. In Proceedings NCGA 5th Annual Conference (Dallas, Tex., May 1984), pp. 96 106.
• 18: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.289-298, Aug. 1988
• 19: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 20: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 21: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 22: Sargur N. Srihari, Representation of Three-Dimensional Digital Images, ACM Computing Surveys (CSUR), v.13 n.4, p.399-424, Dec. 1981 [doi>10.1145/356859.356862]
• 23: Markku Tamminen , Hanan Samet, Efficient octree conversion by connectivity labeling, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.43-51, January 1984
• 24: W:XRNOCK, J.E. The hidden line problem and the use of halftone display. In Proceedings of the Second Unit'ersity of Illinois Conference on Computer Graphics, Pertinent Concepts in (5mtputer Graphic\, M. Faiman and J. Nievergelt, Eds., (Mar. 1969), pp. 154 163.
• 25: W,x'm', A. Fundamentals of Three-Dimensional Computer Graphics. Addison-Wesley Reading, Mass., 1st ed., 1989.
• 26: Jane Wilhelms , Allen Van Gelder, Topological considerations in isosurface generation extended abstract, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.79-86, Nov. 1990
• 27: WYvlI,L, (~., M~'PItEETERS, C., AND WYVIIA,, g. Data structures for soft objects. The Visual Comput. 2, 4 (Aug. 1986), 227 234.
• 28: YAMAIiIr(qlI, K., KUNll, T. L., AND FUJIMt:RA, K. Octree-related data structures and algorithms. IEEE ('omput. Graph. Appl. 4, 1 (,Jan. 1984), 53 ,59.
• 29: 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.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Performance

Keywords:
hierarchical spatial enumeration, isosurface extraction, octree, scientific visualization