“A framework for the analysis of error in global illumination algorithms” by Arvo, Torrance and Smits

In this paper we identify sources of error in global illumination algorithms and derive bounds for each distinct category. Errors arise from three sources: inaccuracies in the boundary data, discretization, and computation. Boundary data consists of surface geometry, reflectance functions, and emission functions, all of which may be perturbed by errors in measurement or simulation, or by simplifications made for computational efficiency. Discretization error is introduced by replacing the continuous radiative transfer equation with a finite-dimensional linear system, usually by means of boundary elements and a corresponding projection method. Finally, computational errors perturb the finite-dimensional linear system through imprecise form factors, inner products, visibility, etc., as well as by halting iterative solvers after a finite number of steps. Using the error taxonomy introduced in the paper we examine existing global illumination algorithms and suggest new avenues of research.

1. ANSELONE, P. M. Convergence and error bounds for approximate solutions of integral and operator equations. In Error in Digital Computation, L. B. Rall, Ed., vol. 2. John Wiley &Sons, 1965, pp. 231-252.
2. ATKINSON, K. E. A Survey of Numerical Methods for the Solution of Fredholm IntegralEquations of the SecondKind. Society for Industrial and Applied Mathematics, Philadelphia, 1976.
3. AUPPERLE, L., AND HANRAHAN, P. A hierarchical illumination algorithm for surfaces with glossy reflection. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM SIGGRAPH, pp. 155-162.
4. BATEMAN, H. Report on the history and present state of the theory of integral equations. Report of the 18th Meeting of the British Association for the Advancement of Science (1910), 345-424.
5. BAUM, D. R., RUSHMEIER, H. E., AND WINGET, J. M. Improving radiosity solutions through the use of analytically determined formfactors. Computer Graphics 23, 3 (July 1989), 325-334.
6. CHANDRASEKAR, S. Radiative Transfer. Dover Publications, New York, 1960.
7. COHEN, M. F., CHEN, S. E., WALLACE, J. R., AND GREENBERG, D. P. A progressive refinement approach to fast radiosity image generation. Computer Graphics 22, 4 (August 1988), 75-84.
8. COHEN, M. F., AND GREENBERG, D. P. The hemi-cube: A radiosity solution for complex environments. Computer Graphics 19, 3 (July 1985), 75-84.
9. GOLBERG, M. A. Asurvey of numerical methods for integral equations. In Solution methods for integral equations: Theory and applications , M. A. Golberg, Ed. Plenum Press, New York, 1979, pp. 1-58.
10. GORAL, C. M., TORRANCE, K. E., GREENBERG, D. P., AND BATTAILE, B. Modeling the interaction of light between diffuse surfaces. Computer Graphics 18, 3 (July 1984), 213-222.
11. GORTLER, S. J., AND COHEN, M. F. Radiosity and relaxation methods. Tech. Rep. TR 408-93, Princeton University, 1993.
12. GORTLER, S. J., SCHR~DER, P., COHEN, M. F., AND HANRAHAN, P. Wavelet radiosity. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM SIGGRAPH, pp. 221-230.
13. HANRAHAN, P., SALZMAN, D., AND AUPPERLE, L. A rapid hierarchical radiosity algorithm. Computer Graphics 25, 4 (July 1991), 197-206.
14. HECKBERT, P. S. Simulating Global Illumination Using Adaptive Meshing. PhD thesis, University of California, Berkeley, June 1991.
15. HILDEBRAND, F. B. Methods of Applied Mathematics. Prentice-Hall, New York, 1952.
16. HOWELL, J. R. A Catalog of Radiation Configuration Factors. McGraw-Hill, New York, 1982.
17. IMMEL, D. S., COHEN, M. F., AND GREENBERG, D. P. A radiosity method for non-diffuse environments. Computer Graphics 20, 4 (August 1986), 133-142.
18. KAJIYA, J. T. The rendering equation. Computer Graphics 20, 4 (August 1986), 143-150.
19. KANTOROVICH, L., AND AKILOV, G. P. Functional Analysis in Normed Spaces. Pergamon Press, New York, 1964.
20. KATO, T. Perturbation Theory for Linear Operators. Springer-Verlag, New York, 1966.
21. KRASNOSEL’SKII, M. A., VAINIKKO, G. M., ZABREIKO, P. P., RUTITSKII, Y. B., AND STETSENKO, V. Y. Approximate Solution of Operator Equations. Wolters-Noordhoff, Groningen, The Netherlands, 1972. Translated by D. Louvish.
22. KRESS, R. Linear Integral Equations. Springer-Verlag, New York, 1989.
23. LINZ, P. Theoretical Numerical Analysis, an Introduction to Advanced Techniques. John Wiley ~ Sons, New York, 1979.
24. LISCHINSKI, D., TAMPIERI, F., AND GREENBERG, D. P. Discontinuity meshing for accurate radiosity. IEEE Computer Graphics and Applications 12, 6 (November 1992), 25-39.
25. LISCHINSKI, D., TAMPIERI, F., AND GREENBERG, D. P. Combining hierarchical radiosity and discontinuity meshing. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM SIGGRAPH, pp. 199-208.
26. MACKERLE, J., AND BREBBIA, C. A., Eds. The Boundary Element Reference Book. Springer-Verlag, New York, 1988.
27. MODEST, M. F. Radiative Heat Transfer. McGraw-Hill, New York, 1993.
28. ORTEGA, J. M. Numerical Analysis, a Second Course. Academic Press, New York, 1972.
29. PHILLIPS, J. L. The use of collocation as a projection methodfor solving linear operator equations. SIAM Journal on Numerical Analysis 9, 1 (1972), 14-28.
30. PLANCK, M. The Theory of Heat Radiation. Dover Publications, New York, 1988.
31. POLYAK, G. L. Radiative transfer between surfaces of arbitrary spatial distribution of reflection. In Convective and Radiative Heat Transfer. Publishing House of the Academy of Sciences of the USSR, Moscow, 1960.
32. RUDIN, W. Functional Analysis. McGraw-Hill, New York, 1973.
33. RUSHMEIER, H. E., PATTERSON, C., AND VEERASAMY, A. Geometric simplification for indirect illumination calculations. Graphics Interface ’93 (May 1993), 227-236.
34. SCHR~DER, P., AND HANRAHAN, P. On the form factor between two polygons. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM SIGGRAPH, pp. 163-164.
35. SILLION, F., ARVO, J., WESTIN, S., AND GREENBERG, D. P. A global illumination solution for general reflectance distributions. Computer Graphics 25, 4 (July 1991), 187-196.
36. TOULOUKIAN, Y. S., Ed. Retrieval Guideto ThermophysicalProperties Research Literature, second ed. McGraw-Hill, New York, 1968.
37. TROUTMAN, R., AND MAX, N. L. Radiosity algorithms using higherorder finite element methods. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM SIGGRAPH, pp. 209-212.
38. WALLACE, J., ELMQUIST, K., AND HAINES, E. A ray tracing algorithm for progressive radiosity. Computer Graphics 23, 3 (July 1989), 315- 324.
39. WARD, G. J. Measuring andmodeling anisotropic reflection. Computer Graphics 26, 2 (July 1992), 265-272.
40. WESTIN, S., ARVO, J., AND TORRANCE, K. Predicting reflectance functions from complex surfaces. Computer Graphics 26, 2 (July 1992), 255-264.
41. ZATZ, H. Galerkin radiosity: Ahigher order solution method for global illumination. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM SIGGRAPH, pp. 213-220.