CSCI 1320 - Assignment #10

This is the final assignment of the semester. There is no real theme to what you have to do for it. It will just exercise a fair bit of what you have learned in this class and hopefully be interesting to program. While this assignment is listed as due on the last day of classes, if you choose to you can turn it in as late as the 15th and get full credit.

Speed Test Problem:

If you did the earlier speed test code then you might find this interesting. Keep the code you had before for comparison, but now also write quick sort or merge sort and run the same tests with them. Once again, you will do it with both ints and with the large structures as well as with 100, 1000, 10000, and 100000 elements in your arrays. For a full description refer back to assignment #9. For this one though I'm going to require that you plot up the data for at least one of the slow sorts and one of the fast sorts. You can do this quite easily with Excel. Then, for fun, add a trendline and see what can give you the best fit. You are unlikely to find n*log(n), but you should see that n*n is a very poor fit for the faster sort.

Graphics Problem:

This is the assignment I've been waiting for with the graphics path. In this assignment you will use your lighting calculations and your raster to help you make a ray tracer. In order to do this, there is at least one other significant function that you have to write. That function is one that tests if a ray in 3-space intersects with a triangle. For fun (and extra credit) you might also write functions that work with spheres because they will look cool. The only problem with doing this is that there is a decent bit of math involved. I'm going to try to explain the method you should use and pick one that largely utilizes the functions you have already written.

The general method goes like this. For each point in your raster you will "send out a ray" and see what, if anything it runs into. The closest thing it runs into is what you would see. From the point where it hits you will send out rays towards each light source. If there is something between the light source and the point then it is in shadow and that light doesn't illuminate that part of the surface so the pixel doesn't get any light from that point. You check all the lights that way and add up the ones that aren't blocked. The way you add it up is similar to what you did in assignment #7/8, but now the point you are using isn't one of the corners, but where your original ray hit the surface.

Because the method of finding intersections is best expressed with vector notation, I'm giving you a PDF file that describes that method. I recommend that you write a function that takes as input the ray data as two points, a start point and another point on the ray and the geometry data. It will return the point on the closest surface intersected, the normal at that point, and the color of that surface. You will also want a function that specifically tells you if a given ray intersects one particular triangle (or sphere), the point where it does, and maybe the normal (though you can find that in the calling function). You might find it helpful to have a triangle structure that stores not only the three points and color, but also the normal vector just to speed things up a bit.

Your program should take one command line argument, the name of the geometry file, and should write a file called raster.txt that has the image. The raster format is the same as before and should be viewable with the Java program you were given with assignment #7/8. For the geometry file, you can take either format, but if your program is executed without a file name it should say what format is expected. If you make your program handle spheres, the number of spheres and data for them should follow the triangles in the format where you give numbers of each. In the other format, lines that begin with an S will be spheres. If you don't handle spheres then just ignore those parts of the input or read them and throw it away.

Keep in mind that you can use a larger raster if you want to make nicer images and certainly try to view your raster with my viewer before turning it in. Your output doesn't have to match mine exactly, but it should look similar. You will be passing around some fairly large amounts of data. Consider using structures to keep track of some of those things.

For more extra credit (and a really cool effect) try to add reflection in. If you only have "perfect" reflection, then when your first ray hits a reflective surface, you find the new ray it would be reflected to, and display whatever that would draw. Basically, you will be doing the rendering recursively. You can think about how you might do other things like making surfaces partially transparent or partially reflective as well. You could also add ambient light though I wouldn't worry about diffuse reflection because that can be a bit too much of a pain.

