CSE131 Module 7: Array Structures

Goals

Goals: By the end of this lab, you should...


Practice Problems

Expect exercises like these on the quiz. There will be a help session covering these exercises on Wednesday at 10:00am in the Steinberg 105 lecture hall. You will benefit most by doing the exercises before you look at the solutions or attend the Wednesday help session when they will be discussed.

  1. Write a method that takes as its parameter an array of integers and returns the sum of the values in the array.
  2. Write a method that takes as its parameter an array of integers and returns the minimum of the values in the array. (Assume the length of the array is greater than zero.)
  3. Write a method that takes as its parameters two arrays of integers and returns the dot product of the two (i.e., the sum of the products of the corresponding elements). Assume the two arrays have the same length.
  4. Write a method that takes as its parameter an array a of integers and returns a new array of the same length, where each entry is the corresponding value in a multiplied by its index in the array.
  5. Write a method that takes as its parameters two arrays of integers and returns a new array where the value at each index is the sum of the corresponding two elements of the given arrays at the same index. Assume the arrays are of equal length.
  6. Write a method that takes as its parameters two arrays of integers and returns a new array where the value at each index is the sum of the corresponding two elements of the given arrays at the same index. Do not assume the arrays are of equal length. Pretend that the shorter array is padded with zeros at the end. (For example, if the arrays are of length 3 and 5, your result should be as if the shorter array had zeros in the "missing" slots.)
  7. Write a method that takes as its parameter an array a of integers and modifies the given array so that it contains a running sum of its original values. For example, if the array originally had the values [3 2 4 7], after running your method that array would instead contain [3 5 9 16], and if you ran it another time on the same array, you'd have [3 8 17 33].
  8. Write a method that takes as its parameter an "two dimensional?" array a of integers and fills the main diagonal with the value 1. (The main diagonal consists of those entries whose row and column index are equal.) Assume the two dimentional array is square.
  9. Write a method that takes an integer parameter n. It should create and return an array of n arrays of integers, where the array for row 0 has length 0, the array for row 1 has length 1, the array for row 2 has length 2, etc. All values in the arrays can remain uninitialized (0).
  10. Write a method that takes an array of String objects and returns a single String that results from concatenating all the strings together, separated by spaces. Do not add a space after the last element, nor before the first one.


Downloads

Download lab7.zip and import it into your CSE131 project in Eclipse.


Project: Matrix

Implement a Matrix class with the following features. Write JUnit tests to thoroughly test all of your methods. To create a JUnit test for a class in Eclipse, right click on the file name "Matrix.java" in the package explorer, and select "JUnit test case" under "new."
  1. A constructor that takes a two-dimensional array of type double and saves it as the values of the matrix.

  2. A toString method that neatly shows the contents of the matrix. In your string use "\n" to insert a line break, and use "\t" where you want a tab between elements. Include JUnit tests that print these strings to the console (using System.out.println) for visual inspection, in addition to any automated tests you perform. Your toString method will come in handy for debugging the other methods.

  3. A scaleRow method that takes a row number (an integer) and a scale factor (a double), and multiplies that row by the given scale factor. This method does not return anything. It just modifies the matrix.

  4. An addRows method that takes two row numbers as parameters, and adds the two rows together, storing the result in place of the second of the two rows.

  5. A plus method that takes another Matrix as its parameter and returns the matrix that results from adding this matrix by the given one. Matrix addition is only valid when the two matrices are the same size in both dimensions, so your plus method should throw an IllegalArgumentException when this is not the case.

  6. A transpose method that takes no parameters and returns a new matrix that is the transpose of this one. Recall that the columns of the transposed matrix have the same values as the rows of the original matrix.

  7. A times method that takes another Matrix as its parameter and returns the matrix that results from multiplying this matrix by the given one. Recall that when you multiply two matrices A and B, the value in the cell at row r and column c of the resulting matrix is the dot product of A's row r with B's column c. Also recall that matrix multiplication is only valid when the number of columns of the first matrix is equal to the number of rows of the second, so your times method should throw an IllegalArgumentException when this is not the case.


Optional Extension 1: 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.


Optional Extension 2: 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.

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


What To Turn In:

Follow these submission instructions to turn in the following files. You will need to do a demo for a TA only if you complete the perspective projection extension.

  1. cover-page.txt -- Be sure to fill in all information.
  2. Matrix.java
  3. MatrixTest.java
  4. For optional extension 2, also turn in the following Java files: Point3D, Vector3D, Line3D, Scene, Projector, and SceneTool.
Reminder: All code you turn in should conform to the CSE131 Style Guide. Full credit will be given only if your work is well organized, clear, readable, and properly documented.
Kenneth J. Goldman (kjg@cs.wustl.edu)