Graphics Reference
In-Depth Information
1
-
r
F
-
r
F
..
..
-
r
F
B
B
E
E
Ê
ˆ
Ê
ˆ
Ê
ˆ
111
112
11
n
1
1
Á
Á
Á
Á
Á
˜
˜
˜
˜
˜
Á
Á
Á
Á
Á
˜
˜
˜
˜
˜
Á
Á
˜
˜
˜
˜
˜
-
r
F
1
-
r
F
-
r
F
221
222
22
n
2
2
.
.
.
.
.
.
.
=
.
.
Á
Á
Á
(10.7)
.
.
.
.
.
Ë
¯
Ë
¯
Ë
¯
-
r
F
-
r
F
..
1
-
r
F
B
E
nn
1
nn
2
nnn
n
n
in matrix form. If we define a matrix
K
= (K
ij
), where K
ij
=d
ij
-r
i
F
ij
, then equation
(10.7) can be written more compactly as
KB
=
E
.
(10.8)
When the B
i
have been solved for, we will have a single radiosity value for each of our
surface patches. We can now use a standard Gouraud shading model renderer to
display the world. The renderer will actually need illumination values at vertices of
the surfaces, but these can be obtained by averaging the illumination values of the
patches surrounding a vertex. In general terms, the overall steps for a radiosity ren-
derer are then
generate the
surfaces for
a scene
subdivide them
into sufficiently
small patches
compute
the form
factors
solve the
matrix equation
(10.8)
display world
using a standard
renderer
Æ
Æ
Æ
Æ
The first four of these steps are view independent, which means that the most time-
consuming computations have to be made only once.
Because the matrix equation (10.8) involves a large matrix, direct methods for
solving it, like Gaussian elimination, are unsuitable and one is led to use iterative
methods. The idea is to make an initial guess
B
(0)
and then by means of a sequence
of corrections produce a sequence of new guesses that hopefully converge to a solu-
tion. Let
B
(k)
denote the kth guess and define the
residual
r
(k)
by
(
)
(
)
k
k
r
=
BE
-
.
The size of a residual tells us how close we are to an actual solution. An iterative algo-
rithm of this type is called a
relaxation method
if at each step of the iteration a guess
is updated in such a way as to set one of the residuals to zero. Although this may
change the other residuals, one hopes that an overall improvement has occurred. Algo-
rithm 10.3.1 is an O(n
2
) algorithm, which computes an approximation to the radios-
ity vector
B
. It is based on a relaxation method called the Gauss-Seidel algorithm. The
justification for the formula in the algorithm is derived from the fact that to make the
ith component of the residual for the kth solution
B
(k)
zero, we must replace the ith
component B
i
(k)
of
B
(k)
by
n
Ê
Á
ˆ
˜
1
Â
(
k
)
(
k
)
B
+
EKB
-
.
i
ij
i
j
K
ii
j
=
1
