Graphics & Visualization (Geometric and Visual Computing) Fall 2002 Qualifier Exam
 
INTRODUCTION

Each candidate will have to answer 4 out of 6 questions from the General part.

In addition, each candidate must select 2 sub-areas amongst the ones listed below and will have to answer 2 out of 4 questions in each sub-area.

Sub-areas:

1. Modeling and Geometric Computing
2. Rendering
3. Vision and Image-Based Rendering
4. Visualization
5. Virtual and Augmented Reality

Students will be allowed to use books, notebooks, computers, and Internet resources. They will not be allowed to ask anyone for help, whether in person, by phone, by Email or any other means.

*************************************************************************************************************
GENERAL PART

(1) Color

Visible light corresponds to the visible wavelengths of light.  A single color is most accurately represented as an continuous function of the visible spectrum; for practical purposes, though, we typically represent colors using three values.

(a) Why does this work?  How do we convert from a continuous power distribution to a color "triple"?

(b) Do any distributions look the same?  Why or why not?

(c) When rendering, we typically use this simple representation of color (triples in some color space).  When we use complex illumination equations, such as in a modern ray tracer, are the resulting colors "correct" (based on the initial colors and the effects we are simulating with our illumination equations)?  Ignore the approximations introduced by any particular lighting model; your answer should focus on the effect of representing color as a triple in some color space.

(2) Global Illumination:  Antialiasing and Ray Tracing

A significant problem with ray tracing (backwards ray tracing, or Whitted ray tracing, in particular) is that it samples only those properties of the surfaces that can be simulated by a single ray passing through a pixel and interacting with the scene.  Much research has gone on, attempting to understand how to improve on the basic model while still being computationally tractable.

Compare adaptive super sampling, path tracing and distributed ray tracing, summarizing how each works, how each tries to remove aliasing effects from the Whitted model (i.e., what additional effect do they allow, or problems can they solve), how they remain computationally tractable, and their relative cost.

(3) Collision

Let P[j]=S[j]+tV[j], for j=1,2,3 and 4, be four moving vertices. How would you compute the time t when the edges (P[1],P[2]) and (P[3],P[4]) collide? How would you apply this solution for predicting the collision between two triangle meshes, each moving at constant velocity?

(4) Silhouettes

Consider a manifold triangle mesh. An edge is said to be silhouette, if it bounds a front and a back triangle. Provide a test for identifying edges that cannot be silhouettes if the viewpoint is
constrained to lie inside the triangle (A,B,C).

(5) Perspective

Is the perspective projection of a non-obstructed sphere a disk? Prove your answer. The perspective transformation of a sphere is a surface in the 3D transformed space. Is it a sphere? Is it a quadric?

(6) Z-buffer

When I have set my near clipping plane to zero and the far clipping plane to 2^23, I had some problems in my OpenGL shaded images due to z-buffer contention. Explain what was going on. What will have more effect on the z-buffer accuracy: moving the far plane to 2^16 or moving the near plane to be at twice further away from the eye than the screen is. (For simplicity, assume that the screen is at distance 1 from the eye.)
 MODELING

VOLUME: Given a triangle mesh that bounds a solid S and assuming infinite precision arithmetic, provide a simple and fast algorithm for computing the exact volume of S. Include the details of the geometric calculations. Can you extend this approach to the computation of the volume of the intersection between two solids bounded by triangle meshes?

COMPONENTS: Consider a triangle soup, i.e. a set of triangles that represent a triangulation of a multi-component manifold surface that bounds a portion of space S. Design a practical algorithm for computing the number of connected components of S and the genus of each component.

RAYS: Let M be the union of all the rays that miss a shape S. Propose a practical algorithm for testing whether S is the complement of M. Illustrate it on: a convex set, a torus, the union of two balls.

SUBDIVISION: Consider the following two-step "split&tweak" subdivision process for a closed loop polygon: (1) insert a new  vertex in the middle of each edge, and (2) move the old vertices
half-way towards the average of their neighbors. Repeated applications of it transform the polygon into a uniform cubic B-spline of which it is the control polygon. Prove it.
 RENDERING

1. You are interested in non-photorealistic images of models that are represented as a collection of triangles.  In particular, you wish to draw the silhouettes of such objects with dark lines.

a) Given a camera position C, describe what it means for an edge of the model to be a silhouette edge.

b) Give TWO algorithms for rendering a polygonal object where the silhouette edges are shown as dark lines.  Be sure both algorithms properly handle hidden surfaces.  Your algorithms may differ in whatever way you like, such as using different ways to determine which edges are silhouettes or in the manner that each edge is drawn.

c) How would you perform anti-aliasing for each of your above two methods for silhouette drawing?

2. Classical (Whitted-style) ray tracing does not capture all of the illumination effects of real scenes.

a) Give two different global illumination effects that are not correctly captured by Whitted-style ray tracing.  Say why classical ray tracing does not capture these effects.

b) Describe a global illumination method that captures both of the effects you discuss in part (a).  Tell why the method you describe does in fact capture these effects.

3. You are interested in showing motion in a static image using motion blur.

a) Give an algorithm for producing motion blurred images of a moving object.

b) Will your algorithm create the same image as a real camera?  For example, does your method treat hidden surfaces correctly?  Defend your answer.

c) Describe how the terms "motion aliasing" and "reconstruction filter" relate to your answer of part (a).

4.  This question investigates extensions to volume rendering.

a) Describe a method for rendering volumetric data directly, that is, without converting it to polygons.

b) How would you modify the algorithm from (a) to perform motion blur?  Will this work correctly for translucent volumes?

