“Bounds and error estimates for radiosity” by Lischinski, Smits and Greenberg

We present a method for determining a posteriori bounds and estimates for local and total errors in radiosity solutions. The ability to obtain bounds and estimates for the total error is crucial fro reliably judging the acceptability of a solution. Realistic estimates of the local error improve the efficiency of adaptive radiosity algorithms, such as hierarchical radiosity, by indicating where adaptive refinement is necessary.First, we describe a hierarchical radiosity algorithm that computes conservative lower and upper bounds on the exact radiosity function, as well as on the approximate solution. These bounds account for the propagation of errors due to interreflections, and provide a conservative upper bound on the error. We also describe a non-conservative version of the same algorithm that is capable of computing tighter bounds, from which more realistic error estimates can be obtained. Finally, we derive an expression for the effect of a particular interaction on the total error. This yields a new error-driven refinement strategy for hierarchical radiosity, which is shown to be superior to brightness-weighted refinement.

1. ANSELONE, P. M. Convergence and Error Bounds for Approximate Solutions of Integral and Operator Equations. In Error in Digital Com-putation, L. B. Rall, Ed., vol. 2, John Wiley & Sons, New York, 1965, pp. 231-252.
2. ARVO,JAMES. The Irradiance Jacobian for Partially Occluded Polyhe-dral Sources. In Computer Graphics Proceedings, Annual Conference Series, 1994.
3. ARVO,JAMES,KENNETH TORRANCE, AND BRIAN SMITS. A Frame-work for the Analysis of Error in Global Illumination Algorithms. In Computer Graphics Proceedings, Annual Conference Series, 1994.
4. BABU? SKA, I., O. C. ZIENKIEWICZ,J.GAGO, AND E. R. DE A. OLIVEIRA, EDS. Accuracy Estimates and Adaptive Refinements in Finite Element Computations, John Wiley & Sons, Chichester, 1986.
5. BREBBIA,C.A.AND M. H. ALIABADI,EDS. Adaptive Finite and Boundary Element Methods, Computational Mechanics Publications, Southampton, and Elsevier Applied Science, London, 1993.
6. BROWN, R. W. Upper and Lower Bounds for Solutions of Integral Equations. In Error in Digital Computation, L. B. Rall, Ed., vol. 2, John Wiley & Sons, New York, 1965, pp. 219-230.
7. CAMPBELL, III, A. T. Modeling Global Diffuse Illumination for Image Synthesis, PhD dissertation, University of Texas at Austin, Austin, Texas, December 1991.
8. COHEN,MICHAEL F. , DONALD P. GREENBERG,DAVID S. IMMEL, AND PHILIP J. BROCK. An Efficient Radiosity Approach for Realistic Image Synthesis. IEEE Computer Graphics and Applications, 6(2), March 1986, pp. 26-35.
9. COHEN,MICHAEL F. AND JOHN R. WALLACE. Radiosity and Realis-tic Image Synthesis, Academic Press Professional, Cambridge, Mas-sachusets, 1993.
10. DELVES,L.M.AND J. L. MOHAMED. Computational Methods for Integral Equations, Cambridge University Press, Cambridge, Great Britain, 1985.
11. GOLUB,GENE H. AND CHARLES F. VAN LOAN. Matrix Computa-tions, The Johns Hopkins University Press, Baltimore, Maryland, 2nd edition, 1989.
12. GORTLER,STEVEN J., PETER SCHR~ ODER,MICHAEL F. COHEN, AND PAT HANRAHAN. Wavelet Radiosity. In Computer Graphics Proceedings, Annual Conference Series, 1993, pp. 221-230.
13. HANRAHAN,PAT,DAVID SALZMAN, AND LARRY AUPPERLE. A Rapid Hierarchical Radiosity Algorithm. Computer Graphics, 25(4), July 1991, pp. 197-206.
14. LEWINS,JEFFERY. Importance, The Adjoint Function: The Physical Basis of Variational and Perturbation Theory in Transport and Diffu-sion Problems, Pergamon Press, New York, 1965.
15. LISCHINSKI,DANI,FILIPPO TAMPIERI, AND DONALD P. GREENBERG. Combining Hierarchical Radiosity and Discontinuity Meshing. In Computer Graphics Proceedings, Annual Conference Series, 1993, pp. 199-208.
16. NISHITA,TOMOYUKI AND EIHACHIRO NAKAMAE. Half-Tone Repre-sentation of 3-D Objects Illuminated by Area Sources or Polyhedron Sources. Proceedings of COMPSAC ’83 (Chicago, Illinois, November 1983), pp. 237-241.
17. SMITS,BRIAN E., JAMES R. ARVO, AND DAVID H. SALESIN.An Importance-Driven Radiosity Algorithm. Computer Graphics, 26(4), July 1992, pp. 273-282.
18. SPARROW, E. M. A New and Simpler Formulation for Radiative Angle Factors. ASME Journal of Heat Transfer, 85(2), May 1963, pp. 81-88.
19. SZAB~ O,BARNA AND IVO BABU? SKA. Finite Element Analysis, John Wiley & Sons, New York, 1991.
20. TARJAN,ROBERT ENDRE. Data Structures and Network Algorithms, SIAM, Philadelphia, 1983.
21. TROUTMAN,ROY AND NELSON L. MAX. Radiosity Algorithms Using Higher Order Finite Elements. In Computer Graphics Proceedings, Annual Conference Series, 1993, pp. 209-212.
22. ZATZ,HAROLD R. Galerkin Radiosity: A Higher Order Solution Method for Global Illumination. In Computer Graphics Proceedings, Annual Conference Series, 1993, pp. 213-220.