Graphics and Visualization
Spring 2004 Qualifier Exam

1. The Rendering Equation

(a)
State the Hanrahan or the Kajiya formulation of the rendering equation,
and briefly describe the terms.

(b)
What aspects of this equation are accounted for by Whitted-style ray
tracing?  Which aspects are NOT accounted for, what does this omit from
rendered images, and why?  (You might consider shadows, indirect
illumination, reflection/refraction, caustics...)

(c)
What aspects are accounted for by Cook-style distribution ray tracing?
Which aspects are NOT accounted for, what does this omit from rendered
images, and why?

(d)
What aspects are accounted for by Kajiya-style path tracing?  Which
aspects are NOT accounted for, what does this omit from rendered images,
and why?  Is there anything wrong at all in such images?


2. Light Contradictions

This question explores some seemingly contradictory statements about
light.

(a)
The BRDF of a Lambertian (perfectly diffuse) surface is CONSTANT.  The
light reflected from a diffuse surface VARIES with the cosine between
the normal and the light.  Reconcile the differences in these statements
(CONSTANT versus VARIES).

(b)
Light intensity FALLS OFF with the square of the distance from a light
source.  Radiance is CONSTANT along an unblocked ray.  Reconcile the
differences in these statements (FALLS OFF versus CONSTANT).

(c)
You are pointing a camera at a large wall and you are walking away
from that wall.  The wall is a perfectly diffuse surface that is
being illuminated by the sun.  How does the amount of light reaching
the camera vary as you back away, and why?

3. Picket Fence

Imagine that you are rendering a white picket fence on a dark background.
This scene of regularly placed vertical rectangles is a classic problem
scene with respect to anti-aliasing.  For each of the three kinds of
scene descriptions and rendering techniques below, answer the following:

  - What is a good way of performing anti-aliasing?
  - What does this anti-aliasing method do when you are very CLOSE to
    the fence, and how does this avoid the stair-step edge effect?
  - What does this anti-aliasing method do when you are very FAR from
    the fence, and how does this avoid the moire pattern effect?

(a)
The fence is described as a collection of polygons, and you are
rendering with a polygon scan-conversion renderer.

(b)
The fence is described as a single texture map of a fence that is placed on
one large polygon, and you are rendering with a ray tracer.

(c)
The fence is described with a light field, and you are rendering with
the Levoy-Hanrahan light field rendering method.


4. Whitted Didn't Say

Turner Whitted's classic paper on ray tracing describes several aspects
of anti-aliasing with a ray tracer, but he left out a number of details.

(a)
Whitted suggests comparing the four adjacent samples at the corners of
a pixel, and says if the colors are too different, subdivide the pixel
and cast rays at the corners of the smaller squares.  How would you
define "too different"?  What is the best filter you can think of to
use on the adaptively sampled set of rays?  (Don't rule out using rays
from adjacent pixels.)  Once you have subdivided a pixel, perhaps
multiple times, how would you go about averaging them using your
filter?

(b)
Whitted suggests making the size of the bounding sphere around a given
object dependent on the distance from the viewer, so that distant
objects get a large bounding sphere and are not missed.  What size
should the sphere be for a particular object at a given distance?  What
should this sphere's size be for a ray that has been bounced off
a flat mirror?  What size sphere for a ray that has bounced off a
curved mirror?  Once the ray tracer has found such a small object, how
should that pixel be sampled?


Modeling

1) Consider a set of N lines in the plane. Assume that no three lines go through the same point and that no two lines are parallel. They partition the plane into faces. What is the number of faces? Assume that the set S if the closure of the union of a subset of these faces. Discuss various representations for S and comment on their costs: (1) cost of storage and transmission and (2) expected cost of testing a random point for inclusion in S.

2) The discrepancy between two polyhedra, A and B, may be measured by the volume of the symmetric difference. Assuming that A and B are represented by their triangle-mesh boundaries, suggest an algorithm for computing that volume exactly (i.e., within the accuracy of floating point operations). Suggest a simpler algorithm for estimating it.

3) Two solids, A and B, each bounded by a triangle mesh interfere a little. You want to find a vector D so that if you translate A by D, it will no longer interfere with B. Suggest a simple algorithm for finding a nearly minimal D. Could we use graphics hardware to accelerate this process? If so, explain how and discuss the consequences on accuracy.

4) Consider a triangle mesh S. Discuss strategies for finding a plane P that maximizes the portion of S that lies within distance d from P. Discuss possible applications of such a tool.


1) Most of computer graphics (ray-tracing, rasterization) assumes that the color and intensity of light transmitted along a ray to the viewer is constant. That is, if the viewer moves back along a ray, the light perceived from the direction of the ray is constant. Yet, we know that the light emitted from a source in a given direction diminishes proportionally to the inverse of the square of of the distance from the source. So... are all the graphics books and papers wrong? Are they using an approximation? Similarly, a diffuse surface emits the same amount of light in all directions. But as we look at a portion of the surface from different angles, we see more or less of the surface. Hence, we should perceive more light from a grazing angle than from a direction normal to the surface. How come we do not?

2) The perspective transformation maps a point P=(x,y,z) into a point P'=(x',y',z'). Assume that the viewer is located at (0,0,-d) and that the screen is z=0. We want the perspective transformation to ensure that (x',y') defines where P projects on the screen and that z' is a monotonic function of z, so that the z-buffer (which stores z' at pixel [x',y'] can be used to correctly select the visible surface. Explain precisely why one could not use the following perspective transform: x'=dx/(d+z), y'=dy/(d+z), z'=z, although it does fulfill the above requirements. Provide the correct formulae for perspective transform and explain why it works. Now assume that the view (screen and viewer) has been transformed so that the local origin is at O and that the local unit vector in the Z-direction is K, and that the local unit vectors in the X- and Y- directions are I and J. Given a pixel [x',y'] and a z-buffer content Zbuf[x',y'], what is the corresponding 3D surface point, P, expressed in global coordinate systems.

3) Catherine wants to live in the US as far as possible from any nuclear power plant. Assume that the earth is flat, that boundary of the country is a polygon, and that the power plants are points. Provide a simplest to implement algorithm for computing the desired location (assume that you will have to implement everything yourself from scratch). What is the worst case computational complexity of your simple algorithm? Now assume that you have access to all publicly available software, how would you solve this problem and what would be the computational complexity of your solution? Explain the relation between this problem and the Hausdorff distance.

4) Consider an original curve, C, and an approximation of it, A. Both are polygons. Discuss the various measures of error (discrepancy) between A and B. For each measure, briefly provide an outline of the algorithm for computing it and argue the benefits and drawbacks for selected applications. Illustrate these benefits and drawbacks with a simple drawing or example.
5) Consider a rectangular window, W, a polygonal occluder, O, and a ball B of center C and radius r. Discuss effective algorithms for testing whether B is occluded (i.e. hidden from all viewpoints V in W).

5) A `natural' 3D volume dataset (say, a medical CT scan) is given
as a sequence of intensities of consecutive voxels without any
information on the resolution of the dataset (a header got lost somewhere).
Assume the total number of voxels is known (say, this is the length of
the file storing the voxel values).
Give a practical algorithm which would attempt to
compute its (most likely) x- y- and z- resolutions.
Explain what makes you believe it would work.

6) Is it possible to obtain any 3D isometry by composing symmetries
about planes? If, in addition to symmetries about planes one is allowed
to use non-uniform scale along the X axis with an arbitrary scaling
factor s, is it possible to obtain any affine transformation as a
composition? Explain why.