Spring 1999 Qualifier: Graphics & Visualization area

The College of Computing research and educational activities in the area
called "Graphics&Visualization" spans most aspects of Geometric and Visual
Computing.  Although we expect all students in this area to have a broad
understanding of  the imaging principles and of the basic geometric
representations and algorithms, we can no longer expect them to cover in
depth the subareas of this mature and rapidly expanding field. Therefore,
we have decided to structure the qualifier into two parts as follows.

PART 1 - GENERAL 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 7 listed below (with the names of the coordinated faculty).

           A.Animation (Jessica Hodgins)
           B.Modeling and Geometric Computing (Jarek Rossignac, Chuck Eastman)
           C.Medical Imaging (Norberto Ezquerra)
           D.Rendering (Greg Turk)
           E.Virtual and Augmented Reality (Larry Hodges, Blair MacIntyre)
           F.Vision and Image-Based Rendering (Irfan Essa, Thad Starner)
           G.Visualization (Bill Ribarsky)

In each selected sub-area, the candidate must answer 3 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, Modeling and Geometric Computing: B1__, B2__, B3__, B4__
__ Area C, Medical Imaging: C1__, C2__, C3__, C4__
__ Area D, Rendering: D1__, D2__, D3__, D4__
__ Area E, Virtual and Augmented Reality: E1__, E2__, E3__, E4__
__ Area F, Vision and Image-Based Rendering: F1__, F2__, F3__, F4__
__ Area G, Visualization: G1__, G2__, G3__, G4__
_________________________________________________________________
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, text books, and papers, provided that you
include in your answer the references that you are using.

------------
GENERAL QUESTIONS
1) Provide examples of the use of sampling techniques for representing and
computing 3D shapes, images, or animations in each one of the following
areas: 3D modeling, rendering, animation, medical imaging, video
understanding. With each example, explain how the samples are interpolated
to infer a continuous representation and illustrate the undesirable
consequences of too coarse a sampling. How are these effects related to
aliasing? Suppose that the data is acquired through a process that
generates samples that are not uniformly distributed (in time and/or in
space).  Explain the additional difficulties and how you would handle them.

2) Let A+tU denote the instance of an object A translated by tU, where t is
a scalar and U is a constant vector. Similarly, consider B+tV to be the
instance of object B translated by tV. (In short: A and B are moving at
constant speeds along straight trajectories without rotating.) Assume that
both A and B are represented by the list of their bounding triangles and
that they are initially disjoint at t=0. Explain how to compute the
smallest value of t for which they collide. Describe the applications and
problems for which such a solution is needed. Explain its limitations.

3) Consider three representation of a polygon P in two dimensions: a list
of vertex loops, a BSP tree, and a quadtree. Describe the algorithms for
deriving the BSP tree and the octree representations from the vertex loops.
Explain how to test for point-in-polygon inclusion using each one of these
three representations. Compare the costs and accuracy tradeoffs.  Propose a
combined representation that reduces the expected cost for testing the
inclusion of a random point.

4) Consider two competing techniques for rendering constant-color,
flat-shaded triangular meshes in 3D: (1) the standard triangle
scan-conversion and (2) casting a ray from the eye through each pixel and
finding the triangle where the ray fist hits the surface. Compare the costs
of both approaches in terms of the number of triangles and the image
resolution. Explain all the factors (and the associated assumptions) that
make scan-conversion more efficient on contemporary hardware and describe
all the acceleration techniques for scanline-based triangle rendering that
do not require spatial data-structures.

5) You are given a set of 3D points P that have been sampled on a curved
surface. Discuss various ways of fitting a surface through these points.
What assumptions need to be made about the initial set of points?  What
geometric primitives can be used?  What metrics are useful to test
"goodness" of fit? Compare these fitting approaches in terms of their
computational efficiency and of the smoothness of the fit. How would you
address the issues of noisy data and inaccurate computation?
 
6) You are creating a poster for the movie "Raise the Titanic", and to do
this you need to convert a model of the Titanic that is described by cubic
Bezier patches into polygons.  Because the ship is large, you want to
create a view-dependent version of the model for a specific viewing
position so that all the polygons are roughly the size of a pixel.  The
image you create from this viewing position will use perspective, so nearby
polygons should be larger than polygons that are farther away.  Describe an
algorithm to solve this.

