CS348b: Computer Graphics: Image Synthesis Techniques

Assignment 1: Algebraic Surface Intersection

Handed out: April 8

Due: April 22

Description

In this assignment, you will add a new shape class to lrt, the rendering system described in the Physically Based Image Synthesis book. This shape will compute ray intersections with algebraic surfaces, which are implicit surfaces defined by polynomial equations in x, y, and z. In class, we derived the technique for intersecting rays with quadric surfaces (polynomials of degree 2) like spheres; this assignment has you generalize this approach to higher-degree polynomials.

Step 1

Download and carefully read the paper “Ray tracing algebraic surfaces”, by Pat Hanrahan, proceedings of SIGGRAPH 1983 (pdf).

Step 2

Next, retrieve a copy of the lrt source code and copy it to your home directory.

• Copy /usr/class/cs348b/files/lrt.tar.gz to your working directory.
• Type gunzip lrt.tar.gz in the directory with lrt.tar.gz. The result is a file named lrt.tar.
• Type tar xvf lrt.tar. This will extract the files you need into a new directory called lrt.
• Compile lrt. The Makefile provided works for the machines in the Sweet Hall lab.

Note that we can't offer much support for other development environments (e.g. Visual C++). However, please let us know if you have success on other platforms - we'll share any tips with the rest of the class!

Step 3

Test lrt by rendering one of the example scenes provided in /usr/class/cs348b/scenes/. This example will assume that you compiled lrt in a directory 348/ in your home directory, ~/348/lrt

• Copy the example scenes to your working directory: cp –r /usr/class/cs348b/scenes ~/348
• Render example1.rib and example2.rib. If you compiled lrt in the directory ~/lrt, then the lrt executable is ~/lrt/lrt, so:

cd ~/348/scenes

~/lrt/lrt decls.rib example1.rib

display example1.tiff

~/lrt/lrt decls.rib example2.rib

display example2.tiff

Step 4

A stub implementation of the algebraic surface primitive is in the file /usr/class/cs348b/hw1/algebraic.cc. Copy this file and the /usr/class/cs348b/hw1/polynomial.h file to the shapes/ directory in your lrt directory and edit the PYWEB_SHAPES_CCFILES line of the Makefile.filelist file to add algebraic.cc to the shape implementations that are compiled. Because lrt is written with a plug-in architecture, it is not necessary to edit any of the rest of lrt’s source code to add the shape. Comments in algebraic.cc will explain which methods you need to implement for the shape.

Your two main tasks are to implement code that automatically computes the coefficients of the univariate polynomial in t such that its zeros give the points of intersection with the ray and to implement code that automatically computes the gradient of the implicit surface at the intersection point in order to compute the surface normal. You do not need to implement optimizations like the common-subexpression elimination described in the paper (but are encouraged to implement the most efficient intersection routine possible!)

So that you don’t need to worry about implementing polynomial root-finding algorithms, we have included the source code to a low-degree polynomial root-finder in polynomial.h. The source code comes from the excellent Magic Software website. A brief description of the algorithms that it uses is available (pdf).

Step 5

We have prepared a number of scene files that describe various algebraic surfaces as well as TIFF image files that show the result you should produce when your implementation renders them. These are in the directory /usr/class/cs348b/scenes. You may wish to start with the sphere scene to help debug your implementation, since you can easily compare the quadratic equation coefficients that your implementation computes to the ones that were derived in class (and in the book). You should make sure your implementation can render all of the examples correctly.

You may want to look through the example scene files a bit to get a sense of the scene description format that lrt supports; the example files are heavily commented.

Submission

Turn in your finished homework using the cs348b submit script:

cd my-lrt-directory/shapes

/usr/class/cs348b/bin/submit

Make sure you hand in algebraic.cc and a README file. The submit script will also submit polynomial.h just in case you made any changes to library. The README should contain instructions for compiling and running your code, and a description of anything non-intuitive you've done. Please do not submit any executables or object (.o) files. We'll be building your submissions ourselves, and those just take up space.

Grading

This homework, like the other programming assignments, will be graded according to the following system:

0 - Little or no work was done
* - Significant effort was put into the assignment, but not everything works correctly.
** - The algorithm you implemented was functionally complete; it passed all of our tests.
*** - Your implementation was substantially faster or more flexible than a straightforward implementation.