Spring 2000 Qualifier: Graphics & Visualization area

Directions: The Qualifier Exam is structured into two parts as follows:

PART 1 — GENERAL COMPUTER GRAPHICS QUESTIONS: Each candidate must answer 4 out of the 6 proposed general questions.

PART 2 - SUB-AREA QUESTIONS: Each candidate must select 2 sub-areas from the 3 listed below:
A. Animation (Jessica Hodgins)
B. Rendering (Greg Turk)
C.Vision (Irfan Essa, Thad Starner, Aaron Bobick)

In each selected sub-area, the candidate must answer 2 out of the 4 proposed questions.

________________________________________________________________
Please check in the list below all the areas and questions that you have selected to answer:

YOUR CANDIDATE NUMBER: _________

GENERAL QUESTIONS: __1, __2, __3, __4, __5, __6

SELECTED AREAS AND QUESTIONS:
__ Area A, Animation: A1__, A2__, A3__, A4__
__ Area B, Rendering: B1__, B2__, B3__, B4__
__ Area C, Vision: C1__, C2__, C3__, C4__
________________________________________________________________

RECOMMENDATIONS:
Your answers can be typed or hand written, but must be perfectly legible. Feel free to use hand drawn figures to illustrate your point. Try to provide concise, yet complete answers. Include just enough details to convince the faculty committee that you understand the issues and would be perfectly capable of working out the details if needed. Use high-level pseudo-code for algorithms (such as "Foreach vertex V of polyhedron P do it V lies inside polyhedron Q then report a hit."). Use vector and matrix notations whenever possible for all geometric calculations. You are authorized to use your notes, textbooks, and papers, provided that you include in your answer the references that you are using.

1. You can freely rotate a 3D object and watch its shadow produced by a point light source at infinity. These shadows are the only information you have about the object. You can span the whole space of rotations and for each orientation, you have the exact shadow. Provide a precise mathematical formulation for the set of objects whose shape may be precisely recovered from this infinite collection of shadows. Suggest a practical algorithm for doing so. Explain how to apply this technique to a lightfield.
   


2. Consider the coordinates of the 6 vertices (A,B,C,D,E,F) of the shadow cast on the z=0 plane by an unknown cube in general position when it is illuminated by a point-light source located at point L. Provide an algorithm for computing L from A, B, C, D, E, and F. You do not need to write out the final expression for L, but you should describe the construction process in sufficient detail to allow its implementation using known geometric constructions.
   


3. Explain the perspective projection.  What are the parameters that define a virtual camera?  Compare the perspective projection to the orthographic projection.  Explain the vanishing point.  How can perspective projective, coupled with a vanishing point be used to extract an approximate 3D model of the scene?  When will this work and when won't it work?
   


4. During his talk, GVU Distinguished Lecturer Alvy Ray Smith, said that graphics is not about vertices and polygons, but about PIXELs.  Do you agree with this?  Justify your answer with respect to the graphics pipeline.  Also, explain various ways to relate pixels to vertices/polygons.  What does texture-mapping and image-based rendering have to do with this?  Any relationship to Aliasing?
   


5. A square mesh with N vertices M polygons has been texture-mapped with a 512x512 image. Explain the following scenarios. Assume NO lighting variation and that the texture coordinates remain the same.

   a) Someone stretches one edge of this mesh so that one edge is twice as long as its opposite edge (like a trapezoid). Is the texture-map recomputed? How? Will it be smooth? What would be the aliasing artifacts, if yes, how would you get rid of them.

   b) The mesh is scaled by 2 (i.e. is twice as big). What happens to the texture-map? What kind of computation is needed to re-render a smooth texture?

   c) Would re-meshing and redefining texture coordinates help in any of the above two instances?

   d) Would interpolation help? If yes, describe one method for interpolation.

6. You are asked to write a textbook for visual computing (includes graphics, vision, rendering etc.).  Generate a Table of Contents.  Justify each listed topic in the Table of Contents and also the ordering of topics in the book.

A. ANIMATION