------------
AREA A. Animation

A1) Consider two instances, Sa and Sb, of an object  S, each defined by
applying to S the corresponding rigid body transformation, Ta and Tb.
Describe how you would represent Ta and Tb and how you would compute a
rigid body transformation T(u) that would smoothly interpolate between Ta
and Tb as u varies between  0 and 1. Define "smoothness" in this context.
Discuss the properties of your interpolation (is it unique, does the motion
depend on the choice of the coordinate system). Comment on other possible
interpolation choices . Which interpolation would you use to produce a
smooth motion that interpolates a larger series of instances (position and
orientations) of S.

A2) Given a planar, two-segment articulated system, describe precisely a
kinematic and inverse-kinematics formulation for this system. Explain but
without full mathematical detail what the dynamics of this system is, how
you would compute the inverse dynamics, and what a simple control scheme
might be.

A3) Dynamic simulations rely heavily on the use of numerical solutions to
the systems of equations of motion. Explain two different integration
techniques and explain under what circumstances each might be the right
choice.

A4) Describe how aliasing occurs in the context of animation. What
techniques are available to reduce or prevent this problem?

------------
AREA B. Modeling and Geometric Computing

B1) Consider a simple triangle mesh that is homeomorphic to a sphere. We
want to represent it by a half-edge data structure. Describe the data
structure (use a figure). Explain how it may be efficiently constructed
from a triangle "soup" (a list of independent triangles). Explain how it
may be used to estimate the normals at the vertices, to derive long general
triangle strips (which may include swaps), and to simplify the model by a
series of edge-collapse operations.

B2) A surface may be represented by an implicit equation or by a parametric
mapping from the plane. Explain precisely how each of these representations
may be used to represent boundaries of more complex 3D shapes. Discuss the
advantages and drawbacks of each representation for the following tasks:
(a) point-in-object classification, (b) ray-tracing, and (c) interference
detection.

B3) Discuss the various ways of measuring the discrepancy   between two
polyhedral sets  in 3D (providing mathematical definitions and high-level
algorithms). Explain the advantages and limitations of each discrepancy
measure and point out which application they are best suited for.

B4) Present several technique for designing 3D shapes through an
interactive graphic interface. Distinguish techniques that operate on the
surface from those which manipulate volumes. Discuss the strength and
limitation of each technique (for instance its ability to change topology),
its dependency on  complex geometric calculations, and the applications for
which it is best suited.

------------
AREA C. Medical Imaging

C1) Describe the major imaging modalities, contrasting the principal
attributes between the resulting imagery (for instance, resolution,
signal-to-noise characteristics, soft-versus-hard tissue contrast,
measurements of structure versus function, etc.). (Major modalities include
planar X-ray, ultrasound, magnetic resonance, X-ray computed tomography,
positron emission tomography, and nuclear scintigraphy.)

C2) Enhancing an image usually attempts to reduce noise, amplify certain
frequencies, or improve visual contrast. In this context, describe:
histogram equalization, low-pass filtering, high-pass filtering,
convolution, first-order derivative filters, second-order derivative
filters, and windowing?

C3) What exactly is the Fourier transform (mathematically and intuitively)?
Give examples and illustrations of 1D signals that undergo such a
transformation. What advantages and disadvantages are there regarding the
use of signals or images (or volumes) that are transformed?

C4) A long-standing problem in medical imaging is that of image
segmentation: extracting and/or identifying different features within an
image or 3D dataset. Describe and discuss the advantages, limitations and
contrasting characteristics of the following segmentation methods:
connected component labelling; watershed anaylsis; anisotropic diffusion;
mathematical morphology; model-based matching; knowledge-based processing.

------------
AREA D.Rendering

D1) Assume that you are writing a scanline-based polygon renderer, and that
you plan to incorporate very high quality 2D texture rendering. Speed is
not a concern.
  D1.a) Describe the highest quality texture mapping method that you can
come up with.  It should be free of aliasing, blurring and other artifacts
as is possible.  Include in your description how it handles the case when
many texels fall in one pixel, and also the case when the texels become
much larger than a pixel.
  D1.b) Describe the shortcomings of MIPmap texturing as compared to your
method.

