xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

c/c++代写-CSC317

时间：2021-03-29

CSC317 Winter 2021: Term Test: Family Name:_______________________________

March. 1, 2021, 3:00 PM (27 hours) First Name: _______________________________

Student ID: _______________________________

Instructions:

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.

A

B

C

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

handleIntersect.

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

Y

X

r1

r2

h1

Z

w

r3

h3

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

convex?

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?

学霸联盟

March. 1, 2021, 3:00 PM (27 hours) First Name: _______________________________

Student ID: _______________________________

Instructions:

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.

A

B

C

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

handleIntersect.

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

Y

X

r1

r2

h1

Z

w

r3

h3

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

convex?

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?

学霸联盟