Overview

The program should be written in either C++ or Java.  You should not use any platform-specific libraries. Assume that it will be compiled with g++ or javac on the department's undergrad network of Suns.

You should take a look at Paul Heckbert's “Writing a Ray Tracer,” which is Chapter 7 of Glassner's An Introduction to Ray Tracing, on reserve at MSE. Pay special attention to section 3, and try not to be overwhelmed by the number of possible options and optimizations for a ray tracer.  You do not have to do things exactly as presented in the article of course; it’s just a model in case that is useful.

Design your program in an object-oriented fashion from the start - we will be making extensions to this program in future assignments (future assignments will include recursive ray tracing and more primitive types). You should have simple classes for vectors, rays, images, and rendering primitives (sphere is child class) as a minimum. Do not get too carried away using all possible language features. Just keep it simple. Note that the vector class is important. I don’t want to see you doing your vector computations one component at a time, which leads to more code, more bugs, and more difficult reading for your instructor. Be safe – use vector addition, subtraction, dot product, cross product, scaling, and normalization functions (inline, if you care about speed).

Program Description

The executable should be called `raycast` and should be callable with the simple command:

raycast <scene description filename> <image output filename>

Included with this homework assignment is a sample set you can used to compare with your own program. The sample set includes a simple scene description, corresponding rendered image, and even test program binaries compiled for sunos and pc_linux. You should test your program on the simple scene file as well as many other test cases you devise to ensure that your program functions properly in all tricky circumstances. The test cases you design should each test some simple aspect of the program for which you have a clear expectation of what the result should look like (so you know if the results are correct). Design enough of these so that you are sure you've covered all the possibilities. See how your test cases compare to your expectations and to my test program (the test program is a bit of a crutch, so try first to develop your own intuition and understanding of what is correct). I will be testing your programs with some of my own test cases.

Place some lights and spheres in a creative and interesting arrangement to create an image at 256x256 resolution. Some of your images may eventually placed in an image gallery (some of the images at this site are from this assignment, some are from future assignments) for this class.

You do not need to perform speed optimizations.

Suggested Approach

1. Start early. I have given you enough time for this assignment, but it will take you the entire time. Starting early will give you time to ask me questions about those crucial details that you didn’t even realize existed until you tried to write the program. Remember, extensions are limited to 2 days, and will cost you significant points. You should be generating some sphere images without illumination by the end of the first week to ensure timely completion.
2. Start with image class and writing ppm files. Test with simply created images like solid color, checkerboard, etc. Make sure you understand your image coordinate system (so you are not writing files upside down or backwards).
3. Write file parser, and necessary data structures for storing information.
4. Write main loop to generate eye rays for entire image. (As a handy debugging trick, you can scale/bias your ray direction’s x, y, and z components and store into r, g, and b of an image. Viewing the image and examining particular values can help you verify that your eye rays are correct. Storing intermediate values as colors like this is a often useful way to debug your program's operation on an entire image at once.)
5. Write sphere intersection routines and use with eye rays. Set the image pixel colors to the sphere's diffuse color. Don’t do any illumination. Your image should thus contain solid-colored ellipses indicating which spheres are visible at each pixel. Run on my test scene and compare images.
6. Add purely local Phong illumination computation.
7. Add shadow rays to determine which lights contribute to each pixel’s illumination.
8. Come up with your own test cases and debug.
9. Design extremely cool demonstration image.

Deliverables

• well-commented source code (I actually read the comments and code)
• instructions for compiling (running should work as specified above)
• one or more interesting scene files and rendered images (with .rt1 and .tif extensions, respectively)
• brief description of each scene (this can be comments at the start of the scene file)

Grading

(05) Style / organization
(05) File input
(05) Image output
(10) Eye ray computation
(10) Sphere intersection/rasterization
(10) Warn light / shading
(10) Shadows
(05) Demonstration scene

PPM Format (extension .ppm)

P3

xres yres

255

r g b r g b r g b r g b

r g b r g b r g b r g b

…

P3 is a magic number that identifies the file type. xres and yres are integers specifying the image resolution. 255 is the maximum color value. r, g, and b are the color values of the pixels. They are each an integer in the range [0, 255]. You can place carriage returns wherever you like in the list of pixel values. Comment lines starting with # are also allowed in the ASCII format.

The binary format is almost the same, except the magic number is P6 and the rgb values in the file are written out as byte values instead of ASCII strings (comments, spaces, etc. are not allowed in this portion of the file).

You should probably start with the ASCII version to test things out, then convert to the binary version, which occupies several times less space.

Scene Description Format (extension .rt1 – that’s a number 1)

# comment lines start with # and may appear anywhere

RESOLUTION: [x resolution] [y resolution]

FIELD_OF_VIEW: <full x field-of-view>

BACKGROUND: <red> <green> <blue>

NUM_LIGHTS: [number of lights]

LIGHT

 POSITION: <x> <y> <z>

 DIRECTION: <x> <y> <z>

 INTENSITY: <red> <green> <blue>

 EXPONENT: <exponent>

 CUTOFF: <angle>

ENDLIGHT

LIGHT

…

ENDLIGHT

LIGHT

…

ENDLIGHT

…

#in other words, one LIGHT…ENDLIGHT block for each light

NUM_SPHERES: <number of spheres>

#similarly, one SPHERE…ENDSPHERE block for each sphere

SPHERE

 CENTER: <x> <y> <z>

 RADIUS: <radius>

 DIFFUSE_COLOR: <red> <green> <blue>

 DIFFUSE_COEFFICIENT: <coefficient>

 SPECULAR_COLOR: <red> <green> <blue>

 SPECULAR_COEFFICIENT: <coefficient>

 SPECULAR_EXPONENT: <exponent>

ENDSPHERE

SPHERE

…

ENDSPHERE

SPHERE

…

ENDSPHERE

…

I have made this format as simple as possible to parse, with little room for variation except white space and number of lights, spheres, etc. You can write your parser by hand or use lex/yacc to generate a parser. If you use lex/yacc, do include the properly-generated .c and .h files with your program source as well as the original lex and yacc input files.

One way you can implement some pretty simple parsing is as follows. Open the file with fopen(). Write a simple procedure to get each line of input. This procedure can include a loop using fgets() to read a line and then test to see if it's all blank or a comment. Return the first non-blank, non-comment line. Use sscanf() to get the useful data out of the input line. sscanf() works in the presence of white space and allows you to check that the expected number of tokens were read.

Sphere Mathematics Refresher

     (X-C).(X-C) - r^2 = 0

Here, X is a point on the sphere, C is the center, and r is the radius. The equation for the ray is:

     X = P + t*V

P is the start of the ray and V is the direction. Substituting this formua for X in the implicit equation yields:

     (P+tV-C).(P+tV-C) - r^2 = 0

Regrouping the terms by powers of t yields:

     (V.V)*t^2 + 2*(P.V - C.V)*t + P.P + C.C - 2*P.C - r^2 = 0

Now you just solve for t using the quadratic formula to get 0, 1, or 2 possible intersections.

Final Words of Encouragement