James Arvo
ABSTRACT
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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 6.CHANDRASEKAR, S. Radiative Transfer. Dover Publications, New York, 1960.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 11.GORTLER, S. J., AND COHEN, M. F. Radiosity and relaxation methods. Tech. Rep. TR 408-93, Princeton University, 1993.Google Scholar
- 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. Google ScholarDigital Library
- 13.HANRAHAN, P., SALZMAN, D., AND AUPPERLE, L. A rapid hierarchical radiosity algorithm. Computer Graphics 25, 4 (July 1991), 197-206. Google ScholarDigital Library
- 14.HECKBERT, P. S. Simulating Global Illumination Using Adaptive Meshing. PhD thesis, University of California, Berkeley, June 1991. Google ScholarDigital Library
- 15.HILDEBRAND, F. B. Methods of Applied Mathematics. Prentice-Hall, New York, 1952.Google Scholar
- 16.HOWELL, J. R. A Catalog of Radiation Configuration Factors. McGraw-Hill, New York, 1982.Google Scholar
- 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. Google ScholarDigital Library
- 18.KAJIYA, J. T. The rendering equation. Computer Graphics 20, 4 (August 1986), 143-150. Google ScholarDigital Library
- 19.KANTOROVICH, L., AND AKILOV, G. P. Functional Analysis in Normed Spaces. Pergamon Press, New York, 1964.Google Scholar
- 20.KATO, T. Perturbation Theory for Linear Operators. Springer-Verlag, New York, 1966.Google Scholar
- 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.Google Scholar
- 22.KRESS, R. Linear Integral Equations. Springer-Verlag, New York, 1989.Google ScholarCross Ref
- 23.LINZ, P. Theoretical Numerical Analysis, an Introduction to Advanced Techniques. John Wiley ~ Sons, New York, 1979.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 26.MACKERLE, J., AND BREBBIA, C. A., Eds. The Boundary Element Reference Book. Springer-Verlag, New York, 1988.Google Scholar
- 27.MODEST, M. F. Radiative Heat Transfer. McGraw-Hill, New York, 1993.Google Scholar
- 28.ORTEGA, J. M. Numerical Analysis, a Second Course. Academic Press, New York, 1972.Google Scholar
- 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.Google ScholarDigital Library
- 30.PLANCK, M. The Theory of Heat Radiation. Dover Publications, New York, 1988.Google Scholar
- 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.Google Scholar
- 32.RUDIN, W. Functional Analysis. McGraw-Hill, New York, 1973.Google Scholar
- 33.RUSHMEIER, H. E., PATTERSON, C., AND VEERASAMY, A. Geometric simplification for indirect illumination calculations. Graphics Interface '93 (May 1993), 227-236.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 36.TOULOUKIAN, Y. S., Ed. Retrieval Guideto ThermophysicalProperties Research Literature, second ed. McGraw-Hill, New York, 1968.Google Scholar
- 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. Google ScholarDigital Library
- 38.WALLACE, J., ELMQUIST, K., AND HAINES, E. A ray tracing algorithm for progressive radiosity. Computer Graphics 23, 3 (July 1989), 315- 324. Google ScholarDigital Library
- 39.WARD, G. J. Measuring andmodeling anisotropic reflection. Computer Graphics 26, 2 (July 1992), 265-272. Google ScholarDigital Library
- 40.WESTIN, S., ARVO, J., AND TORRANCE, K. Predicting reflectance functions from complex surfaces. Computer Graphics 26, 2 (July 1992), 255-264. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- A framework for the analysis of error in global illumination algorithms
Recommendations
Approximating dynamic global illumination in image space
I3D '09: Proceedings of the 2009 symposium on Interactive 3D graphics and gamesPhysically plausible illumination at real-time framerates is often achieved using approximations. One popular example is ambient occlusion (AO), for which very simple and efficient implementations are used extensively in production. Recent methods ...
A progressive multi-pass method for global illumination
A new progressive global illumination method is presented which produces approximate images quickly, and then continues to systematically produce more accurate images. The method combines the existing methods of progressive refinement radiosity, Monte ...
A progressive multi-pass method for global illumination
SIGGRAPH '91: Proceedings of the 18th annual conference on Computer graphics and interactive techniquesA new progressive global illumination method is presented which produces approximate images quickly, and then continues to systematically produce more accurate images. The method combines the existing methods of progressive refinement radiosity, Monte ...
Comments