1. Suppose you want to create an animation of a marionette. What animation technique would you use? Describe in fair detail what you would have to do to create the motion (code or hardware). Explain why you believe this technique is the best one for creating the motion.
2. One of the papers on the reading list describes techniques for making groups of artificial creatures act in a collective fashion. Briefly describe how these techniques have been used successfully in commercial productions and analyze in depth where these techniques might fail and what modifications to the algorithms might help.
3. Camera motions in computer animations made by naive users are often unintuitive and disconcerting. One possible solution to this problem is to restrict the synthesized camera motion to those motions that could be performed by physical cameras in the real world with rotational and translational inertia. Would this be a workable solution to the problem? How would you implement it and what interface would you provide to the user?
4. Several researchers are currently exploring techniques that combine motion capture and simulation in some fashion. Outline three ways that these two techniques can be combined and explain what the key advantages and potential problems are with each technique.

  B. RENDERING

1. Your client is an architect who wishes to plan the look of a new conference room.  You are to create a rendering system that is based on radiosity that will allow the architect to see what the room will look like when illuminated by the lights in the room.  You are to make the program as interactive as possible for as many kinds of room changes as you can, perhaps by doing some pre-computations.  For each question below, either say how you could implement a given interactive capability or describe why it would be difficult to provide a given capability.  Your answers should tell for which of the changes do you not have to run radiosity from scratch.

   A. Can you provide an easy way for the architect to turn on and off particular lights that are at fixed locations?

   B. Can you provide dimmer knobs on the virtual lights?

   C. Can you allow the lights to be moved to different locations on the ceiling?

   D. Can you allow furniture to be moved around?

   E. Can you allow changes in the colors of the walls and furniture?

   F. Can you allow the camera position to be changed?

2. This question is about the relationship between the radiosity, reflectance and rendering equations.

   A. State each of these three equations, using whatever form or notation you prefer. Also give an intuitive explanation of what each equation means.

   B. What is the relationship between the rendering equation and the reflectance equation?  Be sure to include issues about visibility and the domains of integration in your answer.

   C. What is the relationship between the radiosity equation and the rendering equation?

3. Suppose that you are given a scan-line renderer that handles scenes with light-sources.  Also suppose you have a program that allows you to create pixel-wise averages of two or more images, producing a new image.

   A. How would you use these tools to create an image with an area light source? With motion blur? With depth-of-field?

   B. How would the images you create from part (A) differ from those created using distribution ray tracing? That is, what image artifacts would you see? What is it about ray tracing that allows better images to be created?

4. You have been given a procedural shader that creates a solid texture of wood in which there is considerable intensity differences between the dark and light bands in the wood. This shader is being used in a scan-line polygon renderer. When you use the wood shader to make a wooden horse model, the horse looks fine close-up, but far away the texture aliases horribly. How could you anti-alias such a procedural texture? Give as much detail as you can, stating all of the assumptions that you are making about the original shader. What are the pre-filtering, sampling and reconstruction methods that you use in your method?

1. We want to calibrate 4 cameras in a room (assume it is rectangular and has minimal furniture, and the windows have very thick curtains). All four cameras are the same. You are given a laser pointer, a very high wattage light (like a slide projector), a sharp cutting knife and a piece of cardboard. How would you calibrate these cameras? What kind of furnishing would cause problems? What kind of lighting?
2. When he visited us a while ago, Takeo Kanade described covering a hemispherical dome with dozens of inward-looking video cameras that record an event (such as swinging a baseball bat) from many different angles. He then showed that one could re-create the scene from any vantage point, even from positions where there were no cameras. Unfortunately, he did not tell us how he accomplished this.

(A) Describe a method for re-rendering a scene from an arbitrary viewpoint that was captured in this manner. Be sure to describe what data structures you use to store the scene information, tell how you would create these data structures, and describe how you would re-render the scene from your scene description.

(B) When re-rendering the scene using your method from the point of view of one of the original cameras, will your method produce the same view as the original camera captured? Why or why not?

3. Discuss feature matching vs. template matching for recognition. What do these terms mean and what are the basics of each (be very brief)? What are the strengths of one vs. the other? Which one is better for view invariance, why? How does this extend to time (i.e. gesture recognition?)? Based on these concepts, what then is an appearance model (both in space and in time). Does this concept o feature vs. template matching apply to matching in time?"
4. Explain how the ability to generate a movement can assist in perceiving it (this is called the "motor theory of perception"). How would such an internal model help a system understand where it is and how to move, etc., or know the trajectory of a ball thrown through the air so that it can be caught. What is an alternative to this approach to perception?