CSE 131 Module 7: Array Structures

Gaussian Elimination

Add a method to your Matrix class to perform Gaussian elimination, as described in this Wikipedia article. Write JUnit tests that use your method to solve systems of equations.

Perspective Projection of a 3D Wireframe Scene

This is more involved than other extensions, so this perspective projection extension counts as two (2) extension credits. It's a challenge, but the directions are specific and success is pleasing.

This extension was prepared for CSE131 when the class had 4 lectures per week. There is no time in class to cover this topic in the current format for CSE131, so you are on your own if you want to undertake this extension.

You will be required to defend your design and implementation to the instructor to receive the credits for this extension.

In this extension, you will implement an application that allows a user to view a perspective projection of a 3D scene from different vantage points by interacting with three sliders that control the viewer's distance from the center of the scene and the viewer's latitude and longitude on an imaginary sphere around the image, where the radius of the sphere is defined by the viewer's distance. When finished, your application will look something like this:

Part I: Components

In order to build any application, it is necessary to fully understand the requirements and then decompose the problem into manageable pieces. Based on the 3D projection algorithm presented in class, we suggest that you include the following components in your design. Since this lab is about system integration, this problem involves quite a few classes. Each class has only a few methods, but you should feel free to implement additional methods and/or classes if you find them helpful. Thorough testing of each component will save you time during integration. All classes should have appropriate toString methods.
1. A Point3D class, similar to your Point class from Lab 4, except that it will have x, y, and z coordinates, which should be of type double in order to support the required mathematics. At a minimum, your Point3D class should have: (1) a constructor that takes as parameters the coordinates of the point, (2) a plus method that adds a Vector3D (see below) to the point in order to return a new Point3D object, (3) a minus method that subtracts another point from this one in order to produce a Vector3D, and (4) a toMatrix method that returns a 4-by-1 matrix, where the rows contain the values x, y, z, and 1. (The Matrix class is described below.)

The last method provides a conversion between two representations of the point in order to simplify multiplying point by a matrix for the perspective projection calculation. Point3D is immutable because it has no mutating methods. So, to avoid creating multiple matrices for the same point, you can create its 4-by-1 matrix once within the Point3D constructor, and return that same matrix each time toMatrix is called.

2. A Vector3D class similar to your Vector class from Lab 4, except that it will have x, y, and z dimensions, which should be of type double in order to support the required mathematics. At a minimum, your Vector3D class should have: (1) a constructor that takes as parameters the three dimensions of the vector, (2) a magnitude method that returns the square root of the sum of the squares of the three dimensions, (3) a scale method that produces a new Vector3D by multiplying all three dimensions by a given double scale factor, and (4) a crossProduct method that takes another Vector3D and returns a new Vector3D that is the cross product of the two vectors. For vectors u = (ux, uy, uz) and v = (vx, vy, vz), the cross product u × v = (uy*vz − uz*vy, uz*vx − ux*vz, ux*vy − uy*vx).

3. A Line3D class with two instance variables (of type Point3D) that represent the two endpoints of a line segment in three-dimensional space. At a minimum, you'll need a constructor that takes the two endpoints as parameters.

4. A Scene class that will be used to represent entire 3D scenes for projection onto a plane for viewing. A Scene object should encapsulate a collection of Line3D objects. (You can use your own linked list, or use LinkedList from the java.util package.) At a minimum, your Scene class should have (1) an add method that adds a given Line3D object to the scene, (2) an iterator method that returns an Iterator over the collection of lines in the scene, and (3) a drawXY method that takes as its parameters a yops.GraphicsPanel and draws the scene on the graphics panel by adding a yops.Line object to the panel for each line in the scene, ignoring the z coordinate. This will have the effect of flattening the scene by projecting it straight down the z-axis.

Optional but recommended: For your convenience in creating scenes, you may want to add methods to your Scene class that support adding lines relative to a "current position," like a 3D etch-a-sketch. To accomplish this, you'll need an instance variable (of type Point3D) to keep track of the current position. Useful methods include (1) a moveTo method that sets the current position to a given point without creating a line, (2) a lineTo method that creates a line from the current position to a destination point, and sets the current position to that destination, (3) a moveBy method that shifts the current position by a given Vector3D without creating a line, and (4) a lineBy method that is the same as moveBy except that it also creates a line from the old to the new current position.

