Game Development Reference
In-Depth Information
The finite elements method (Zienkiewicz, 1989) represents a complex function f
by subdividing its domain into n elements e i on which it is approximated by a linear
sum (projection on a base of functions { γ j }):
f ( x )
f j γ j ( x )
f ( x )
=
i
j
This technique was applied to project the radiosity function (Heckbert, 1993;
Bekaert &Willems, 1996). By substituting the approximation to B in equation 15.13,
we obtain a system of linear equations:
K i , i
j , j , B i
B j =
E j +
(15.14)
j
i , j
E j being the coefficients of projection of E ( x ):
E j =
γ j ( x ) E ( x ) dA
(15.15)
x
And K i , i
j , j
the generalised shape factor :
γ j ( x )
K i , i
j , j
ρ ( x ) K ( x , x ) γ i
=
(15.16)
x
x
The steps for formulating and resolving a generic radiosity problem thus consists of:
Subdividing the surfaces of the scene into elements A i ;
Selecting a base of functions γ for the projection;
Calculating the generalised shape factor K between each element of the scene;
Resolving the system of linear equations (unknown
=
coefficients of projection);
Reconstructing the radiosity function B using the coefficients obtained;
Deducing an image from the radiosity function in the scene.
The main problem of radiosity by finite elements is its complexness in terms of time
and memory. For n e elements and functions of order n o , the resolution by direct matrix
inversion has a complexity of O ( n 3 ) with n
n e n o . In fact, this matrix is sparse and
more effective methods can be used (Gortler et al., 1993a), for example the Gauss-
Seidel method or the Southwell relaxation method. Their calculation complexity is
O ( n 2 ) and memory complexity is O ( n 2 )(respectively O ( n )). The functions of upper
order are rarely used due to several discontinuities of radiosity (caused mainly by
shadows). Generally, it is better to more finely discretise the surfaces and reduce the
order of the functions used. Hence constant functions are preferred to elements (Goral
et al., 1984), further simplifying the radiosity equation:
=
ρ i
j
F j B j
B i =
E i +
(15.17)