Many three dimensional computation (such as those in video games) seem to benefit from a hierarchical data structure. Like hashing, quadtree are data structures that seem to work best in practice (the theoretical worst case times are overly pessimistic).
The board goal of this assignment is to be able to deal with quadtrees for purposes of light interactions in global illumination.
Consider a room illuminated by a single source of light placed on the ceiling. When painted with "the color of the wall", as in the figure on the left, the picture appears unrealistic. On the other hand, color may be computed using indirect lighting. For example, the ceiling does not "see" the light source. However, it is not dark because of the light reflected from the floor. (Note that in the picture on the left, the light source has not been deliberately painted white.)
In general, any piece of the geometry in a scene receives light both from the source of light (if visible), and an infinite number of points in the scene. And this is true for all points. To get around infinity, we divide the scene into "small" parts and compute interactions between them.
Of course, we will not produce a picture in this assignment. Instead, you will be given two objects (for example, the wall on the left (W) and the floor(F)) and you will set up links. The link W-->F means the floor receives light from the wall (which it does). However, this link is too imprecise because we do not know which part of wall the floor receives light from. (By the way, we also want to set up the link F-->W.)
We could split the wall into a grid (a 2D array) of size m. And the floor too. Now we have m2 links. But this is an overkill because we do not need to subdivide the wall uniformly. Far portions of the wall are unlikely to impact the floor too much. A quadtree is a better representation of the floor than an array.
You will be given two three dimensional quadrilaterals (w and f) in 3D space and two small numbers (Feps and Aeps). You will store each quadrilateral as a quadtree based on the following pseudo code.
Refine(Patch f, Patch w, double Feps, double Aeps) {
double Ffw, Fwf;
// You will be given function Estimate.
Ffw = Estimate(f,w);
Fwf = Estimate(w,f);
if (Ffw < Fwf) {
if (Fwf<Feps)
Link(f,w);
else {
if (isDividable(w,Aeps) { // You will be given function isDividable
// code to divide w into 4 parts w.sw, w.nw, w.se, w.ne here
// sw, nw, se, ne stand for southwest, northwest, southeast, northeast, respectively.
Refine(f, w.sw, Feps, Aeps);
Refine(f, w.nw, Feps, Aeps);
Refine(f, w.se, Feps, Aeps);
Refine(f, w.ne, Feps, Aeps);
}
else
link(f,w);
}
}
else { // Ffw >= Fwf
// code same as above, but reverse the role of f and w.
// The reverse of Refine(f, w.sw, Feps, Aeps) is Refine(w, f.sw, Feps, Aeps).
}
}
In this project, you need to implement the interface Quadtree as follows.
public class QuadtreeImpl implements Quadtree {
// set the root node of the quadtree
public void setRoot(Quadnode root);
// returns the root of the quadtree
public Quadnode getRoot();
// returns true if the quadtree has a descendant that contains the patch
// with name patchName.
// This is mainly for grading purpose.
public boolean containsNodeWithPatchName(String patchName);
// It should have some more methods, such as:
// (1) Given a point, find the smallest patch containing it, if any.
// (2) Given a point, find all the patches adjacent to it.
// However, they are not required in this project.
// constructs the 2 quadtrees representing floor and wall respectively.
// returns them as a LightInteractionObject.
// Feps and Aeps are the arguments for the pseudo code refine(), see description above..
public LightInteractionObject lightInteraction(Patch floor, Patch wall, double Feps, double Aeps) throws NonPositiveEpsException;
}