Spring 2003 Graphics Qualifier

THE EXAM HAS TWO PARTS

Instructions:  

Give detailed answers to questions mentioning all the assumptions you are making and be comprehensive in your answers showing the details of your approach and understanding of the problem.

GENERAL QUESTIONS:  Answer any 4 general questions.

SECTION I: COLOR

1.  Color.
a) What is the relationship between a color specified in the RGB, HSV and LAB color spaces?
b) If sunlight shines on a CRT display that is displaying digital images (photographs of natural scenes), what is the visible effect of the color appearance on the display?  Why?
c) If I asked the same question (what is the effect of sunlight) about images on paper, you could not answer the question.  Why not?  What additional information would you need to describe the effects of sunlight on printed images?  Is this a simple, hard or almost-impossible calculation?

2. Describe and compare four common "fast" (i.e. near real time) shadow techniques (projected planar shadows, stenciled shadow volumes, light maps, shadow maps).  Be sure to discuss the limitations of each technique, the simplifying assumptions each makes, and the minimum hardware required to implement them in near-real-time applications.

3. One of the simplest approaches to image-based rendering are planar imposters.  Unfortunately, imposters only work perfectly when viewed from a single viewing position.  As the relationship between the viewer and the imposter changes, errors in the quality of the imposter are introduced.
a) for some collection of geometry on which an imposter is to be based, where do you place the plane for the imposter?
b) what causes imposter error in a dynamic scene? (i.e., how do imposters simplify the rendering of complex scenes, and what are the implications of these simplifications in a dynamic world)
c) describe 2 approaches to adding depth information to planar imposters.  How do they improve the quality of the resulting scene, and what limitations do they still have?
4. At each vertex V of a triangle mesh, we store a function I(D) which for each direction D, returns the color that a viewer would perceive when looking at V from that direction. We say that the association of V with I is a surfel.
 
Discuss the relation between this representation and two other representations used in graphics: (1) a simple triangle mesh with surface normals and vertex colors and (2) a lightfield. (Explain how they are related, whether one is an approximation of another, and if so, what is the nature of that approximation).  In particular, explain how you would perform the following conversions
 - surfels to mesh
 - mesh to surfels
 - surfels to lightfield
 - lighfield to surfels

5. The accuracy of 3D from stereo images: Assume that you have two digital mages taken from known camera positions and orientations with a perfectly calibrated pinhole camera.  Assume that the two camera position are each specified by a local coordinate system, so that the camera is at (0,0,-1) and the screen of 2^24 pixels in each direction spans the square of [-1,1]x[-1,1] in the z=0 plane. You identify a feature on both images by selecting a single pixel through
which the feature is visible. Provide the geometric computation of the best estimate for the location of the feature in 3D.  Assume that the two lines (which start from the viewpoint and go through the center of the selected pixel) do not intersect.  Select your notation and provide the details of the geometric construction that you would implement to compute the feature location.  Discuss the sources and magnitude of the error associated with this calculation. Also explain the different applications of such a calculation in contemporary computer graphics.

6. Any triangle in the plane is a perspective projection of some equilateral triangle in 3D. Is this true or not?  Why?
 
SUB-AREA QUESTIONS
Listed below are Sections II through VI.  Answer 2 questions in any 2 sub-areas of your choice.

SECTION II: AR/VR

1.  Registration. When overlaying graphics on a user's view of the world using see-through head-worn displays, there are a variety of factors that contribute to registration errors.  We can roughly consider the registration errors to come from tracking error, calibration error, and system latency.  Consider only system latency, and discuss how you might counter the effects of system latency in an AR system.  Discuss both system that use video see-through and those that use optical see-through displays.  For any solutions you propose, be sure to discuss the pros, cons, and simplifying assumptions of each.

2.  Tracking.
a) Summarize the differences in tracking requirements for VR and AR.
b) For each of the commonly used tracking technologies, discuss the pros and cons of each for use in VR and AR applications.

