Height distributional distance transform methods for height field ray tracing

ABSTRACT

Height distributional distance transform (HDDT) methods are introduced as a new class of methods for height field ray tracing. HDDT methods utilize results of height field preprocessing. The preprocessing involves computing a height field transform representing an array of cone-like volumes of empty space above the height field surface that are as wide as possible. There is one cone-like volume balanced on its apex centered above each height field cell. Various height field transforms of this type are developed. Each is based on distance transforms of height field horizontal cross-sections. HDDT methods trace rays through empty cone-like volumes instead of through successive height field cells. The performance of HDDT methods is evaluated experimentally against existing height field ray tracing methods.

REFERENCES

• 1: D. P. Anderson, Hidden Line Elimination in Projected Grid Surfaces, ACM Transactions on Graphics (TOG), v.1 n.4, p.274-288, Oct. 1982 [doi>10.1145/357311.357313]
• 2: B. Chazelle , H. Edelsbrunner , L. Guibas , M. Sharir, Lines in space-combinators, algorithms and applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.382-393, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73044]
• 3: COHEN, D., AND SH~D, A. 1993. Photo-realistic imaging of digital terrains. Comput. Graph. For. 12, 3, 363-373.
• 4: Richard Cole , Micha Sharir, Visibility problems for polyhedral terrains, Journal of Symbolic Computation, v.7 n.1, p.11-30, Jan. 1989 [doi>10.1016/S0747-7171(89)80003-3]
• 5: COQUILLART, S., AND GANGNET, M. 1984. Shaded display of digital maps. IEEE Comput. Graph. Appl. (July), 35-42.
• 6: DANIEI~SON, P. E. 1980. Euclidean distance mapping. Comput. Graph. image Process. 14, 227-248.
• 7: William Dungan, Jr., A terrain and cloud computer image generation model, ACM SIGGRAPH Computer Graphics, v.13 n.2, p.143-150, August 1979
• 8: J. C. Hart , D. J. Sandin , L. H. Kauffman, Ray tracing deterministic 3-D fractals, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.289-296, July 1989
• 9: James T. Kajiya, New Techniques for Ray Tracing Procedurally Defined Objects, ACM Transactions on Graphics (TOG), v.2 n.3, p.161-181, July 1983 [doi>10.1145/357323.357324]
• 10: Gary A. Mastin , Peter A. Watterberg , John F. Mareda, Fourier synthesis of ocean scenes, IEEE Computer Graphics and Applications, v.7 n.3, p.16-23, March 1987 [doi>10.1109/MCG.1987.276961]
• 11: MUSGRAVE, F. K. 1988. Grid tracing: Fast ray tracing for height fields. Res. Rep. YALEU/DCS/RR-639, (July).
• 12: David W. Paglieroni, A unified distance transform algorithm and architecture, Machine Vision and Applications, v.5 n.1, p.47-55, Winter 1992 [doi>10.1007/BF01213529]
• 13: David W. Paglieroni , Sidney M. Peterson, Parametric height field ray tracing, Proceedings of the conference on Graphics interface '92, p.192-200, September 1992, Vancouver, British Columbia, Canada
• 14: PAGLIERONI, D. W., AND PETERSEN, S.M. 1994. Terrain visualization by ray tracing a conical height field transformation. U.S. Patent 5,355,442, assignee: Loral.
• 15: Azriel Rosenfeld , John L. Pfaltz, Sequential Operations in Digital Picture Processing, Journal of the ACM (JACM), v.13 n.4, p.471-494, Oct. 1966 [doi>10.1145/321356.321357]
• 16: UNRUH, J. E., AND MIKHAIL, E.M. 1977. Image simulation from digital data. In Proceedings of ACSM Fall Technical Meeting, 1-12.
• 17: YAMADA, H. 1984. Complete Elucidean distance transform by parallel operation. In Proceed- ings of the 7th International Conference on Pattern Recognition (Montreal, Canada), 69-71.
• 18: ZUIDERVELD, K. I., KONING, A. H. J., AND VIERGEVER, M.A. 1992. Acceleration of ray-casting using 3D distance transforms. In Proceedings of SPIE, 1808, Visualization in Biomedical Computing, 324- 335.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Raytracing

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

General Terms:
Algorithms, Theory

Keywords:
distance transform, height field, hierarchical methods, incremental methods, parameter plane transform, parametric/nonparametric HDDT methods, ray tracing, terrain