A framework for the analysis of error in global illumination algorithms

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.

REFERENCES

• 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: Larry Aupperle , Pat Hanrahan, A hierarchical illumination algorithm for surfaces with glossy reflection, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.155-162, September 1993 [doi>10.1145/166117.166137]
• 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: D. R. Baum , H. E. Rushmeire , J. M. Winget, Improving radiosity solutions through the use of analytically determined form-factors, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.325-334, July 1989
• 6: CHANDRASEKAR, S. Radiative Transfer. Dover Publications, New York, 1960.
• 7: Michael F. Cohen , Shenchang Eric Chen , John R. Wallace , Donald P. Greenberg, A progressive refinement approach to fast radiosity image generation, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.75-84, Aug. 1988
• 8: Michael F. Cohen , Donald P. Greenberg, The hemi-cube: a radiosity solution for complex environments, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.31-40, Jul. 1985
• 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: Cindy M. Goral , Kenneth E. Torrance , Donald P. Greenberg , Bennett Battaile, Modeling the interaction of light between diffuse surfaces, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.213-222, July 1984
• 11: GORTLER, S. J., AND COHEN, M. F. Radiosity and relaxation methods. Tech. Rep. TR 408-93, Princeton University, 1993.
• 12: Steven J. Gortler , Peter Schröder , Michael F. Cohen , Pat Hanrahan, Wavelet radiosity, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.221-230, September 1993 [doi>10.1145/166117.166146]
• 13: Pat Hanrahan , David Salzman , Larry Aupperle, A rapid hierarchical radiosity algorithm, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.197-206, July 1991
• 14: Paul Seagrave Heckbert, Simulating global illumination using adaptive meshing, University of California at Berkeley, Berkeley, CA, 1992
• 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: David S. Immel , Michael F. Cohen , Donald P. Greenberg, A radiosity method for non-diffuse environments, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.133-142, Aug. 1986
• 18: James T. Kajiya, The rendering equation, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.143-150, Aug. 1986
• 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: Dani Lischinski , Filippo Tampieri , Donald P. Greenberg, Discontinuity Meshing for Accurate Radiosity, IEEE Computer Graphics and Applications, v.12 n.6, p.25-39, November 1992 [doi>10.1109/38.163622]
• 25: Dani Lischinski , Filippo Tampieri , Donald P. Greenberg, Combining hierarchical radiosity and discontinuity meshing, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.199-208, September 1993 [doi>10.1145/166117.166143]
• 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: Peter Schröder , Pat Hanrahan, On the form factor between two polygons, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.163-164, September 1993 [doi>10.1145/166117.166138]
• 35: Françis X. Sillion , James R. Arvo , Stephen H. Westin , Donald P. Greenberg, A global illumination solution for general reflectance distributions, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.187-196, July 1991
• 36: TOULOUKIAN, Y. S., Ed. Retrieval Guideto ThermophysicalProperties Research Literature, second ed. McGraw-Hill, New York, 1968.
• 37: Roy Troutman , Nelson L. Max, Radiosity algorithms using higher order finite element methods, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.209-212, September 1993 [doi>10.1145/166117.166144]
• 38: J. R. Wallace , K. A. Elmquist , E. A. Haines, A Ray tracing algorithm for progressive radiosity, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.315-324, July 1989
• 39: Gregory J. Ward, Measuring and modeling anisotropic reflection, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.265-272, July 1992
• 40: Stephen H. Westin , James R. Arvo , Kenneth E. Torrance, Predicting reflectance functions from complex surfaces, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.255-264, July 1992
• 41: Harold R. Zatz, Galerkin radiosity: a higher order solution method for global illumination, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.213-220, September 1993 [doi>10.1145/166117.166145]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Measurement, Performance, Theory

Keywords:
boundary elements, discretization, error bounds, global illumination, linear operators, projection methods, radiosity, reflectance functions