“Hierarchical view-dependent structures for interactive scene manipulation” by Brière and Poulin

The result of a scene manipulation is usually displayed by re-rendering the entire image even if the change has affected only a small portion of it. This paper presents a system that efficiently detects and recomputes the exact portion of the image that has changed after an arbitrary manipulation of a scene viewed from a fixed camera. The incremental rendering allows for all visual effects produced by ray tracing, including shadows, reflections, refractions, textures, and bump maps. Two structures are maintained to achieve this. A ray tree is associated with each pixel and is used to detect and rebuild only the modified rays after an optical or geometrical change. A color tree represents the complete color expression of a pixel. All changes affecting the color of a pixel without changing the corresponding ray tree require only re-evaluation of the affected portions of the color tree. Optimizations are presented to efficiently detect the modified structures by the use of strategies such as grouping similar information and building hierarchies. Pruning and weighted re-evaluation of information are also considered to manage the memory requirements. The incremental rendering is done efficiently and accurately and is suitable in an interactive context.

1. James Arvo. Backward ray tracing. SIGGRAPH 86 Tutorial notes on Developments in Ray Tracing, August 1986.
2. Robert L. Cook. Shade trees. Proceedings of SIGGRAPH 84. In Computer Graphics, 18, 3 (July 1984), pp. 223-231.
3. Franklin C. Crow. Shadow algorithms for computer graphics. Proceedings of SIGGRAPH 77. In Computer Graphics, 11, 2 (July 1977), pp. 242-248.
4. Thomas A. Funkhouser and Carlo H. S6quin. Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments. Proceedings of SIGGRAPH 93. In Computer Graphics Proceedings, Annual Conterence Series, August 1993, pp. 247-254.
5. Ned Greene. Applications of world projections. Proceedings of Graphics Interface 86, (May 1986), pp. 108-114.
6. Ned Greene. Detecting intersection of a rectangular solid and a convex polyhedron. In Paul Heckbert, editor, Graphics Gems IV, pages 74-82. Academic Press, Boston, 1994.
7. Ned Greene and M. Kass. Hierarchical Z-buffer visibility. Proceedings of SIG- GRAPH 93. In Computer Graphics Proceedings, Annual Conference Series, August 1993, pp. 231-240.
8. Brian Guenter, Todd B. Knoblock, and Erik Ruf. Specializing shaders. Proceedings of SIGGRAPH 95. In Computer Graphics Proceedings, Annual Conference Series, August 1995, pp. 343-350.
9. Eric Haines and John Wallace. Shaft culling for efficient ray-traced radiosity. In Eurographics Workshop on Rendering, 1991.
10. Pat Hanrahan and Paul E. Haeberli. Direct WYSIWYG painting and texturing on 3D shapes. Proceedings of SIGGRAPH 90. In Computer Graphics, 24, 4 (August 1990), pp. 215-223.
11. David A. Jevans. Object space temporal coherence for ray tracing. Proceedings of Graphics Interface 92, (May 1992), pp. 176-183.
12. Peter Litwinowicz and Gavin Miller. Efficient techniques for interactive texture placement. Proceedings of SIGGRAPH 94. In Computer Graphics Proceedings, Annual Conference Series, July 1994, pp. 119-122.
13. K. Murakami and K. Hirota. Incremental ray tracing. In Eurographics Workshop on Photosimulation, Realism and Physics in Computer Graphics, June 1989, pp. 17-32.
14. Mark Segal, Carl Korobkin, Rolf van Widenfelt, Jim Foran, and Paul E. Haeberli. Fast shadows and lighting effects using texture mapping. Proceedings of SIG- GRAPH 92. In Computer Graphics, 26, 2 (July 1992), pp. 249-252.
15. Carlo H. S6quin and Eliot K. Smyrl. Parameterized ray tracing. Proceedings of SIGGRAPH 89. In Computer Graphics, 23, 3 (July 1989), pp. 307-314.
16. Alan Watt and Mark Watt. Advanced Animation and Rendering Techniques: Theory and Practice. Addison-Wesley Publishing Company, 1992.
17. Turner Whitted. An improved illumination model for shaded display. Communications of the ACM, 23(6):343-349, June 1980.
18. Lance Williams. Casting curved shadows on curved surfaces. Proceedings of SIGGRAPH 78. In Computer Graphics, 12, (August 1978), pp. 270-274.