“Hierarchical image caching for accelerated walkthroughs of complex environments” by Shade, Lischinski, Salesin, DeRose and Snyder

We present a new method that utilizes path coherence to accelerate walkthroughs of geometrically complex static scenes. As a preprocessing step, our method constructs a BSP-tree that hierarchically partitions the geometric primitives in the scene. In the course of a walkthrough, images of nodes at various levels of the hierarchy are cached for reuse in subsequent frames. A cached image is reused by texture-mapping it onto a single quadrilateral that is drawn instead of the geometry contained in the corresponding node. Visual artifacts are kept under control by using an error metric that quantifies the discrepancy between the appearance of the geometry contained in a node and the cached image. The new method is shown to achieve speedups of an order of magnitude for walkthroughs of a complex outdoor scene, with little or no loss in rendering quality.

1. John M. Airey, John H. Rohlf, and Frederick E Brooks, Jr. Towards image realism with interactive update rates in complex virtual building environments. Computer Graphics (1990 Symposium on Interactive 3D Graphics), 24(2):41-50, March 1990.
2. Bradford Chamberlain, Tony DeRose, Dani Lischinski, David Salesin, and John Snyder. Fast rendering of complex environments using a spatial hierarchy. In Proceedings of Graphics Interface ’96, May 1996.
3. Shenchang Eric Chen and Lance Williams. View interpolation for image synthesis. In Computer Graphics Proceedings, Annual Conference Series, pp. 279-288, August 1993.
4. James H. Clark. Hierarchical geometric models for visible surface algorithms. Communications of the ACM, 19(10):547-554, October 1976.
5. Matthias Eck, Tony DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, and Werner Stuetzle. Multiresolution analysis for arbitrary meshes. In Computer Graphics Proceedings, Annual Conference Series, pp. 173-182, August 1995.
6. Henry Fuchs, Zvi M. Kedem, and Bruce Naylor. On visible surface generation by a priori tree structures. Computer Graphics, 14(3): 175- 181, June 1980.
7. Thomas A. Funkhouser and Carlo H. S6quin. Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments. In Computer Graphics Proceedings, Annual Conference Series, pp. 247-254, August 1993.
8. B. Garlick, D. Baum, and J. Winget. Interactive viewing of large geometric databases using multiprocessor graphics workstations. SIG- GRAPH ’90 Course Notes: Parallel Algorithms and Architectures for 3D Image Generation, 1990.
9. Ned Greene, Michael Kass, and Gavin Miller. Hierarchical z-buffer visibility. In Computer Graphics Proceedings, Annual Conference Series, pp. 231-238, August 1993.
10. Timothy L. Kay and James T. Kajiya. Ray tracing complex scenes. Computer Graphics, 20(4):269-278, August 1986.
11. Daivid Luebke and Chris Georges. Portals and mirrors: Simple, fast evaluation of potentially visible sets. In 1995 Symposium on Interactive 3D Graphics, pp. 105-106, April 1995.
12. Paulo W. C. Maciel and Peter Shirley. Visual navigation of large environments using textured clusters. In 1995 Symposium on Interactive 3D Graphics, pp. 95-102, April 1995.
13. Leonard McMillan and Gary Bishop. Plenoptic modeling: An imagebased rendering system. In Computer Graphics Proceedings, Annual Conference Series, pp. 39-46, August 1995.
14. Jackie Neider, Tom Davis, and Mason Woo. OpengGL Programming Guide. Addison Wesley, 1993.
15. Matthew Regan and Ronald Pose. Priority rendering with a virtual reality address recalculation pipeline. In Computer Graphics Proceedings, Annual Conference Series, pp. 155-162, July 1994.
16. Jarek Rossignac and Paul Borrel. Multi-resolution 3D approximations for rendering complex scenes. Research Report RC 17697 (#77951), IBM, Yorktown Heights, New York 10598, 1992. Also appeared in the IFIP TC 5.WG 5.10.
17. Gernot Schaufler. Exploiting frame to frame coherence in a virtual reality system. In Proceedings of VRAIS ’96, pp. 95-102, April 1996.
18. Gernot Schaufler and Wolfgang Stiirzlinger. A three dimensional image cache for virtual reality. In Proceedings of Eurographics ’96, 1996. To appear.
19. Seth J. Teller. Visibility Computations in Densely Occluded Polyhedral Environments. PhD thesis, Computer Science Division (EECS), UC Berkeley, Berkeley, California 94720, October 1992. Available as Report No. UCB/CSD-92-708.
20. Jay Torborg and Jim Kajiya. Talisman: Commodity realtime 3D graphics for the PC. In Computer Graphics Proceedings, Annual Conference Series, August 1996.