c) How would you modify your volume renderer if you wanted to get global illumination effects such as color bleeding and indirect illumination?

 VISION

1) Describe the epipolar geometry between two uncalibrated views of a 3D scene, and the role of the fundamental matrix in this respect. What is the significance of this for 3D reconstruction of the scene ? If you would build a 2-view 3D reconstruction algorithm, how would you use the epipolar gemetry in the algorithm ?

2) If one orthographically projects a scene into a number of images, you get orthographic images. Consider the joint image (all images taken together): what is the dimension of that space?  If I keep the cameras in a constant position, but move the scene, what happens to the joint image, specifically: what is the dimension of the subspace in which it moves? Similarly, if I keep the scene constant, but move the images, what is the dimension of the subspace now? Describe an algorithm that takes advantage of this to reconstruct orthographic structure and motion.

3) You are responsible for designing a new computer vision security system to help protect the Questian capital from the dreaded sphere-bots.  These bots sneak up at night, rolling a few feet at a time and then stopping for a bit to avoid detection.   They can sense active illumination (lights, IR etc) and destroy such sources instantly.  The also have auto-camouflage skin that picks up the statistics of the texture of the background so they are hard to see.

The cameras are mounted on auto-serving pan-units that swivel back and forth continuously.  These images are fed back to a security desk. Because the sphere bots attack at night, the camera images you get back tend to be noisy as the system tries to boost gain.

3a) Design at least one Computer Vision algorithm that will make it easier for the security guard to see the 'bots in the imagery. Be as specific as possible - e.g. if you algorithm uses edges, say how you get them.

3b) Suppose you want the system to sound an alarm, i.e. detect the bots itself.  Now what would you do? Again suggest at least one method, more is better.  Be very specific as to how your algorithm would work (and possibly fail).

4) Suppose you are wearing stereo glasses looking at a  stereo display at one 1 meter in the distance.  Assume you are seeing a cube.  Now you back away another meter.  Does the apparent shape of the object change?  Why or why not? And if yes, how?

VISUALIZATION

1) Splat-it

Splatting is a technique widely used in volume and surface visualization.
Describe the approximations used in the technique and how it differs from image-order volume rendering.  Discuss in detail the advantages and disadvantage of splatting and how the latter might be improved.

2) Terrain Everywhere

Multi-resolution terrain rendering is a visualization topic that has received wide attention.  Discuss methods that maintain interactivity and preserve visual quality.  What are the advantages and disadvantages of TIN versus regular grid spacing methods? How can one make a terrain rendering approach scalable?

3) Field Visualization

Describe in detail a principal-component or eigenvalue approach to representing 3D tensor fields.  Assume that these are general tensor fields.

How would you construct and handle the symmetric and anti-symmetric parts?  What are the advantages and disadvantages of your approach for representing both overviews and detailed views of a complex field?  What elements would you add to improve visual understanding?

4) Visual Exploration
Interactive visualization is sometimes said to be a technique for "visual exploration" and "knowledge discovery".  Why would this be the case and how, in detail, would one set up an interactive visualization system to do this?  Frame your answer in terms of a concrete example involving multidimensional and large 3D or 4D data.   Knowledge discovery is a slippery concept.  How would you quantify whether a visualization system was efficiently accomplishing this?
VR & AR

1) In AR, graphics are superimposed on a user's view of the world.   Unfortunately, both the viewing models we use in computer graphics, and the technology available with current (and near-future) head-worn displays, limits how well we can register graphics with the world.  Ignoring registration errors from tracking and modeling, discuss the various limits imposed by our 3D graphics systems and display technologies on our ability to merge graphics with the world, and suggest how they may be fixed in the future (if at all;  hypothesize technological improvements, but don't suggest impossible things).  Be sure to discuss both video mixed and optical see-through displays.

2) Tracking and Data Fusion

There has been steady progress in tracker development over the past few years.  Some research has focused on improving techniques for a single kind of sensor (e.g., computer vision), which some have focused on fusing multiple kinds of sensors (e.g., inertial + vision).  It seems clear that fusing multiple sensors is the only way sensing may ever "work".

(a) Why won't a single sensor type be sufficient?  (Include concrete examples of why at least 3 popular tracking technologies will not be sufficient by themselves.)

(b) Assume you had to build a tracking system that would work across the entire Tech campus, both inside and outside.  You are allowed to modify the building interiors in ways that does not change their appearance "significantly", but you are not allowed to modify the exterior of buildings or add any visible artifacts to the outside areas of campus.  Given today's technologies (and a large monetary budgets and a skilled team of engineers), how good a tracker could you build?

What technologies would you use, and why?  Given the state of research, what technologies would you imagine including in the near (5 year) future that would improve your tracker?

3) Despite more than 30 years of work on immersive virtual environments, widespread adoption of VR has yet to occur.  Various culprits are blamed for this situation: inadequate displays, lack of compelling applications, error-prone and cumbersome tracking systems, difficulty creating content, and lack of suitable interaction techniques.

a) Choose one of these potential reasons and argue why it is the primary barrier preventing widespread use of VR.

b) Describe how you would structure a research program aimed at surmounting that barrier.

c) Choose another potential reason and argue why it is not a barrier to the adoption of VR.

4) Some of the research on virtual environments has focused on trying to understand how interaction in an immersive virtual environment differs from interaction with a traditional desktop display or interaction in the real world. Choose two research results showing a positive or negative performance difference between VR and either a traditional desktop GUI or an interaction with the real world, and describe how those results can inform our design of interaction techniques for virtual environments.