Bounds and error estimates for radiosity

ABSTRACT

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.

REFERENCES

• 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: James Arvo, The irradiance Jacobian for partially occluded polyhedral sources, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.343-350, July 1994 [doi>10.1145/192161.192250]
• 3: James Arvo , Kenneth Torrance , Brian Smits, A framework for the analysis of error in global illumination algorithms, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.75-84, July 1994 [doi>10.1145/192161.192179]
• 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: Alvin Theophilus Campbell, III, Modeling global diffuse illumination for image synthesis, University of Texas at Austin, Austin, TX, 1992
• 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: Michael F. Cohen , John Wallace , Pat Hanrahan, Radiosity and realistic image synthesis, Academic Press Professional, Inc., San Diego, CA, 1993
• 10: L. M. Delves , J. L. Mohamed, Computational methods for integral equations, Cambridge University Press, New York, NY, 1985
• 11: GOLUB,GENE H. AND CHARLES F. VAN LOAN. Matrix Computa-tions, The Johns Hopkins University Press, Baltimore, Maryland, 2nd edition, 1989.
• 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: 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: 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]
• 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: Brian E. Smits , James R. Arvo , David H. Salesin, An importance-driven radiosity algorithm, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.273-282, July 1992
• 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: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 21: 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]
• 22: 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
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Radiosity

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

General Terms:
Algorithms, Measurement, Performance, Theory, Verification

Keywords:
a posteriori error bounds and estimates, adaptive refinement, global illumination, hierarchical radiosity, importance