Description

Submission guidelines:
Please prepare your answers neatly written or typed. Submit electronically on Gradescope. If

you have prepared hand-written solutions, please still submit online by uploading a scan or
photograph. Acceptable formats are .pdf (preferred), .jpg or .png.

Question 1: (680: 15 pts)

// Algorithm to determine if a polygon is concave or convex
// Polygon vertices could be provided in CW or CCW order

Input: v[1], …, v[N] // N polygon vertices
Output: True or False // True if convex, False if concave

Vector e1, e2; float z;
int sign_of_sine_theta=0;

// compute cross-product between successive edges
// if sign of all the z values are all the same, then convex
// loop around polygon, taking cross product at each vertex

for (j=1; j<=N; ++j){ if(j==N)
k=1;
else
k=j+1;
if(j==1) i=N; else i=j-1;

e1= v[j]-v[i]; e2= v[k]-v[j]; z = (e1.x * e2.y) – (e2.x * e1.y); // z of cross-product

if(z < 0.0){ if(sign_of_sine_theta > 0) return False; // sines with different signs else
sign_of_sine_theta = -1;
}
else if (z > 0.0){ if(sign_of_sine_theta < 0) return False; // sines with different signs
else
sign_of_sine_theta = 1;
}
}
return True;

b) Extra credit (5 pts): Suppose the point in the interior of the polygon is not provided. Describe a strategy for finding such a point. Pseudocode not required.
c) Extra credit (10 pts): Look up the “shoelace formula” for the area of a polygon. Can you come up with an alternate algorithm based on this formula? Pseudocode needed here.

Question 2: (680: 20 pts)
(a) Write a 4 x 4 homogeneous transform matrix M that when applied to a point 𝑝 = (𝑥, 𝑦, 𝑧, 1) yields 𝑝 = (𝑥 , 𝑦 , 𝑧 , 1) where

𝑥 𝑧 + 𝑎

𝑦 = 3𝑦 + 𝑏

𝑧 𝑧 + 𝑐

(b) What three or four basic computer graphics transforms occur when applying M to a 3D point? In other words, how can you decompose M into transforms such as scaling, rotation, translation? Give a homogeneous transform matrix for each, and show the order in which they are multiplied.

Question 3: (680: 10 pts)
Derive the shear matrix that would transform the block “h” character on the left to the italic “h” character on the right. Show your answer first with variables, then replace the variables with values for your final answer.

Question 4: (680: 20 pts)
Consider the following unit quaternions
𝑞

𝑞 , 0, −

a) 𝑞 represents a rotation of angle 𝜃 about a unit vector 𝑢 . What is this angle and vector? (Note: there are several acceptable answers).
b) 𝑞 represents a rotation of angle 𝜃 about a unit vector 𝑢 . What is this angle and vector?
(Note: again, several acceptable answers).
c) Does rotation by 𝑞 and 𝑞 commute? Why?
d) Extra credit (5 pts): When do two rotations commute? When do they not? Prove these statements. (Hint: consider the equation for quaternion multiplication).

Question 5: (680: 15 pts)
Derive a 3D homogeneous transformation matrix to scale along the u-axis with origin C by Su. Your solution should not use trigonometric functions for Rin or Rout, instead use the orthonormal basis vectors as discussed in class.

. .

Question 6: (680: 20 pts)
Derive a homogeneous transformation matrix that can be used to reflect 3D points about a plane with equation ax + by + cz = d. Your solution should not include the explicit computation of any Euler rotation matrices Rx, Ry, and Rz.