CS 428 - Fall 2011 Project 4: Ray tracing Due electronically: Wednesday, December 7th, 12 noon Image and scene file due: Tuesday, December 14th, 12 noon Check this page frequently for updates and clarifications (Significant changes or clarifications are marked with [Update])

Description

All of the assignments so far have used OpenGL to render the objects in the scene. Now it's your turn! Ray tracing is capable of producing more interesting lighting effects than a scan-line rendering approach. (Well, it is possible now to implement some of these effects using programmable hardware.) While the lighting model used is very similar to that of OpenGL, the difference comes in the rendering of shadows, reflections, and refractions (as seen in the image above), by using a better model of light transport.

Objective

From this assignment, you will understand how a recursive ray tracer works; from sending out rays through each pixel, to intersecting it with objects in the scene, to recursively sending out more rays. In the end, you'll find that it's just a large number of relatively simple geometric computations.

Program

You will be provided with skeleton code for this program, which supplies the main program structure. There is no graphical user interface -- you specify a scene file, and the program produces an image. Use the program "eog" to view the resulting images.

If you want to work on a Windows PC, you can use a program like pic2pic to convert from PPM files to something you can view (like TIF).

The relatively boring stuff (parsing the scene file, reading and writing image files, computing ray-object intersections, and transformations) has been done for you. You will have to write the main parts of the ray tracer; generating the rays (for each pixel), determining the relevant intersections with the scene, and computing the resulting color of the ray. You will also have to recursively send out additional rays (for shadows, reflections and refractions).

In some cases, you will find code that is a placeholder for what you need to write -- just remove it once you start on that part. In addition, you will probably have to add code elsewhere, and not just where the comment markers are. So don't feel confined by where these comments are placed.

The skeleton code for this project can be found (on the cereal machines) in the directory
      ~decarlo/428/proj4
Also included is a Makefile.

Note that we are not using OpenGL in this assignment.

A description of the scene file format is given in "README.running". Several sample scene files are provided (easy, easytex, hard, hardchecker) in the project directory, as well as their corresponding output in the directory (at 256x256 resolution)
      ~decarlo/428/proj4ex

Handing in

Hand in the following:

1. all of your java files (no class files please)
2. your makefile
3. a description file descrip.txt

1. your scene file
2. a 512x512 PPM image of that scene

Hand in your image in PPM format (this is the format that your program will save it in, so you won't need to do anything here -- please don't convert it to another format). Your scene file should be substantially different from the sample ones provided (which simply are there to help you test your program). Feel free to hand in more than one scene file and image. Keep in mind you might need to let it run for quite a while (a day or more!) to get your image, if you implement a lot of the extra features.

You will need to create a tar archive to hand in, that contains your java files, Makefile, and description:

   tar cf proj4.tar Makefile *.java descrip.txt

This assignment is a bit vague so that you can make a lot of the design decisions yourself. There are several approaches to the problems here. Use your best judgement to try and get the most useful result. Ask for help or clarification when you need it.

Program use

To run the program on a particular scenefile:     java Trace scenefile

A description of the scene file format is provided in the README.running file.

There are a number of command line options available (italicized words indicate you need to specify a particular value):

• -res width height
  The dimensions (in pixels) of the resulting image. The default is 128x128.

• -out image.ppm
  The rendered output of the ray tracer is placed in this file. The default is out.ppm.

• -quiet
  The ray tracer produces no text output when run (unless you print stuff yourself!).

Data structures

The Scene class stores all of the information about a scene (objects, lights, materials, the camera, the matrix stack, some scene parameters, and the image being rendered). Aside from the image, all of this information comes from the scene file. The method Scene.render() is the main loop of the ray tracer, where a ray is cast out for every pixel in the image. An image of type RGBImage is produced.

The elements of the scene are subclasses of the abstract class RaytracerObject, which holds the specification of the scene element as taken from the scene file. Most of the methods in this abstract class are for parsing the scene file (the other classes that handle parsing are Parser, ParamSpec, MatrixStack and, SceneCommand). Note that you can print out objects in the RaytracerObject class---this is useful for debugging.

The following are the scene element classes: Camera, Light, Material and Shape. Each provides a specification of the scene element, along with methods for their manipulation and computation.

