Editing Radiosity (computer graphics) (section)

=== Solution methods ===
The equation can formally be solved as matrix equation, to give the vector solution:
:<math>B = (I - \rho F)^{-1} E \;</math>
This gives the full "infinite bounce" solution for B directly.  However the number of calculations to compute the matrix solution scales according to ''n''<sup>3</sup>, where ''n'' is the number of patches.  This becomes prohibitive for realistically large values of ''n''.

Instead, the equation can more readily be solved iteratively, by repeatedly applying the single-bounce update formula above.  Formally, this is a solution of the matrix equation by [[Jacobi iteration]].  Because the reflectivities ρ<sub>i</sub> are less than 1, this scheme converges quickly, typically requiring only a handful of iterations to produce a reasonable solution.  Other standard iterative methods for matrix equation solutions can also be used, for example the [[Gauss–Seidel method]], where updated values for each patch are used in the calculation as soon as they are computed, rather than all being updated synchronously at the end of each sweep.  The solution can also be tweaked to iterate over each of the sending elements in turn in its main outermost loop for each update, rather than each of the receiving patches.  This is known as the ''shooting'' variant of the algorithm, as opposed to the ''gathering'' variant.  Using the view factor reciprocity, ''A''<sub>i</sub> ''F''<sub>ij</sub> = ''A''<sub>j</sub> ''F''<sub>ji</sub>, the update equation can also be re-written in terms of the view factor ''F''<sub>ji</sub> seen by each ''sending'' patch ''A''<sub>j</sub>:
:<math>A_i B_i = A_i E_i + \rho_i \sum_{j=1}^n A_j B_j F_{ji}</math>
This is sometimes known as the "power" formulation, since it is now the total transmitted power of each element that is being updated, rather than its radiosity.

The [[view factor]] ''F''<sub>ij</sub> itself can be calculated in a number of ways. Early methods used a ''[[Hemicube (computer graphics)|hemicube]]'' (an imaginary cube centered upon the first surface to which the second surface was projected, devised by [[Michael F. Cohen]] and [[Donald P. Greenberg]] in 1985). The surface of the hemicube was divided into pixel-like squares, for each of which a view factor can be readily calculated analytically.  The full form factor could then be approximated by adding up the contribution from each of the pixel-like squares. The projection onto the hemicube, which could be adapted from standard methods for determining the visibility of polygons, also solved the problem of intervening patches partially obscuring those behind.

However all this was quite [[computation]]ally expensive, because ideally [[form factor (radiative transfer)|form factor]]s must be derived for every possible pair of patches, leading to a [[Quadratic function|quadratic]] increase in computation as the number of patches increased. This can be reduced somewhat by using a [[Binary space partitioning|binary space partitioning tree]] to reduce the amount of time spent determining which patches are completely hidden from others in complex scenes; but even so, the time spent to determine the form factor still typically scales as ''n'' log ''n''.  New methods include adaptive integration.<ref>G Walton, ''Calculation of Obstructed View Factors by Adaptive Integration'', [http://www.bfrl.nist.gov/IAQanalysis/docs/NISTIR-6925.pdf NIST Report NISTIR-6925], see also http://view3d.sourceforge.net/</ref>