Graphics & Visualization


(Geometric and Visual Computing)
The exam will have two parts:

GENERAL QUESTIONS

Each candidate will have to answer 4 out of 6 questions that either cover general   issues that pertain to the overall G&V field or focus on specific modeling or graphic techniques that are used by practitioners in most G&V sub-areas.

1) Integration Methods:
    Please present an overview of all integration methods in use for dynamic
simulations for animations.  Why are these in wide use for computer graphics
animation? Why are these still not in use for real numerical simulations?
Please provide answer for the latter with respect to sampling in time and
time step sizes.  Please also discuss the stability issues and the bounds
that are used in practice and also the theoretical bounds.

2) Finite X Methods
    Provide an overview of Finite Difference and Finite Element methods.
For which types of problems are these ideal for?  What are the requirements
of each for modeling deformable objects and under what circumstances is one
preffered over the other. Is there some numerical advantage of one over the
other. What are the assumption made for computer graphics animations that
are not valid for real models used in mechanics literature.  Comment a bit
on material properties too.  Any idea what Finite Volume methods are

3) Control for Animation
    Even though everyone claims that there are 3 types of animation
techniques. A) keyframing, B) motion capture, and C) simulation. Some may
argue that (B) and (C) are still simple subsets of (A).  Do you buy that
argument? The argument could be that MoCap simply provides more keyframes
(at 60hz for example).   Can some parameteric model be fitted to it along
the lines of arc parameterization to make it more similar to keyframing?
For simulation, the keyframes are in much different space.  Can this space
be parameterized?  What are the implications of control for animation for
(B) and (C) .. Is there a chance that some control techniques will be
available soon that will provide similar comtrols as keyframing does?  Feel
free to use some specific examples to answer your question.
 
(4) Motion
You have a camera that runs at 30hz and 60hz.  You have a motor with a speed
control that is attached to wheel with well defined spokes (imagine a wooden
wheel from a horse cart).Assume there are 18 spokes. You can control the
speed of this wheel.  You can define the speed in terms of rotations per
second then the frequency of each spoke.  Now you have a strobe light that
you can also control the strobing frquency. How would you set up the system
to show apparent motions using the 30 and 60hz camera of the wheel moving
forward (in the direction of it's rotation) and opposite it.  At what speeds
will the blur be dominant.  Specifying assumptions, compute the frequency of
the spokes/sec and the strobes for the 2 camera settings.  Is this possible,
if not, why NOT?

1) PERSPECTIVE
The perspective transformation used for 3D rendering maps a model point P=(x,y,z) to a point (x',y',z') so that (x',y') are the coordinates of the point where  P appears on the screen. Typically,  z' is chosen as a monotonic function of z, so as to ensure that depth order is preserved for z-buffer based hidden surface removal. Company X has proposed to set z'=z, normalized so that its range varies between  0 and 2^32-1, and to represent Z' as an integer. Explain why this approach does not work.

2) SHADOW
Assume that the light source is the edge (u,v). It is not a point source, nor an area source.
The scene comprises only two triangles connected to each other: (a,b,c) and (c,b,d).
Both the light source and the triangles are above the floor. Explain very precisely how to compute the exact shadow (umbra) cast by the two triangles on the floor. In particular,  provide a formal definition of the shadow and state its properties. Is it connected? Is it convex? Is it polygonal? Note that discrete methods which would use pixels or sample the edge are not appropriate. However, you may assume that geometric tools for generating simple shapes (rays, edge, planes, cones) and for computing their intersections are available.

3) REGISTRATION
Consider a viewpoint V and three screen locations (P,Q, and R) through which you see the three vertices (A,B,C) of equilateral triangle of edge length L. Assume that you are given the 3D locations of V, P, Q, and R. Explain how you would compute a possible location for the vertices (A,B,C).

4) SELF-INTERSECTION
A piece of cloth is simulated by a triangle mesh and animated through physical simulation. However, the self-intersection detection algorithm is far too slow. Suggest a good algorithm that would detect self-intersections and explain in detail what it would do and how you would implement it.