Particular shapes are defined as subclasses of Shape, and provide the low-level ray-object intersection routines. There are four types of objects defined: sphere, cylinder, cone and box (in classes Sphere, Cylinder, Cone, and Box). You are welcome to add more of your own (ask us for references for ray-object intersections for a particular object, if you can't find it).

The (matrix) transformations of the Shape are accessible using a number of accessors, which return a Matrix4d object: Shape.getMatrix(), Shape.getInvMatrix(), and Shape.getInvTMatrix() (for M, the inverse of M, and the inverse transpose of M). You'll use these matrices, and the various forms of the Matrix4d.transform method to transform the ray from the world to object space, and the intesection point and normal back to world space. Keep in mind that it affects the result whether you tranform a Point3d or Vector3d (it will add the proper w component of the homogenous coordinate for you when you pass these), so don't just convert back and forth between these indiscriminately.

There are three classes used for geometric computation: Ray (which represents a ray), ISect (which represents an intersection point, and other accompanying information), and Tools (which provide utility routines you will be using to compute reflected and refracted vectors, as well as scale colors).

You should be using the javax.vecmath package for all of your vector and matrix operations. Don't write out the code yourself for the calculations! (You will lose points this time if you do this.) Also, be sure to use Vector3d for vectors and Point3d for points, so your computations are correct.

The classes you will primarily be modifying are Scene, Light, and Camera.

Requirements

The following is a description of what is required to produce a fully-functional recursive ray tracer from the skeleton code. I suggest you proceed in the order they are listed, and test it when suggested (or even more often!).

• Rays are sent out from each pixel in Scene.render() using Camera.pixelRay(), which you must complete. (Be sure to normalize the ray direction for the ray you compute.)

  Writing this program is a good opportunity to learn how to sanity-check your code. Once you finish this part, you should be thinking about how can you test out Camera.pixelRay()? One simple but not exhaustive test (on the scene easy) would be to look at the return value when you pass it the origin: the return value should be a ray where the point is (0,0,-near) (on the near plane) and the direction is (0,0,-1) (looking down negative z-axis, normalized). So you can just temporarily add this line at the top of Scene.render() after the call to camera.setup():
      System.out.println(camera.pixelRay(0,0));
  The default value of near is 1, so you can do a much better test by temporarily adding camera { near=0.5 } at the top of your scene file. (Note this won't change the field-of-view because that is controlled separately! Look at Camera.computeUVN() for details.) Also, this works on easy because of the default values of eye, look and up (there is no camera in the scene file). This is what I meant by this not being exhaustive, and suggests you should probably be thinking about what other tests you can do...

• Determine the first object the ray intersects by completing the method Scene.intersects(), which is called from Scene.castRay(). Recall that current shape contains the relevant transformations for that object. (Be sure that you have normalized the normal vector at the intersection point inside Scene.intersects.)

• At this point, if you run your program on the easy test file, you should see each object drawn in a solid color (using it's k_d value), where the visibility of each object is properly computed in the image.

• Write the method Light.compute() to determine the illumination due to a particular light source at the intersection point. In addition, the diffuse and specular components should be attenuated (as well as use a tinted version of the light source, which the shadow computation will provide later on). Use the Phong model for specular reflection; do not implement the approximation using the halfway vector. Using Tools.reflect() to compute r_i, the reflection of the light direction l_i, around the normal. Then, in Scene.castRay, determine the total illumination of the intersection point by calling Light.compute() for each light. Also, modulate the reflectance by the texture of the material (if any is present). Use the method Tools.termwiseMul3d to multiply two vectors (colors) in a termwise fashion (treating each of the R, G, and B components separately).

  Here is the equation for light i which has intensity L_i and if it's a positional light, the distance between the light and surface point is d_i, r_i is the reflected light direction, and t_i is the tint. The function a(d) models light attenuation for point lights, and is described in section 10.1 of the text (and in a comment at the top of Light.java); it's value is one for a directional light (which are thus not attenuated). The material properties are given by the reflectances k_a, k_d, and k_s, and the texture function T(u), where u are the texture coordinates of that surface point.

  

• Now, easy will now produce a shaded image, instead of solid colors as before. There will be no shadow yet, so you can compare your output to easy-nonrecursive.ppm. Test both point and directional lights by using different test files (easy contains a point light source, hard contains a directional light). easytex contains a test of texturing, which you can apply using Material.getTextureColor() from Light.compute(). You can also test your specular light computation on hard (the objects will have highlights, but obviously won't be transparent or reflective yet; there is a sample output file called hard-nonrecursive.ppm showing this result)

• Next comes shadows: complete Scene.shadowRay() and Scene.shadowTint(). At each intersection, determine which objects are between the intersection point and the light by casting a ray towards the light. This will give you the light tinting value that is passed to Light.compute().
  When computing shadow rays, you should pass false to the all argument of the hit methods, so that it doesn't bother computing all of the information about the intersection point --- you only need to know which object was in the way -- not anything specific. (This is for efficiency only). All other times, you should pass true for this argument.

• Now the sphere in easy will cast a shadow on the flat box below; your output should match easy.ppm.

• The method castRay() is made recursive by computing the reflection and refraction rays at the intersection point, and sending out new rays (and adding their results into the total light at that point, scaling the reflection ray output by k_s and refraction ray by k_t). so the total light for each pixel is: where I_{light i} is the computation for light i given above. For refraction, you may assume that the objects do not spatially overlap (no interpenetration, no containment). This way, a ray is either going into an object from the external scene (which has an index of refraction of 1), or vice versa. Use methods in the Tools class here for the geometric computations.

  With transparent objects, you will also have rays coming from inside an object. This ray should still reflect off (internally) or refract through the surface. But the normal vector at the intersection point returned by Scene.intersects() always points outside the surface. For the refraction computations to proceed correctly, be sure that the normal vector you pass Tools.refract()) is pointing inside for just these rays. What you need to do is simply check if the ray is coming from inside the object (it is if the dot product of the ray direction and the normal vector is positive, and if it is pass in a negated copy of the normal vector. Also keep track of the fact that it has been flipped, as this tells you whether you are traveling into or out of the object---this determines the order of the refraction indices (the last two arguments to Tools.refract()).

  Make sure your reflection and refraction rays are pointing the right way (and that their direction is not backwards). Test them separately using the sample output to check your results (hard-reflectonly.ppm and hard-refractonly.ppm).

  The surface normals in the intersection data structure always point outward. With refraction rays, a ray might hit the surface from the inside. For this ray tracer, we will assume that the appropriate thing to do here is to perform a direct lighting computation, on the inside of the surface. But the surface normal is facing the wrong way. (Remember how OpenGL dealt with this problem using a two-sided lighting model.) Anyway, this means you have to detect situations where this occurs (you can easily do this by examining the dot product of the surface normal and the incoming ray direction), and then negate the surface normal when using it in the lighting computation, so that it points inward. If this step is skipped, then there is only one specularity visible on the transparent sphere for hard-refractonly.ppm, instead of two (the second one is on back of the sphere, on the inside).

• The test file hard contains one shiny and one transparent sphere. Compare your results with the sample output. (You might want to first do reflection, then test, then do refraction).

• That's it!
• Try some of the extensions below (some of them are required for graduate students).
• Now, make a scene file of your own, render it, and hand it in.

Extensions

The following is a list of optional extensions. The first three are required for graduate students.

• [Required for CS grad students]
  Perform anti-aliasing. Modify Scene.render() so that your images are anti-aliased. Shoot out at least four rays per pixel (save the work across pixels if samples are shared). Notice that if you are sharing results that the program proceeds in columns, not rows.

• [Required for CS grad students]
  Instead of the anti-aliasing above, do adaptive supersampling; (trace five rays through each pixel -- at the four corners and the center, and recursively split that pixel into four if there is a large difference between the color of the 5 rays). Add a command line switch called -adaptive that you use to turn this on (it should be off by default).
  
  It's also acceptable to use 4 rays instead of 5, as long as you share the results at the "top" level of the recursion. It's fine to recompute any shared points further into the recursion.

• [Required for CS grad students]
  Distribution ray tracing. This is discussed in the reference below. Implement two of the following:
  • soft shadows (distributing rays over light area). Add something to the light in the file format that allows you to specify the size or shape of each light. It would be sufficient to just add a light radius, and assume spherical lights.
  • diffuse reflections (distributing over reflection direction). Use the shininess to control the degree of reflection scattering.
  • diffuse refractions (distributing over refraction direction). Add something to the material to control the degree of refraction scattering (a translucency amount).

  Consider firing more rays based on how much spread there is in the distribution; that way, you don't slow down your program too much for the easy cases. For instance, when the shininess value is very high, you will need fewer rays. Come up with a heuristic which produces reasonable results, letting the easier cases (i.e. almost perfect reflections) go faster than harder ones (very blurry reflections). One effective algorithm computes an online measure of variance in the ray colors, and stops firing rays in situations where the colors don't vary as much (assuming enough rays have been fired to get a good estimate of the variance). (If you don't understand what this paragraph means, either ask about it, or skip it.)
  
  You must add a command line switch "-distrib D" that you use to turn this on (it should be off by default). The value of D is a multiplier that says how many rays are fired at each interaction. When D is zero, your code should reduce to a normal recursive ray tracer (with perfect reflections, etc.). If you take the ceiling of D times the number of rays your model uses, then for very tiny values (say, D = 0.001), it will fire one random ray at each interaction. This means your ray tracer won't be significantly slower, but you can still see what the effects will be (approximately, although they'll be noisy). Set it up so that on average, D rays will be fired at each interaction, although this will be modulated by the heuristics you have in place above to use more rays for the harder cases.

  Reference: Cook, Porter, Carpenter, "Distributed ray tracing", SIGGRAPH '84, pp. 137-145.
  [PDF]
  
  Here are examples:

  Backward ray tracing (with adaptive supersampling) CPU time = 10 sec @ 256x256	Distribution ray tracing with penumbra, glossy reflections/refractions (no adaptive supersampling) CPU time = 40 sec @ 256x256	Distribution ray tracing (with adaptive supersampling) CPU time = 16.6 min @ 256x256 CPU time = 48.2 min @ 512x512

  Note: This scene is an altered version of hardchecker where the light has radius 4, for the glass sphere, Ks=0.3, shiny=200, translucency=200, and for the mirrored sphere, shiny=50.

• [Easy] Bump mapping. Make your surfaces appear bumpy using images (section 10-18 in the text). You'll need to add a field to the material in the scene file to specify the bump mapping file (just like the "texture" field). Make a bump image (use "gimp" or Photoshop in the ARC computer lab, perhaps).

• [Easy] Implement some simple procedural textures (like the built-in "checker" texture; where you specify two colors, as well as the u and v repeats). Take note how the "checker" command was implemented in Material.

• [Medium] Solid noise textures (marble). Add something to the material to specify the presence and parameters of the texture. Again, take note how the "texture" command was implemented in Material.

• [Hard] Constructive solid geometry (CSG). Build composite shapes from the provided primitives using Union, Intersection, and Difference operations. These objects should have the correct transparent, refractive and shadow casting behavior (as the other primitives do). You will need to use the hierarchical object aspect of the scene file, and to allow for the specification a particular CSG operation, as well as create a new CSG "container" object. You might want to ask about this before starting. Here are some readings:

  Reference: excerpt from Hanrahan, "A Survey of Ray-Surface Intersection Algorithms", in "An Introduction to Ray Tracing", Glassner ed.
  [PDF]

• [Easy to Medium] Write a short program that will generate an interesting scene. Don't make it too complicated, though, so that you have a chance for your scene to render in a reasonable amount of time! Hand in your program as well as the scene file (this can count as your handed-in scene file).
  Here's a simple example: Sphere tree
  (the code to generate the scene file for this image was 30 lines long, and took a few minutes to write)

• [Medium to Hard] Speed up your ray tracer with hierarchical bounding volumes. Use the hierarchy of objects (not necessary with disjoint children) and bounding volume at each internal tree node which contains all of its children). It's ok (or even preferable) if you specify the hierarchy in the file using up/down instead of computing one. Again, you might want to ask us about the details before starting.

• [Easy to Medium] Use ChromaDepth to make your pictures 3D (you'll need special glasses -- ask me for a pair if you want to try this).

  Reference: Bailey and Clark, "Using ChromaDepth to Obtain Inexpensive Single-image Stereovision for Scientific Visualization", Journal of Graphics Tools 3(3) 1998, pp. 1-9.
  [PDF]

  Note that this paper describes how to do it in OpenGL, you'll find it easy to translate this to ray tracing. Be sure to use the full extent of the color range (tailored to your scene) for the most substantial depth percepts. You should look at the RGBimage class (specifically the setPixel and adjustColor methods) so you get this part right.

  Can you get the depth of image content seen in reflections and refractions to appear at the correct depth? (I'm quite sure this bit isn't too difficult, but haven't actually tried it!)

• Feel free to add additional features other than those listed here.

Hints

The following are some suggestions...

• Test this program a little at a time, so you have a chance at finding bugs. Don't write the whole thing and expect it to work on the first try. Also, when debugging, consider disabling certain features (such as recursive rays) as a means to isolate the cause of a bug.
• Ray tracing is slow. Consider turning down the recursion level (or making other simplifications) while testing your program so you don't have to wait so long to see the result of your latest coding efforts. Lower resolution images are faster too!
• Test reflection and refraction separately, as it's too hard to figure out what bugs you might have with both are on.
• Images use up your quota, but you should have enough. Ask for more if you need to (be sure to say you're in CS 428). Corrupted image files (that eog can't read) can be caused by you being over quota. Type "quota -v" to check your quota.
• "Stack overflow" probably means that you have an unbounded recursion.
• If you can't log in, you might be over quota (use the 'Failsafe session' at the log in screen, and you will be able to log in to remove some files; or just telnet in from some other machine, like remus).
• The output images are gamma converted (contrast is raised) so the are properly displayed on the monitors in the lab. Look at RGBimage.adjustColor if you're curious how it works.
• The assignment is difficult; if you're stuck, ask for help! Don't waste hours of your time trying to find some strange bug. Go get a beer or something. Or ice cream. Or maybe just do your homework for another class!