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 amongst the 3 listed below:
A. Modeling and Geometric Computing (Jarek Rossignac, Chuck Eastman)
B. Rendering (Greg Turk)
C.Virtual and Augmented Reality (Larry Hodges, Blair MacIntyre)

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, Modeling and Geometric Computing: A1__, A2__, A3__, A4__
__ Area B, Rendering: B1__, B2__, B3__, B4__
__ Area C, Virtual and Augmented Reality: 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 "For each vertex V of polyhedron P do if 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. Remember that it is always a good idea to state what your assumptions are, especially if you think the question can be interpreted several ways.

1.     Explain and justify the perspective transformation used in contemporary graphics pipelines. In particular, answer the following questions:

• What parameters define the transformation and what do they represent?
• What is the image of a point (x,y,z) by such a transformation?
  
• Why is such a transformation used instead of simply casting rays from the eye through each pixel and computing their intersections with the object?
• Why does the perspective transformation not map the z coordinate to zero?
• Explain what could go wrong if we used a perspective transformation that would correctly map x and y, but leave z unchanged.
• Where are points at infinity mapped?
  

2.     Consider a set of triangles in three-space. We want to discuss when they form the boundary of a manifold solid.

• What condition would one need to impose on the triangles for their union to be a valid boundary of a manifold solid, regardless of the chosen data structure? (Remember that the union of two sets is independent of their overlap.)
  
• Describe a simple half-edge data structure that accelerates the traversal of the boundary from one triangle to another and illustrate its use for estimating vertex normals, for building triangle strips, and for simplifying the mesh through a series of edge-collapses.
  
• Explain the additional conditions that the use of your data structure imposes on the triangles. Explain how you would test these conditions.
  
• Assuming that the above conditions are verified, explain how you would compute the number of bodies (maximally connected components of the solid).
  
• Explain for each component how you would compute the number of its handles and holes.

3.     Provide a complete description of Binary Space Partition Trees as they are used for visible surface determination. Include pseudo-algorithms for how a BSP Tree is constructed from a boundary representation, how the BSP tree is used when an image is rendered, advantages and disadvantages of BSP trees compared to other visible surface determination techniques, and any other details that you think are important.

4.     List the major steps in a typical rendering pipeline and, for each one, point out which (scene, lighting, viewing) parameters influence its performance. Define precisely conditions under which using texture mapping instead of geometric details will result in improved rendering performance. Also define conditions for levels-of-details techniques to improve performance. Discuss the range of these parameters for practical applications of 3D graphics found currently in the consumer market and conclude on the expected benefits of texture mapping and LOD in these situations.

5.     Octrees, uniform cell decomposition, and bounding hierarchies are three data structures that can help accelerate ray tracing.

• Describe how each of these data structures is constructed for a scene that is a collection of polygons.
  
• Describe the algorithms for intersecting a ray with the scene using each of the three data structures.
  
• Analyze the computational complexity of performing a ray/scene intersection for each of the methods. State any assumptions that you make about the collection of polygons that make up the scene.
  

6.    Aliasing is a problem that we constantly encounter in computer graphics.

• What is aliasing and where does it come from?
  
• Give examples of both spatial and temporal aliasing that can occur in computer graphics, and discuss how each can be overcome.
  

A1.     A set of N triangles splits the 3D space into regions (a region, also called a 3-cell, may be formally defined as the maximally connected component of the difference between the 3D space and the union of all the triangles). Assume for simplicity that all triplets of triangle-supporting planes intersect at a single point.

• What is the maximum number of regions (prove or explain your derivation)?
• How would you represent each region so that you can efficiently test an arbitrary point for inclusion in the region?
• Produce a high-level description of a practical algorithm that identifies all the non-empty regions and builds their representation (as suggested above).

A2     Let C be a polygonal curve in 2D that joins point A to point B.

• Explain how to produce a polygonal approximation G of C that would remain within a given tolerance from C but would have significantly fewer vertices.
• Explain how you define the tolerance and provide a high-level algorithm for testing whether one polygon is within tolerance from another.
• Discuss the pros and cons of the various simplification and fitting strategies that you can think of for building G.

A3.     Discuss five precise representations of a polygonal region:

• CSG,
• BSP,
• Boundary,
• Recursive difference of convex sets: A - (B+C+D), where A is a convex polygon and where B, C, and D are represented in a similar manner as differences between a convex set, and so on, recursively if necessary (- and + denote Boolean difference and union)
• Triangulation

• For each representation:
  • Suggest a simple data structure
  • Explain in detail the algorithm for testing for point-in-polygon inclusion

• Outline the algorithms for the following representation conversion:
• CSG to Boundary
• Boundary to BSP
• Boundary to Recursive difference of convex sets
  

