Maximum mipmaps for fast, accurate, and scalable dynamic height field rendering

ABSTRACT

This paper presents a GPU-based, fast, and accurate dynamic height field rendering technique that scales well to large scale height fields. Current real-time rendering algorithms for dynamic height fields employ approximate ray-height field intersection methods, whereas accurate algorithms require pre-computation in the order of seconds to minutes and are thus not suitable for dynamic height field rendering. We alleviate this problem by using maximum mipmaps, a hierarchical data structure supporting accurate and efficient rendering while simultaneously lowering the pre-computation costs to negligible levels. Furthermore, maximum mipmaps allow for view-dependent level-of-detail rendering. In combination with hierarchical ray-stepping this results in an efficient intersection algorithm for large scale height fields.

REFERENCES

• 1: Lionel Baboud , Xavier Décoret, Rendering geometry with relief textures, Proceedings of Graphics Interface 2006, June 07-09, 2006, Quebec, Canada
• 2: James F. Blinn, Simulation of wrinkled surfaces, Proceedings of the 5th annual conference on Computer graphics and interactive techniques, p.286-292, August 23-25, 1978
• 3: Nathan A. Carr , Jared Hoberock , Keenan Crane , John C. Hart, Fast GPU ray tracing of dynamic meshes using geometry images, Proceedings of Graphics Interface 2006, June 07-09, 2006, Quebec, Canada
• 4: Cohen, D., and Shaked, A. 1993. Photo-Realistic Imaging of Digital Terrains. Computer Graphics Forum 12, 3, 363--373.
• 5: Daniel Cohen-Or , Eran Rich , Uri Lerner , Victor Shenkar, A Real-Time Photo-Realistic Visual Flythrough, IEEE Transactions on Visualization and Computer Graphics, v.2 n.3, p.255-265, September 1996 [doi>10.1109/2945.537308]
• 6: Robert L. Cook, Shade trees, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.223-231, January 1984
• 7: Donnelly, W. 2005. GPU Gems 2. Addison-Wesley Professional, ch. Per-Pixel Displacement Mapping with Distance Functions.
• 8: Dummer, J., 2006. Cone Step Mapping: An Iterative Ray-Heightfield Intersection Algorithm. http://www.lonesock.net/files/ConeStepMapping.pdf.
• 9: Guennebaud, G., Barthe, L., and Paulin, M. 2006. Real-Time Soft Shadow Mapping by Backprojection. In Proceedings of EGSR'06, 227--234.
• 10: Christian Henning , Peter Stephenson, Accelerating the ray tracing of height fields, Proceedings of the 2nd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, June 15-18, 2004, Singapore [doi>10.1145/988834.988878]
• 11: Hugues Hoppe, Smooth view-dependent level-of-detail control and its application to terrain rendering, Proceedings of the conference on Visualization '98, p.35-42, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 12: Wei Hu , Kaihuai Qin, Interactive Approximate Rendering of Reflections, Refractions, and Caustics, IEEE Transactions on Visualization and Computer Graphics, v.13 n.1, p.46-57, January 2007 [doi>10.1109/TVCG.2007.14]
• 13: Jeschke, S., Mantler, S., and Wimmer, M. 2007. Interactive Smooth and Curved Shell Mapping. In Proceedings of EGSR'07, 351--360.
• 14: Kolb, A., and Rezk-Salama, C. 2005. Efficient Empty Space Skipping for Per-Pixel Displacement Mapping. In Proceedings of Vision, Modeling and Visualization (VMV'05), 407--414.
• 15: Peter Lindstrom , David Koller , William Ribarsky , Larry F. Hodges , Nick Faust , Gregory A. Turner, Real-time, continuous level of detail rendering of height fields, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.109-118, August 1996 [doi>10.1145/237170.237217]
• 16: Musgrave, F. K. 1988. Grid Tracing: Fast Ray Tracing for Height Fields. Tech. Rep. YALEU/DCS/RR-639, Yale University, Dept. of Computer Science Research.
• 17: Kyoungsu Oh , Hyunwoo Ki , Cheol-Hi Lee, Pyramidal displacement mapping: a GPU based artifacts-free ray tracing through an image pyramid, Proceedings of the ACM symposium on Virtual reality software and technology, November 01-03, 2006, Limassol, Cyprus [doi>10.1145/1180495.1180511]
• 18: Ohbuchi, E. 2003. A Real-Time Refraction Renderer for Volume Objects Using a Polygon-Rendering Scheme. In Proceedings of Computer Graphics International, 190--195.
• 19: Oliveira, M. M., and Policarpo, F. 2005. An Efficient Representation for Surface Details. Tech. rep., Universidade Federal do Rio Grande do Sul.
• 20: Fabio Policarpo , Manuel M. Oliveira, Relief mapping of non-height-field surface details, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California [doi>10.1145/1111411.1111422]
• 21: Policarpo, F., and Oliveira, M. M. 2007. GPU Gems 3. Addison-Wesley Professional, ch. Relaxed Cone Stepping for Relief Mapping.
• 22: Fábio Policarpo , Manuel M. Oliveira , João L. D. Comba, Real-time relief mapping on arbitrary polygonal surfaces, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053453]
• 23: Serban D. Porumbescu , Brian Budge , Louis Feng , Kenneth I. Joy, Shell maps, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 24: Qu, H., Qiu, F., Zhang, N., Kaufman, A., and Wan, M. 2003. Ray Tracing Height Fields. In Proceedings of Computer Graphics International, 9-11, 202--207.
• 25: Ramsey, S. D., Potter, K., and Hansen, C. 2004. Ray Bilinear Patch Intersections. Journal of Graphics Tools 9, 3, 41--47.
• 26: Risser, E., Shah, M., and Pattanaik, S. 2005. Interval Mapping. Tech. rep., University of Central Florida.
• 27: Roettger, S., Heidrich, W., and Slussallek, P. 1998. Real-Time Generation of Continuous Levels of Detail for Height Fields. In Proc. 6th Int. Conf. in Central Europe on Computer Graphics and Visualization, 315--322.
• 28: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 29: Smits, B., Shirley, P., and Stark, M. 2000. Direct Ray Tracing of Smoothed and Displacement Mapped Triangles. PhD thesis.
• 30: Szirmay-Kalos, L., Aszodi, B., Lazanyi, I., and Premecz, M. 2005. Approximate Ray-Tracing on the GPU with Distance Impostors. Computer Graphics Forum 24, 3 (Sept.), 695--704.
• 31: Natalya Tatarchuk, Dynamic parallax occlusion mapping with approximate soft shadows, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California [doi>10.1145/1111411.1111423]
• 32: Chris Wyman, Interactive image-space refraction of nearby geometry, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, November 29-December 02, 2005, Dunedin, New Zealand [doi>10.1145/1101389.1101431]

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.6 Methodology and Techniques
          Subjects: Graphics data structures and data types
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture; Visible line/surface algorithms

Keywords:
GPU, displacement mapping, graphics hardware, height field intersection, real-time rendering, simplification/level of detail, spatial data structures, surface details, texturing techniques