CMSC 435/634 Fall 2008, Assignment 4

CMSC 435/634: Introduction to Computer Graphics

Assignment 4
Ray Tracing
Due November 9, 2009

The Assignment

Implement a program that will render spheres in a world space using ray tracing techniques. Your program should accept input from a text file, which will specify various details about the scene, including the locations and sizes of spheres. You should write your output to an image file in PPM format. The focus of this assignment is on visibility only, so your ray-traced objects should be rendered in a solid color; no lighting effects are involved (lighting will be the focus of assignment 5).

Sample Input Files

There are a few sample input files located at:

    /afs/umbc.edu/users/r/h/rheingan/pub/435/Proj4/samples

The files balls1.nff, balls2.nff, and balls3.nff correspond to different levels of recursion for a fractally defined series of spheres. balls3.nff should take a relatively long time to ray trace.

Input File Format

The input file will use a subset of the NFF file format. NFF is a simple plain text format that contains various commands to describe a scene. The link above describes the format in full, however you only need to support the commands listed below (descriptions are copied from the NFF specification). Note that some commands, like "b" only use a single line, while others such as "v" span multiple lines.

In the format descriptions, %g denotes a floating point number and %d denotes an integer. Coordinates are given in world space.

Sample code in C for reading the NFF format is located at the address below. You may refer to, use, modify, or ignore it as you see fit.

    /afs/umbc.edu/users/r/h/rheingan/pub/435/Proj4/readnff.c

b	Background color. A color is simply RGB with values between 0 and 1: "b" R G B Format: b %g %g %g If no background color is set, assume RGB = {0,0,0}.
v	Viewpoint location. Description: "v" "from" Fx Fy Fz "at" Ax Ay Az "up" Ux Uy Uz "angle" angle "hither" hither "resolution" xres yres Format: v from %g %g %g at %g %g %g up %g %g %g angle %g hither %g resolution %d %d The parameters are: From: the eye location in XYZ. At: a position to be at the center of the image, in XYZ world coordinates. A.k.a. "lookat". Up: a vector defining which direction is up, as an XYZ vector. Angle: in degrees, defined as from the center of top pixel row to bottom pixel row and left column to right column. Hither: distance of the hither [near] plane (if any) from the eye. Mostly needed for hidden surface algorithms. Resolution: in pixels, in x and in y. Note that no assumptions are made about normalizing the data (e.g. the from-at distance does not have to be 1). Also, vectors are not required to be perpendicular to each other. For all databases some viewing parameters are always the same: Yon is "at infinity." Aspect ratio is 1.0. A view entity must be defined before any objects are defined (this requirement is so that NFF files can be displayed on the fly by hidden surface machines).
f	Fill color and shading parameters. Description: "f" red green blue Kd Ks Shine T index_of_refraction Format: f %g %g %g %g %g %g %g %g RGB is in terms of 0.0 to 1.0. Kd is the diffuse component, Ks the specular, Shine is the Phong cosine power for highlights, T is transmittance (fraction of contribution of the transmitting ray). Usually, 0 <= Kd <= 1 and 0 <= Ks <= 1, though it is not required that Kd + Ks == 1. Note that transmitting objects ( T > 0 ) are considered to have two sides for algorithms that need these (normally objects have one side). The fill color is used to color the objects following it until a new color is assigned. Note - for this project, you are only concerned with the first three arguments: red, green, and blue. We will revisit the other arguments in project 5.
s	Sphere. A sphere is defined by a radius and center position: "s" center.x center.y center.z radius Format: s %g %g %g %g If the radius is negative, then only the sphere's inside is visible (objects are normally considered one sided, with the outside visible). Currently none of the SPD scenes make use of negative radii.

Output File Format

The PPM format is one of the simplest image formats available. See the man page for 'ppm' on the university GL server for a description.

To create a PPM file, first you should store your image in an array of bytes in y/x/color index order:

    unsigned char pixels[HEIGHT][WIDTH][3];

When filling in this array, remember that it is in y/x order, not the more familiar x/y order. The final index is the color component, with r=0, g=1 and b=2. Color values range from 0 to 255. For example, this would store a floating point color value of .5 into the green component at x,y:

    pixels[y][x][1]= .5*255;

Once you've filled in the pixels array, actually writing the PPM file is quite simple:

