Rendering Techniques Assignment 4:

Accelerated Ray Tracing Flythroughs

Assigned: Wednesday, April 2, 2003
Due: Wednesday, April 16, 2003

Overview

For this assignment, you will speed up your ray tracer to scale better to large numbers of primitives, implement a movable camera, and demonstrater your program by generating a flythrough of a sizeable and interesting scene.

Program Description

Your raytracer should now run with the following command line: 
raytrace <scene description filename> <views filename> <image output file basename>
or
java raytrace <scene description filename> <views filename> <image output file basename>
The scene description format will be exactly the same as the previous assignment (.rt3). The views file will specify a sequence of virtual camera positions, each with a position, a forward direction, and an up direction. The output file will just be a base name, to which your program will append an image number and a ".ppm" suffix (you should use a constant number of digits for the image number so that an alphabetical listing of file names will remain properly sorted by frame number).

This assignment includes a sample scene as well as a new test executable (please let me know ASAP if you find new flaws in the executable).

Acceleration Structures

In class we studied both bounding volume hierarchies and spatial partitions for accelerating ray tracing. You may implement speedup technique you like so long as it provides significant speedups for large scenes (and provides identical output to an unaccelerated program). For the test program, I chose to construct a bounding sphere hierarchy because it builds on the programs existing ability to perform simple ray-sphere intersection tests. An easy way to build such a hierarchy is to take a top-down, recursive approach. Begin by computing an axis-aligned bounding box containing all the scenes primitives. Surround this box by a sphere to form the root node of your hierarchy. If the number of primitives in the node is more than some threshold you choose, break the box into 8 octants, and assign each primitive to one of the octants (according to which octant contains the interior center of the primitive). For each (nonempty) octant, find a bounding box, and proceed recursively until the threhold is reached. In this scheme, each primitive is associated with a single leaf node of the hierarchy.

Your bounding volume hierarchy (or other acceleration structure of your choosing) will need to perform two functions. First, given a ray, you should be able to compute the closest (positive) intersection point. Second, given an shadow ray, you should be able to compute a filter color describing how the light should be filtered according to the primitives between the light and the primitive of origin (this would be black if there is an opaque primitive in the way).

View File Specification (.rtv)

Each different image to be generated has a view in the view file. Each view has an eye (camera) position, forward vector, and up vector. As described in the following section, this is enough to specify your complete camera coordinate system, so long as forward and up are non-zero, non-colinear vectors.
# comment lines start with # and may appear anywhere

NUM_VIEWS: [number of views]
VIEW
 EYE: <x> <y> <z>
 FORWARD: <x> <y> <z>
 UP: <x> <y> <z>
ENDVIEW

Moving Cameras

Each camera in the view file triggers the generation of an image file. Your previous ray tracer assumed the camera position is (0,0,0), the forward direction is (0,0,-1), the up direction is (0,1,0), and the right direction is (1,0,0).  The three vectors form an orthonormal basis for your camera coordinate system. You should first convert the view from the file into an orthonormal basis. There is no guarantee that the forward and up vectors in the file will be orthogonal or normailzed. A standard procedure to make an orthonormal basis is as follows. Compute a right vector as the cross product of the forward vector and the up vector (i.e. right = forward x up). The cross product guarantees that the right vector is orthogonal to both forward and up. Then compute a new up vector as the cross product  of the right vector and the forward vector (i.e. up = right x forward). Then normalize the three vectors. You now have an orthonormal basis which retains the direction of the given forward vector and maintains the direction of the given up vector as much as possible (if forward and up were already orthogonal, the up direction will be unchanged). The only requirement here is that the given forward and up vectors are non-colinear and non-zero.

Recall that the cross product of two 3D vectors follows the right-hand rule and is defined as follows:
 A = (Ax,Ay,Az), B = (Bx,By,Bz), A x B = (AyBz - AzBy, AzBx-AxBz, AxBy - AyBx)
Think of the x, y, and z coordinates of vectors in your previous eye ray computation as the magnitude of the right, up, and backward vectors of your camera coordinate system. Multiplying these values by the new right, up, and backward vectors transforms them to the new, desired camera coordinate system. You can use this transformation, for example, to set up the position for the upper left corner of your screen and the vectors for stepping right and down as you walk from pixel to pixel.

Note: Generating lots of images in a single execution may be a good motivation to clean up any memory leaks!

Flythrough

To design an interesting flythrough, you need an interesting scene and an interesting path. This is your chance to be creative. You may need to write another small program to generate your scene, and it may be convenient to write a small program to generate the path. You can design things by hand, make creative use of randomization, or whatever you like. Some simple paths to consider are straight lines, revolving the viewing direction about a stationary view point, or moving in a circle, etc. The demo will be given somewhat more weight in the grading of this assignment than it was in previous assignments.

After generating a sequence of ppm images, you will need to apply some lossy compression (the compressed tifs we have made so far are lossless, but cannot compress dramatically). The simplest way is to convert to JPEG images (.jpg). From Windows, you can perform batch conversion of ppms to jpgs in XnView. You can use "convert" in unix to accomplish the same thing. You can view your sequence in XnView in slide show mode or in "animate" (as well as "display") in unix. Don't be surprised when you notice lots of aliasing.

Deliverables

Submit a single .zip file  containing the following: Note: there is a danger here of your submission becoming too large in terms of file space. I would like to keep submissions down to a size of 1 MB, if possible. A 256x256 .jpg can look pretty reasonable with a file size of about 10 kB, so you may be able to make as many as 100 images. You may achieve much better compression ratios by converting your ppms to a compressed movie format such as AVI, MPEG, or Quicktime. I may add some additional information to this assignment to tell you how to do this if you want to.

Final Words of Encouragement

I am hoping you will find the speedup and moving camera easy enough to get done in the first week, leaving the entire second week for your to explore creative ways to make a scene and a flythough. Good luck, and have fun!


Home
April 2, 2003