5) TRANSFORMATIONS
A graphics library RGL works just like OpenGL, but it offers only two instructions that alter the modeling transformation:
(1) LoadIdentity(): reset it to the identity
(2) Reflect(P): substitute it with the composition of a reflection about a plane P in 3D and the current modeling transformation.
By combining the calls to the two functions, is it possible to obtain any isometry of the 3-space as the modeling transformation? Assume the library has been extended so that it contains another instruction, ScaleX(s), which substitutes the modeling transformation with its composition with the (non-uniform) scale in X with scaling factor s. Using the three instructions, is it possible to specify any affine transformation as the modeling transformation? Prove all your claims.

6) MORPHING
An algorithm that morphs between two convex planar polygons embeds them into two parallel planes z=0 and z=1, computes their convex hull H and computes the morph at time t between 0 and 1 as the intersection of H and the plane z=t. Assuming that the polygons are represented as circular lists of vertices in counterclockwise order, design a linear-time algorithm for computing H. Propose a way of representing the morph that allows to compute it at time increments using as few expensive arithmetic operations (multiplications, divisions) as possible.


1) THE VOLUME OF A POLYHEDRON
Let P be a polyhedron. Some of its faces may be convex and some may have holes. Each face is bounded by one or more cyclic loops of edges. The edges in each loop are oriented, so that if you travel along an edge in the direction of its orientation with your head up along the outward normal to that face, the interior of the face is on your left. Assume that P is represented by the list of its loops. Each loop is represented by the cyclic list of its vertices, in the order in which they are encountered when traveling along the loop in the direction of the oriented edges. Please write a very simple algorithm that would compute the exact volume of P (it we ignore round-off errors or assume extended precision rational arithmetic). Your algorithm should not require that you triangulate the faces of P nor tetrahedralize its interior. Hint: The heart of your algorithm could look like: " for each loop L of P do { for each oriented edge (a,b) of L do .};". Justify that your algorithm is correct.

2) HAUSDORFF DISTANCE
To speed up transmission and processing in Computer Graphics, we often use approximations of detailed 3D shapes. One may measure the discrepancy between a shape A and its approximation B by the Hausdorff distance H(A,B). Let M(a,B) denote the minimum distance between a point a and the set B. Let D(A,B) be the maximum of M(a,B) for all a in A. Then, H(A,B)=max(D(A,B),D(B,A)).  When A and B are triangle meshes, we propose to compute H(A,B) as the maximum over all u of the minimum over all v of H(u,v), where  u is a triangle of A or B and v is a triangle of the other set. Is this algorithm correct? If so, prove it. If not, demonstrate why it is wrong and suggest how to fix it.

3) ARRANGEMENT
Consider an arbitrary arrangement of edges on a plane. Two edges may intersect each other. Let U be the union of these edges and D be the complement of U in the plane. Provide an algorithm for computing the number of connected components of D. (Two points are in the same connected component of D if you can go from one to the other without crossing an edge.)

4) THE CONVEX HULL OF A TRIANGLE MESH
Assume that you have a triangle mesh M that is composed of a single manifold shell of zero genus. We propose the following algorithm for computing the convex hull of M. Repeat the following two steps until all edges are convex: (1) remove all vertices that have exactly 3 incident edges that are concave (when doing so, you also remove the 3 incident triangles and replace them by a single one) and (2) flip a concave edge. Describe what representation for M you would use to implement this algorithm. Provide the details of detecting whether an edge is concave and for flipping an edge. Use drawings to clarify these implementation details. Will this algorithm always produce a convex hull? Justify your answer.

