
Boston University CS 580
Assignment 3
Masha Shugrina
Problem Summary:
To implement radiosity algorithm for modeling diffuse reflections within a closed environment
represented modeled using quadrilateral geometric primitives.
Algorithm:
The algorithm can be summarized using the following components:
1. Subdivide the Scene
The scene is input as a text file composed of octahedrons and quadrilaterals,
which are subdivided into patches of roughly equal dimensions based on the constant
maximum patch size. The patches are stored in a quadtree representation as
follows:
The original imput patches of the quadrilateral geometric primitives are
each subdivided into 4 subpatches. The process continues recursively until the
prespecified patch width is reached. Then, during the initalization process of the scene,
the leaves are connected linked into a singly linked list. These leaf patches
are referred to by indices i and j in the following duscussion.
2. Iterative Radiosity Solution
Radiosity is based on computing the light energy reflected from patch to
patch within the scene using a large linear equation system. Because computing
the exact solution is very computationally expensive, iterative methods are preferable.
This project implements the Progressive Radiosity iterative algorithm:
&forall patches i B_{i} = E_{i}, &Delta B_{i} = E_{i}
while not converged
pick i s.t. &Delta B_{i}*A_{i} is maximal
for every other patch j
&Delta rad = &Delta B_{i}*&rho_{j}F_{ji}
&Delta B_{j} += &Delta rad
B_{j} += &Delta rad
&Delta B_{i} = 0
display intermediate image result
Here, &rho is the reflectance of the patch.
This method eliminates the necessity of evaluating every possible Form Factor,
and hence attains greater efficiency. Additionally, it allows the intermediate
result to be displayed.
3. Form Factor Computation
Form Factor F_{ij}
is defined as the light energy that reaches patch j from patch i divided by the total
light energy reflected from patch i, or mathematically:
F_{ij}= 1/A_{i}&int _{Ai}&int _{Aj}[cos &phi_{i} cos &phi_{j}/&phi r^{2}] dA_{j}dA_{i}
where A_{i} and A_{j} are the areas of patches i and j, dA's are the differential
areas, and &phi 's are angles formed between the line connecting the differential areas and their
respective normals.
Because the closed form of this integral is highly impractical, a number of numerical
approximation techniques have been devised. This project implementes the Monte Carlo algorithm,
that can be summarized as follows:
from the center of patch i shoot out N rays, uniformly distributed over the hemisphere
set up an array F[num_patches]
for each ray r
compute the intersection with the closest other patch j in the scene
F[num_patches] += cos &phi_{i} cos &phi_{j}/&phi r^{2}
from each entry j in F obtain the following
F_{ij} = F[j]*A_{j}/N
F_{ji} = F[j]*A_{i}/N
Hence, at each step in the progressive radiosity algorithm, a whole row of Form Factors is
computed. The relationship F_{ji}A_{j}= F_{ij}A_{i} is utilized
to avoid overcomputation. The rayscene intersection is made more efficient for simple quadrilateral
models by the quad tree representation: first the intersection points are computed for each mother patch,
and then the intersected leaf within the patch subtree is identified via inside/outside plane tests (two
for each step down the tree).
4. Error Computation
For a scene with n patches the radiosity linear equation problem can be formulated in terms of the KB=E matrix
equation, where K is an n*n matrix with K[i][j] = &rho_{i}F_{ij} and 1's across
across the diagonal, E is the n*1 vector of emission coefficients for each patch, and B is the n*1 vector
of unknown radiosity values for each patch in the scene. Given this information, the error, termed the residual,
is computed as follows:
R = KBE,
where B is the estimated radiosity solution. The length of this vector can be used as the
convergence criterion for the Progressive Radiosity, and for the implementation of adaptive subdivision.
However, because the value of the residual that produces the desired image is to be determined empirically,
this implementation provides user with the maximum control of the resultant image. The algorithm automatically
runs for #iterations n = #patches/10, and the user is given the freedom to request another round of n
iterations. This feedback loop approach seems to me more trustworthy and artistically feasible than the
residual computation. After all, the scene may look better in a preconvergence gloom.
5. Adaptive Subdivision
This is a possible extension of the system.
6. Rendering
During the subdivision process, the vertices of the newlycreated subpatches are not duplicated. Each vertex keeps track
of its 4 (or less) immediate neighboring patches. Before rendering, the color of each vertex is computed by averaging
the radiosities of the neighboring patches. Then, rendering is performed using OpenGL smooth polygon
shading. Backface culling is enabled.
Results:
Cornell Box:
The following images were produced using a subdivision model of order of 2,000 patches.
These two images show the vertex to patch pointers used to interpolate the radiosity values
of the patches.
These are intermediate results for 50, 300 and 1000 iterations of the Progressive Radiosity Algorithm, respectively.
(Click to enlarge).
These are three views of the final result achieved with about 1200 iterations.
Cafe:
The first image was produced with 2700 patches, 1000 iterations and took approximately 15 minutes on
a 1.73 GHz processor. The second and third images were achieved with 680 patches and 400 iterations:
they deomonstrate the need of adaptive subdivision for scenes with small objects (notice the peculiar
"lack" if shadows due to interpolation over oversized patches).
Miscellaneous Room:
This was achieved via 800 iterations for a 700 patch model. The images show uninterpolated, interpolated,
wireframe and vertextopatchconnections views.
The results are rather convincing even without adaptive subdivision, however, the system as it is now
cannot produce nice sharp shados, especially from thing objects s.a. table legs. However, the system
has been designed to allow for this modification, and this extensions would be fairly simple to
implement.
Program:
The program is a simple console application built in VC++. It compiles and runs on Windows using the
OpenCV and OpenGL libraries. The expected input is a text file, the specifications for which as well
as other useful information can be found in the README file. The most important files in the bundle
are scene.cpp and geomTypes.cpp.
Download All Files
