**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

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.