Graphics Qualifier
October 29, 2004
Directions: There are 6 general, 4 modeling, 4 rendering, 4
visualization, and 4 vr/ar questions.
Please answer 4 out of 6
general questions; 2 out of 4 questions in 2 other sections of your choice. The total number of answered questions
we are expecting from each student: 8).
1) Glider: We want to
roller-blade on an oriented manifold triangle mesh M in 3D. Our feet are never
to leave the surface. We want our head to remain vertical with respect to the
surface of the mesh at the point of contact. Furthermore, we want to slide at a
constant tangential velocity (no acceleration component in a tangential
direction with respect to M). Assume that we start at a point P of edge (A, B)
and that we just entered triangle T, which has vertices (A, B, C), with an
initial velocity vector V that is tangential to T. Please describe in details
how you will compute the time t and position P䴜 when we leave T, and also how
to identify the edge through which we exit T. Now, assume that we exit T
through edge (B, C) and enter triangle T䴜 with vertices (C, B, D). Describe
in details how to compute our new velocity vector V䴜 in T䴜. For simplicity,
assume that you never hit a vertex.
2) Shadow: A point light
source is located at (0,0,h). The floor is defined by z=0. Provide simple
formulae for the coordinates (x䴜,y䴜,z䴜) of the floor-shadow P䴜 cast by
point P=(x,y,z). Now express the transformation that takes P to P䴜 as the
result of a multiplication by a 4x4 matrix (using homogeneous coordinates) followed
by a division. Explain how such a formulation can be used for casting shadows
of 3D objects, discuss its limitations, and compare it to other approaches for
rendering shadows.
3) Texture: A small company
presented a graphics card which performs texturing as follows. For any textured
triangle, it projects it to the screen. For each pixel within the triangle's
projection, it linearly interpolates texture coordinates from the projected
vertices and uses the interpolated texture coordinates (after proper scaling)
to look up the color from the texture. Does this approach work (explain)? If it
does not, how can it be fixed?
4) Projection of Projection:
Consider an ideal projector (with a point-sized bulb) that projects qualifier
questions onto a screen. We don't assume anything about the orientation of the
projector with respect to the screen (which means that the text on the screen
will generally appear distorted). You take a picture of the projected text
(again, with an ideal pinhole camera) from some (arbitrary) place in front of
the screen, then do simple thresholding to extract the text and produce a slide
out of your picture. Is it always possible to place the projector (with the new
slide in it) so that the text shows up undistorted on the screen? Explain why.
5) Loops in a planar
section: Consider a genus zero triangle mesh in 3D and a function F given by
Ax+By+Cz+D for any point (x,y,z) on the mesh (the mesh is its domain). Let m
and n be the number of local maxima and local minima of this function. How many
loops can the intersection of the mesh and the plane Ax+By+Cz+D=0 possibly
have? If m+n is small and the mesh is large, how would you find all loops in
the section if you were given all maxima and minima? Come up with a heuristic
which, in certain cases, will run in sublinear (with respect to the size of the
mesh) time. You can assume that there are no singularities: that F does not
have the same value at any vertex and that the section consists of some number
(possibly zero) of disjoint loops.
6) Splines and section
areas: A QUAL-spline function associated with a watertight manifold triangle
mesh is defined as follows. For a parameter t, compute the surface area of the
intersection of the volume bounded by the mesh and the plane parallel to the xy-plane passing
through (0,0,t). When (i.e. under what assumptions on the mesh, as mild as
possible) is a QUAL-spline C1-smooth? How would you describe its slope at t in
terms of the geometry of the mesh?
1) Triangles: You are given
a set of independent triangles in 3D (the so-called polygon soup) and are told
that they approximate the boundary of a manifold 3D solid object S. Each
triangle has its own 3 vertices and there is no connectivity information. More
over, the edges of the triangles do not match properly: some triangles are
slightly larger and extend past their intersections with their neighbors, some
are slightly smaller and leave gaps between them and their neighbors. You can
assume that these extensions and gaps are small compared to the size of the
triangles. You cannot assume that the triangles are consistently oriented.
Propose a reasonably robust algorithm for deciding whether a given point P lies
on or close to the boundary of S. Them assuming that P does not, propose an
algorithm for deciding whether P lies inside S or outside of S. Discuss the
time complexity and robustness of your solution.
2) Carving: Assume that you
start with the 3D model of a solid cube. The user manipulates interactively a
virtual wire that burns material that it sweeps through. Explain how you would
represent the difference between the cube and the burned sweeps and how you
would update it as the user continues to carve. Also explain how you would
compute when that difference is disconnected. The user would select the
component to keep for subsequent carving operations, and you will discard the
others.
3) Storage size: Assume that
you have a human brain represented as the set of black voxels in a binary
voxelized space of 1024 cubed voxels. Assume that roughly 50% of the voxels are
black. Discuss several exact representations/encodings of the data and for each
estimate how much storage (in bits) will be necessary. Now, assume that you are
allowed to use a lossy compression. What approach would you suggest and how
much storage do you expect to need.
4) Separation: Assume that
nodes of a regular 3D lattice of 128 samples in each dimension are painted
either red or green. We want to build a triangle mesh M that is the boundary of
a solid (not necessarily of a single connected component) that contains all
green nodes and none of the red ones. Of course, we would like to use as few
triangles in M as possible. Can you outline an approach and comments on its
limitations and on the difficulties one may run into when implementing it?
1) Anti-Aliasing of
Synthesized Textures
When people talk about
texture synthesis, they might be referring
to two quite different
approaches: 1) solid texture synthesis using
composition of functions
such as Perlin noise, or 2) texture synthesis
from a sample texture image,
such as Wei-Levoy pixel-at-a-time or
Efros-Freeman patch-based
synthesis methods. Depending on
which
method is being used, quite
different approaches to anti-aliasing
may be necessary. Describe methods for anti-aliasing each
of these
kinds of synthesized
textures in turn. Be sure to
include in your
answer the kinds of filters
you would use and why. Also
discuss
both texture magnification
and decimation (viewing from very near
and very far).
2) Sub-Surface Scattering
(a) What is a BSSRDF, and what does it tell you about a
surface?
Be as specific as you can, including a
description of the
meaning of its six parameters.
(b) What visual phenomena are evident for a surface in which
sub-surface scattering occurs? Contrast this with an
entirely opaque surface.
(c) Describe an algorithm for rendering surfaces that exhibit
a
significant amount of sub-surface
scattering of light.
3) REYES
The REYES rendering system
approaches some aspects of rendering
in a manner different than
many other scan-conversion systems.
This question examines some
of those aspects.
(a) What is a micropolygon? What is the size of a micropolygon and
why?
What are the benefits of micropolygons over polygons?
(b) In what order are the following operations performed in
REYES:
1) visible surface determination, and 2)
surface shading.
What are the benefits and the drawbacks of
performing these
two operations in the REYES order?
(c) What are CATS?
What are the benefits of CATS?
4) Path Tracing
(a) State the rendering
equation and describe the meaning of the
various terms.
(b) Discuss the phenomena of
indirect illumination and caustics,
and how they relate to the rendering equation.
(c) Describe a Kajiya-style
path tracing renderer, and state how
this differs from a traditional Whitted-style
ray tracing
program.
Which of these two kinds of renderers allow indirect
illumination and/or caustics, and why?
1) The samples (nodes) on a
regular x-y-z grid have been segmented into red and green nodes. You want to
construct a smooth surface that separates red and green nodes. Explain why the
topology of that surface is not well defined and suggest how to chose a particular
topology and why. Propose an algorithm for computing that surface.
2) You look at an aquarium
filled with oil or some other semi transparent liquid. In the aquarium, there
are two semi transparent balls, one red and one green. On is in front of the
other. Discuss what happens to the light along a ray that pierces both balls.
In particular, explain whether the perceived color would be different if you
were to swap the order of the two balls (while keeping the length of the ray
intersection with each ball the same. Based on your answer, discuss whether it
is necessary to render volumetric models in a back-to-from order or not.
3) Terrain
One of the primary data
structures for representing terrain data is
the quadtree.
a) Explain what type of data
the quadtree is good for representing.
b) Explain what type of
visualization problem the quadtree solves, and
explain in sufficient detail how the quadtree
structure can help solve it.
c) Explain what type of
terrain-related data the quadtree is NOT so useful for.
4) Why Visualization?
a) Briefly explain in 3
paragraphs or less how visualization techniques are
useful to people. That is, what aspects of human
perception + cognition +
action are being better served?
b) In the context of mobile
visualization, explain how human perception +
cognition + action is affected by the user's context,
c) Explain what have a
mobile visualization system must be redesigned to
account for this change in context.
1) Tracking
One of the primary technologies
enabling of Virtual Environment is
the use of 3D position and
orientation trackers.
Explain the various types of
3D trackers, their properties, strengths
and weaknesses. Outline a
methodology for evaluating the quality
of a tracker in general (on
the basis of its energy transmission
principle), as well as in
the specific case of a particular piece
of tracking hardware.
2) VR Optics
a) Give a short description
of how time-multiplexed stereoscopic display
systems work.
b) Explain what we mean by
the accommodation / convergence conflict in a
stereoscopic display?
c) What spatial and temporal
properties of a stereo HMD would be ideal,
and why?
What is typically delivered in commercial systems, and what
remaining challenges would need to be faced to deliver
something closer
to ideal.
3) Systems
A systems architecture for
virtual environments software must have certain
operational properties.
a) What are the N basic
components of a visually coupled system?
b) Briefly outline two
software architectures for delivering VR experiences,
and describe their strengths and weaknesses.
4) 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.