A4.     Consider two poses of an object. Each one is defined by a 4x4 matrix that represents the rigid-body transformation that moves the object from its initial position and orientation to the desired pose. Explain the meaning of the different entries in the matrix. Why do people use a 4x4 matrix? What are its drawbacks and advantages? Given the matrices for the initial and final poses, we want to compute and animate a minimum-angle rotation and minimum displacement translation that move the object from the initial to the final pose. Describe an algorithm for doing so and include the details of the geometric calculations using matrix and vector notations.

RENDERING

B1.     Discuss the advantages and limitations of Image-Based Rendering techniques based on the concept of Lightfield (also called Lumigraph). Explain how the data for such a concept is acquired, stored, and used for interactive graphics. Explain how Lightfields are related to panoramas and to the plenoptic function. Specifically, explain what conditions are imposed on the viewer by the choice of using Lighfields. Discuss the advantages and drawbacks of light fields over polygon shading, radiosity, raytracing, and texture mapping.

B2.     The Rendering Equation.

• What is the Rendering Equation, and what do each of the terms mean?
  
• Equation 16.20 on page 734 of Foley & van Dam is meant to describe the shading at a surface for multiple light sources. Relate as many of the terms and symbols in it as you can to parts of the Rendering Equation. What assumptions are being made in order to simplify the Rendering Equation into the form of 16.20?

B3.    This question explores the flexibility of two common approaches to direct volume rendering, namely Levoy-style ray tracing and Westover-style splatting.

• You wish to augment a volume renderer so that it accepts and renders polygons at the same time as it renders volume data. Volume data and polygons should even be allowed to interpenetrate each other, and you want your renderer to gracefully handle this, including proper occlusions between the two types of data. Describe how you would accomplish this for each of a ray tracing and a spatting volume renderer.
• Assume that both your spatting and ray tracing volume renderer use trilinear interpolation as their reconstruction filter kernels. You wish to change the filter kernel to a Sinc function that has a radius of three voxels. How can you change each of the two volume renderers to use this filter kernel?
  

B4.     There are many occasions in rendering where the three steps of pre-filtering, sampling and reconstruction are performed. Select TWO rendering techniques from the following list: 2D image texture mapping, volume rendering, light field rendering, and ray tracing.

• For each of the two techniques that you select, describe in each instance how pre-filtering, sampling and reconstruction are performed.
  
• Say what it means algorithmically to omit the pre-filtering step for each of your two chosen techniques. Describe the consequences of doing no pre-filtering for each of the techniques. That is, what artifacts will the resulting images have?
  
• For each of the two techniques, describe a POOR choice for a reconstruction filter, and tell what you would need to do algorithmically to use this filter. Say what the effect of doing so would be on the rendered images.
  

VIRTUAL AND AUGMENTED REALITY

C1.   a) There are several different tracking technologies used by virtual and augmented reality. Describe the advantages and disadvantages of each of the following technologies: magnetic, ultrasonic, gyroscopic, vision (using fiducial marks).

    b) Compare the tracking requirements of AR and VR, and discuss which of the above tracking techniques are most appropriate for each (and why).

    c) Recently, there has been research in creating hybrid trackers that combine two or more sensors to form a single tracker that has some of the benefits of each sensor, while avoiding the disadvantages. Most of these efforts combine vision with something else: describe an example hybrid vision tracker (at a high level) and discuss the advantages of the component sensors that are desired, and the disadvantages of the component sensors that your example hopes to avoid.

    d) The Intersense hybrid tracker does not use vision, but combines a variety of inertial, magnetic and tilt sensors with an ultrasonic sensor. The ultrasonic sensor has a very low accuracy (2-3 cm): why is this acceptable in the context of this hybrid tracker?

C2.     Virtual Reality/Environments may be viewed as an application area that creates challenging research problems across a number of fields. For example, some of the issues in the design of head-mounted displays are usually addressed in an academic environment in a physics or optical engineering department while others may be research issues for industrial engineering or industrial psychology. Describe three different research problems in the area of Virtual Environments that would also be appropriate research problems in three different areas in the College of Computing (areas are Learning Sciences and Technology, Computer Architecture, Database Systems, Graphics & Visualization, Human-Computer Interaction, Intelligent Systems, Networking & Communications, Programming Languages & Compilers, Software Methodology & Engineering, Systems, Theory). For each problem describe why it is of interest to VR and why it is a research problem in an area of computing.

C3.     Give complete description of a hierarchical tree structure that could be used to represent the relative locations and orientations of all the components of a virtual environment, including transmitter, receivers, user, and geometric objects in the world. From your example describe how you would compute the transformations that represent an object’s position if the object were to begin on a table in the scene, be picked up by the user’s hand, then moved to and deposited on a second table in the scene.

C4.     Answer the following questions with respect to VR display systems:

• What are the three basic components of a visually coupled system?
• What are some of the differences between LEEP optics and a Fresnel Lens optical system in a head-mounted display.
• Give a short description of how time-multiplexed stereoscopic display systems work.
• Explain what we mean by the accommodation / convergence conflict in a stereoscopic display?
• What are some of the factors that affect "ghosting" in a time-multiplexed stereoscopic display system?