|
ABSTRACT
This paper presents a rapid hierarchical radiosity algorithm for illuminating scenes containing large polygonal patches. The algorithm constructs a hierarchical representation of the form factor matrix by adaptively subdividing patches into subpatches according to a user-supplied error bound. The algorithm guarantees that all form factors are calculated to the same precision, removing many common image artifacts due to inaccurate form factors. More importantly, the algorithm decomposes the form factor matrix into at most O(n) blocks (where n is the number of elements). Previous radiosity algorithms represented the element-to-element transport interactions with n2 form factors. Visibility algorithms are given that work well with this approach. Standard techniques for shooting and gathering can be used with the hierarchical representation to solve for equilibrium radiosities, but we also discuss using a brightness-weighted error criteria, in conjunction with multigridding, to even more rapidly progressively refine the image.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Appel, A.A. (1985) An efficient program for many-body simulation. SIAM J. Sci. Star. Computing 6(1), 85-103.
|
| |
2
|
Barnes, J., Hut, P. (1986) A hierarchical O(NlogN) forcecalculation algorithm. Nature 324, 446-449.
|
 |
3
|
|
 |
4
|
|
| |
5
|
|
 |
6
|
|
 |
7
|
|
| |
8
|
Cohen, M.F., Greenberg, D.P., Immel, D.S., Brock, P.J. (1986) An efficient radiosity approach for realistic image synthesis. IEEE Computer Graphics and Applications 6(2), 26- 30.
|
 |
9
|
|
 |
10
|
|
| |
11
|
Esselink, E. (1989) About the order of Appel's algorithm. Computing Science Note KES-1, Department of Computer Science, University of Groningen.
|
| |
12
|
Greengard, L. (1988) The rapid evaluation of potential fields in particle systems. MIT Press, Cambridge, MA.
|
| |
13
|
Hanrahan, P., Salzman, D.B. (1990) A rapid hierarchical radiosity algorithm for unoccluded environments. Published in K. Bouatouch, Photosimulation, Realism and Physics in Computer Graphics. Springer-Verlag (1991), Reprinted as Princeton University CS-TR-281-90.
|
 |
14
|
|
| |
15
|
Medley, T.J.V. (1988) A shading method for computer generated images. Master's Thesis, The University of Utah
|
| |
16
|
Siegel, R., Howell, J.R. (1981) Thermal radiation heat trans. yet. Hemisphere Publishing Co., Washington, DC
|
 |
17
|
|
 |
18
|
|
 |
19
|
|
 |
20
|
|
| |
21
|
Warnock, J. (1969) A hidden-surface algorithm for computer-generated half-tone pictures. Technical Report TR 4-15, NTIS AD-?53 671, Computer Science Department, University of Utah.
|
CITED BY 106
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Weiping Shi , Jianguo Liu , Naveen Kakani , Tiejun Yu, A fast hierarchical algorithm for 3-D capacitance extraction, Proceedings of the 35th annual conference on Design automation, p.212-217, June 15-19, 1998, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
J. P. Singh , C. Holt , J. L. Hennessy , A. Gupta, A parallel adaptive fast multipole method, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.54-65, December 1993, Portland, Oregon, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L. Alonso , F. Cuny , S. Petit Jean , J.-C. Paul , S. Lazard , E. Wies, The virtual mesh: a geometric abstraction for efficiently computing radiosity, ACM Transactions on Graphics (TOG), v.20 n.3, p.169-201, July 2001
|
|
|
|
|
|
Mark Goudreau , Kevin Lang , Satish Rao , Torsten Suel , Thanasis Tsantilas, Towards efficiency and portability: programming with the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1996, Padua, Italy
|
|
|
|
|
|
|
|
|
Daniel Meneveaux , Kadi Bouatouch , Gilles Subrenat , Philippe Blasi, Efficient clustering and visibility calculation for global illumination, Proceedings of the 2nd international conference on Computer graphics, virtual Reality, visualisation and interaction in Africa, February 03-05, 2003, Cape Town, South Africa
|
|
|
Donald P. Greenberg , Kenneth E. Torrance , Peter Shirley , James Arvo , Eric Lafortune , James A. Ferwerda , Bruce Walter , Ben Trumbore , Sumanta Pattanaik , Sing-Choong Foo, A framework for realistic image synthesis, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.477-494, August 1997
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tom Mertens , Jan Kautz , Philippe Bekaert , Hans-Peter Seidelz , Frank Van Reeth, Interactive rendering of translucent deformable objects, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ricardo Avila , Taosong He , Lichan Hong , Arie Kaufman , Hanspeter Pfister , Claudio Silva , Lisa Sobierajski , Sidney Wang, VolVis: a diversified volume visualization system, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tom Mertens , Jan Kautz , Philippe Bekaert , Hans-Peter Seidel , Frank Van Reeth, Interactive rendering of translucent deformable objects, Proceedings of the SIGGRAPH 2003 conference on Sketches & applications: in conjunction with the 30th annual conference on Computer graphics and interactive techniques, July 27-31, 2003, San Diego, California
|
|
|
|
|
|
|
|
|
Greg Coombe , Mark J. Harris , Anselmo Lastra, Radiosity on graphics hardware, Proceedings of the 2004 conference on Graphics interface, p.161-168, May 17-19, 2004, London, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pascal Guitton , Jean Roman , Gilles Subrenat, Implementation results and analysis of a parallel progressive radiosity, Proceedings of the IEEE symposium on Parallel rendering, p.31-38, October 30-31, 1995, Atlanta, Georgia, United States
|
|
|
David Zareski , Bretton Wade , Philip Hubbard , Peter Shirley, Efficient parallel global illumination using density estimation, Proceedings of the IEEE symposium on Parallel rendering, p.47-54, October 30-31, 1995, Atlanta, Georgia, United States
|
|
|
|
|
|
Jaakko Lehtinen , Matthias Zwicker , Emmanuel Turquin , Janne Kontkanen , Frédo Durand , François X. Sillion , Timo Aila, A meshless hierarchical representation for light transport, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
|
|
|
|
|
|
|
|
|
|
|
|
Tobias Ritschel , Thorsten Grosch , Jan Kautz , Hans-Peter Seidel, Interactive global illumination based on coherent surface shadow maps, Proceedings of graphics interface 2008, May 28-30, 2008, Windsor, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|