This assignment will have you completeing your chosen path. These assignments will be due at midnight on the 16th of December. Obviously you can turn it in at any time before that.
Data Structures - If you have been doing the data structures option then for this assignment you will write some more advanced graph algorithms using the graph code that you did for assignment #8.
Text Game - If you have chosen the text game, this assignment is basically to have you make it so that it is somewhat playable. To do that you will add stuff to interact with. These could be items or other characters. Remember, all the data for these things will be included in the XML file. So for example, if you can talk to other characters, dialog trees could be put in the XML file. If you are just picking up items, the descriptions of those items and an encoding of what they let the player do should be in the XML file as well.
Note that your game will be truly like the old style text games where if the player doesn't do anything, the game doesn't do anything. This definitely isn't real-time. Instead, you should make it so that when the player enters a command, all the other parts of the game that need to do something (might not be many) also do what they are supposed to.
Physics - For this assignment you will extend your basic "integrator" from assignment #9 with the octree being used to optimize the interactions. This style of doing numerical integration is called a tree code and was originally developed by Barnes and Hut in the early 1980s. Normal gravitational algorithms require O(n^2) time because each particle interacts with every other particle. A tree code scales as O(n log n) because particles don't interact directly with distant particles, instead they interact with groups of distant particles.
You will probably want to read your particles into a list and keep the "real" particles in the list. Just use the tree for force calculations. The other advantage of this is that you can use the list to calculate the bounds on your octree. To do this you need a minimum and maximum value in x, y, and z. Make the tree center on the point between the min and max for each dimension and make the size of the root the largest difference of the three.
To make this work, you will expand your octree so that each internal node stores the center of mass and total mass for all the particles below that node in the tree. You can just fill these with zeros while you are adding particles. After the whole tree has been built, you will do another pass through that can set these values based on the values of the children. That's faster than calculating them with every particle that is added.
A critical parameter for an octree integrator is the "opening angle", theta. When you calculate how much force there is on a particle, you traverse the tree. If the size of a node divided by the distance from the particle to the node is less than theta, then you treat that node as one big particle at the center of mass location. If it isn't smaller, then you recurse into all of the children. When you get to a leaf node with a particle you always do a direct forcing.
The functions you need for this are the same ones you had for assignment #9: read, write, writePlot, and advance. The only change is that advance takes the system, a dt, and a theta value. Theta values typically range from about 0.1 to 0.3. Larger values make it run faster, but are less accurate. If you followed the advice for assignment #9 and broke up the collision and force applying code, all you will be changing other than adding theta to the parameter list in advance is to have the force calculation use the octree instead of direct force calculations.
Here is an xml file that has a central star and a bunch of "fluffy" protoplanets in orbit around it. If you run the system for very long you should get a number of mergers in the system. You can also use this C++ program to create new files. Just give it the number of particles you want in orbit around the "Sun". This can be helpful for creating a slightly smaller input file to start working with. The program takes one command line argument for the number of particles to put around the central body.
Ray Tracing - You will combine the efforts of your last two assignments to make a full, optimized ray tracing code. To do this, you will enhance your octree, add lights, and calculate colors then write out the raster. This will have you alter the octree that you wrote, and also use the functions you wrote to see if a ray intersects a triangle or a sphere.
A critical factor in optimizing the ray tracing is the idea of bounding spheres. We use bounding spheres to allow us to quickly reject groups of objects from things like tests for collisions. In this case, the idea is that if a ray doesn't intersect with a sphere, it can't intersect with any items inside of that sphere. So you will need functions that find the bounding sphere of a geometry element as well as the bounding sphere for two spheres.
The first function, calcBSphere geom, will return a bounding sphere with teh same center and radius as the geometry if the geometry is a sphere. If it is a triangle, just return a sphere whose center is at the average position of the three points and whose radius is equal to the largest distance from the center point to any of the points on the triangle. That's not an optimal bounding sphere, but it will work well enough for these purposes.
The second function, sharedBSphere sphere1 sphere2, will first check if one sphere and completely inside the other and if so, return the larger sphere. If that isn't the case, it returns a new sphere whose center is on the line connecting the two sphere centers that touches both spheres on the outer edges. To see how to do this, assume the sphere centers are c1=(x1,y1,z1) and c2=(x2,y2,z2) with radii r1 and r2. Let the vector sep=c1-c2 normalized and d=distance(c1,c2). Then the new center and radius, c3 and r3, are given by the following. r3=(d+r1+r2)/2.0. c3=(c1-r1*sep)+(r3*sep)=c1+(r3-r1)*sep.
After you have those functions, the next step is to enhance your octree so that you can use it to optimize the ray tracing. There are two steps to this. First, each node in the octree will now store a list of geometry instead of just points and each node will keep track of the bounding sphere of all geometry below it. We will also change up the tree a bit. Instead of having one point per leaf, geometry elements will go into the smallest node that holds the center of the objects bounding sphere, and where the size of the node is at least twice the bounding sphere's radius. So there is no difference between internal nodes and leaf nodes. All can hold geometry and can even hold more than one geometry object. The object won't always truly fit in the node, but that's ok because after you build the tree by placing all the objects in it, you will then do another pass to calculate the mutual bounding spheres of all geometry objects in or below each node and store the mutual bounding spheres in the nodes. To get this you call sharedBSphere on all the chilrden's bounding spheres as well as all the contents bounding spheres. This work bascially has you modifying the datatype for your octree, the add function for you octree, and then putting in a finalizeTree function that does the bounding sphere work.
So now you have an octree that keeps track of the bounding spheres of all objects below any given node, but you still need some more features to do an actual rendering. A simple one is that you will store a list of lights for the scene. Each light is a point that also has a color for it. Colors will be a 3-tuple of reals for red, green, and blue. Each value will normally be between 0.0 and 1.0 for black to full saturated in that color. Your geometry objects will also have colors and reflectivities associated with them. That part is just modifying your datatypes and code to read them in from an XML file. Look at the file linked to below to see an example of a geometry file with all this information.
To render the scene, you will use a function called calcColor that takes a ray, an octree, and a list of lights and returns a tuple of the color you should see along that ray. The way this function works is that it uses the octree to efficiently find the first object the ray hits. Remembering the location it hit as well as the normal there, and the color there, it then sends rays from that point to each of the lights in the list using the octree. If that ray hits something, it means that point is shadowed from that light and that light doesn't contribute color. If the ray doesn't hit something, that light contributes a color or (dotProduct normal (normalize vectorToLight))*surfaceColor*lightColor/(square (distance intersectPoint light)). This is done for each of red, green, and blue. If the surface the original ray hit has no reflectivity, this value, summed over all lights, is what is returned. If the surface has a reflectivity, then we take this value for color and add into it the reflectivity times the color of the reflected ray. To get the reflected ray, just take the incoming ray and add to it, 2*(dotProduct normal (normalized incomingRay))*normal. So reflection is just as easy as recursively calling calcColor.
The last step is to write a function that calls calcColor many times for all the rays that would go from the "eye" through each pixel in a raster and write out the pixel colors to a file. The XML file will give you the location of the eye as well as a description of the raster location in 3-space. The file you should output should start with one line that is the size of the raster in pixels in x and y then have 6 characters per pixel after that until the end of the file. Each pixel is represented by a hex RGB value, like in HTML. The first two characters are the hex for red with a value between 00 and ff (0 and 255). The next two are for green and the last two are for blue. Don't put any white spaces between the pixels. The function that does this should be called render and it should take a filename for the geometry file, a filename for the raster output file, and the size of the raster in x and y. (render inputFileName outputFileName sizex sizey) This is really the only function people will call from the top level because it reads in the geometry file, builds the tree and list of lights, then casts all the rays and writes the raster to the proper file.
Once you have written a raster, you can view it with the following JAR file. Just save the jar file where you put your raster text file and type in java -cp RasterViewer.jar RasterViewer fileName. This should bring up a window displaying your rendering and allow you to save it as a PNG file.
Here is a sample XML file that you can use as input for your program to test it and also to see what the format of the XML file should be. You can obviously create your own XML files by hand or using any tool you want. I have a C program that will create some simple geometries here. Is you use this, don't worry about putting in alpha values unless you want to put transparency into your program.
XSLT Processor - This is the next option in the advanced XML. XSLT is an XML based technology that does style sheet transformations on XML data files. What you will do for the assignment is to write your own XSLT transformer. This will read in two XML files, a data file and a style sheet file. It will apply the style sheet transformations to the original XML file to produce a new XML document that you can then write out to file.
Here is a link to a page describing XSLT. If you are going to attempt this option you must read this or some other reference on XSLT. Note that you do not have to be able to create a fully functional XSLT program. Just something that works for some basic XML data sets.