5. A Projector class that will keep track of the current location of the viewer (distance, latitude, and longitude) in order to project a 3D scene onto a 2D plane from that perspective. At a minimum, the Projector class should have (1) a constructor that takes as its parameters the width and height (in pixels) of the desired image after projection, (2) three methods to independently set the distance, latitude, and longitude of the viewer's position, and (3) a project method that takes a Scene as a parameter and returns a new Scene (in which all of the z coordinates are 0) that is a perspective projection of the given scene from the current vantage point of the user.

Design notes: The projector will use the 3D projection algorithm presented in class to obtain a perspective projection of the scene. Internally, the projector will need to keep the four matrices (perspective, scale, rotation, and translation) in instance variables. When the distance, latitude, or longitude of the vantage point are changed, the projector should recompute these matrices as needed. For example, when setLatitude is called, the rotation and translation matrices need to be recomputed since they depend upon the latitude. You'll also want to update the combined matrix PSRT. We recommend creating private methods for recomputing each of those matrices, and for updating PSRT by multiplying them. Also, to simplify the method that projects an entire scene, it's a good idea to write a method that will project a single point. Then you can call that method on each endpoint of each line in the scene.

Mathematics note: Some of matrices in the calculations involve near and far, which correspond to the distances from the viewer to the two planes that "bracket" the scene. You will create a scene using coordinates in the range -1 to 1. Since the viewing distance is measured from (0,0,0) at center of the scence, we can be sure that the scene is bracketed by the near and far planes if we always let near be distance-2 and far be distance+2.

Part II: Integration

After decomposing an application and implementing the pieces, the next step is system integration: putting the pieces together implement the whole application. Some integration occurs naturally when individual components are built. (For example, the Projector class uses several other classes.) Sometimes it's hard to know during integration testing where to place the "blame" when something doesn't work. Therefore, it's a good idea to make sure that each class is tested before it is used by some other class, to minimize the number of problems encountered during integration.

The central "glue" for system integration will be a YOPS tool that creates a scene and accepts user input (through sliders) to update the projected image of that scene. The tool will use the Scene class and the Projector class, which each use various other components you have created.

Open the provided file SceneTool.java. Note that this class includes the main method for your program, so this is the class you will run. Modify SceneTool as follows to complete the integration of your application.

1. Create an instance variable to hold a three-dimensional Scene and another instance variable to hold a Projector that will be used to project that scene.

2. Write a method that creates a scene centered at the origin. To keep things simple, use coordinates in the range -1.0 to 1.0 in all three dimensions (x, y, and z). For example, you might create a "house" consisting of a cube and a triangular roof. (If you implemented the convenience methods in your Scene class, this will save you the trouble of hand-computing the coordinates of each point, since you can just move by a certain amount in a given direction.)

3. In the SceneTool constructor, call your method to initialize the scene. Also, create a Projector object (passing in the width and height of the yops graphics panel) to initialize the other instance variable.

4. Complete the implementations of the methods setDistance, setLatitude and setLongitude. These take as their parameter a slider value from YOPS in the range 0 to 100. Using Math.PI, these methods should call the appropriate method on the projector to provide it values in the following ranges:
• distance should range from 0 to 10.
• longitude should range from -pi to pi.
• latitude should range from -pi/3 to pi/3.
Important: To give the viewer immediate feedback, you should update the display after setting the appropriate value in the projector. Therefore, in each of these methods, call an update method of your tool (described below) so that the scene is redisplayed from the new vantage point each time a slider is adjusted.

5. Write an update method that first clears the graphics panel (GraphicsPanel provides a clear method for this purpose), then uses the projector to project the scene, and finally calls the drawXY method of the resulting scene to display it to the user on the graphics panel.
Test your program to be sure it works as required.
Make an appointment with the instructor to defend and demo your design and implementation.