CMSC 420 Section 0401 - Programming Assignment 2
Visibility & Light Interactions
Due March 13, 11:45PM


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.

Your task:

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)
		else {
			if (isDividable(w,Aeps) { // You will be given function isDividable
				// code to divide w into 4 parts w.sw, w.nw,, 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,, Feps, Aeps);
				Refine(f,, Feps, Aeps);
	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).
  1. Estimate(f,w) is a mathematical function based on the coordinates of f and w. Let u represent half the distance of the longer diagonal of w, and v represent the distance between the two centers of f and w. Estimate(f,w) is defined as u2/(u2+v2). Note that this function is not symmetric.
  2. isDividable is function to determine if a patch is dividable with respect to a given precision.
  3. When a patch is subdivided into four parts (specifically southwest, northwest, southeast, northeast), the four patches are named with convention southwest = 00, northwest = 01, southeast = 10 and northeast = 11. For example, if the name of a patch is w01, its four subdivisions are named "w0100", "w0101", "w0110" and "w0111". In a quadtree, the four children of a node should have these patches in sequence. For example, the first (leftmost) child is named "w0100".
  4. link(a,b) will store a link from a to b in the hashtable (of Part 1) and will be useful to answer queries.
  5. A one dimensional example is shown below with the help of a binary tree.


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;