1) Reflectance
  (a) Write out the equation for the reflectance equation (*not* the
      rendering equation), and describe what each of the terms under the
      integral sign represent.

  (b) Some textbooks give an equation like this for calculating the
      shading of a ray traced surface:

      I = Ia * Ka + Ip [ Kd * (N dot L) + Ks * (R dot V)^n] + Krefl * Irefl
        + Ktrans * Itrans

      The above equation states that the intensity is the sum of an
      ambient term, a diffuse term, a specular term, a reflected term
      and a transmitted (refracted) term.  State how each of these
      terms relates to the reflectance equation.  For each term, say
      whether it accurately matches the reflectance equation (and
      real-world reflectance), and if not, say why.  For each term that
      is not properly calculated, give a method that would more accurately
      match real-world reflectance.

2) Adaptive Supersampling
  (a) One way to perform anti-aliasing for a ray tracing renderer is
      to create a large image (e.g. 4096 x 4096) and use the average
      of blocks of 4 x 4 pixels as the color of one pixel in a 512 x 512
      image.  What kind of pre-filter is this implementing for
      anti-aliasing?  What would be a better shape for a pre-filter, and
      how would you modify the above method to use it?

  (b) Some ray tracers cast a small number of rays per-pixel and then
      shoot more rays only if the first rays returned substantially
      different colors.  Thus more rays might be shot at a the silhouette
      of a dark object in front of a light background.  Say how you would
      implement this adaptive supersampling idea.  Through which locations in
      the pixel would you shoot the first few rays?  How would you determine
      whether more rays are necessary?  Where would you shoot additional
      rays in the pixel, if needed?  How would you determine the final
      pixel color from all of the rays, if you wanted a high-quality
      pre-filter?

3) Pen-and-Ink Ray Tracer
  This question explores the use of a ray tracer for creating pen-and-ink
  styles of illustrations.  Assume that you begin with a ray tracer that
  can render spheres and polygons, and that it can perform texture
  mapping.  In all your answers, give enough details so that a fellow grad
  student would know how to implement your ideas.

  (a) How would you modify your ray tracer to create dark silhouettes
      for the spheres?

  (b) How would you modify the ray tracer to show silhouettes for
      collections of polygons?  If your answer is the same as (a),
      explain why your method works in both cases.

  (c) How would you create cross-hatching on a sphere?
 
  (d) How would you create cross-hatching on a collection of polygons?
      If your answer is the same as (c), explain why your method works
      in both cases.

4) Hair
  There are several important issues that arise when attempting to render
  hair.  You have been given the task of using standard PC graphics
  hardware (that scan-converts polygons and lines) to render realistic
  hair.  Don't worry about compute time -- just concentrate on
  generating the best images.  Describe how to render high-quality hair
  in this setting, being sure to address the issues of anti-aliasing,
  self-shadows, and hair-like reflectance of light (including convincing
  highlights).
 
1) Computational Steering
Computational steering has been a goal of visualization ever since the field was established. What is computational steering, what role does visualization play in it, and why would visualization offer unique capabilities? To have successful computational steering, the simulation or model being steered must be integrated with the visualization. Choose an example and describe in detail how this could be done.

2) Out-of-Core Visualization
There has been a good deal of work over recent years on the out-of-core visualization of 3D objects. Much of this work has centered on complex 3D objects. Describe the issues for out-of-core visualization and the criteria for obtaining a successful result. How must data organization and interactive visualization be integrated? Suppose rather than a few very complex objects, one had a very large collection of objects that are individually simpler. How would the out-of-core approach differ in this case?

3) Interactive Visualization
Suppose that you needed to interactively visualize a very large collection of textured polygonal objects where the depth complexity of a given scene might be quite large. Typical multiresolution mesh rendering techniques would break down at some point. Why is that? (Be precise.) Describe in detail an alternative method for this type of scene that might achieve the desired interactivity and visual quality. Be specific in terms of the types of models you are considering, how many, and the types of scenes.

4) Vis and InfoVis
Information visualization and data visualization are often considered to be closely related sister fields. However, some consider them to be different.
Describe some keys ways in which the two fields might be different and give details.
Choose a multivariate, large scientific dataset. How might techniques of information visualization be combined with traditional techniques of data visualization to explore and analyze these data? What advantages, if any, would the information visualization techniques bring to this analysis?