\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{epsfig}

\textheight= 8in \textwidth=4.5in
\parindent =0pt
\hsize = 4in
%\voffset = 1 in
%\hoffset= 1 in
\parindent = 0pt
\parskip = 0.2cm
\tolerance = 10000
\input{../../newcomm}

\begin{document}
\bibliographystyle{plain}



{\bf  Advanced Computer Graphics}  \hfill \today \hrule
{\bf G. Farin }\\




\centerline{\bf Radiosity}

 \section{Form factors}

Assume a scene is composed of $n$ patches $\PP_i$. A subset of
these patches encloses the scene. Each patch receives light from
other patches and reflects light back into the scene. All
reflections are assumed to be diffuse only.  The interaction
between patch $i$ and patch $j$ is given by a {\em form factor}
$f_{ij}$. It determines how much light $\PP_i$ receives from patch
$\PP_j$:
$$
    f_{ij}=\frac{{\rm light~ from}~\PP_j~{\rm to}~\PP_i}
        {{\rm all~light~from~}\PP_j}.
$$
We immediately have:
$$
    \sum_{i=1}^n f_{ij} = 1; ~~ j=1,\ldots, n.
$$
 The $f_{ij}$ are given by
 \beq
    f_{ij}=\frac{1}{\| \PP_i \|} \int_{\PP_i}\int_{\PP_j}
        \frac{\cos \Phi_i \cos \Phi_j {\rm d}\PP_j}
            {\pi r^2}
            \label{eq:doubleint}
\eeq
where the meaning of the involved terms is from Figure
\ref{fig:fij}.
\begin{figure}
       \epsfig{file=fij.ps, height = 2.5 in}
        \caption{The form factor geometry.}
            \label{fig:fij}
\end{figure}

In order to motivate (\ref{fig:doubleint}), assume that $\PP_i$
has very small area. Then, again using Figure \ref{fig:fij}, we
would have
$$
    f_{ij}=\frac{\cos \Phi_i \cos \Phi_j \| \PP_j \|}
                { r^2}.
$$
From this we arrive at (\ref{eq:doubleint}) by integrating over
the areas of $\PP_i$ and $\PP_j$. Note that we have
 \beq
    f_{ij}\| \pp_i \| = f_{ji}\| \PP_j \|.
        \label{eq:recip}
\eeq

An easier way to determine the form factors is by the use of a
{\em hemicube}, a simplified model of a hemisphere. Subdivide each
of the five faces of the hemicube into squares (pixels), resulting
in a total of $M$ pixels. Center the upper half of a cube at a
subpatch $\PP_{i,\rho}$ of $\PP_i$ such the top is parallel to
$\PP_i$. We assume that are $R$ such subpatches.

Now project $\PP_j$ onto the hemicube. Count all pixels visible
from $\PP_{i,\rho}$. Let the number of these pixels be
$n_{i,j,\rho}$. Keep in mind that we only count pixels which are
not occluded by other objects. We repeat this for all subpatches
$\PP_{i,\rho}$, which means a recentering of the hemicube.  Then
$$
    f_{ij} = \frac{1}{\| \PP_i \| }\sum_{\rho=1}^R \frac{\| \PP_{i,\rho} \|n_{ij\rho}}{M}
$$


\section{Setting up the linear system}

Let $b_i$ the brightness of patch $\PP_i$. Let $e_i$ be the amount
of light emitted by $\PP_i$, let $\rho_i$ be the reflectivity of
$\PP_i$, and let $a_i$ be its area. Now the total intensity of
light leaving $\PP_i$ is given by \beq
   a_i b_i = a_ie_i + \rho_i\sum_{j=0}^n f_{ij}a_jb_j;~~i=1,\ldots,n.
        \label{eq:radio1}
\eeq
 The first term gives how much light is emitted by $\PP_i$.
The second term collects all contributions from the other patches;
the factor $\rho_i$ shows how much of that is being reflected by
$\PP_i$.

Invoking (\ref{eq:recip}), we may rewrite (\ref{eq:radio1}) as
$$
   a_i b_i = a_ie_i + \rho_i\sum_{j=0}^n f_{ji}a_i b_j;~~i=1,\ldots,n
$$
and simplify to
\beq
   b_i = e_i + \rho_i\sum_{j=0}^n f_{ji} b_j;~~i=1,\ldots,n.
\eeq

In matrix form:
 \beq
    \bb = \ee + R F \bb
\eeq or
\beq
    \ee =  [I- R F ]\bb
    \label{eq:linsys}
\eeq
where $R$ is a diagonal matrix holding the $\rho_i$ and $F$
is the matrix of form factors. The matrix $I-RF$ has 1's on the
diagonal since we can assume $f_{ii}=0$.

\section{Solving the system}

This linear system for $\bb$ may be huge, but it will always be
sparse. For such systems, an iterative solution is most effective.
In an iterative scenario, one produces a first guess $\bb^0$ for
$\bb$, e.g., by setting all $b_i=0.5$. Then a next guess $\bb^1$
is found from
$$
   \bb^1 = \ee + R F \bb^0
$$
and this process is continued until convergence happens, which is
guaranteed for this scenario. In practice a vector $\bb^k$ is
called the solution if $\| \bb^k - \bb^{k-1} \| < \epsilon$ for
some tolerance epsilon. This iterative process is known as
$Gauss-Jacobi$ iteration.

In that method, all elements of $\bb^k$ is updated from
$\bb^{k-1}$ in one step. A different strategy is usually more
effective. Once the first element of $\bb^k$ has been computed,
the second element of $\bb^k$ may be computed by using this new
$b^k_1$ instead of the old $b^{k-1}_1$. Similarly, the $b^k_3$ may
be computed using $b^k_1$ and $b^k_2$. This process of immediate
updating is known as {\em Gauss-Seidel} iteration.

The matrix $I-RF$ is strictly diagonally dominant, with all
eigenvalues less than unity in absolute value. For such matrices,
a power expansion exists for the inverse:
$$
    [I-RF]^{-1} = \sum_{i=0}^\infty [RF]^i.
$$
Thus
$$
    \bb = \sum_{i=0}^\infty [RF]^i\ee = \ee + [RF]\ee + [RF]^2\ee
    +\ldots
$$
Each term corresponds to one level of tracking reflections.











\end{document}
