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

j
(
x
)
dAdA

=

(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)

Search Nedrilad ::

Custom Search