CS248 Final Review - Dec. 4, 1999

To know:

Questions:

1. 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()).

2. 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.

3. 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.

4. 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 solid color.

5. 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 magnifying.

6. 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.

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

8. 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 correspond to?
     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:

9. 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 that position.
   • It combines the two colors from different levels together, using the .75 and .25 weights, to generate the final color.

10. 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.

Know:

• How to construct a perspective matrix given the left, right, top, bottom, near, and far clipping planes (look up and read about glFrustum()).
• What the OpenGL viewing pipeline is, from object space to window coordinates.
• Off-axis viewing frustums.

Simple Perspective Questions

1. Give 2 reasons for clipping before homogenization.
   1. Avoids unnecessary divisions.
   2. 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.
      
   3. 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.

2. 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).)

3. What part of a 4x4 matrix tells you that it is a perspective transformation?
   If any of the first 3 elements of the last row are not [0 0 0], then it is a perspective transform.

4. 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).

5. 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.

Minor Clarification:
* 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.

Know:

The six visible-surface determination algorithms discussed in class:

• Z-buffer
• Watkins
• Warnock
• Weiler-Atherton
• 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?

Questions:

1. 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 reporters?
   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.

2. [hard] 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 z_win into the range 0 to 1:
   z_win = [(z_near + z) * z_far] / [(z_far - z_near) * z]
   A single bucket dz_win = (1 - 0) / 2¹⁶, 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:
   dz_win = z_neardz / [(z_far - z_near) * z²] + 0
   (or)
   dz = dz_win * [(z_far - z_near) * z²] / [z_near]
   Plugging the values of 2^-16, .01, 20, and 10, we get:
   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 z_far / z_near . Thus the TAs suggest increasing z_near. 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.

To know:

• 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

Questions:

1. 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).

2. 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.

3. 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.

4. 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.
   

   	Directional Light (w=0)	Point Light (w=1)
   Orthographic Projection (viewer w=0)	a)	b)
   Perspective Projection (viewer w=1)	c)	d)

   Answer: a) no, b) yes, c) yes, d) yes.

5. 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 energy.)

6. 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.]