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.

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 *m*^{2} 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). } }

**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**u**^{2}/(**u**^{2}+**v**^{2}). Note that this function is not symmetric.-
**isDividable**is function to determine if a patch is dividable with respect to a given precision. - 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". **link**(**a**,**b**) will store a link from**a**to**b**in the hashtable (of Part 1) and will be useful to answer queries.- 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; }

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

- The maximum points are 100.
- Grading will focus on the classes
**QuadtreeImpl**. However, bugs in your implementation of HashTable in programming assignment 1 may break the functionality required in this assignment. - The public drivers for grading will be posted soon.
- [5/6/02 Added by TA:] The public driver QuadtreeDriver1 is now available.
- [5/19/02 Added by TA:] All the grading drivers and keys are available in p2_drivers.tar.gz.

- Tar and gzip your
***.java**files (including the hashtable), and submit. - Submission is handled using the submit program with submission index 5.
Ex:
**"~sc42002/bin/submit 5 foo.tar.gz"**. - I(TA) reserve the right to deduct up to 10 points if you don't follow the submission procedure.