CS 410 Fall 99
Programming Assignment 3 -- BSP Trees
Due Thursday, November 4

Your assignment is to implement Binary Space Partition (BSP) trees.  This is a data structure used in many 3D gaming applications such as Quake and Doom to handle occlusion when rendering polyhedral objects.  Read the handout on BSP trees for information on how they work.

Getting Started

Unpack the WinZip archive BSP.zip into a new project folder. You will find four Java source files and an executable file solution.exe. Create a new project with the Java source files. The main class is BSP and it is found in BSP.java. Compile and run it. You should see eight colored rotating cubes. You can control the motion of the cubes with the mouse, you can click the mouse to toggle back and forth between solid and skeleton forms, and you can zoom in and out with the arrow keys.

You will notice that in solid mode, something looks very wrong. That is because right now the faces of the cubes are being rendered in a fixed order, not always back-to-front, so some faces that really should be in back appear in front. To fix this, you will need to create a BSP tree that will allow you to render the objects in the correct back-to-front order. Double-click on solution.exe to see what the finished product should look like.

The Files

Here is a description of the four source files. They may contain some Java constructs you have not seen before. You should have copies of them in front of you to refer to as you read this.

BSP.java.  This contains the BSP class and main procedure. The main procedure creates the graphics window, initializes the event handlers that will process mouse and key events in that window, and starts up a separate animation thread to run concurrently with the original thread. The animation thread continuously updates and redraws the image, while the original thread listens for mouse and key events.

The four classes My...Adapter handle the various mouse and key events. MyWindowAdapter shuts the program down when you click on the little box with the X in the upper right corner. MyMouseAdapter intercepts mouse clicks and toggles between solid and skeleton display mode. MyMouseMotionAdapter responds to mouse motions by changing the velocity of rotation. MyKeyAdapter sets the velocity for zooming in response to the arrow keys being pressed or released. The class Animation is the class of the animation thread. The Thread and ...Adapter classes and the ...Listener interfaces are defined in the java.awt library.

Geometry.java. This contains definitions of several useful geometric primitives.

Figure.java. This contains the routines for updating and rendering the image and animation.

BSPTree.java. Right now this file is empty. This is where you should supply your implementation of BSP trees. See the handout on BSP trees for basic information.

What do I have to do?

You should implement BSP trees as described in class and in the handout on BSP trees. All routines for the construction and manipulation of BSP trees should go in the file BSPTree.java. In addition, you will have to change the render routine of the Figure class to make use of BSP trees; you will have to add code to insert newly created Square objects into the BSPTree; and any other code as necessary. You are free to change any code you like; just make sure that if you change anything, you tell us clearly what you did and why.

There are two main routines you will have to provide. One is an insert routine for inserting a newly created Square object into a BSPTree. See the handout on BSP trees for how to do this. You do not have to worry about deletion. You will also need a way of enumerating the elements of the tree in the order determined by a given point representing the position of the viewer. This is also described in the handout.

What are we looking for?

As usual, clean, concise, elegant code.  Lots of comments.  At every step, tell us what you are doing and why.  Get started early!

What do I turn in and how?

Please pass in a printout showing any code that you have changed. In addition, you should submit your project online in the CSUGLab as before in your personal handin directory \\goose\courses\cs410-fall99\proj3\<login-id>, where <login-id> is your CSUGLab login identifier. Please check as soon as possible that this directory exists and that you can save files there. Sorry, no diskettes accepted.

When you are ready to submit, copy all the files in your project directory to your handin directory.  Please copy your entire project, including all executables, .class files, source files, and project (.vjp, .sln) files into your handin directory.

If you are working with a partner, you only need to submit once, and you may submit it in either partner's handin directory.

The deadline for electronic submission is Thursday, November 4, 7pm.   At that time the permissions on the handin directory will change and you will not be able to access it.  You may modify or replace files in your handin directory before the deadline as often as you wish.

Please contact cs410@cs.cornell.edu if you encounter problems.


Thanks to Peter Shirley for suggesting this as a project.