@ ~ Computer Graphics, Volume 22, Number 4, August 1988 A Progressive Refinement Approach to Fast Radiosity Image Generation Michael F. Cohen, Shenchang Eric Chen, John R. Wallace, Donald P. Greenberg Program of Computer Graphics, Cornell University Abstract A reformulated radiosity algorithm is presented that produces initial images in time linear to the number of patches. The enormous memory costs of the radiosity algorithm are also elim- inated by computing form-factors on-the-fly. The technique is based on the approach of rendering by progressive refinement. The algorithm provides a useful solution almost immediately which progresses gracefully and continuously to the complete radiosity solution. In this way the competing demands of real- ism and interactivity are accommodated. The technique brings the use of radiosity for interactive rendering within reach and has implications for the use and development of current and future graphics workstations. CR Categories and Subject Descriptors: 1.3.3 [Computer Graphics]: Picture/Image Generation - Display algorithms. 1.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism General Terms: Algorithms Additional Key Words and Phrases: radiosity, progressive re- finement, backward ray tracing, z-buffer, global i~lumination, adaptive subdivision. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. ©1988 AC M -0-89791-275 -6/88/008/0075 $00.75 1 Introduction Two goals have largely shaped the "field of image synthesis since its inception: visual realism and interactivity. The desire for realism has motivated the development of global illumination algorithms such as ray tracing {19], [5], [12] and radiosity [7], [13], [3], with often impressive results. However, the need for interactive manipulation of objects for geometric modeling and other computer aided design areas has generated another path of evolution. This path, dominated by speed, led from the work o~" early researchers [18], [8], [14] and others, to the develop- ment of current engineering workstations capable of drawing thousands of shaded polygons a second [16], [6]. In order to achieve this performance, much of what is central to the goal of realism has had to be sacrificed, including the effects of shad- ows and global illumination. On the other hand, algorithms like ray-tracing and radiosity are too expensive on current machines to be used as the basis of interactive rendering. One approach to accommodating the competing demands of interactivity and image quality is offered by the method of ren- dering by adaptive refinement [2]. In this approach rendering begins with a simple, quickly rendered version of the image, and progresses through a sequence of increasing realism, until a change in the scene or view requires that the process start again. The aim is to provide the highest quality image possible within the time constraints imposed by the user's manipulation of the scene. It is crucial to this approach that the early images be of usable quality at interactive speeds and that the progression to greater realism be graceful, that is, automatic, continuous, and not distracting to the user. In the words of Bergman, what is needed is a golden thread, a single rendering operation that, with repeated application, will continually refine the quality of an image. This paper presents a reformulation of the radiosity algorithm that provides such a thread. The radiosity approach is a particu- larly attractive basis for a progressive approach for two reasons. First, the process correctly simulates the global illumination of diffuse environments. Second, it provides a view-independent 75f SIGGRAPH '88, Atlanta, August 1-5, 1988 solution of fhe diffuse component of reflection. Thus the re- finement process may continue uninterrupted as the user views the scene from different directions. Unfortunately, the conven- tional radiosity algorithm provides no usable results until after the solution is complete, a computation of order n '2, ( where n is the number of discrete surface patches). The original algorithm has the additional disadvantage of using Urn 2) storage. In the revised radiosity algorithm presented here, an initial ap- proximation of the global diffuse illumination provides a starting point for refinement. A reorganization of the iterative solution of the radiosity equations allows the illumination of all surfaces in the environment to be updated at each step and ensures that the correct solution is approached early in the process. In addi- tion to providing a basis for graceful image refinement, the new algorithm requires only O(n) storage. 2 The Cost of Realism for the Conven- tional Radiosity Algorithm The radiosity algorithm is a method for evaluating the intensity or radiosity at discrete points and surface areas in an environ- ment. The relationship between the radiosity of a given discrete surface area, or patch, and the radiosity of all other patches in the environment is given by: BiAi = EiAi + Pl ~, BjFjiAi (1) 3=1 where Bi -- radiosity of patch i (energy/unit area/unit time), El = emission of patch i (energy/unit area/unit time), Ai = area of patch i, A s -- area of patch j, j~ = form-factor from j to i (fraction of energy leavlng patch j which arrives at patch i), p~ = reflectivity of patch i, and n = number of discrete patches. Using the reciprocity relationship for form-factors [15], FijA, = FjiAj (2) and dividing through by Ai, the more familiar radiosity equation is obtained: B, = E, + p~ ~ BjF~ (3) j=l or in matrix form: .... I iilt -raP21 1 - p2F22 -p2F2. I B2 E2 .... I = L -p.F,~ -p,~F,~2 • • .1 - pnFn,~J ~ ,~ (4) The computation involved in the conventional hemi-cube ra-