The holodeck ray cache: an interactive rendering system for global illumination in nondiffuse environments

ABSTRACT

We present a new method for rendering complex environments using interactive, progressive, view-independent, parallel ray tracing. A four-dimensional holodeck data structure serves as a rendering target and caching mechanism for interactive walk-throughs of nondiffuse environments with full global illumination. Ray sample density varies locally according to need, and on-demand ray computation is supported in a parallel implementation. The holodeck file is stored on disk and cached in memory by a server using a least-recently-used (LRU) beam-replacement strategy. The holodeck server coordinates separate ray evaluation and display processes, optimizing disk and memory usage. Different display systems are supported by specialized drivers, which handle display rendering, user interaction, and input. The display driver creates an image from ray samples sent by the server and permits the manipulation of local objects, which are rendered dynamically using approximate lighting computed from holodeck samples. The overall method overcomes many of the conventionl limits of interactive rendering in scenes with complex surface geometry and reflectance properties, through an effective combination of ray tracing, caching, and hardware rendering.

REFERENCES

• 1: John Milligan Airey , Frederick P. Brooks, Jr., Increasing update rates in the building walkthrough system with automatic model-space subdivision and potentially visible set calculations, 1990
• 2: ASHDOWN, I. 1993. Near-field photometry: a new approach. J. Illuminating Eng. Soc. 22, 1, 163-180.
• 3: K. Bala , J. Dorsey , S. Tellet, Bounded-Error Interactive Ray Tracing, Massachusetts Institute of Technology, Cambridge, MA, 1998
• 4: CAMAHORT, E., LERIOS, A., AND FUSSELL, D. 1998. Uniformly sampled light fields. In Proceedings of the 1998 Eurographics Workshop on Rendering Techniques, G. Drettakis and N. Max, Eds.
• 5: Shenchang Eric Chen, QuickTime VR: an image-based approach to virtual environment navigation, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.29-38, September 1995 [doi>10.1145/218380.218395]
• 6: Michael F. Cohen , Shenchang Eric Chen , John R. Wallace , Donald P. Greenberg, A progressive refinement approach to fast radiosity image generation, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.75-84, June 1988
• 7: Carolina Cruz-Neira , Daniel J. Sandin , Thomas A. DeFanti, Surround-screen projection-based virtual reality: the design and implementation of the CAVE, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.135-142, September 1993 [doi>10.1145/166117.166134]
• 8: Lucia Darsa , Bruno Costa Silva , Amitabh Varshney, Navigating static environments using image-space simplification and morphing, Proceedings of the 1997 symposium on Interactive 3D graphics, p.25-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253298]
• 9: DARSA, L. AND SILVA, B. C. 1996. Multi-resolution representation and reconstruction of adaptively sampled images. In Proceedings of the Conference on SIBGRAPI '96, 321-328.
• 10: Paul E. Debevec , Camillo J. Taylor , Jitendra Malik, Modeling and rendering architecture from photographs: a hybrid geometry- and image-based approach, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.11-20, August 1996 [doi>10.1145/237170.237191]
• 11: Paul Joseph Diefenbach, Pipeline rendering: interaction and realism through hardware-based multi-pass rendering, University of Pennsylvania, Philadelphia, PA, 1996
• 12: Steven J. Gortler , Radek Grzeszczuk , Richard Szeliski , Michael F. Cohen, The lumigraph, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.43-54, August 1996 [doi>10.1145/237170.237200]
• 13: Ned Greene, Hierarchical polygon tiling with coverage masks, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.65-74, August 1996 [doi>10.1145/237170.237207]
• 14: Ned Greene , Michael Kass , Gavin Miller, Hierarchical Z-buffer visibility, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.231-238, September 1993 [doi>10.1145/166117.166147]
• 15: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 16: Baining Guo, Progressive radiance evaluation using directional coherence maps, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.255-266, July 1998 [doi>10.1145/280814.280888]
• 17: Paul Haeberli, Paint by numbers: abstract image representations, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.207-214, Aug. 1990
• 18: David Kirk , James Arvo, Unbiased sampling techniques for image synthesis, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.153-156, July 1991
• 19: LARSON, G.W. 1988. The holodeck: A parallel ray-caching rendering system (Unpublished presentation). In Proceedings of the 2nd Eurographics Workshop on Parallel Graphics and Visualization (Rennes, France, Sept. 1988),
• 20: Gregory Ward Larson , Holly Rushmeier , Christine Piatko, A Visibility Matching Tone Reproduction Operator for High Dynamic Range Scenes, IEEE Transactions on Visualization and Computer Graphics, v.3 n.4, p.291-306, October 1997 [doi>10.1109/2945.646233]
• 21: Greg Ward Larson , Rob Shakespeare, Rendering with radiance: the art and science of lighting visualization, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 22: Marc Levoy , Pat Hanrahan, Light field rendering, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.31-42, August 1996 [doi>10.1145/237170.237199]
• 23: Dani Lischinski, Incremental Delaunay triangulation, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 24: LISCHINSKI, D. AND RAPPOPORT, A. 1998. Image-based rendering for non-diffuse synthetic scenes. In Proceedings of the 9th Eurographics Workshop on Rendering (Vienna, Austria, June 1998), 301-314.
• 25: David Luebke , Carl Erikson, View-dependent simplification of arbitrary polygonal environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.199-208, August 1997 [doi>10.1145/258734.258847]
• 26: Leonard McMillan , Gary Bishop, Plenoptic modeling: an image-based rendering system, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.39-46, September 1995 [doi>10.1145/218380.218398]
• 27: MILLER, G., RUBIN, S., AND PONCELEN, D. 1998. Lazy decompression of surface light fields for pre-computed global illumination. In Proceedings of the 9th Eurographics Workshop on Rendering (Vienna, Austria, June 1998),
• 28: Jeffry Nimeroff , Julie Dorsey , Holly Rushmeier, Implementation and Analysis of an Image-Based Global Illumination Framework for Animated Environments, IEEE Transactions on Visualization and Computer Graphics, v.2 n.4, p.283-298, December 1996 [doi>10.1109/2945.556498]
• 29: Eyal Ofek , Ari Rappoport, Interactive reflections on curved objects, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.333-342, July 1998 [doi>10.1145/280814.280929]
• 30: Frederic H. Pighin , Dani Lischinski , David Salesin, Progressive Previewing of Ray-Traced Images Using Image Plane Disconinuity Meshing, Proceedings of the Eurographics Workshop on Rendering Techniques '97, p.115-125, June 16-18, 1997
• 31: PREPARATA, F. P. AND SHAMOS,M. 1985. Proximity: Fundamental Algorithms. Springer-Verlag, New York, NY.
• 32: SCHAUFLER, G. 1998. Per-object image warping with layered imposters. In Proceedings of the 1998 Eurographics Workshop on Rendering Techniques, G. Drettakis and N. Max, Eds.
• 33: Jonathan Shade , Dani Lischinski , David H. Salesin , Tony DeRose , John Snyder, Hierarchical image caching for accelerated walkthroughs of complex environments, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.75-82, August 1996 [doi>10.1145/237170.237209]
• 34: SHIRLEY, P., WADE, B., HUBBARD, P., ZARESKI, D., WALTER, B., AND GREENBERG, D. 1995. Global illumination via density estimation. In Proceedings of the 1995 Eurographics Workshop on Rendering Techniques, 219-230.
• 35: SILLION, F., DRETTAKIS, G., AND BODELET, B. 1997. Efficient imposter manipulation for real-time visualization of urban scenery. In Proceedings of the 1997 Eurographics Forum on Computer Graphics, 207-218.
• 36: Francois X. Sillion , Claude Puech, Radiosity and Global Illumination, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 37: Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.61-70, July 1991
• 38: Jack Tumblin , Holly Rushmeier, Tone Reproduction for Realistic Images, IEEE Computer Graphics and Applications, v.13 n.6, p.42-48, November 1993 [doi>10.1109/38.252554]
• 39: Douglas Voorhies , Jim Foran, Reflection vector shading hardware, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.163-166, July 1994 [doi>10.1145/192161.192193]
• 40: Bruce Walter , Gün Alppay , Eric Lafortune , Sebastian Fernandez , Donald P. Greenberg, Fitting virtual lights for non-diffuse walkthroughs, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.45-48, August 1997 [doi>10.1145/258734.258766]
• 41: WALTER, B., DRETTAKIS, G., AND PARKER, S. 1999. Interactive rendering using the render cache. In Proceedings of the lOth Eurographics Workshop on Rendering (June), 27-38.
• 42: WARD, G. 1991. Real Pixels. Academic Press Prof., Inc., San Diego, CA.
• 43: Gregory J. Ward, The RADIANCE lighting simulation and rendering system, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.459-472, July 1994 [doi>10.1145/192161.192286]
• 44: Gregory J. Ward , Francis M. Rubinstein , Robert D. Clear, A ray tracing solution for diffuse interreflection, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.85-92, June 1988

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.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.0 General
          Subjects: Image displays

General Terms:
Algorithms

Keywords:
illumination, image reconstruction, mesh generation, ray tracing, rendering system, virtual reality