D2) Depth-of-field and motion blur are two effects that distribution
raytracing handle elegantly.  This question explores these effects in a
light field renderer (the image-based rendering technique).
   D2.a) Describe the process of rendering an image (given a camera
position) using a light field representation of a scene.
   D2.b) How would you modify a light field renderer to create
depth-of-field effects (that is, partially out-of-focus images)?
   D2.c) How can you create motion blur in a light field renderer?

D3) This question is about bidirectional reflectance distribution functions.
   D3.a) What is the domain and range of a general BRDF?  What kind of data
structure would you use to store a BRDF?
  D3.b) You are writing a Kajiya-style Monte Carlo ray tracing renderer
that accounts for indirect lighting effects.  Assume a ray from the eye
reaches a surface.  Describe how to choose a direction to shoot a ray from
this surface according to the surface's BRDF. That is, the probability
distribution of the ray's direction should be proportional to the BRDF,
given the direction of the ray from the eye.

D4. This is a question about shadows.
   D4.a) Describe TWO different ways to render images with shadows.
   D4.b) For each of the above two methods, say what their shortcomings
are. These might include aliasing, blockiness, lack of penumbra, etc.
   D4.c) How can you overcome the shortcomings of each method, perhaps by
modifying the algorithm or using more compute cycles?  Which shortcomings
are not fixible, and why?

------------
AREA E.Virtual and Augmented Reality

E1. Describe what we mean by each of the following four ways of
conceptualizing a virtual environment: (a) Hardware perspective, (b) User's
perspective, (c) Application designer's perspective, (d) Classification of
environmental activity. Explain why these four aspects are important and
how you would use them to discuss the early design stages of a VR system
for Electronic Shopping.

E2. 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 stereoscopic voxels? What are
some of the factors that affect "ghosting" in a time-multiplexed
stereoscopic display system?

E3. What are the effects (both pros and cons) of having the real world be
visible in an Augmented Reality system? Discuss the technologies used to
produce such viewers and explain the various research challenges in
Augmented Reality. For each research challenge, point to the best-to-date
results and suggest avenues for further research.

E4. Four hardware approaches to building virtual environments are
head-mounted displays, the CAVE, the BOOM, and the Immersive Workbench.
Describe the basic components of each approach and compare them based on
whatever criteria you think is appropriate.

------------
AREA F.Vision and Image-Based Rendering

F1) Define disparity? How is it used in determining scene characteristics?
How does it hurt in determining scene characteristics?  Discuss limits on
disparity as applied to stereo systems. In a stereo system, what is the
ideal way of positioning cameras relative to each other?  How would you
position 3 cameras? 4 cameras? Discuss the advantages and disadvantages of
each configuration.

F2) The sun is out is shinning brightly.  It is about 3pm, and there are no
clouds.  You are in an open field and there are many telephone poles.  You
want to generate a simple 3D model of the car.  How would you do it using
the sun?  What are the limitations of this method?  What can you measure
and what you can't? Discuss the variabilities associated with sun position,
car position and pole position.  Justify your answer within some
assumptions.

F3) Explain Kalman Filtering (KF)?  Why is it so useful in vision? What
assumptions are usually made to apply KF to vision.  Work through a typical
example where KF would help.  In what scenarios would it fail.  What are
the primary linearizing assumptions used in vision? Can KFs be used in
rendering? In animation?

F4) Describe the various shape from X methods. Where X is variation of some
type.  For example, shape from shading.  Be brief.  Now discuss the
validity of several of these methods as applied to Image-based Rendering
Methods. What is the difference?  Choose your favorite Image-based
Rendering approach and discuss what aspects of shape from X methods was
used. If yes why? if not, why not.  Describe the methods in brief detail.

------------
AREA G.Visualization

G1) Describe in detail the different approaches to volume visualization
(surface rendering, volume rendering, and texture memory). Discuss the
advantages and drawbacks of each.

G2)  Compare and contrast scientific visualization and information
visualization. Do they use variations of the same methods?  Are different
approaches or techniques needed in the two fields?  Where and why?

G3) Describe in detail a principal-component or eigenvalue approach to
representing tensor fields.  Assume that these are general tensor fields.
How would you construct and handle the symmetric and anti-symmetric parts?

G4) Consider a multidimensional, time dependent collection of spatial data.
Describe two separate methods to visualize this multivariate, temporally
evolving dataset.