“Wavelet radiosity” by Gortler, Schröder, Cohen and Hanrahan

Radiosity methods have been shown to be an effective means
to solve the global illumination problem in Lambertian diffuse
environments. These methods approximate the radiosity integral
equation by projecting the unknown radiosity function into a set
of basis functions with limited support resulting in a set of n
linear equations where n is the number of discrete elements in the
scene. Classical radiosity methods required the evaluation of n2
interaction coefficients. Efforts to reduce the number of required
coefficients without compromising error bounds have focused on
raising the order of the basis functions, meshing, accounting for
discontinuities, and on developing hierarchical approaches, which
have been shown to reduce the required interactions to O(n).
In this paper we show that the hierarchical radiosity formulation
is an instance of a more general set of methods based on wavelet
theory. This general framework offers a unified view of both
higher order element approaches to radiosity and the hierarchical
radiosity methods. After a discussion of the relevant theory, we
discuss a new set of linear time hierarchical algorithms based on
wavelets such as the multiwavelet family and a flatlet basis which
we introduce. Initial results of experimentation with these basis
sets are demonstrated and discussed

1. ALPERT, B. A Class of Bases in L2 for the Sparse Representation of Integral Operators. SIAM Journal on Mathematical Analysis 24, 1 (Jan 1993).
2. ALPERT, B., BEYLKIN, Q., COLEMAN, R., AND ROKHLIN, V. Wavelet-like Bases for the Fast Solution of Second-kind Integral Equations. SIAM Journal on Scientific Computing 14, 1 (Jan 1993).
3. BEYLKIN, Q., COIFMAN, R., AND ROKHLIN, V. Fast Wavelet Transforms and Numerical Algorithms I. Communications on Pure and Applied Mathematics 44 (1991), 141-183.
4. CHUI, C. I~. An Introduction to Wavelets, vol. 1 of Wavelet Analysis and its Applications. Academic Press Inc., 1992.
5. COHEN, M., 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.
6. COHEN, M. F., AND GREENBERG, D. P. The Hemi-Cube: A Radiosity Solution for Complex Environments. Computer Graphics 19, 3 (July 1985), 31-40.
7. DAUBECHIES, I. Ten Lectures on Wavelets, vol. 61 of CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, 1992.
8. DELVES, L. M., AND MOHAMED, J. L. Computational Methods for Integral Equations. Cambridge University Press, 1985.
9. GORAL, C. M., TORRANCE, K. E., GREENBERG, D. P., AND BATTAILE, B. Modelling the Interaction of Light between Diffuse Surfaces. Computer Graphics 18, 3 (July 1984), 212-222.
10. GORTLER, S. J., COHEN, M. F., AND SLUSALLEK, P. Radiosity and Relaxation Methods; Progressive Refinement is Southwell Relaxation. Tech. Rep. CS-TR-408-93, Department of Computer Science, Princeton University, February 1993.
11. HANRAHAN, P., SALZMAN, D., AND AUPPERLE, L. A Rapid Hierarchical Radiosity Algorithm. Computer Graphics 25, 4 (July 1991), 197-206.
12. HECKBERT, P. S. Simulating Global Illumination Using Adaptive Meshing. PhD thesis, University of California at Berkeley, January 1991.
13. HECKBERT, P. S. Radiosity in Flafland. Computer Graphics Forum 2, 3 (1992), 181-192.
14. KAJIYA, J. T. The Rendering Equation. Computer Graphics 20, 4 (1986), 143-150.
15. LISCHINSKI, D., TAMPIERI, F., AND GREENBERG, D. P. A Discontinuity Meshing Algorithm for Accurate Radiosity. IEEE CG&A 12, 4 (July 1992).
16. MALLAT, S. G. A Theory for Multiresolution Signal Decomposition: The Wavelet Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 11 (July 1989), 674-693.
17. PRESS, W., TEUKOLSKI, S., VETTERLING, W., AND FLAN- NERY, B. Numerical Recipies in C, The Art of Scientific Computing, 2 ed. Cambridge University Press, 1992.
18. SALESlN, D., LISCHINSKI, D., AND DERosE, T. Reconstructing Illumination Functions with Selected Discontinuities. Third Eurographics Workshop on Rendering (1992), 99-112.
19. SCHR/SDER, P. Numerical Integration for Radiosity in the Presence of Singularities. In Fourth Eurographics Workshop on Rendering (1993).
20. SCHRODER, P., GORTLER, S. J., COHEN, M. F., AND HANRA- nAN, P. Wavelet Projections For Radiosity. In Fourth Eurographics Workshop on Rendering (June 1993).
21. SCHRCIDER, P., AND HANRAHAN, P. On The Form Factor Between Two Polygons. In Computer Graphics, Annual Conference Series, 1003 (August 1993), Siggraph.
22. STOER, J., AND BULIRSCH, R. Introduction to NumericalAnalysis. Springer Verlag, New York, 1980.
23. SZELISKI, R. Fast Surface Interpolation Using Hierarchical Basis Functions. IEEE Trans. PAM112, 6 (June 1990), 513-439.
24. YSERENTANT, H. On the Multi-level Splitting of Finite Element Spaces. Numerische Mathematik 49 (1986), 379-412.
25. ZATZ, H. R. Galerkin Radiosity: A Higher-order Solution Method for Global Illumination. In Computer Graphics, Annual Conference Series, 1003 (August 1993), Siggraph.