CS 426 Assignment 5

Ray Tracing

Due 1159 PM Monday, December 9


Introduction

In this assignment you will implement a basic ray tracer. Use a recursive approach, as suggested in Hearn and Baker, paragraph 14.6 (read paragraphs 14.1, 14.2 and 14.6, and the appropriate lecture notes).

Your program will support two primitives: spheres and triangles. You'll have a simple material model and a handful of lights. In order to get complete credit, a number of possible extensions and their various point values are specified below.

Your program will take its input in a simple ASCII format (which, conveniently, is parsable by Tcl) and will generate its output as PPM "raw" image files (click here for the PPM specification).


Advice

We advise you to work with a partner on this assignment. You may not work with the same partner you had in any earlier assignments.

Ray tracers are very, very modular programs. If you start early, you can design a system where you can add features as you go. You may want to seriously consider using an object-oriented programming style (either in C or C++).


Scenes

Scene description are read from a Tcl scene description (TSD), which is specified by a number of input lines which you will likely parse with Tcl by creating one Tcl command for each of the commands below.

A number of sample scenes are available in /u/cs426/Examples/RayTracer.

Camera

camera_from   x y z
Location of the camera in world coordinates.
camera_target x y z
The camera is looking at this point in space. You may prefer to use camera_forw.
camera_forw   x y z
The vector defines which direction is forward.
camera_up     x y z
The vector defines which direction is up.
camera_angle  theta
The angle, in degrees, specifies the angle from the left side of the screen to the right side of the screen. When you're rendering your image, you'll use this number to space out the rays you fire. You should scale this angle appropriately in the Y direction based on the resolution of the output image. If the image is wider than tall, the angle from top to bottom will be proportionately smaller.
camera_resolution x y
The pixel resolution of the final output image.

Geometry

max_vertices n
Hint to the system that you'll have no more than this many vertices - makes memory allocation simpler. This statement should occur before any vertices are specified.
max_normals  n
Hint to the system that you'll have no more than this many normals - makes memory allocation simpler. This statement should occur before any normals are specified.
vertex  x y z
Each time you run this command, you add a vertex to the vertex pool. Future references to these vertices will be by vertex number. The initial vertex is number zero.
normal  x y z
Just like vertex, this command adds a normal to the normal pool, with numbering that begins at zero. The normal pool should be kept separate from the vertex pool.

You may find it useful for the vertex and normal commands to return their index numbers back to Tcl.

tri     v1 v2 v3
This adds a triangle to the world using these three vertices. This triangle is flat, and its normal vector can be inferred from the vertices. In case you decide you care, you can treat these vertices as occuring in counter-clockwise order (i.e.: if you want to do backface culling - this isn't required, though).
ntri    v1 n1 v2 n2 v3 n3
This is just like the tri primitive except you get to specify a normal for each vertex. Remember, the normals come from the normal pool and the vertices come from the vertex pool.

Note: the arguments passed to tri and ntri are indices into the vertex and normal pools.

sphere  x y z radius
This adds a sphere to the world centered at the given point with the given radius.

Lights and Materials

These work in much the same way as OpenGL calls. You set the current material and it applies to all future objects until you change it. Unlike OpenGL, you should compute shadows, i.e.: shoot a ray at each light, and only add its contribution to a surface if it's directly visible.
background       r g b
Defines the background color, i.e., when a ray doesn't intersect anything in the scene. Note that R,G,B are defines as floating point numbers between zero and one.
ambient_light    r g b
Defines an ambient light - all objects are illuminated by this light. Note: the world can have precisely one ambient light. Further calls to ambient_light redefine this number.
parallel_light   r g b   x y z
Defines a parallel light - much like the sun, these lights are infinitely far away, and only have a direction vector.
point_light      r g b   x y z
Defines a point light - these radiate light evenly in all directions, but their energy falls off as 1/r2.
spot_light       r g b   px py pz  nx ny nz  angle1 angle2
Defines a spot light - this is optional for your assignment. Spot lights exist at a point in space (px,py,pz) and point in a given direction (nx,ny,nz). angle1 and angle2, both in degrees, specify how the light falls off. For any angle between zero and angle1, the light should be just like a point light. Between angle1 and angle2, the light falls off. For angles greater than angle2, the light isn't there. If you do this, start with linear falloff, then you may want to play with various gamma functions (just like assignment 2).
material  r g b  Ka Kd Ks n_s  T index_of_refraction
RGB is in terms of 0.0 to 1.0.

Ka is the ambient component, Kd is the diffuse component, Ks the specular, n_s is the Phong cosine power for highlights, T is transmittance (fraction of contribution of the transmitting ray). Usually, 0 <= Ka <= 1, 0 <= Kd <= 1, and 0 <= Ks <= 1, though it is not required that Ka + 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). Also note that you can use Ks to define the contribution of a reflected ray.

