CSC317 Winter 2021: Term Test: Family Name:_______________________________
March. 1, 2021, 3:00 PM (27 hours) First Name: _______________________________
Student ID: _______________________________

Attempt all 5 questions; the total mark is 35.
Please answer questions legibly in the space provide (preferably type) and submit electronically on MarkUs
under Test1.

1: /5
2: /10
3: /10
4: /5
5: /5
Total: /35

1. [5 marks] Raster Images
You are given an mxn black and white image (each pixel (x,y) has a color c(x,y), that is black=0 or white=1) like the
image shown below. Your task is to devise an algorithm to reduce the height of the image removing entire rows of
pixels (such the example rows A, B, C shown). You wish to alter the “visual quality” of the image as little as
possible. In the example below, removing row A would be worse that removing row B, which would be worse that
removing row C, intuitively in its visual impact on the resulting image.

a) (3 marks) Write an error function e(x) that captures the impact of removing the n (width of image) pixels of
row x, on the resulting image. e(x) should be non-negative, zero for no visual degradation, and increasing
with loss in visual quality. Explain how you are measuring visual quality, and why your function is a good
measure of its loss.

b) (2 mark) How can you use e(x) algorithmically to find the best k rows to remove.

2. [10 marks] Ray-object intersections
Describe a procedure panIntersect which returns the number of intersections between a ray (origin at O, direction
D) and a sauce-pan defined as the shape below. The body of the pan is defined by two cylinders centered at the
origin, with their cylindrical axis along the Y axis. The outer wall of the body has radius r1 and height h1, and the
inner wall has radius r1. The wall and bottom thickness of the pan w=r1-r2. The pan handle is a cone with a
spherical end along the X axis. The apex of the cone is distance r2+w/2 along the X axis and the cone smoothly
transitions into part of a sphere of radius r3 a distance of h3 from the origin along the X axis. The procedure
panIntersect also returns parameter values along the ray, for the intersection points in an array t (in increasing order
of t) in the case of an intersection.

int panIntersect(point O, vector D, float r1, r2, r3, h1, h2, h3, float &t[]) ;

a) (4 marks) Write the intersection procedure as a modular result of the intersection with the different parts of
the saucepan i.e. assume intersection procedures for the body and handle bodyIntersect and

b) (2 marks) Write the intersection procedure for bodyIntersect.

c) (2 marks) Write the intersection procedure for handleIntersect.

d) (1 mark) What is the maximum number of intersections possible, for a ray with the saucepan.

e) (1 mark) Is the number of ray-pan intersections, equal to the sum of the number of ray-body and ray-
handle intersections, for all rays. If yes, prove it; if no, show a counterexample.

3. [10 marks] Short Answers (2 each)

a) Radiosity is an efficient for walk-throughs of static 3D scenes. Why?

b) When rendering a die in a scene, the image of the dot representing the number ‘one’ on one side of the die
shows up in 4 different regions of the image. How many levels of recursion is necessary to produce such an
image and why (as a baseline Ray-casting is zero levels of recursion)?

c) Imagine your surface is made of a special translucent diffuse material that only lights up when the light is
behind the surface (ignore any self-occlusion of the surface). Modify the local Phong illumination formula
for such a material.

d) A point P is said to lie on a silhouette if its surface normal is perpendicular to P-E (the vector from the eye
to the point). Suppose we have a mesh edge defined by two vertices P1 and P2 with respective vertex
normals N1 and N2. Show how you can determine if a silhouette point P exists on the edge and give a
formula for computing this point (expressed in terms of P1, P2, N1, N2 and E).

e) What does the following surface look like qualitatively (describe it in a few words) and what is the normal
vector at a point s(u,v) of the following 3D surface shape?
s(u,v) = [ u(β + αv) cos v , u(β + αv) sin v , cv ]
where (u, v) ∈ [0, 1] × ℝ and α, β, c ∈ ℝ are constants.

4. [5 marks] Bounding Volume
Provide an algorithm to compute a tight axis-aligned bounding cylinder, where the cylindrical axis could any of
the X, Y or Z axes. Is this bounding cylinder tighter than a bounding cube? Tighter than a bounding sphere? If
yes, prove it; if not provide illustrating sets of points as counterexamples.

5. [5 marks] Triangulating non-self-intersecting 2D Polygons

a) (1 mark) Provide an algorithm to test if a polygon P1,P2,,..,Pn with vertices in counter-clockwise order is

b) (1 mark) Provide an algorithm to triangulate a convex polygon. The algorithm outputs n-2 triangles (such
as P1,P2,P3 , P2,P4,P7 etc.) What is its time complexity of the algorithm?

c) (3 marks) Will the algorithm above work on concave polygons. If yes, prove it; If not, provide a
counterexample and provide an algorithm that will work on concave polygons. What is the complexity of
this algorithm?