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.

• A TwoDPoint is a 2D point representing a point on the view plane. For rendering, 3D objects must be projected onto the view plane.
• A ThreeDPoint represents a point or vector in 3D Euclidean space consisting of x, y, and z coordinates. Routines are provided for vector addition and subtraction, inner (dot) product, length of a vector, cosine of the angle between two vectors, and projecting a 3D point onto the 2D view plane with respect to a given viewer position and orientation.
• A Matrix is a 3x3 matrix representing a linear transformation on 3-dimensional space. The three rows are denoted x, y, and z. Each row is a ThreeDPoint. There are routines provided for matrix-vector multiplication, matrix-matrix multiplication, and transpose. All 3D linear transformations we will encounter will be orthonormal rotations about the origin. Orthonormal means rigid angle- and length-preserving. The matrix representing such a transformation has determinant 1 and its rows are vectors of length 1 and are orthogonal (perpendicular) to each other. For such matrices, the transpose is the inverse. The rotation of the cubes is governed by such a transformation.
• A Square is a 2D square embedded in 3D space. It has four corners, a center, and a normal vector perpendicular to the square. It also has a color. A project operation is provided that projects the square onto the 2D view plane according to the viewer's position and orientation. It produces a Polygon object, defined in java.awt, for displaying on the screen. The square is embedded in an infinite 2D plane; the behind routine determines which side of this plane a given point occupies.
• A Cube consists of six Squares, called its faces. It has a color. All its faces are the same color.

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

• The constructor initializes the window and image buffers.
• The orientation matrix is initialized to the identity. This is the matrix that determines the current position and orientation of the viewer and light source relative to the cubes. The routines viewerPosition and lightSource calculate these positions and orientations.
• The routine render draws all the squares comprising all the faces of the cubes. Right now it just draws them in some fixed order of no particular significance, so the occlusion is incorrect. The variable intensity is a brightness factor that determines how bright the color of the face is. It is proportional to the cosine of the angle of the light source; the more perpendicular, the brighter the face. The subroutine scaleColor is used to calculate the color scaled by the intensity factor. Instead of being drawn directly on the screen, the squares are rendered to an off-screen buffer; when the rendering is complete, the buffer is dumped to the screen. This strategy avoids flicker.
• The routine animate continuously updates the orientation matrix by composing it with an increment determined by the current velocity of rotation.  It also updates the distance of the viewer from the cubes by including increment of zoom determined by the current zoom velocity.  Finally, it calls render to render the new image.

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.

Acknowledgement

Thanks to Peter Shirley for suggesting this as a project.