The fill color is used to color the objects following it until a new color is assigned.

Note: add some code to your assignment 4 program, such that the function which creates the input file for your ray tracer also writes the appropriate material lines

For the assignment, you're required to deal with neither transparent nor reflective objects. It's optional. See the Grading section, below.

Miscellany

render file.ppm
Given the full scene, camera, lighting, and such has been specified, this runs the ray tracer and sends its output to "file.ppm" in PPM "raw" format. It should only take you about six lines of code to do this: just use fputc() for the R, G, and B parts and fprintf() for the headers.

You should be able to view your images with xv, where you can convert them to any other format, such as GIF and JPEG for your personal Web pages.

clear_scene
Frees all internal memory. If you want to write a Tcl script that generates multiple images, you'll need this.
trace_depth n
It's possible for your raytracer to get into infinite loops, so this specifies the maximum number of bounces before you terminate a ray.

Implementation Notes

For the theory behind ray tracing, see the lecture notes for lecture 15, and paragraph 14.6 of Hearn and Baker.

Pay very careful attention to this quote:

Novice programmers often neglect the design phase, instead diving into coding without giving thought to the evolution of a piece of software over time. The result is a haphazard, poorly modularized code which is difficult to maintain and modify. A few minutes of planning short-term and long-term goals at the beginning is time well spent.
- Paul Heckbert, ``Writing a Ray Tracer,'' in An Introduction to Ray Tracing, edited by Andrew Glassner.
You should think very carefully about the structure of your system. You need to intersect rays with triangles, spheres, and possibly with your acceleration structures. You want some kind of generic object with function pointers to the intersection functions (C++ folks would use inheritance with virtual functions). Start early, and you've got plenty of time to finish. Start the night before, and you'll get nowhere.

Assuming you implement your ray tracer using Tcl as an interface, you'll only need Tcl, not Tk. A side benefit is that you can run your program anywhere, not just an SGI. Ultimately, you should have a Tcl script which runs your ray tracer like so:

raytrace teapot.tsd teapot.ppm
The simplest possible version of the "raytrace" script only really needs to say:
#!./rayshell

source [lindex $argv 0]
render [lindex $argv 1]
exit
In the example directory you'll find raycharles, a working raytracer written by Dan Wallach, his interface code to Tcl, and algebra3.cc, which contains vector and matrix routines in C++ which you are free to use.


Grading

If you support all the commands listed above, except for the ones marked optional, you will get 8/10 points. To get the remaining credit, you can choose from the laundry list below. If you have ideas for extensions which are not on the list, let us know. These point values are somewhat fuzzy in that you can do an amazing job and get significantly more than the value here. Likewise, you can do a shoddy job and get less. Also, please don't worry about somebody ``blowing the curve'' by doing everything. We'll have a reasonable upper bound on the grades.

Note: you may want to think about continuing your ray tracer for your final project.

FeatureValue
Primitives
Cones and cylinders0.5 points
Constructive solid geometry1.0 point
Metaballs, splines, and other algebraic surfaces1.0 points
Fractals or other recursively defined primitives, evaluated on-the-fly (usually tied into your acceleration structure)0.5 points
Lighting
Spot lights0.5 points
Area lights / soft shadows1.0 points
Sampling
Jittered, filtered oversampling0.5 points
Adaptive oversampling1.0 points
Motion blur1.0 points
Depth of field / real camera lenses1.0 points
Materials
Texture and bump mapping (cylindrical, spherical, and planar projections)1.0 points
Procedural textures (checkerboards, wood, marble, wavy water, etc.)1.0 points
Displacement mapping1.0 points
Miscellaneous
Good acceleration structures (hierarchical bounding volumes, spatial octrees, etc.) - if you're amazingly fast, you'll get more points1.0 points
Reflections0.5 points
Transparency0.5 points
Make a short MPEG movie of bouncing balls0.25 points
Make a user interface which shows the ray tracing in progress0.25 points
Spread out the samples so you see a coarse picture quickly0.25 points
Parallelize your ray tracer (CS461 folks may want to do this on ACME)0.5 points


More pictures and info

Ray tracers can be extremely small programs, too. Check out Paul Heckbert's ray tracer on the back of a business card.

Ray tracers generate really beautiful pictures. Check out The Raytracing Competition for some inspiration.

Finally, also submit a URL's for:

Maybe you can make your favourite image to look like this, or even like this... (image created by Kevin Odhner).


Patrick Min and Dan Wallach, CS Department, Princeton University
Last modified: Thu Nov 21 13:22:11 1996