3. Optics.
Explain the design challenges and tradeoffs that must be confronted when designing a head-mounted display for: 1) VR use and 2) AR use In particular, describe how a VR HMD may or may not be different from an AR HMD. Since with AR, the method of augmentation will inform the HMD design, be explicit about this in your discussion.  You must be sure to consider all of the gear that a user may wear on his/her head.

4.  While VR has not lived up to the original "hype" surrounding it, there have been some important successes in the application of VR technology.  The quality of the graphics is often blamed for VR not achieving more widespread success, but this is an oversimplification.  Clearly, both the technology and the characteristics of the application domains both play a part in the success of a VR application.  Using at least 3 examples of both successful and unsuccessful VR applications, discuss the characteristics of those applications, and the interplay
with the input and output technologies, that led to these successes and failures.

SECTION III: ANIMATION

1.  A director wanted a realistic animation of an ARM. This arm is fixed at the shoulder, with 2 links and a joint between.  This arm needs to (a) juggling motions, (b) tasks of picking up and moving objects, and (c) swinging arms while walking. Another team is responsible for the wrist, so for this task assume the wrist is fixed.  3 different animators worked on the project.  One used key-framing and with interpolation, 2nd used motion capture with 3 points tracked, and the third used simulation.  All of them animated to the same task (i.e. the director provided explicit timings and required motions), and the animators were very talented. Just looking at the output trajectories of all the three animators, it is hard to distinguish which method was used for which animation.   How would one analyze the three different outputs to figure out which method was used to generate which output?  State briefly how would this differ if the goal was to animate cloth using the same three methods and then compare.

2.  Compare the Baraff & Witkin and Choi & Ko cloth papers. Discuss their integration methods and more appropriately the difference in modeling of physics of the cloth.  What exactly is the difference in formulation?  Baraff & Witkin talk a lot about not wanting to deal with Penalty methods, while many other simulation methods really rely on them. Which is a more stable system of the two?  What about time step sizes between the two?  Do you think Choi & Ko is feasible/correct?  Explain.

3.  After much effort (which included many hours of mocap of an actor), a motion capture tech working with an animator, was able to capture motions that they desired.  It had all the perfect timing, and it was easy to cleanup the footskate etc.

When the data was sent to the animation house, the animator found several gaps in the data where some of the frames were just deleted/missing.  The motion capture tech and the animator are now faced the task of filling in these gaps as calling in the actor is too expensive.  What are their choices?  (Hint: Exemplar-based OR Simulation, OR both).  Assuming that some of the motions are repetitious (i.e., walking/running) and some are very dynamic (i.e. jumping / kicking / hitting objects).  Suggest methods and state which one is better and why?  Also state what is really possible.  How big should the gap be that makes any of these efforts impossible?  Why is simple geometric interpolation not sufficient?  Explain in detail with algorithms.  Feel free to make assumptions to help with your exposition and use drawings (hand-drawn OK).

4.  For the Lord of The Potters movies, the producers decided to model some of the creatures in clay and then scanned these in to generate models.  Sometimes it is possible to shape these clay models in various poses and scan in separate poses as keyframes for interpolation, except what you have is 3D meshes that one needs to interpolate between.  In some instances the animators had stock footage of a real person moving (say maybe from mocap or by rotoscoping) that they wanted to map on these creatures, for example to make them walk.  What would the modelers animators have to do? How can they provide for interpolation between 3D meshes and how can they control the meshes using other form of data?  Don't worry the modelers are very good at dealing with the meshes, so you should concentrate on how the mesh will move and how to control the speed of these movements (i.e. what needs to be done to allow for keyframing, motion retargeting, and maybe even simulation).

SECTION IV: MODELING

1. Is the surface area of an isosurface extracted using the Lorensen's marching cubes algorithm a piecewise polynomial function of the isovalue? What is the degree of the polynomial pieces?  Explain your answer.

2. Describe an incremental algorithm for computing the convex hull of a number of points in 3D. What is the running time of your algorithm?

