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

## Overview:

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.

## Motivation:

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)
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
}
}
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.

## Implementation:

In this project, you need to implement the interface Quadtree as follows.

```public class QuadtreeImpl implements Quadtree {
// set the root node of the quadtree

// returns the root of the quadtree

// 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;
}
```
• Here is the class Quadnode given to you. Each Quadnode contains a Patch. Note that there are 3 static methods of class Patch you may use for you implementation.
• The method lightInteraction is the main one you need to implement. It takes two patches (say floor and wall) as input, and returns the two quadtrees of them and the hashtable storing it as a LightInteractionObject This method is only for this special quadtree with this specific functionality (light interaction). (That is, a generic quadtree might not contain such an object).
• The hashtable can be any of your implementations HashTable, BrentHashTable, or GonnetMunroHashTable. Note that they all extend AbstractHashTable in part B, programming assignment 1.
• For each (key, value) pair stored in hashtable, the key is the name of a patch, and the value is a PatchSet storing all patches with links from the key patch.
• For full credit, you need to expand your hashtable whenever the number of (key,value) pair exceeds the size/capacity of the table. That means you need to create a larger hashtable and put all the (key,value) pairs in the larger one.
• For full credit, you need to handle the exceptions by improper Feps or Aeps correctly, specifically the NonPositiveEpsException.
• All the resource (java files) your need for this project is here.