CMSC 341 Spring 2009
|| Friday, March 20, 2009
||11:59pm Friday April 3, 2009
||Sample command line arguments:
"file1.txt 5 5 file2.txt"
||Deadline extended until Sunday April 5th, 11:59 pm
- To gain experience implementing a Binary Tree ADT from scratch
- To gain experience using inheritance with generic classes
- To gain experience using Tree Iterators
- To gain experience using a Binary Tree in a real application
- To gain experience implementing the Adapter Design Pattern
A Binary Search Tree is most commonly used for maintaining information in a manner such that
any node's left child is less than that of its value and a right child is greater than it.
This definition is recursive and visually creates a partitioning of data held within the structure.
A Binary Space Partition Tree is an implementation upon this which is commonly used in graphics
to divide a scene up about a specific polygon into all polygons that are either behind or infront
of that specific polygon. For a polygon, or anything (an object), to be in view (visible to us) we commonly
say you are facing it. For an object to be infront of you, we commonly refer to objects that are
in view from our left shoulder to the right.
In this project you will implement a variation upon both of these data
structures creating a Space Tree which will be used to partition objects in a scene based upon
a viewing location and view direction vector.
We will implement a variation of a binary search tree using inheritance called a Space Tree. This will
require you to implement your own Binary Search Tree ADT and create the derived Space Tree implementation.
This Space Tree has a couple of properties (some recursive) that must be upheld at all times
given the following information:
The viewer is located at an object in Cartesian space. The point at which the viewer resides is indicated
(x,y) The view vector consists of (dx,dy) which represents the run and rise of the direction in which the viewer is facing/directed.
Space Tree Properties:
- The Root is always the point at which the viewer resides, initially (after creation) this will be at an object in Cartesian space
- A node's right child is an object infront of the node applying the viewer's vector
- A node's left child is an object behind of the node applying the viewer's vector
Figure 1: All letters are objects in the scene. X is the object where viewer resides at that specific time. v
is the view vector of the viewer. If we look at the children of Y, we can see the effect of applying v to Y. Note that
E is infront of Y thus its right child, and D is behind Y making it its left child.
Distance and View Vectors
Computing distance between any two points P1 and P2 can be computed by the following calculation (wikipedia.com):
Calculates the distance between any two points
Given the view vector of the Space Tree v knowing if an object is in view (infront or behind) is a simple comparison.
First, we apply the viewer's view vector v to a node(object) and call this vector v' at P0.
Then given any point P1, not currently present in our tree, we calculate another vector v1
If v1 is not within a 90o rotation of v' then it is out of view and behind P0. Seen in Figure 2. To find the
Θ for the difference in rotation (90o from v') lets look at how to rotate a vector v by &Theta degrees to create v'':
|P1(x) - P0(x)|
|P1(y) - P0(y)|
|vx*cos(&Theta) - vy*sin(&Theta)|
*cos(&Theta) + vx*sin(&Theta)|
Using v' and v1 you can solve for &Theta .
where v1 and v' are normalized.
|&Theta = cos-1(v1 dot v')|
|v1 dot v' = v1(x)*v'(x)+v1(y)*v'(y)|
Project 3 will be invoked with multiple command line arguments.
- The first argument is the name of the text file which will contain the objects in the scene. These are to be inserted
into the Space Tree in the order read from the file based on the 2nd and 3rd command line arguments. The first object in this file
is to be inital viewer location.
- The second argument is the view vector. Note this view vector may divide your scene
any way you can draw a straight line. (Two integers)
- The third argument is the name of a text file containing a series of commands.
Every command defined below triggers the resulting response in the application. Please
note that the commands are case sensitive and illegal commands should be dealt with such
that the program does not abort execution.
- PRINTSCENE - Prints the name of all objects in the scene starting with the object that is farthest out of view to farthest in view
- PRINTVIEW - Prints the name of all objects in view of the viewer starting with the object closet to farthest
- ADDOBJECT - Adds an object with Name and X Y coordinates
- MOVE - Moves the viewer along the vector to the next Ith object given integer value.
- ROTATE - Rotates the view vector given an integer value for the degree. A positive value will represent a counter clockwise rotation
and negative will represent a clockwise rotation.
- REMOVEOBJECT - Removes the object at the viewer's current location moving the viewer to the next closest
object in view
The Scene Object ADT
The Scene Object ADT is a Binary Node with a few changes to the methodology. The left child is a node that is behind the parent
and the right child is a node that is infront. Scene objects also have a name(string) and x and y coordinates (The object file will contain these fields in this order).
will be integer values.
The Space Tree ADT
This ADT will implement the properties of the Space Tree, manage the viewer location, and manage
the view vector. The Space Tree also has the following functionality:
- printViewableObjects() - this functions prints all objects infront of the viewer.
- moveViewpoint(int) - this function moves the viewer location forward or backward along the veiw vector to
the next closest scene object. Forward and backwards are denoted by positive and negative values. See project notes for a definition of closest.
- rotateView(int) - this will trigger your tree to recreate itself at the viewer's location with the new view vector calculated from the old vector
- insert(Scene Object) - this will insert of a scene object into the tree.
Basic Project Requirements
- ALL TREES used in this project must be created from scratch. This includes tree
iterators if you choose to use one. This means NO JAVA TREES or ITERATORS are permitted.
- You create/modify your own tree, tree node, and tree iterator.
- The Space Tree must be implemented using inheritance from the Binary Tree you create.
- All possible exceptions discussed pertaining to Trees
must be caught and dealt with appropriately. Your program should continue
processing after an exception if at all possible.
- Only the Space Tree class is instantiated in main( )
or in functions called from main( ).
- You may include any private data and private functions to any class.
- Be prepared for your code to work on large data sets.
- The move function must result in a splay operation. You can use either top-down or bottom-up splay methods.
- You must bulletproof your code as much as possible, e.g. making sure that the command line
parameters are all valid, that the files named in it all exist, and that there is at least one
report command. In case of invalid report parameters, your program should print them and a message
indicating that the command is in error.
Project Notes and Hints
- You may not use the java tree classes and will recieve 0 points in this event. However,
you may use the material presented in class as a guide. This does not mean you can copy any code
from the slides.
- For this project you are to consider closest as an object in the Space Tree which is nearest
to the partition line created by a node view vector.
- One or more objects may neither be infront nor behind a node. In this event, we will always treat these
nodes as behind based on their distance.
- Only implement methodolgy you NEED in your base classes.
- Trees are generic in type.
- The move operation should not trigger a recreation (or a new tree construction) of your entire tree about the new
- To answer the questions with this project, you may need to implement code that is not required by the
output of the project.
- There are many ways to implement your tree ADT. Choose the most appropriate given the requirements of
the Space Tree.
- Adhere to and live by the K.I.S.S. principle.
- This is not an easy project. Start early!!!
- Good Luck!
Files To Be Submitted
You must use CVS to check out your module in the Proj3 repository and to check in your code.
That must include an ant build.xml file with targets for creating javadoc (named "doc"), for
running your program (named "run" and that allows the command line arguments to be specified
with -Dargs, like this ant -Dargs="arg1 arg2 ..." run), and for compiling your code (this
must be the default target). The build.xml file that comes with your module in the Proj3
repository has all of this. Do not submit or put under CVS control your javadoc output.
We will build it with the "ant doc" command. See the projects page for more information on all of these topics.
If you don't submit a project correctly, you will not get credit for it. Why throw away all
that hard work you did to write the project? Check your submittals. Make sure they work.
Do this before the due date.
Grading and Academic Integrity
Project grading is described in the Project
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for this
Remember, the due date is firm. Submittals made after midnight of the due
date will not be accepted. Do not submit any files after that time.