3. Consider a manifold mesh with no boundary. Let's call a closed path (loop) on this mesh nontrivial if cutting the mesh along it yields just one connected component.  Characterize meshes for which nontrivial loops exist.  Design an efficient algorithm which finds a nontrivial closed path or reports that no such path exists.

4. Fixing a self-intersecting deformed surface: A triangle mesh that was initially homeomorphic to the surface of a ball has been deformed by a space warp. Now it self-intersects. Explain in details how you would compute the self-intersection and how you would construct a manifold triangle mesh that represents the watertight boundary of the new solid that corresponds to the deformed shape and may have a different topology. Discuss what type of topological changes your algorithm can deal with.

SECTION V: VISION

1. Photometric stereo is a technique for recovering the shape of an object (its needle-map) from multiple images acquired under different lighting conditions using a single fixed camera. Why does the conventional technique assume that the object is Lambertian? What would happen if this technique were applied to a spherical mirror? A more realistic reflectance model for painted or plastic objects is the Phong model, which combines Lambertian reflectance with a specular lobe. Discuss how a conventional photometric stereo algorithm could be extended to cope with objects that follow a Phong-shading model. Be as concrete as possible.

2. Recently there has been considerable interest in image-based rendering techniques based on the concept of the \emph{light field} (or Lumigraph), a 4-D representation of the flow of light through unobstructed space. With sufficient computational resources it is possible to imagine generating a light field in real-time from an array of cameras and rendering interpolated views at video rates. As cameras and displays become sufficiently miniaturized and low-power, this trend may make it possible to realize the long-held dream of a cloak of invisibility, by appropriate capture and rendering of rays of light at the boundary of an enclosing surface. Sketch out the design of such an invisibility device. Make any necessary simplifying assumptions and assume sufficient computational power and sensor/display technology. Be as concrete as possible about the algorithmic
details.

3. PCA is a standard dimensionality reduction technique which has been applied in a variety of vision domains from face recognition to texture analysis. From the standpoint of pattern classification, what are the advantages and disadvantages of PCA? Discuss the computational issues that arise in applying PCA to image data. Suppose that the input for a particular object detection task is a binary image. (You can assume that the image has already been segmented so that all of the pixels come either from the target of interest or from the nontarget class). Give specific examples of binary images (for object and non-object classes) for which PCA would work well and for which PCA would work poorly. Give examples of image classes for which PCA works well and explain why. What alternatives to PCA are there for situations where it does not work well?

4. How can factorization-based structure-from-motion approaches be extended to non-rigid scenes? If U and V are the measurement matrices for the first and second components of measured feature points in an image sequence, describe the qualitative difference between using [U|V] on the one hand, and [U'|V']' on the other hand. How are these matrices factored and what are the rank constraints on them?

SECTION VI: VISUALIZATION

Scalable Volvis
Volume visualization tends to deal with large volumes of data. (Why is that?) Describe in detail an approach that could produce interactive visualizations for a scalably large volume of data (one that could handle volumes of data that might be too large to reside in memory). Such an approach would have to have appropriate data structures coupled to appropriate rendering techniques. Explain.

InfoVis
In information visualization, one often hears of "focus + context".  Describe what this is and why it is important. Give several examples of its use. Discuss thoroughly how one would set up a general and interactive focus + context capability.

Navigating Collections
Suppose that you had a collection of 3D objects (e.g., buildings or statues in a sculpture garden) that you wanted to navigate around freely, coming in for close-up views or drawing back for overviews. How would you organize these objects for such an interactive visualization? Would you need different techniques for overviews or close-ups; why or why not?

Dataflow
Dataflow environments are said to be powerful and flexible tools for visualization. Why is that? Describe in detail the structure and use of such an environment. What are the drawbacks? Suppose you have a "visual steering application" that closely coupled a simulation to visualization (e.g., a weather simulation coupled to visual results). Parts of the simulation and the visualization could be parallelized.  At what level, if any, could this be done in a dataflow system and how?