1. On the invisibility of balls

What is the shape of the perspective projection of an unobstructed ball?

Justify your answer. Provide the details of a simple geometric calculation that would establish precisely whether a ball of center G and radius r is hidden from a viewpoint V by a triangle having vertices A, B, and C. Use 3D vectors rather than coordinates in the formulation of your solution. Discuss how such a test could be used to accelerate graphics.

2. A matter of perspective

Consider a perspective transformation T that maps a point P=(x,y,z) to a point P'=dP/(d+z).

3. The shape of a Lightfield

Consider a lightfield L of a 3D object S. Let B be the subset of the rays of L that miss S.

4. The color of light

5. Collision detection

Briefly describe an algorithm to perform collision detection between N concave 3D objects moving around on a heightfield terrain.

6. Nearest neighbor

Having a number of sites in the plane, we want to find the one which is the closest (in the Euclidean metric) to a query point.

1. Finding things in a triangle soup

Consider a set T of triangles that do not necessarily have matching edges or vertices and in fact may intersect each other. Their union does not necessarily form a water-tight boundary of a 3D region. You are told that within a tolerance E, these triangles split three-space into several 3D regions (each being a connected solid). Explain how you would interpret this statement into a more precise mathematical formulation. Provide a practical algorithm for computing a triangle mesh representations for each one of these regions.

2. Sizing the difference

Provide a simple algorithm for computing precisely the volume of a shape A bounded by a triangle mesh. Now, consider two solids, A and B, each bounded by a triangle mesh. We now want to compute the volume of the symmetric difference (i.e., of the set of points that belong to one of the solids, but not to both). Explain what one would need to do to compute that volume exactly. (Can the previous algorithm be used on a simple combination of the meshes of A and B? If not, why?) Suggest an approximate algorithm for estimating the volume of the symmetric difference that would be fast and easier to implement.

3. Juggling trees

Consider three representations of a polyhedron A:

Explain how each representation may be used to test whether an arbitrary point P lies in A. For each, discuss the factors that affect the expected cost for an unknown P. (Assume that P lies in an axis aligned box around A.) Can you predict which of the three representations is the most efficient for this point-inclusion test? Discuss further improvements that would reduce the expected cost of the test.

4. Mid-point tessellation

Consider a two-parameter array A[n,m] of control points in 3D. Explain how to compute a precise approximation of the uniform B-spline surface from A, by using only one geometric primitive, mid(P,Q), which computes the midpoint of P and Q. (Use an iterative subdivision.) Provide and explain the pseudo-code for your tessellation algorithm. Assume that the resulting approximation has V vertices, how many times was the 'mid' primitive used? Comment on the suitability of this approach for the hardware tessellation of B-spline surfaces.

1. Given: scisors, glue, a small detector which measures the energy of photons hitting it from all directions and a sheet of magic paper which absorbs all the light hitting it, build a device for measuring radiance. Discuss in detail all the approximations you are making and how to possibly increase the precision of your device.

2. This question is about the merits of using Kajiya-style path tracing (from his The Rendering Equation paper) versus backward ray tracing (shooting rays from the light source). For each of the two phenomena below, describe how the phenomena is captured by each of the two methods of path tracing and backwards ray tracing, or if it is not, say why not. Also, say which of the two methods is preferable (in your opinion) to capture the given phenomenon and why.

3. You have been asked to write the hair rendering system for Shrek III, and the director wants it to look as life-like as possible. Discuss how you plan to accomplish this, including how you will treat issues of anti-aliasing, non-isotropic reflectance effects, shadows, hair translucency, and the interreflection of light through hair (especially when hair is lit from the back).

4. In some ways, MIPMAP texture rendering is similar to Levoy and Hanrahan's image-based rendering using Light Fields.

1. If you were modeling a melting candle, you could get some of the required effects by keeping the model intact. But in some situations, candles gutter, and a stream of melted wax runs down the face of the unmelted candle. What physical effects would you have to include to model this phenomena? Explain in some detail how you would go about it.

2. Hodgins et al. 1995 described a number of hand-designed techniques for building control systems for various dynamic behaviors. This approach is inherently limited because the implementor must have a great deal of domain knowledge about the particular behavior. How might you incorporate motion capture data into the design of a control system. Explain what class of behaviors your approach is likely to work for (static, dynamic, whole body, upper body, stylistic, etc.)?

3. Describe the various methods of integration used in Simulation. Specifically describe the Euler, Mid-Point, Ringe-Kutta and other higher-order methods used in the literature. Compare each method for the case of a simple five link mass-spring model that is used to model hair (in Monster's Inc. for example). Also discuss implicit versus explicit, backwards vs. forward methods for integration and discuss issues of general stability of integration methods. A table maybe a great idea if you can manage it.

4. Spline-based inbetweening of keyframes will control curvature quite well. However, there is a temporal problem. What is the problem and how does one fix it? (Hint: Has something to do with space reparameterization).

1. A well-known technique in computer vision is to decompose an image in terms of principal components, derived from a large set of training examples using PCA. Why is this done? What is the problem of such an 'eigenface' approach in the case of face detection and/or face recognition? Can it easily model spatial deformations in the image? In the same application, does a straight PCA approach lead to a well-behaved density in the original 'face-space'? If not, describe an extension that would have this characteristic.

2. On Shape from X

The task is to extract a shape of highly reflective object (ie. Chrome balls etc.). How would you do it? Assuming a fixed camera, what would you vary? How can you use the reflectivity of the object to help with this? Discuss the various approaches you would use and also how would convexity/concavity of the object effects this. Please draw figures.

3. Recognition using Templates OR Features

You have been asked to write an algorithm for recognition of images of hands with fingers used to count from 0 thru 5. Images are lit, but there are shadows. Images are not aligned, and there is variation in angles and scales. Two forms of recognition are desired, each aimed at counting the numbers of fingers in the image. In one, the goal is to detect how many fingers are visible, and it does not matter which (ie. the count 2 is because of the index finger and the small finger, or the thumb and the index finger). In the second, the goal is to detect specific fingers. (ie. Index and 2nd finger are visible and the count is 2). Feel free to make simplifying assumptions as appropriate. Discuss where template-based recognition will work and where the feature-based recognition will work, and why.

4. Human Vision

When modeling of the human vision system began, the computational analysis focused on linear time-invariant systems theory: frequency tuned receptive fields, spatial (or spatial-temporal) filters, summation properties of detection. Eventually though the presence of non-linearities became clear. Discuss at least three nonlinear computations in the human visual system and describe what capabilities that non-linearity provides. Make sure at least two of them are above the level of the retina.