Next: Gauss-Seidel iteration Up: RADIOSITY METHOD Previous: Cubic tetrahedral algorithm

# Solution of the linear equation

The most obvious way to solve a linear equation is to apply the Gauss elimination method [PFTV88]. Unfortunately it fails to solve the radiosity equation for more complex models effectively, since it has complexity, and also it accumulates the round of errors of digital computers and magnifies these errors to the extent that the matrix is close to singular.

Fortunately another technique, called iteration, can overcome both problems. Examining the radiosity equation,

we will see that it gives the equality of the energy which has to be radiated due to emission and reflection (right side) and the energy really emitted (left side). Suppose that only estimates are available for radiosities, not exact values. These estimates can be regarded as right side values, thus having substituted them into the radiosity equation, better estimates can be expected on the left sides. If these estimates were exact -- that is they satisfied the radiosity equation --, then the iteration would not alter the radiosity values. Thus, if this iteration converges, its limit will be the solution of the original radiosity equation.

In order to examine the method formally, the matrix version of the radiosity equation is used to describe a single step of the iteration:

A similar equation holds for the previous iteration too. Subtracting the two equations, and applying the same consideration recursively, we get:

The iteration converges if

for some matrix norm. Let us use the norm defined as the maximum of absolute row sums

and a vector norm that is compatible with it:

Denoting by q, we have:

according to the properties of matrix norms. Since represents the portion of the radiated energy of surface i, which actually reaches surface j, is that portion which is radiated towards any other surface. This obviously cannot exceed 1, and for physically correct models, diffuse reflectance , giving a norm that is definitely less than 1. Consequently q<1, which provides the convergence with, at least, the speed of a geometric series.

The complexity of the iteration solution depends on the operations needed for a single step and the number of iterations providing convergence. A single step of the iteration requires the multiplication of an N dimensional vector and an dimensional matrix, which requires operations.

Concerning the number of necessary steps, we concluded that the speed of the convergence is at least geometric by a factor . The infinite norm of is close to being independent of the number of surface elements, since as the number of surface elements increases, the value of form factors decreases, sustaining a constant sum of rows, representing that portion of the energy radiated by surface i, which is gathered by other surfaces, multiplied by the diffuse coefficient of surface i. Consequently, the number of necessary iterations is independent of the number of surface elements, making the iteration solution an process.

Next: Gauss-Seidel iteration Up: RADIOSITY METHOD Previous: Cubic tetrahedral algorithm

Szirmay-Kalos Laszlo
Mon Oct 21 14:07:41 METDST 1996