CS248 Final Review - Dec. 4, 1999
This page includes a few notes and example problems from the
review session. See also the
course schedule, which lists the assigned readings and Prof. Levoy's
class notes. If you want to test yourself on these questions before
you see the answers, go to the
Disclaimer: These questions were designed to give you an idea of
what kinds of questions we might ask about the material.
This was not intended to be an exhaustive coverage
of all material you should know for the exam.
CS248 Autumn '99 Final Exam:
- When: 12:15 - 2:15pm, Friday, Dec. 10, 1999.
TCSEQ 200 (The gray building with the slanted walls between Gates
and the Quad).
- Material: The second half of the quarter, from 3D transforms
(Thurs., Oct 28) to lighting (Tues., Nov 30). It will NOT include
material from the last class (volume rendering, image-based
- Office Hours: As regularly scheduled (See the
course outline), or by appointment.
(by Lucas Pereira)
(I forgot to cover this at the review session. Even though this
class was the Thursday before the midterm, the material was not
covered in the midterm, and so will be fair game for the final,
although will not be heavily emphasized.)
- 3D transformations & image transformations (
Oct 28 Lecture)
- 3D cartesian / 4D homogeneous coords
- What does it mean if a vertex's w is 0?
- right/left handed coordinate systems
- rotation, translation, scaling, and the corresponding 4x4 matrices
- the inverse matrices for rotate, translate, and scale
- image warping: forward-mapping (splatting / texture-order) vs.
- Which properties (lengths, angles, parallel lines, straight
lines) are preserved by each class of transformation
(rigid, linear, affine, projective).
(by Lucas Pereira)
- Where on earth can you walk forward 6219 miles (1/4 circumference),
turn right, walk forward 6219 miles, turn right,
walk forward 6219 miles, and be back where you started?
Anywhere. You will always be back where you started, regardless of
your initial position and orientation. But this is easiest to
visualize if you start at the north pole. You'd walk to
the equator, walk 1/4 of the way around the equator, and walk back.
You'll now be facing 90 degrees left of your starting direction.
- When viewed by a perspective projection, which of the following
properties of a texture-mapped plane will be preserved:
lengths, angles, parallel lines, and straight lines?
No, No, No, and Yes. (Straight lines stay straight, but
lengths, angles, and parallel lines may all change).
- When rendering with OpenGL texture-mapping (GL_NEAREST, no mipmaps),
is this a forward-mapping or backward-mapping operation?
Backward-mapping, because you iterate over each pixel on the
screen, and compute backwards to find the texture coordinates
on the object that will map to that position on the screen. A
forward-mapping algorithm would iterate over each pixel on the
texture, and draw it on the screen.
- Lucas wants to do rotatez(90), but he spilled coffee on his
keyboard and his z key no longer works. He decides instead
that he can do it with the following: rotatex(90) [
rotatey(angley) [ rotatex(-90) ]].
Is he right? What should (angley) be?
Yes, he's right, because the matrices work out. Rotations in
different axes are not independent. Angley
would need to be 90. (Partial credit for -90, you just got the sign
or the order of operations wrong.)
(by Sean Anderson)
- Can a 1-D texture map be applied to a 2-D surface? How?
Yes. Texture coordinates not the same thing as position coordinates.
You can easily specify 1-D texture coordinates at each vertex
(for example, glTexCoord1f()).
- Can a 2-D texture map be applied to a 1-D line? How?
Yes. Just specify a 2-D texture coordinate for each vertex of the line.
The color applied to the line will be the colors along the straight
lines between those coordinates in the 2-D image.
- What is minification? Magnification?
Minification is when you map multiple texture pixels (texels) to a single
screen pixel (e.g. shrinking the texture). Magnification is when you
have less texture pixels (texels) than screen pixels.
- What are the effects of using GL_NEAREST as your texture filter
when minifying? Magnifying? Explain.
When minifying, GL_NEAREST can cause noise and aliasing.
When magnifying, GL_NEAREST will cause blocky squares of
- What are the effects of using GL_LINEAR as your texture filter
when minifying? Magnifying? Explain.
Linear interpolation does not fix the noise/aliasing problems
when minifying, but gives smooth linear interpolation when
- What is the common OpenGL approach to avoid aliasing
while minifying? Will it have any effect on magnifying?
OpenGL uses mipmapping, which creates extra textures with fewer
pixels (usually by averaging down), which can be used instead
of the original texture to avoid aliasing. It does not have
any effect on magnification, because OpenGL will use the highest-
resolution texture for magnification.
- What filter kernel does GL_NEAREST correspond to?
GL_NEAREST, or point-sampling the texture, is equivalent to
using a simple box reconstruction filter, which has the
width/height of one (texel), and oriented on the surface
of the object, aligned with the texture coordinate axes,
not screen axes.
- What filter kernel does GL_LINEAR correspond to?
GL_LINEAR, or linearly interpolating the texture, is equivalent to
using overlapping bartlett (tent) reconstruction filters, which
have a width/height of two texels, and oriented on the surface
of the object aligned with the texture coordinate axes.
- What filter kernel does GL_LINEAR with mipmapping
This was a bad question. Mipmapping makes
the whole process nonlinear, since the contributing pixels in the
original texture depend on where exactly the sample is taken,
and what mipmapping level(s) it uses. My apologies for
confusing people. Instead, I offer the following question
to get you thinking about mipmapping:
- How does mipmapping with tri-linear interpolation compute
the texture color for a vertex?
- it figures out the minification factor (say, 2.5:1).
- it picks the two mipmap levels that are closest
(say, 2:1 and 4:1). It computes two weights
(0.75 and 0.25) to apply to the color generated from
each of the two levels.
- For each of those two levels, it uses the vertex's
texture coordinates to find the four closest texels
in that level, and does bi-linear interpolation between
those four texels to find the color at that level at
- It combines the two colors from different levels together,
using the .75 and .25 weights, to generate the final
- To make things simpler, Lucas has turned his '89 Integra
Racing game into a drag-racing game. As such, he has his car
racing up the Y axis of a single texture-mapped ground
polygon. The viewer always looks orthographically straight
down on his car. In this orthographic view, the ground
texture is magnified (more pixels than texels). Because his
car goes so fast (many texels per frame), the ground plane
looks choppy, instead of smoothly motion-blurred. Since Prof.
Levoy is his advisor, he figures that all problems can be
solved with proper filtering. Could standard mipmapping solve
his problem? Why or why not?
No, standard mipmapping would not help, because it subdivides
equally in both directions, and since it's magnifying, you
want to use the highest resolution. But summed-area tables
could solve the problem, because they can do rectangular
filters, and thus blur only in the direction of travel.
- How to construct a perspective matrix given the left, right, top,
bottom, near, and far clipping planes (look up and read about
- What the OpenGL viewing pipeline is, from object space to window
- Off-axis viewing frustums.
Simple Perspective Questions
- Give 2 reasons for clipping before homogenization.
- Avoids unnecessary divisions.
- Allows easier clipping of lines or polygons that go
through the view frustum and have a point behind the viewer.
Imagine you have a line that has one point in the frustum and
another point that is behind it. For concreteness, suppose
the points of the line are P1 = [1 1 10000 1]' and P2 = [-1
-1 10000 1]' (where ' means transpose). Suppose that the
perspective view frustum has near=1, far=2, and the
horizontal and vertical fields of view are both 90 degrees.
The viewer is at the origin looking down the -z axis. So,
left = -1, right = +1, bottom = -1,
top = +1, and the perspective matrix, M, we get after
plugging in the expression described in the glFrustum() man
pages, we get:
1 0 0 0
0 1 0 0
0 0 -3 -4
0 0 -1 0
So, applying the perspective transformation and homogenizing, we get:
M*P1' = [1 1 -30004 -10000]' -> [-.0001 -.0001 3.0004 1]'
M*P2' = [-1 -1 29996 10000]' -> [-.0001 -.0001 2.9996 1]'
Notice that the line connecting these two transformed points
does not go through the normalized device space box,
(-1, -1, -1) to (+1, +1, +1). The line does
intersect the view frustum, though. Thus we see clipping lines
(and my a similar reason, polygons) after homogenizing is not such
a simple matter.
- Note the following
reason, which is given in the online notes and previously here
too, is wrong: Allows detection of points behind the viewer (This
benefit is only an issue when points can have W values other than
1, such as in rendering NURBS or fancy shadow algorithms). Sorry
for the confusion.
- What is the condition used to determine if the x coordinate (xc) of a
non-homogeneous projected point is within the left and right walls (at
-1 and +1 on the near plane) of a perspective view frustum?
if (-wc <= xc <= wc) then inside.
(Since we can multiply by wc through (-1 <= xc/wc <= 1).)
- What part of a 4x4 matrix tells you that it is a perspective
If any of the first 3 elements of the last row are not [0 0 0], then it
is a perspective transform.
- Consider a view of a scene with 2 cubes oriented arbitrarily; how many
vanishing points could there be in the image?
Six (one for each distinct edge direction).
- Where is the viewer's eye and what is the viewing direction when the
perspective transform is applied?
The eye is at the origin. The view is down the -z direction.
(by David Koller)
* The normalized device coordinate space used in Foley (your
encyclopedic text) has z ranging from 0 to 1. In lecture and in OpenGL,
it ranges from -1 to +1.
The six visible-surface determination algorithms discussed in class:
- BSP Tree
- Ray tracing
Questions to consider for each algorithm:
- How does the algorithm work?
- What is the asymptotic time complexity of the algorithm?
- How can antialiasing be incorporated with the algorithm?
- How can shading be incorporated with the algorithm?
- What preprocessing is necessary to use the algorithm?
- Is the algorithm well-suited to hardware support?
- Is the algorithm well-suited to parallelization?
- How complex is the algorithm to implement?
- What are the best-case/worst-case input scenes for the algorithm?
- How/why is the algorithm used in modern graphics systems?
(by Szymon Rusinkiewicz)
- NASA wants to draw a picture of Mars to try to visualize the
landing site of the missing Mars Polar Lander probe, and so
they're trying to pick a good hidden-surface algorithm. They
have a high-powered supercomputer, with 1.7GB of RAM. They
want to draw a 3000x3000 pixel image. Unfortunately, their
Mars model consists of ten Billion polygons, and so they can
only load 2% of it in memory at a time. They want to minimize
disk accesses. Alas, they only have programmers who know how
to implement Watkin's algorithm, Weiler-Atherton, BSP trees,
and Z-buffering. Which algorithm should they use, and why?
(For each discarded algorithm, state why it's a bad choice.)
If they can load a million polygons per second off disk, how
long will it take before they will have a picture to show
Z-buffer, because it could render the image in a single pass.
BSP would require building a data structure that wouldn't fit
in memory. Watkin's algorithm requires building an edge table
that also wouldn't fit in memory (and would require many
passes to do incrementally). Weiler-Atherton, among other
things, requires sorting, which is painful on 10-billion
polygons, especially when you'd have to sort on disk. The
image would take about 10,000 seconds [3 hours] to do in a
single pass with Z-buffer.
A cs248 student is experiencing difficulties with his z-buffer,
so he sends email to the cs248tas. The problem, he says, is
that he's seeing really bad artifacts. Upon investigation,
they realize that he's setting the near clipping plane to
0.01, the far clipping plane to 20, and most objects are
about 10 units away. The TAs tell him that his problem is
lack of precision; different surfaces are getting mapped to the exact
same Z-value in his 16-bit Zbuffer.
What is the depth range of a single z "bucket"
at a distance of 10 units away? How could he fix his problem?
You may assume the following formula maps zwin into
the range 0 to 1:
zwin = [(znear + z) *
zfar] / [(zfar - znear) *
A single bucket dzwin = (1 - 0) / 216, or
2-16, in window coordinates. This is the smallest
difference that we can store in the zbuffer. Now we must figure out
what size step this corresponds to in eye coordinates at a distance
of 10 units. We could solve this algebraically, but it is easier to
solve it by differentiating with respect to z. We get:
dzwin = zneardz /
[(zfar - znear) * z2] + 0
dz = dzwin *
[(zfar - znear) * z2] /
Plugging the values of 2-16, .01, 20, and 10, we
dz = 2-16 * [19.99 * 100] / 0.01
dz = 3.05
This means that, at a distance of 10 units, surfaces up to
3 units apart might map to the same Z value! Thus for close
surfaces, you'll see the one that was drawn last, not the one
that should be in front.
It becomes clear that the dominating factor in the bucket size of
the zbuffer algorithm is zfar / znear .
Thus the TAs suggest increasing znear. For example,
by setting the near plane to 1.0 instead of 0.01,
dz = 2-16 * [19 * 100]
dz = 0.029
Now surfaces more than .03 units apart at a depth of 10 will
be occluded properly. This is over 100 times more accurate than
before. Where did all the extra precision come from? In the
previous scenario, we were using a lot of bits to get high
accuracy between .01 and 1, since the zbuffer maps nonlinearly
to give higher accuracy to close objects. Since our objects
were typically further away, we "moved" that precision to where
the objects actually exist.
- Terminology: definitions and units of Radiant flux, Irradiance,
Radiant intensity, and Radiance
- Illumination of a surface by a point or directional light results in
a cos(theta_i) term in the irradiance
- Reflection off a surface described by BRDF (function of 4 parameters)
- Lambertian (diffuse) reflection -> constant BRDF -> looks equally bright
in all directions
- Shiny surface -> peak around direction of ideal specular reflection
- OpenGL lighting model: diffuse term (N dot L), Phong/Blinn specular
term (N dot H), ambient term, emissive term. Gouraud interpolation
(interpolation of per-vertex colors across polygons)
- Local vs. global illumination
- You change the normal vectors of an OpenGL triangle, but don't change
the position of the vertices. Which components of the color seen
by the viewer (ambient, diffuse, and specular) might change? Why?
The ambient component will not change, because it is directionless.
The diffuse component could change, because it depends on
N dot L, and we changed N.
The specular component could also change,
because the specular component depends on the dot product of the
halfway vector (H in Foley & vanDam, S in the red
book) with the normal (raised to the shininess exponent).
- An object is sitting in a room with lights you can't turn off.
You want to take a picture of the object with only a single point light
source. You accomplish this by taking the object's picture with the
normal light in the room, and another picture with that light plus a
point light source. You then subtract the first picture from the second.
Will this work? Why or why not?
Yes, this will work, because light transport and reflection is a linear,
additive process. As someone pointed out, this is no longer the case if
you have coherent light and need to worry about interference effects.
- You are in an empty room (just 4 walls, floor and ceiling),
with a single light bulb. You carefully measure the dimensions of the
room, the color of the paint on each wall, and the radiant intensity
of the light bulb. You use these measurements to construct an OpenGL
model of the room, and render the scene. Nevertheless, the rendering
will not look like a photograph of the room. Why not?
OpenGL does local lighting, not global illumination.
- In the table below, write "YES" or "NO" in each of the four squares,
to indicate whether a viewer might see a finite-sized specular
highlight (shiny spot) on a large flat plane. You may assume the
plane is made up of many tiny triangles, so that it is effectively
computing a normal for each pixel.
Answer: a) no, b) yes, c) yes, d) yes.
|| Directional Light (w=0)
|| Point Light (w=1)
| Orthographic Projection|
| Perspective Projection|
- Infinite Engine Motor Corp. (IEMC) introduces their new luxury
car, the W=0, with Seaborgium headlights. They advertise that
these headlights are only the size of a dime, but put out the
same power as their regular six-inch xenon headlights. Ralph
Nader, having lost his bid for governor, decides to sue IEMC,
claiming (a) that the radiance of the new headlights is
greatly increased, and will damage peoples' foveae. IEMC
counters that the headlights are safe, because (b) they emit
the same flux, and (c) provide the same irradiance. Which of
these claims (a, b, c) are right? Do you think these
headlights are more dangerous to oncoming drivers? Why or why
not? (You may assume that oncoming drivers view the headlights
close enough that the six-inch headlights get focused on many
cells of the fovea.)
a, b, and c are all correct. Yes, these headlights are a hazard,
because the increased radiance means that cells will receive more
- Lucas is still writing his '89 Integra Racing game. Since he
has spent all quarter hacking instead of washing his car, his
car is now an ideal dusty surface. He wants to capture this
appearance, but can't think of the right coefficients to model
this surface accurately. Is it possible to model this surface
with the Phong shading model? (in theory; ignore whether
OpenGL will allow these values.) Assuming his car is
completely coated (100% coverage) with ideal white dust, what
values of Kd, Ks, and n (the cos(a) exponent) should he pick?
Is such an "ideal dusty surface" physically possible?
(Consider the total flux falling on the car, and total flux
exiting the car.)
Yes, it is possible to model with Phong shading. Kd = (0,0,0),
Ks = (1,1,1), n = -1. No, it's not physically possible, because
there is finite incoming flux, and infinite outgoing flux.
[Real dust does not match ideal dust at extreme grazing angles.]
Copyright © 1999 Lucas Pereira, Sean Anderson,
David Koller, and Szymon Rusinkiewicz
December 9, 1999 01:23:37 AM