Describe the tristimulus theory of color perception and its relevance to
computer displays?
What is the CIE Chromaticity diagram?
Can every color perceptible to the human eye be displayed as a combination
of three primaries? Give evidence to support your answer.
Write equations that convert a color in the RGB model to the CMY model.
Describe which part of the RGB color cube represents gray values.
Same question for the CMY color cube, the HSV color hexcone, and the HLS
double cones.
Image Quantization
What is intensity quantization? When does it happen? How can
we compensate for it?
True or false: dithering spreads quantization error among pixels.
Image Sampling and Reconstruction
"A pixel is a sample, not a little square." What are the implications of
this statement on image processing algorithms?
If a pixel is an infinitely small sample, how is it visible on the screen
of a CRT display?
Display on a CRT is most similar to what reconstruction filter?
How many samples are required to represent a given signal without loss
of information?
What signals can be reconstructed without loss for a given sampling rate?
When is a signal bandlimited? What is the Nyquist rate for a bandlimited
signal?
What is aliasing? When does it happen? Give three examples?
What is antialiasing? How does antialiasing compare with dithering?
Convolution in the spatial domain is equivalent to what operation in the
frequency domain?
What is a sinc reconstruction filter? What are its properties?
Why don't we use sinc filters for reconstruction in practice?
Write a convolution filter well-suited for edge detection. Same for blurring.
Image Warping
Compare forward mapping and reverse mapping for image processing.
What are the advantages and disadvantages of each method?
Image Composition and Metamorphosis
What is the meaning of the following rgba tuples: (1,1,1,1), (1,1,1,0.5),
(0.5,0.5,0.5,1), (1,1,1,0)?
What is the resulting pixel color of: (1,0,0,0.5) over (0,1,0,0.5) over
(0,0,1,0.5)?
3D Primitives
What is the volume of a 3D point? a 3D ray? a 3D line? a 3D polygon? a
3D sphere?
What issues must be addressed by a 3D rendering system but not by a 2D
rendering system?
Why does a 3D line not have a convenient implicit represenation?
What is the implicit representation for a 3D plane? What are the
geometric interpretations of each parameter?
Ray Tracing
What is a primary ray? a secondary ray?
What is a ray tree? What determines the branching factor at each node of
the ray tree?
Describe how shadows are determined in a recursive ray tracer. Extend your
answer to consider polygonal area light sources.
Derive the algebraic solution for the intersection of a ray and a plane.
Derive the algebraic solution for the intersection of a ray and a sphere.
Derive the algebraic solution for the intersection of a ray and an infinite
cylinder.
Which of the following spatial data structures partition 3D space into
non-overlapping cells: a) grid, b) octree, c) BSP tree, d) bounding volume
hierarchy?
What is the expected computational complexity of intersecting a ray with
a scene containing N triangles using the following spatial data structures:
a) none, a) grid, c) BSP tree.
Derive the equation for determining the direction of refraction rays given
an incoming ray and indices of refraction.
If L represents emission from a light source, C represents reception at
a camera, D represents a diffuse reflection at a surface, and S is a pure
specular reflection at a surface, which of the following ray paths are
modeled by your ray tracer of assignment #3: a) LDC b) LSC c) LDDC d) LSSC
e) LSDSC f) LDSDC
Ray tracing is an approximate solution method for the rendering equation.
Explain.
Direct Illumination
Give examples from the real world of light sources best approximated by
OpenGL point light sources, by directional light sources, and by spot light
sources.
Write an equation describing the attenuation with distance (r) of light
intensity eminating from a point light source in the real world.
How is it modeled in OpenGL? Why are they different?
Give examples from the real world of surface materials that are primarily
diffuse and/or primarily specular.
Derive the equation for diffuse reflectance (Iout = cos(theta) * Iin).
Write the equation for the Phong model of surface reflectance including
ambient, emissive, diffuse, specular, transmission, and shadow terms.
What is the ambient term? Why is it included in the model?
Modeling Transformations
What types of 3D transformations can be represented with a 3x3 matrix?
What types of 3D transformation can be represented by a 4x4 matrix and
3D homogeneous coordinates?
Why do we represent transformations with matrices?
Which of the following 3D points with homogenous coordinates is closer
to the origin: (8, 4, 2) or (4, 2, 1)?
What is a linear transformation? What are its properties?
What is an affine transformation? Which properties of linear transformation
do not apply to affine transformations?
What is a projective transformation? Which properties of affine transformation
do not apply to projective transformations?
Write a sequence of transformation matrices that scales 3D points based
on their distances from an arbitrary origin O = (Ox, Oy, Oz).
Write a sequence of transformation matrices that rotates 3D points counter-clockwise
by theta degrees about an arbitrary 3D line defined by P1 and P2.
Viewing Transformations
Write the parameters describing a pin-hole camera.
Write the matrix that transforms a 3D coordinate system with origin O and
orthogonal basis vectors e1, e2, and e3 to the standard cartesian coordinate
system with the origin at (0,0,0) and basis vectors (1,0,0), (0,1,0), and
(0,0,1).
To what direction does the camera "towards" vector map during a transformation
from the world coordinate system to a right-handed camera coordinate system?
What is a parallel projection? Write a parameterized matrix that
can be used for all possible parallel projections. What is the geometric
interpretation for each of the parameters?
What is a perspective projection? Write a parameterized matrix that
converts a perspective view frustum to a canonical viewing volume.
What is the geometric interpretation for each parameter?
Can any parallel projection be described in terms of a perspective projection?
Vice-versa?
Is it possible to represent a 3D->2D parallel projection with a 3x3 matrix?
If so, write it. If not, why? Same question for perspective
projection.
Under what circumstances are parallel projections mostly used? Same
question for perspective projections. Which type of projection produces
the most realistic-looking images?
Textures
What is a reason to use texture mapping rather than lots of little polygons?
Are the two representations functionally equivalent? What are the differences?
Describe the different coordinate systems used for texture mapping.
Describe how texture coordinates are computed during scan conversion with
a sweep-line algorithm.
Describe at least three different lighting parameters that could be modulated
with texture maps. For each, give an example object for which the texture
map would be useful.
What are Mip Maps? Give an example of when they are useful. Why are they
used?
What is bump mapping? Give an example object that might use it. Write a
procedure that describes a plausible bump map for that object.
What is environment mapping? When is it used? How could an environment
map be captured?
Hidden Surface Removal
Write the equation for determining whether a polygon is back-facing with
respect to a viewer.
For each of the following algorithms, how does it insure that the pixels
resulting from rendering the front-most polygons are in the frame buffer:
a) depth-sort, b) z-buffer, c) ray casting, d) Warnock's area subdivision,
e) scan-line?
What is image-space precision? object-space precision? Specify whether
the following algorithms operate with object-space or image-space (pixels)
precision: a) back-face culling, b) depth-sort, c) z-buffer, d) ray casting,
e) Warnock's area subdivision, f) scan-line.
For each of the following hidden surface removal methods, a) back-face
culling, b) depth-sort, c) z-buffer, d) scan-line, specify in which stage
of the rendering pipeline it executes: DB traversal, modeling transform,
trivial reject, lighting, viewing transform, clipping, projection, rasterization,
or display.
If writing pixels into the frame buffer is hypothetically the performance
bottleneck in the rendering pipeline, rank the following algorithms from
fastest to slowest: a) depth-sort, b) z-buffer, c) ray casting, d) Warnock's
area subdivision, e) scan-line?
Which hidden surface removal algorithms perform more slowly for frame buffers
with higher resolution?
What is depth-complexity? Which hidden surface removal algorithms perform
more slowly for scenes with high depth-complexity?
Z-buffers have become ubiquitous in hardware on most PC graphics accelerators.
What are the disadvantages of the z-buffer algorithm?
The z-buffer method requires a z-value to be stored for every pixel in
the entire screen. In some situations, this memory requirement is prohibitive.
Propose a method in which the z-buffer approach is used, but memory is
allocated for only part of the screen. What additional problems arise?
Radiosity
Write the radiosity equation. For each of the terms (B, E, rho, and F)
describe its meaning and give suitable units.
The radiosity equation is system of equations. What are the variables to
be solved for? Is the system of equations linear?
Which of the following assumptions must be true for the basic radiosity
equation to be a good approximation to the rendering equation: a) all surfaces
are diffuse, b) all surfaces are planar, c) the radiosity is the same at
all points on a patch element, d) there are no occlusions resulting from
one patch blocking light transfers between any other two patches.
If we write the radiosity equation as Ax=b, consider the properties of
A: What are the values on the diagonal for planar patch elements? Is the
matrix diagonal dominant? Is it symmetric? When can it be singular? Is
it positive definite?
The radiosity method studied in class simulates which types of lighting
effects: a) shadows, b) direct illumination from area light sources, c)
direct illumination from point light sources, d) indirect illumination
due to reflections off specular surfaces, e) indirect illumination due
to reflections off diffuse surfaces?
Write an an expression for the form factor F_ij for two mutually visible
patch elements i and j. Give a short intuitive explanation for each term.
How does the expression change if the two patch elements are partially
occluded by blockers?
What is the relationship between F_ij and F_ji if we assume uniform light
reflection?
What is radiance? How is it different than radiosity?
Is the progressive radiosity method assymptotically more efficient than
Gauss-Seidel iteration? If so, why? If not, why do people use progressive
refinement?
Meshes
The computers in MECA can draw triangle strips at faster rates than independent
triangles. Why?
If an object's surface is a closed 2-manifold, how many faces can share
each edge? How many faces can share each vertex?
Write the Euler-Pontcare formula for 3D polyhedra. Give values for V, E,
and F for: a) a cube, b) an octahedron, c) a dodecahedron, d) an icosahedron.
What is the computational complexity of an operation that changes the coordinates
of a vertex V for each of the following mesh representations: a) list of
triangles with explicit vertex coordinates stored redundantly (like the
.ray representation)? b) triangle strip/fan? c) Vertex table and face table
with references to vertices? d) winged-edge?
What is the computational complexity of an operation that inserts a new
vertex on the edge between two existing vertices V1 and V2 for each of
the following mesh representations: a) list of triangles with explicit
vertex coordinates stored redundantly (like the .ray representation)? b)
triangle strip/fan? c) Vertex table and face table with references to vertices?
d) winged-edge?
Given a winged-edge data structure and a pointer to an edge E and a face
F, write pseudo-code for the following functions: a) Return the face across
E from F. b) Return the edge adjacent to E moving counter-clockwise around
F. c) Return the vertex adjacent to E moving clockwise around F. What is
the computational complexity of these operations?
Curves
For each of the following properties, give an example of a curve representation
that guarantees it: a) local control, b) interpolates control points, c)
C1 continuity, d) C2 continuity, d) curve lies with convex hull of control
points.
Why do computer graphics applications use piecewise polynomial curves of
degree 3 rather than curves of higher-order, say degree 100?
How many control points are required to specify a Bezier curve of degree
d?
From the Bernstein polynomials (the Bezier blending functions), prove that
a cubic Bezier curve interpolates V0 and V3.
What property of the Bernstein polynomials guarantees that a Bezier curve
lies within the convex hull of its control points?
Draw a Bezier curve for which recursive subdivision would be a more efficient
method for rendering.
What is C1 continuity? How is it different than G1 continuity? How is it
different that C2 continuity?
Draw a spline curve comprising two Bezier curve segments in which the derivatives
at the joint are in OPPOSITE directions.
How many degrees of freedom are available for a spline with m cubic segments?
How many constraints (degrees of freedom) are required to specify C2 continuity
at each interior joint of a spline with m cubic segments? How many constraints
at the endpoints of the spline? How many degrees of freedom are left?
Which of the following properties are guaranteed by C2 interpolating splines
a) C2 continuity, b) interpolation of control points, c) local control,
d) convex hull.
Which of the following properties are guaranteed by cubic B-Splines: a)
C2 continuity, b) interpolation of control points, c) local control, d)
convex hull.
Which of the following properties are guaranteed by cubic Catmull-Rom Splines:
a) C2 continuity, b) interpolation of control points, c) local control,
d) convex hull.
Surfaces
What is an implicit surface? Give a simple example.
Which of the following are true for implicit surfaces: a) easy to draw,
b) easy to test intersections, c) hard to describe complex shapes, d) local
control?
What is an parametric surface? Give a simple example.
Which of the following are true for parametric surfaces: a) easy to draw,
b) easy to test intersections, c) hard to describe complex shapes, d) local
control?
Which of the following are true for a cubic Bezier tensor product surface:
a) interpolates the four corner control points, b) interpolates the centroid
of the control points, c) lies within the convex hull of the control points,
d) provides local control, e) has at most one point with positive curvature.
Show that a point at parameter values (u,v) on a bicubic Bezier patch is
the same as the point at parameter value u on a cubic Bezier curve defined
by the four control points B1-B4 found by evaluating four Bezier curves
through a group of four patch control points at parameter value v.
What is a subdivision surface? Give a simple example.
Which of the following are true for subdivision surfaces: a) easy to draw,
b) easy to test intersections, c) hard to describe complex shapes, d) local
control?
For each of the following properties, list the surface representations
(mesh, implicit, parametric, subdivision) that provide it best and worst:
a) high accuracy, b) conciseness, c) local support, d) C2 continuity, e)
efficient display, f) efficient intersections.
Solids
What is a voxel grid? Give a simple example.
What is the storage requirements for a uniform voxel grid with 512 voxels
on each side of the cube and 24 bits of data in each voxel?
What is the computational complexity of tracing a ray through a voxel grid
with N^3 voxels: a) O(1), b) O(logN), c) O(N), d) O(NlogN), e) O(N^2),
f) O(N^3).
Which of the following are true for voxels: a) fast iso-surface rendering,
b) easy to test intersections, c) hard to describe complex shapes, d) affine
invariant?
What is a quadtree? an octree? Give a simple example. What is an advantage
of such a representation compared to uniform voxels? a disadvantage?
What is the computational complexity of tracing a ray through an octree
with at most N^3 cells: a) O(1), b) O(logN), c) O(N), d) O(NlogN), e) O(N^2),
f) O(N^3). Is the expected complexity less? Under what conditions?
What is a binary space partition (BSP)? Give a simple example. What is
an advantage of such a representation compared to an octree? a disadvantage?
Which of the following are true for a BSP: a) all leaf cells are convex,
b) finding which cell contains a point takes expected-case O(logN) time
using a BSP with N leaf cells, c) the largest number of cells possibly
resulting from a BSP constructed by N splits has O(N) leaf cells.
Describe the visibility ordering algorithm used when drawing BSPs. Explain
why it is guaranteed to produce a front-to-back (or back-to-front) ordering.
What is the computational complexity of tracing a ray through a balacned
BSP with N leaf cells: a) O(1), b) O(logN), c) O(N), d) O(NlogN), e) O(N^2),
f) O(N^3). Is the expected complexity less? Under what conditions?
What is constructive solid geometry? Give a simple example. What is an
advantage of such a representation compared to other solid representations?
a disadvantage? <\li>
Draw a CSG tree for a coffee cup. <\li>
Give an algorithm to draw an image of the surface of a CSG object. <\li>
For each of the following properties, list the solid representations (voxels,
octrees, BSPs, CGS) that provide it best and worst: a) high accuracy, b)
conciseness, c) guaranteed validity, d) efficient boolean operations, e)
efficient display.
