Spring 2001 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 (this year, there are only 2 listed):
A. Animation (Jessica Hodgins)
B. Rendering (Greg Turk)

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

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. Develop an algorithm that would identify which objec ts are visible from a given location X. Assume that objects are polyhedra, but need not be convex. Assume error-free arithmetic. We want absolute accuracy. Describe the overall high-level algorithm and also provide the details and constructions of all the steps that may not be obvious to a developer. Analyze the worst case complexity of your algorithm in terms of the number O of objects and of the average number V of vertices that each one of them has. Outline a different approach that would be much faster and would still guarantee a conservative solution (reporting correctly ALL visible objects and possibly including a relatively small number of invisible objects). Indicate which subareas of graphi cs and other fields are related to this problem and provide at least one reference to each

2. Consider a triangle mesh that forms a connected two- manifold with boundary (i.e. each edge has one or two incident triangles and the neighborhood of each vertex is homeomorphic to a disk or a half-disk). Propose an algorithm for addin g new triangles that would fill the holes in this mesh and produce a manifold mesh without boundary and without self-intersection. Provide precise definitions of the terms you will be using (such as the boundary of each hole) and define and prove properties that your approach will be exploiting.
3. Imagine a particle moving (jumping?) along a path de fined by points in the plane as follows: it stays for 1 second at the first point, then for 1 second at the second point, then for 1 second at the third and so on. To make the movement less annoying we apply the averaging operator to this trajectory: to get a new location at time t we take the average location along the input path over time interval t till t+1. Give a quick argument that by applying this averaging procedure several times we will obtain smoother and smoother trajectories. What curve are we going to obtain if we apply this operator once? Twice? Three times? (explain why).
4. a) During the German advance on Paris in 1940, the F rench Army were greatly hampered by the Nazis' effective use of camouflage. By painting their tanks and armored infantry carriers with a green that was carefully matched to the color of the Ardennes fores t, they were able to maneuver entire divisions without being detected. After the war, Baron Reynaud Gaspard de Bouvoir, whose chateau was overrun and briefly occupied, conceived of a remarkably simple idea to foi l such camouflage techniques in the future. His notion wa s to outfit soldiers with strongly colored eyeglasses. Monsieur le Baron reason ed that these glasses would provide its wearer with an a lternative trichromatic vision, enabling soldiers to d iscern between the forest and the painted tanks, whose colors appeared identica l to persons of normal trichromatic vision but whose sp ectral power distributions (SPD) were nearly certainly not identical.
   Is the baron correct? If so, for what k inds of lens coloration would the scheme work? If not, where did he go wrong? Justify your answer.

   b) Define the term "color gamut". < p> c) Explain precisely why we cannot print all col ors that appear on a CRT.

   d) If two people in different locations (say, a graphics designer and her customer) want to display an image o n their CRTs so that they can discuss it over the phone, can we guarantee that t he colors will appear exactly the same on the two CRTs if they physcially identical (ie. same make, model, year, etc.)? Why or why not?

5. In terrain visualization, a very large surface geome try (heightfield) must be textured with a large number of images derived from aerial photography. A typical terrain visualization user will have very high resolution geometry and/or airphotos for some areas of the Earth, and low resolution for the rest. Explain, compare, and contrast two major approaches to managing levels of detail in this context. Examine performance issues with respect to memory consumption and execution time, both during database creation, and during interactive database viewing.
6. Consider a surface S that is entirely visible from a viewpoint V. The surfac e may have several disconnected components and holes. S is separated from V by a plane P, w hich you may think of as a window or screen through which we see the surface. As sume that we make a single image of S using a regularly spaced array of pixels on P (the usual perspective image from V) and that for each pixel we store a dep th (distance to the surface) in a z-buffer.

   a) Define the term "topology of the surface"

   b) Explain why, in general, the content of the z-buffer is not sufficient to reconstruct the topology of the original surface.

   c) Provide a mathematical characterization of a general class of surfaces whose topology cou ld be correctly reconstructed from the z-buffer sampling. Specify your assumptio ns in terms of the scene parameters (bounding sphere around the surfaces, resolu tion of the z-buffer, and others that you should provide...). To simplify, you m ay initially assume that the S lies on a plane parallel to P and then explain ho w to deal with curved S.

   d) Suggest techniques for checking whether a given surface satisfies your characterization.

PART II: SUB-AREA QUESTIONS. ANSWER TWO OF FOUR QUESTIONS IN ANY TWO OF THE SUB-AREAS

A. ANIMATION

1. What exactly is a quaternion? (Describe it intuitively and in simple terms, provide a mathematical representation and give examples of how quaternions are u sed.).
2. One of the problems with motion capture is that it provides too much "realism" and animated motion produced via mocap is immediately identifiable as such. Hand animation, on the other hand, often produces a caricature of the character's motion with key features exaggerated. Explain how you might combine these two techniques to automatically produce caricature-like motion from motion capture data.
3. One of the main characters in the upcoming Monsters Inc from Pixar has a great deal of fur. Explain the problems in animating fur and how you would address those problems within the constraints of the Pixar animation pipeline.
4. In the animation and virtual environments that we would like to able to create, synthetic creatures must interact by colliding and pushing on each other. Using a naive algorithm, general object collision detection in a scene can require O(n^2) work per frame (where n is the number of polygons). Explain how collision detection might be performed more efficiently.

B. RENDERING

1. It is possible to modify the normal radiosity method to allow surfaces that have non-diffuse BRDF's. In classic al radiosity there is one unknown quantity for each patch ( its radiosity). For scenes with non-diffuse BRDF's, there are many - unknowns for each patch, one unknown for each of many small solid angles over the hemisphere surrounding a patch. Each unknown is the integral of outgoing radiance over this solid angle. This que stion is about setting up such a problem, still using a ma trix formulation.

   a) What are good choices for the solid angles around each patch, to use in defining the unknowns? Why would this be good choices?

   b) What would the matrix entries be in this formulation? What would replace the form-factors and/or the reflectance coefficients?

   c) What would the size of this matrix system be? Would it be a diagonally dominant matrix? How would the solution time compare to traditional radiosity?

2. You are designing a ray tracing renderer and you wi sh to include anti-aliasing of the image by super-sampling within a pixel.

   a) Discuss the merits and drawbacks of each of the following possibilities for filter kernels: impulse, box, bilinear, Gaussian, sinc.

   b) Describe how you would implement the anti-aliasing so that the user could have a choice of the filter to use.

   c) What is adaptive super-sampling, and how would it affect your implementation from part (B)?

3. Image-based rendering (IBR) systems differ in the n umber of sub-spaces of the 5D plenoptic function (radiance field) that they use.

   a) Describe a published IBR system that uses a 2D su b-space of the plenoptic function. How could you modify this system to use a 3D sub-space of the plenoptic function, keeping much of the same spirit of the original system? Give enough details of your new system that another graphics researcher would know how to begin implementing it.

   b) Describe any published IBR system, other than the one you chose in part (A), that uses less than the full 5D plenoptic function. How could you modify this system to capture the full 5D plenoptic function, keeping much of the same spirit of the original system?

4. In volume rendering there are image-order methods (such as ray-casting) and object-order methods (such as splatting). In principle these methods should give nominally the same results for the same levels of accuracy, but in practice they do not. Discuss the advantages and disadvantages of each class of methods and the artifacts that can result from each. Which artifacts can be removed, and how? Finally, give a detailed account of the complexity of the two classes of methods taking into account sub-sampling for compositing.