For help with the executable, just type the executable name and no arguments. My executable does a number of other things that can help you, such as giving you some nice functionality for building geometries. I highly recommend that if you pick this option you download that file and play with it some before beginning and use it to help you make better inputs. Most of the options for building your geometries are straight forward. My tool asks for alpha values and reflectivities for just about everyting. You can ignore these if you don't do that. If you want to do that, I store the values in the top byte of the packed rgb so you should talk to me about how to get those out for your rendering. Three of the options are things you might not understand. Option 4 constructs a very simple fractal "terrain". It does this by doing midpoint displacements on a triangle. You have to give it the bounding triangle and an original offset. The offset should be a fairly small faction of the edge length. You also tell it how many levels to go down. Don't go higher than 5. The sheet option lets you enter four points and a surface is drawn with straight edges for those point. You tell it how many subregions to break it into and if you want it to be checkered. If it is checkered you will give it two colors for the checkering. Lastly, there is an option to add a "cylinder". This is actually a prism that approximates one. You pick the center spots for the top and bottom faces and one point on the top rim then tell it how many points to use around the rims. Using 4 would give you a cube type of shape.

Also, I have put up a new JAR file with a RasterViewer that will let you save the images you make as JPG or PNG files so you can do more with them. The use is the same as for assignment #7/8.

geometry file : raster file : executable : geometry file 2 : geometry file 3

For this you will extend what you have done in the previous assignments in a few ways. First, you will add the ability to have multiple sections so you will want a section structure that holds an array of students. Second, you will make a menu option so that the user can add a section and another so they can select which section to be working with. Third, the save and load features need to save and load all the sections. You can do this by writing the number of sections first, followed by each section and each section can be written exactly the way you were writing one section for the previous assignments. A user needs to create a section before doing anything else. Sections should be named with strings. How you store the sections is up to you. A linked list might be ideal, but you can assume that there won't be more than 10 sections so a fixed array will also work.

Your new menu should look like this.

Add section
Select section
Add student name
Enter a grade for everyone in the current section for an assignment, quiz, test, or class participation
Enter a single grade for one student
Prints grades and average for one student
Print section average and standard deviation for any grade
Write gradebook to a file
Read gradebook from a file
Print whole class (like in assignment #9)
Sort section by student name
Sort section bt student average
Quit

input file : output file : executable

Chemistry Problem:

This will start with the code for the chemistry problem in assignment #5 and use it to actually balance the chemical formula that was typed in. The input of the problem will look the same as before and the process starts the same as well. You find the formulas for each of the elements that relate the coefficients of the terms in the chemical formula. The extra step added here is that you will solve for those coefficients so that you could produce a balanced equation.

Basically you are solving a system of linear equations. The problem here is that the system is basically always underspecified. That means that there are more terms with coefficients for you to solve for than there are elements producing equations. We can get around this problem fairly easily though. The route that we will use to solve this problem is to do Gaussian elimination on the matrix that gives the number of each type of element. To understand how this is done, let's look at the math a bit.

Basically, what you are doing is solving the equation Ax=0. Here A is a matrix of the coefficients that you found where the things on the right hand side have been made negative. x is the vector of coefficients [a, b, c, ...]. The standard formula used to represent systems of linear equations in Ax=y, but in this case y happens to be a vector of zeros. In order for this to be solved normally, A needs to be a square matrix. In your problem it generally isn't because normally there are more terms than there are elements in them. If there are more elements than terms the system is overspecified and you can just say that without trying to solve it. More likely the system is underspecified which means that there are an infinite number of solutions. However, you only have to find one.

For this you will populate the A matrix with double values that are the coefficients you got from the previous assignment. So the first column is all the coefficients on the first term for each element and so forth. You will do Gaussian elimination until you run out of elements (which is likely to happen before you run out of terms). The objective of Gaussian elimination is to turn A into a triangular matrix. Once you have that, solving the system is very straightforward. This is what you always do given a system of linear equations, you steadily subtract equations to remove variables until you get down to one variable. Then you solve that one and begin placing solved values back into the earlier equations until you have solved for all the variable. Gaussian elimination is just a formal method of doing this. Instead of trying to describe it here I will say you should come talk to me for a description of how to do it. The main trick here is that you will assume the terms above the number of elements have values of 1 in the x vector.

After you have done the Gaussian elimination you will have solved this you can simply print out the coefficients.

For extra credit you could have it deal with over specified systems, or you can try to get it to turn the final answers into minimal integer values since that is what people normally want for this..