FILE *f = fopen("trace.ppm","wb");
fprintf(f, "P6\n%d %d\n%d\n", WIDTH, HEIGHT, 255);
fwrite(pixels, 1, HEIGHT*WIDTH*3, f);
fclose(f);

Tips on Implementing the Ray Tracer

First and foremost, start early!

Here is a basic outline of what your ray tracer will need to do:

Read the input file. You should define a structures to hold the view and sphere data, then create a collection of spheres in world space.
Calculate the image plane and pixel locations in world space. The rays can be thought of as passing through a rectangle that is perpendicular to the view direction and at a distance of "hither" from the eye.
For every pixel in the image, cast a ray:
- Calculate the direction of the ray as it travels from the eye point, through a pixel, and into the scene.
- Determine if the ray intersects any of the spheres in the scene, and find the one closest to the eye. Remember that if a ray intersects a sphere, it will usually do so twice, so pick the nearer intersection point.
- If the ray hit a sphere, set the pixel to the color of the sphere. Otherwise, set it to the background color.

For testing purposes, you will probably find it useful to construct a simple scene with a single sphere and with the view pointing directly down one axis. Move the sphere around in the scene and make sure the resulting image correctly reflects the changes.

If you implement multiple object types (see below), a ray tracer can make good use of object-oriented programming. A common approach is to define a generic object class with an abstract "intersect" method, and then define spheres, polygons, etc. to be derived from it, each with their own specialized method for calculating ray intersections.

Extra Credit (some mandatory for those taking 634)

Add support for the remaining object types in the NFF specification.
- p - Polygons (10 points - mandatory for 634)
- c - Cylinders and Cones (10 points)
You will need to derive the formulas for intersecting rays with either type of object. You should be wary of floating point precision issues, especially in the case of cylinders and cones. Hint: for polygons, first find the ray's intersection point with the plane containing the polygon.

Note that polygons may be either convex or concave. For the 10 extra credit points, you only need to support convex polygons (likewise, students in 634 only need to support convex polygons). Concave polygons will be worth an additional 5 points.

Also note that in the NFF format, polygons may also be specified using "pp", which includes normals used for lighting. Since we are ignoring lighting for this assignment, you only need to support the "p" command.
Implement regular and jittered super-sampled anti-aliasing. You should use a command line flag, -j, to indicate jittered sampling, with the default being non-jittered. You should also add a command line flag, -a, to indicate the number of samples per pixel, with the default being 1. Your command line would then look like:
```
    raytracer -a 16 -j balls1.nff
```
(10 points, 5 for each sampling method)
Make your raytracer multithreaded. You should add an aditional command line argument (-t) that specifies the number of threads to use. It will be up to you how to split up the work between your threads, but you should document the method used and run several tests with different numbers of threads to show any speedup you get over a single threaded approach. (10 points)

Standard Procedural Database

More sample scenes in NFF format can be created using a set of programs called the "Standard Procedural Database", which is freely downloadable. A copy of the SPD is also located at:

    /afs/umbc.edu/users/r/h/rheingan/pub/435/Proj4/spd

The sample files listed above were created using the SPD program 'balls', which writes an NFF file to standard output. For example:

    balls -s 1 > balls1.nff

The -s option controls the level of recursion. Note that the output of the SPD programs typically includes NFF commands other than the ones required for this assignment (balls outputs a single polygon which was removed from the sample files). Therefore, if you want to test your ray tracer using the SPD programs, you should be able to handle the presence of such commands in your input file (you should simply ignore any commands you do not implement).

The program 'shells' outputs many spheres, similarly to balls; 'lattice' and 'jacks' output cylinders and cones, 'tetra' and 'teapot' output primarily convex polygons, and 'gears' includes concave polygons.

What To Turn In

Submit your assignment as 'Proj4'. Include your source code and makefile. Please do not submit PPM files, as they can be very large. If you must submit images, convert them to a compressed format such as .jpeg. The 'convert' program is available on the GL servers, so for example you can do:

    convert image.ppm image.jpg

Also include a readme file with a description of what hardware / software environment you used to develop your project, and a description of any help you received or outside resources you used. (If you received no help beyond the text and course staff, state as much.) Your readme should also include any instructions necessary for using your program.

Working At Home

If possible, don't. We test things out on the university computers and may or may not be able to help you if things don't work right for you at home. If you do work at home, your final submitted version must be able to run on the gl machines and must be electronically submitted there.